2996 lines
162 KiB
Python
2996 lines
162 KiB
Python
#!/usr/bin/env python3
|
||
"""
|
||
LeetCode Hot 100 图解 HTML 页面生成器
|
||
用法: python3 generate.py [--category 哈希] [--slugs two-sum,group-anagrams] [--all]
|
||
"""
|
||
import json, os, sys, textwrap
|
||
|
||
from linked_list_algos import (
|
||
js_intersection_of_two_linked_lists,
|
||
js_reverse_linked_list,
|
||
js_palindrome_linked_list,
|
||
js_linked_list_cycle,
|
||
js_linked_list_cycle_ii,
|
||
js_merge_two_sorted_lists,
|
||
js_add_two_numbers,
|
||
js_remove_nth_node_from_end_of_list,
|
||
js_swap_nodes_in_pairs,
|
||
js_reverse_nodes_in_k_group,
|
||
js_copy_list_with_random_pointer,
|
||
js_sort_list,
|
||
js_merge_k_sorted_lists,
|
||
js_lru_cache,
|
||
)
|
||
from binary_tree_algos import (
|
||
js_binary_tree_inorder_traversal,
|
||
js_maximum_depth_of_binary_tree,
|
||
js_invert_binary_tree,
|
||
js_symmetric_tree,
|
||
js_diameter_of_binary_tree,
|
||
js_binary_tree_level_order_traversal,
|
||
js_convert_sorted_array_to_bst,
|
||
js_validate_binary_search_tree,
|
||
js_kth_smallest_element_in_a_bst,
|
||
js_binary_tree_right_side_view,
|
||
js_flatten_binary_tree_to_linked_list,
|
||
js_construct_binary_tree_from_preorder_and_inorder,
|
||
js_path_sum_iii,
|
||
js_lowest_common_ancestor_of_a_binary_tree,
|
||
js_binary_tree_maximum_path_sum,
|
||
)
|
||
|
||
BASE = os.path.dirname(os.path.abspath(__file__))
|
||
PROBLEMS_FILE = os.path.join(BASE, 'shared', 'problems.json')
|
||
|
||
from dp_algos import (
|
||
js_climbing_stairs, js_pascals_triangle, js_house_robber,
|
||
js_perfect_squares, js_coin_change, js_word_break,
|
||
js_longest_increasing_subsequence, js_maximum_product_subarray,
|
||
js_partition_equal_subset_sum, js_longest_valid_parentheses,
|
||
)
|
||
|
||
with open(PROBLEMS_FILE, encoding='utf-8') as f:
|
||
ALL_PROBLEMS = json.load(f)
|
||
|
||
# ========== Difficulty class ==========
|
||
DIFF_CLASS = {'简单': 'easy', '中等': 'medium', '困难': 'hard'}
|
||
DIFF_ICON = {'简单': '🟢', '中等': '🟡', '困难': '🔴'}
|
||
|
||
# ========== Template ==========
|
||
def gen_html(p, algo_js):
|
||
"""Generate complete HTML for a problem."""
|
||
d = p['difficulty']
|
||
slug = p['slug']
|
||
title = p['title']
|
||
cat = p['category']
|
||
did = str(p['id']).zfill(3)
|
||
diff_cls = DIFF_CLASS.get(d, 'medium')
|
||
diff_icon = DIFF_ICON.get(d, '🟡')
|
||
|
||
return f'''<!DOCTYPE html>
|
||
<html lang="zh-Hans">
|
||
<head>
|
||
<meta charset="UTF-8">
|
||
<meta name="viewport" content="width=device-width, initial-scale=1.0">
|
||
<title>{did}. {title} – 图解</title>
|
||
<link rel="stylesheet" href="../shared/style.css">
|
||
<style>
|
||
/* page-specific overrides */
|
||
.vis-area {{ min-height: 120px; padding: 16px 0; }}
|
||
.code-section {{ margin-top: 16px; }}
|
||
</style>
|
||
</head>
|
||
<body>
|
||
<div class="container">
|
||
<h1>{diff_icon} {did}. {title} <span class="badge {diff_cls}">{d}</span></h1>
|
||
<p class="subtitle">分类：{cat} ｜ LeetCode Hot 100</p>
|
||
|
||
<!-- 控制面板 -->
|
||
<div class="controls" id="controls">
|
||
<label for="inputArea">输入：</label>
|
||
<input type="text" id="inputArea" placeholder="默认示例，可自定义">
|
||
<button id="applyBtn" class="primary">生成图解</button>
|
||
<select id="exampleSelect"></select>
|
||
<span style="flex:1"></span>
|
||
<button id="prevBtn">◀ 上一步</button>
|
||
<button id="nextBtn">下一步 ▶</button>
|
||
<button id="jumpBtn">⏭ 跳到结果</button>
|
||
<button id="autoBtn">自动播放</button>
|
||
<button id="resetBtn">重置</button>
|
||
</div>
|
||
|
||
<!-- 步骤流水线 -->
|
||
<div class="pipeline" id="pipeline"></div>
|
||
|
||
<!-- 提示条 -->
|
||
<div class="hint info" id="hintBox">
|
||
<span id="stepInfo"></span><br>
|
||
<span id="hintText"></span>
|
||
</div>
|
||
|
||
<!-- 可视化面板 -->
|
||
<div class="panels">
|
||
<div class="panel" id="mainPanel">
|
||
<h3>📊 可视化</h3>
|
||
<div class="vis-area" id="vizArea">点击「生成图解」开始</div>
|
||
</div>
|
||
<div class="panel-grid">
|
||
<div class="panel" id="detailPanel">
|
||
<h3>📝 当前步骤详情</h3>
|
||
<div id="detailContent">等待开始...</div>
|
||
</div>
|
||
<div class="panel" id="resultPanel">
|
||
<h3>✅ 结果</h3>
|
||
<div id="resultContent">等待完成...</div>
|
||
</div>
|
||
</div>
|
||
</div>
|
||
|
||
<!-- 代码 -->
|
||
<div class="panel code-section">
|
||
<h3>💻 参考代码（Python）</h3>
|
||
<div id="codeArea"></div>
|
||
</div>
|
||
|
||
<footer>Powered by QwenPaw · 图解算法 · LeetCode Hot 100</footer>
|
||
</div>
|
||
|
||
<script src="../shared/algo-viz.js"></script>
|
||
<script>
|
||
"use strict";
|
||
(function() {{
|
||
// ========== Algorithm Logic ==========
|
||
{algo_js}
|
||
}})();
|
||
</script>
|
||
</body>
|
||
</html>'''
|
||
|
||
|
||
# ========== Algorithm JS Generators ==========
|
||
# Each function returns a JS string for the specific algorithm
|
||
|
||
def js_two_sum():
|
||
return r'''
|
||
const examples = [
|
||
{input: [2,7,11,15], target: 9, label: '示例1: nums=[2,7,11,15], target=9'},
|
||
{input: [3,2,4], target: 6, label: '示例2: nums=[3,2,4], target=6'},
|
||
{input: [3,3], target: 6, label: '示例3: nums=[3,3], target=6'},
|
||
];
|
||
|
||
let nums, target, steps, stepCtrl;
|
||
|
||
function buildSteps(arr, tgt) {
|
||
nums = arr; target = tgt;
|
||
steps = [];
|
||
const map = {};
|
||
steps.push({stage:'start', msg:'开始遍历数组，用哈希表记录已访问的元素', highlights:{}, mapKeys:[], idx:-1});
|
||
for (let i = 0; i < arr.length; i++) {
|
||
const complement = tgt - arr[i];
|
||
steps.push({stage:'check', msg:`检查 nums[${i}]=${arr[i]}，需要的补数 complement = ${tgt} - ${arr[i]} = ${complement}`, highlights:{[i]:'orange'}, mapKeys:Object.entries(map), idx:i, complement});
|
||
if (complement in map) {
|
||
steps.push({stage:'found', msg:`找到！补数 ${complement} 在哈希表中，对应索引 ${map[complement]}`, highlights:{[i]:'green', [map[complement]]:'green'}, mapKeys:Object.entries(map), idx:i, result:[map[complement], i]});
|
||
return;
|
||
}
|
||
map[arr[i]] = i;
|
||
steps.push({stage:'store', msg:`补数 ${complement} 不在哈希表中，将 nums[${i}]=${arr[i]} → 索引 ${i} 存入哈希表`, highlights:{[i]:'blue'}, mapKeys:Object.entries(map), idx:i});
|
||
}
|
||
steps.push({stage:'done', msg:'遍历完毕，未找到满足条件的两个数', highlights:{}, mapKeys:Object.entries(map), idx:-1});
|
||
}
|
||
|
||
function render(step) {
|
||
if (!step) return;
|
||
const s = steps[step];
|
||
let viz = renderArray(nums, {highlights: s.highlights});
|
||
if (s.complement !== undefined) {
|
||
viz += '<div style="margin-top:8px;color:#64748b;">complement = ' + s.complement + '</div>';
|
||
}
|
||
$('vizArea').innerHTML = viz;
|
||
|
||
let detail = '<div class="calc-block">' + s.msg + '</div>';
|
||
if (s.mapKeys && s.mapKeys.length > 0) {
|
||
detail += '<div style="margin-top:8px;"><b>哈希表：</b>';
|
||
s.mapKeys.forEach(([k,v]) => { detail += `<code>${k}→${v}</code> `; });
|
||
detail += '</div>';
|
||
}
|
||
$('detailContent').innerHTML = detail;
|
||
|
||
if (s.stage === 'found') {
|
||
$('resultContent').innerHTML = `<div class="final-answer">返回 <b>[${s.result}]</b><br>nums[${s.result[0]}] + nums[${s.result[1]}] = ${nums[s.result[0]]} + ${nums[s.result[1]]} = ${target}</div>`;
|
||
} else if (s.stage === 'done') {
|
||
$('resultContent').innerHTML = '<div class="final-answer" style="border-color:#f87171;background:#fef2f2;">未找到答案</div>';
|
||
}
|
||
|
||
$('hintText').textContent = s.msg;
|
||
const stages = ['start→开始','check→检查','store→存入','found→找到'];
|
||
$('pipeline').innerHTML = stages.map(st => {
|
||
const [key, label] = st.split('→');
|
||
return `<span class="pipe-step ${s.stage===key?'active':''}">${label}</span>`;
|
||
}).join('<i>→</i>');
|
||
}
|
||
|
||
function init() {
|
||
const sel = $('exampleSelect');
|
||
examples.forEach((e,i) => { sel.innerHTML += `<option value="${i}">${e.label}</option>`; });
|
||
$('inputArea').value = 'nums=[2,7,11,15], target=9';
|
||
buildSteps(examples[0].input, examples[0].target);
|
||
stepCtrl = new StepController({onStep: render});
|
||
stepCtrl.setSteps(steps.map((_,i) => i));
|
||
$('stepInfo').textContent = `步骤 1 / ${steps.length}`;
|
||
stepCtrl.onStep = (idx) => { render(idx); $('stepInfo').textContent = `步骤 ${idx+1} / ${steps.length}`; };
|
||
$('applyBtn').onclick = () => {
|
||
const m = $('inputArea').value.match(/nums=\[([^\]]+)\].*target=(\d+)/);
|
||
if (!m) { alert('格式: nums=[2,7,11,15], target=9'); return; }
|
||
const arr = m[1].split(',').map(Number);
|
||
const tgt = parseInt(m[2]);
|
||
buildSteps(arr, tgt);
|
||
stepCtrl.setSteps(steps.map((_,i) => i));
|
||
render(0);
|
||
$('stepInfo').textContent = `步骤 1 / ${steps.length}`;
|
||
};
|
||
$('exampleSelect').onchange = () => {
|
||
const e = examples[parseInt($('exampleSelect').value)];
|
||
$('inputArea').value = `nums=[${e.input}], target=${e.target}`;
|
||
buildSteps(e.input, e.target);
|
||
stepCtrl.setSteps(steps.map((_,i) => i));
|
||
render(0);
|
||
};
|
||
$('prevBtn').onclick = () => stepCtrl.prev();
|
||
$('nextBtn').onclick = () => stepCtrl.next();
|
||
$('jumpBtn').onclick = () => stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick = () => { const on = stepCtrl.toggleAuto(); $('autoBtn').textContent = on ? '暂停' : '自动播放'; };
|
||
$('resetBtn').onclick = () => { stepCtrl.reset(); $('autoBtn').textContent = '自动播放'; };
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`def twoSum(nums, target):
|
||
hashmap = {}
|
||
for i, num in enumerate(nums):
|
||
complement = target - num
|
||
if complement in hashmap:
|
||
return [hashmap[complement], i]
|
||
hashmap[num] = i
|
||
return []`, {lang:'Python'});
|
||
'''
|
||
|
||
def js_group_anagrams():
|
||
return r'''
|
||
const examples = [
|
||
{input: ["eat","tea","tan","ate","nat","bat"], label: '示例1'},
|
||
{input: [""], label: '示例2: [""]'},
|
||
{input: ["a"], label: '示例3: ["a"]'},
|
||
];
|
||
let strs, steps, stepCtrl;
|
||
|
||
function sortedKey(s) { return s.split('').sort().join(''); }
|
||
|
||
function buildSteps(arr) {
|
||
strs = arr; steps = [];
|
||
const groups = {};
|
||
steps.push({stage:'start', msg:'遍历每个字符串，将其按字母排序后的结果作为 key 分组', current:'', key:'', groups:{}});
|
||
for (let i = 0; i < arr.length; i++) {
|
||
const s = arr[i];
|
||
const key = sortedKey(s);
|
||
steps.push({stage:'sort', msg:`处理 "${s}"：排序后 key = "${key}"`, current:s, key, groups:JSON.parse(JSON.stringify(groups)), idx:i});
|
||
if (!groups[key]) groups[key] = [];
|
||
groups[key].push(s);
|
||
steps.push({stage:'group', msg:`将 "${s}" 加入分组 ["${key}"]`, current:s, key, groups:JSON.parse(JSON.stringify(groups)), idx:i});
|
||
}
|
||
steps.push({stage:'done', msg:'分组完成', current:'', key:'', groups:JSON.parse(JSON.stringify(groups))});
|
||
}
|
||
|
||
function render(step) {
|
||
const s = steps[step];
|
||
let viz = '<div class="nums-line">';
|
||
strs.forEach((st,i) => {
|
||
const cls = s.idx===i ? (s.stage==='group'?'green':'orange') : 'default';
|
||
viz += `<span class="chip ${cls}" style="min-width:auto;padding:4px 12px;">"${st}"</span>`;
|
||
});
|
||
viz += '</div>';
|
||
if (s.current) viz += `<div style="margin-top:8px;">当前: <code>"${s.current}"</code> → key: <code>"${s.key}"</code></div>`;
|
||
$('vizArea').innerHTML = viz;
|
||
let detail = '<div class="calc-block">' + s.msg + '</div>';
|
||
detail += '<div style="margin-top:8px;"><b>分组结果：</b></div>';
|
||
Object.entries(s.groups).forEach(([k,v]) => {
|
||
detail += `<div style="margin:4px 0;"><code>${k}</code> → [${v.map(x=>`"${x}"`).join(', ')}]</div>`;
|
||
});
|
||
$('detailContent').innerHTML = detail;
|
||
if (s.stage === 'done') {
|
||
const result = Object.values(s.groups);
|
||
$('resultContent').innerHTML = `<div class="final-answer">返回 <b>${JSON.stringify(result)}</b><br>共 ${result.length} 个分组</div>`;
|
||
}
|
||
$('hintText').textContent = s.msg;
|
||
const stages = ['start→开始','sort→排序','group→分组','done→完成'];
|
||
$('pipeline').innerHTML = stages.map(st => {
|
||
const [k,l] = st.split('→');
|
||
return `<span class="pipe-step ${s.stage===k?'active':''}">${l}</span>`;
|
||
}).join('<i>→</i>');
|
||
}
|
||
|
||
function init() {
|
||
const sel = $('exampleSelect');
|
||
examples.forEach((e,i) => { sel.innerHTML += `<option value="${i}">${e.label}</option>`; });
|
||
$('inputArea').value = '["eat","tea","tan","ate","nat","bat"]';
|
||
buildSteps(examples[0].input);
|
||
stepCtrl = new StepController({onStep: render});
|
||
stepCtrl.setSteps(steps.map((_,i)=>i));
|
||
$('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
stepCtrl.onStep = (idx) => { render(idx); $('stepInfo').textContent = `步骤 ${idx+1} / ${steps.length}`; };
|
||
$('applyBtn').onclick = () => {
|
||
try { const arr = JSON.parse($('inputArea').value); buildSteps(arr); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0); }
|
||
catch(e) { alert('请输入合法 JSON 数组，如 ["eat","tea"]'); }
|
||
};
|
||
$('exampleSelect').onchange = () => {
|
||
const e = examples[parseInt($('exampleSelect').value)];
|
||
$('inputArea').value = JSON.stringify(e.input);
|
||
buildSteps(e.input); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0);
|
||
};
|
||
$('prevBtn').onclick = () => stepCtrl.prev();
|
||
$('nextBtn').onclick = () => stepCtrl.next();
|
||
$('jumpBtn').onclick = () => stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick = () => { const on = stepCtrl.toggleAuto(); $('autoBtn').textContent = on ? '暂停' : '自动播放'; };
|
||
$('resetBtn').onclick = () => { stepCtrl.reset(); $('autoBtn').textContent = '自动播放'; };
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`def groupAnagrams(strs):
|
||
groups = {}
|
||
for s in strs:
|
||
key = ''.join(sorted(s))
|
||
if key not in groups:
|
||
groups[key] = []
|
||
groups[key].append(s)
|
||
return list(groups.values())`, {lang:'Python'});
|
||
'''
|
||
|
||
def js_longest_consecutive():
|
||
return r'''
|
||
const examples = [
|
||
{input: [100,4,200,1,3,2], label: '示例1: [100,4,200,1,3,2]'},
|
||
{input: [0,3,7,2,5,8,4,6,0,1], label: '示例2: [0,3,7,2,5,8,4,6,0,1]'},
|
||
];
|
||
let nums, steps, stepCtrl;
|
||
|
||
function buildSteps(arr) {
|
||
nums = arr; steps = [];
|
||
const numSet = new Set(arr);
|
||
let best = 0;
|
||
steps.push({stage:'start', msg:'将所有数放入集合，寻找每个连续序列的起点', sorted:[...new Set(arr)].sort((a,b)=>a-b), current:-1, streakNums:[], best:0});
|
||
const sortedUnique = [...new Set(arr)].sort((a,b)=>a-b);
|
||
for (const num of sortedUnique) {
|
||
if (numSet.has(num - 1)) continue;
|
||
let streak = 1, current = num;
|
||
const streakNums = [num];
|
||
steps.push({stage:'start_seq', msg:`${num} 是连续序列的起点（${num-1} 不在集合中）`, sorted:sortedUnique, current:num, streakNums, streak, best});
|
||
while (numSet.has(current + 1)) {
|
||
current++; streak++; streakNums.push(current);
|
||
steps.push({stage:'extend', msg:`序列延伸：${current} 在集合中`, sorted:sortedUnique, current, streakNums, streak, best});
|
||
}
|
||
best = Math.max(best, streak);
|
||
steps.push({stage:'end_seq', msg:`序列结束，长度=${streak}，最长=${best}`, sorted:sortedUnique, current, streakNums, streak, best});
|
||
}
|
||
steps.push({stage:'done', msg:`最长连续序列长度为 ${best}`, sorted:sortedUnique, current:-1, streakNums:[], best});
|
||
}
|
||
|
||
function render(step) {
|
||
const s = steps[step];
|
||
const hl = {};
|
||
if (s.streakNums) s.streakNums.forEach(n => { hl[n] = s.stage==='end_seq'?'green':'purple'; });
|
||
if (s.current >= 0) hl[s.current] = 'orange';
|
||
let viz = '<div style="margin-bottom:8px;"><b>排序去重后：</b></div>';
|
||
viz += renderArray(s.sorted, {highlights: hl});
|
||
if (s.streakNums && s.streakNums.length > 0)
|
||
viz += '<div style="margin-top:8px;color:#8b5cf6;">连续序列: [' + s.streakNums.join(', ') + '] 长度=' + s.streak + '</div>';
|
||
$('vizArea').innerHTML = viz;
|
||
$('detailContent').innerHTML = '<div class="calc-block">' + s.msg + '</div>';
|
||
if (s.best > 0) $('detailContent').innerHTML += `<div class="current-answer">当前最长：<b>${s.best}</b></div>`;
|
||
if (s.stage === 'done') $('resultContent').innerHTML = `<div class="final-answer">最长连续序列长度 = <b>${s.best}</b></div>`;
|
||
$('hintText').textContent = s.msg;
|
||
const stages = ['start→开始','start_seq→起点','extend→延伸','end_seq→结束','done→完成'];
|
||
$('pipeline').innerHTML = stages.map(st => { const [k,l]=st.split('→'); return `<span class="pipe-step ${s.stage===k?'active':''}">${l}</span>`; }).join('<i>→</i>');
|
||
}
|
||
|
||
function init() {
|
||
const sel = $('exampleSelect');
|
||
examples.forEach((e,i) => { sel.innerHTML += `<option value="${i}">${e.label}</option>`; });
|
||
$('inputArea').value = '[100,4,200,1,3,2]';
|
||
buildSteps(examples[0].input);
|
||
stepCtrl = new StepController({onStep: render});
|
||
stepCtrl.setSteps(steps.map((_,i)=>i));
|
||
$('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
stepCtrl.onStep = (idx) => { render(idx); $('stepInfo').textContent = `步骤 ${idx+1} / ${steps.length}`; };
|
||
$('applyBtn').onclick = () => {
|
||
try { const arr = JSON.parse($('inputArea').value); buildSteps(arr); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0); }
|
||
catch(e) { alert('请输入合法 JSON 数组'); }
|
||
};
|
||
$('exampleSelect').onchange = () => {
|
||
const e = examples[parseInt($('exampleSelect').value)];
|
||
$('inputArea').value = JSON.stringify(e.input);
|
||
buildSteps(e.input); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0);
|
||
};
|
||
$('prevBtn').onclick = () => stepCtrl.prev();
|
||
$('nextBtn').onclick = () => stepCtrl.next();
|
||
$('jumpBtn').onclick = () => stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick = () => { const on = stepCtrl.toggleAuto(); $('autoBtn').textContent = on ? '暂停' : '自动播放'; };
|
||
$('resetBtn').onclick = () => { stepCtrl.reset(); $('autoBtn').textContent = '自动播放'; };
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`def longestConsecutive(nums):
|
||
num_set = set(nums)
|
||
longest = 0
|
||
for num in num_set:
|
||
if num - 1 not in num_set:
|
||
streak = 1
|
||
while num + streak in num_set:
|
||
streak += 1
|
||
longest = max(longest, streak)
|
||
return longest`, {lang:'Python'});
|
||
'''
|
||
|
||
def js_move_zeros():
|
||
return r'''
|
||
const examples = [
|
||
{input: [0,1,0,3,12], label: '示例1: [0,1,0,3,12]'},
|
||
{input: [0], label: '示例2: [0]'},
|
||
{input: [1,0,2,0,3], label: '示例3: [1,0,2,0,3]'},
|
||
];
|
||
let nums, steps, stepCtrl;
|
||
|
||
function buildSteps(arr) {
|
||
nums = [...arr]; steps = [];
|
||
let slow = 0;
|
||
steps.push({stage:'start', msg:'快慢指针：slow 指向第一个可放非零元素的位置', arr:[...nums], slow:0, fast:0});
|
||
for (let fast = 0; fast < nums.length; fast++) {
|
||
steps.push({stage:'check', msg:`fast=${fast}，nums[${fast}]=${nums[fast]} ${nums[fast]===0?'是零，跳过':'不是零，交换到前面'}`, arr:[...nums], slow, fast});
|
||
if (nums[fast] !== 0) {
|
||
if (slow !== fast) {
|
||
[nums[slow], nums[fast]] = [nums[fast], nums[slow]];
|
||
steps.push({stage:'swap', msg:`交换 nums[${slow}] 和 nums[${fast}] → [${nums}]`, arr:[...nums], slow, fast});
|
||
}
|
||
slow++;
|
||
steps.push({stage:'advance', msg:`slow 前进到 ${slow}`, arr:[...nums], slow, fast});
|
||
}
|
||
}
|
||
steps.push({stage:'done', msg:'完成！', arr:[...nums], slow, fast:nums.length});
|
||
}
|
||
|
||
function render(step) {
|
||
const s = steps[step];
|
||
const hl = {};
|
||
if (s.fast < s.arr.length) hl[s.fast] = 'orange';
|
||
if (s.slow < s.arr.length) hl[s.slow] = 'blue';
|
||
for (let i = 0; i < s.slow; i++) { if (s.arr[i] !== 0) hl[i] = 'green'; }
|
||
let viz = renderArray(s.arr, {highlights: hl, pointers: {slow: s.slow, fast: s.fast}});
|
||
$('vizArea').innerHTML = viz;
|
||
$('detailContent').innerHTML = '<div class="calc-block">' + s.msg + '</div>';
|
||
if (s.stage === 'done') $('resultContent').innerHTML = `<div class="final-answer">结果：<b>[${s.arr}]</b></div>`;
|
||
$('hintText').textContent = s.msg;
|
||
const stages = ['start→开始','check→检查','swap→交换','advance→前进','done→完成'];
|
||
$('pipeline').innerHTML = stages.map(st => { const [k,l]=st.split('→'); return `<span class="pipe-step ${s.stage===k?'active':''}">${l}</span>`; }).join('<i>→</i>');
|
||
}
|
||
|
||
function init() {
|
||
const sel = $('exampleSelect');
|
||
examples.forEach((e,i) => { sel.innerHTML += `<option value="${i}">${e.label}</option>`; });
|
||
$('inputArea').value = '[0,1,0,3,12]';
|
||
buildSteps(examples[0].input);
|
||
stepCtrl = new StepController({onStep: render});
|
||
stepCtrl.setSteps(steps.map((_,i)=>i));
|
||
$('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
stepCtrl.onStep = (idx) => { render(idx); $('stepInfo').textContent = `步骤 ${idx+1} / ${steps.length}`; };
|
||
$('applyBtn').onclick = () => {
|
||
try { const arr = JSON.parse($('inputArea').value); buildSteps(arr); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0); }
|
||
catch(e) { alert('请输入合法 JSON 数组'); }
|
||
};
|
||
$('exampleSelect').onchange = () => {
|
||
const e = examples[parseInt($('exampleSelect').value)];
|
||
$('inputArea').value = JSON.stringify(e.input);
|
||
buildSteps(e.input); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0);
|
||
};
|
||
$('prevBtn').onclick = () => stepCtrl.prev();
|
||
$('nextBtn').onclick = () => stepCtrl.next();
|
||
$('jumpBtn').onclick = () => stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick = () => { const on = stepCtrl.toggleAuto(); $('autoBtn').textContent = on ? '暂停' : '自动播放'; };
|
||
$('resetBtn').onclick = () => { stepCtrl.reset(); $('autoBtn').textContent = '自动播放'; };
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`def moveZeroes(nums):
|
||
slow = 0
|
||
for fast in range(len(nums)):
|
||
if nums[fast] != 0:
|
||
nums[slow], nums[fast] = nums[fast], nums[slow]
|
||
slow += 1`, {lang:'Python'});
|
||
'''
|
||
|
||
def js_container_with_most_water():
|
||
return r'''
|
||
const examples = [
|
||
{input: [1,8,6,2,5,4,8,3,7], label: '示例1: [1,8,6,2,5,4,8,3,7]'},
|
||
{input: [1,1], label: '示例2: [1,1]'},
|
||
];
|
||
let height, steps, stepCtrl;
|
||
|
||
function buildSteps(arr) {
|
||
height = [...arr]; steps = [];
|
||
let left = 0, right = arr.length - 1, maxArea = 0;
|
||
steps.push({stage:'init', msg:'双指针从两端开始', left, right, maxArea, area:0});
|
||
while (left < right) {
|
||
const h = Math.min(arr[left], arr[right]);
|
||
const w = right - left;
|
||
const area = h * w;
|
||
maxArea = Math.max(maxArea, area);
|
||
steps.push({stage:'calc', msg:`left=${left}(h=${arr[left]}) right=${right}(h=${arr[right]}) → 高=${h} 宽=${w} 面积=${area}`, left, right, maxArea, area});
|
||
if (arr[left] < arr[right]) { left++; steps.push({stage:'move', msg:`左边矮，左指针→${left}`, left, right, maxArea, area}); }
|
||
else { right--; steps.push({stage:'move', msg:`右边矮，右指针→${right}`, left, right, maxArea, area}); }
|
||
}
|
||
steps.push({stage:'done', msg:`指针相遇，最大面积=${maxArea}`, left, right, maxArea, area:0});
|
||
}
|
||
|
||
function render(step) {
|
||
const s = steps[step];
|
||
const maxH = Math.max(...height);
|
||
let viz = '<div style="display:flex;align-items:flex-end;gap:4px;height:120px;margin-top:12px;padding:8px 0;">';
|
||
height.forEach((h,i) => {
|
||
const pct = (h / maxH * 100); const bg = i===s.left||i===s.right ? 'var(--blue)' : '#cbd5e1';
|
||
viz += `<div style="width:36px;height:${pct}%;background:${bg};border-radius:4px 4px 0 0;display:flex;align-items:flex-start;justify-content:center;font-size:11px;font-weight:700;color:${i===s.left||i===s.right?'white':'#475569'};padding-top:4px;">${h}</div>`;
|
||
});
|
||
viz += '</div>';
|
||
viz += `<div style="margin-top:10px;color:var(--green);">💧 最大面积 = ${s.maxArea}</div>`;
|
||
$('vizArea').innerHTML = viz;
|
||
$('detailContent').innerHTML = '<div class="calc-block">' + s.msg + '</div>';
|
||
if (s.stage === 'done') $('resultContent').innerHTML = `<div class="final-answer">最大盛水量 = <b>${s.maxArea}</b></div>`;
|
||
$('hintText').textContent = s.msg;
|
||
const stages = ['init→初始化','calc→计算','move→移动','done→完成'];
|
||
$('pipeline').innerHTML = stages.map(st => { const [k,l]=st.split('→'); return `<span class="pipe-step ${s.stage===k?'active':''}">${l}</span>`; }).join('<i>→</i>');
|
||
}
|
||
|
||
function init() {
|
||
const sel = $('exampleSelect');
|
||
examples.forEach((e,i) => { sel.innerHTML += `<option value="${i}">${e.label}</option>`; });
|
||
$('inputArea').value = '[1,8,6,2,5,4,8,3,7]';
|
||
buildSteps(examples[0].input);
|
||
stepCtrl = new StepController({onStep: render});
|
||
stepCtrl.setSteps(steps.map((_,i)=>i));
|
||
$('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
stepCtrl.onStep = (idx) => { render(idx); $('stepInfo').textContent = `步骤 ${idx+1} / ${steps.length}`; };
|
||
$('applyBtn').onclick = () => {
|
||
try { const arr = JSON.parse($('inputArea').value); buildSteps(arr); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0); }
|
||
catch(e) { alert('请输入合法 JSON 数组'); }
|
||
};
|
||
$('exampleSelect').onchange = () => {
|
||
const e = examples[parseInt($('exampleSelect').value)];
|
||
$('inputArea').value = JSON.stringify(e.input); buildSteps(e.input); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0);
|
||
};
|
||
$('prevBtn').onclick = () => stepCtrl.prev();
|
||
$('nextBtn').onclick = () => stepCtrl.next();
|
||
$('jumpBtn').onclick = () => stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick = () => { const on = stepCtrl.toggleAuto(); $('autoBtn').textContent = on ? '暂停' : '自动播放'; };
|
||
$('resetBtn').onclick = () => { stepCtrl.reset(); $('autoBtn').textContent = '自动播放'; };
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`def maxArea(height):
|
||
left, right = 0, len(height) - 1
|
||
max_area = 0
|
||
while left < right:
|
||
h = min(height[left], height[right])
|
||
max_area = max(max_area, h * (right - left))
|
||
if height[left] < height[right]:
|
||
left += 1
|
||
else:
|
||
right -= 1
|
||
return max_area`, {lang:'Python'});
|
||
'''
|
||
|
||
def js_3sum():
|
||
return r'''
|
||
const examples = [
|
||
{input: [-1,0,1,2,-1,-4], label: '示例1: [-1,0,1,2,-1,-4]'},
|
||
{input: [0,1,1], label: '示例2: [0,1,1]'},
|
||
{input: [0,0,0], label: '示例3: [0,0,0]'},
|
||
];
|
||
let nums, steps, stepCtrl;
|
||
|
||
function buildSteps(arr) {
|
||
nums = [...arr].sort((a,b) => a - b); steps = [];
|
||
const result = [];
|
||
steps.push({stage:'sort', msg:`排序: [${arr}] → [${nums}]`, arr:[...nums], i:-1, l:-1, r:-1, triplets:[], currentSum:null});
|
||
for (let i = 0; i < nums.length - 2; i++) {
|
||
if (i > 0 && nums[i] === nums[i-1]) continue;
|
||
let l = i + 1, r = nums.length - 1;
|
||
steps.push({stage:'fix', msg:`固定 nums[${i}]=${nums[i]}，双指针 [${l}..${r}]`, arr:[...nums], i, l, r, triplets:JSON.parse(JSON.stringify(result)), currentSum:null});
|
||
while (l < r) {
|
||
const sum = nums[i] + nums[l] + nums[r];
|
||
steps.push({stage:'calc', msg:`${nums[i]}+${nums[l]}+${nums[r]}=${sum}` + (sum===0?' ✓':sum<0?' → L右移':' → R左移'), arr:[...nums], i, l, r, triplets:JSON.parse(JSON.stringify(result)), currentSum:sum});
|
||
if (sum === 0) {
|
||
result.push([nums[i], nums[l], nums[r]]);
|
||
steps.push({stage:'found', msg:`找到 [${nums[i]},${nums[l]},${nums[r]}]`, arr:[...nums], i, l, r, triplets:JSON.parse(JSON.stringify(result)), currentSum:0});
|
||
while (l < r && nums[l] === nums[l+1]) l++;
|
||
while (l < r && nums[r] === nums[r-1]) r--;
|
||
l++; r--;
|
||
} else if (sum < 0) { l++; } else { r--; }
|
||
}
|
||
}
|
||
steps.push({stage:'done', msg:`共找到 ${result.length} 个三元组`, arr:[...nums], i:-1, l:-1, r:-1, triplets:JSON.parse(JSON.stringify(result)), currentSum:null});
|
||
}
|
||
|
||
function render(step) {
|
||
const s = steps[step];
|
||
const hl = {};
|
||
if (s.i>=0) hl[s.i] = s.stage==='found'?'green':'purple';
|
||
if (s.l>=0) hl[s.l] = s.stage==='found'?'green':'orange';
|
||
if (s.r>=0) hl[s.r] = s.stage==='found'?'green':'blue';
|
||
const pointers = {};
|
||
if (s.i>=0) pointers['i']=s.i; if (s.l>=0) pointers['L']=s.l; if (s.r>=0) pointers['R']=s.r;
|
||
let viz = renderArray(s.arr, {highlights:hl, pointers});
|
||
if (s.currentSum !== null) viz += `<div style="margin-top:8px;">和 = <b style="color:${s.currentSum===0?'var(--green)':s.currentSum<0?'var(--blue)':'var(--red)'};">${s.currentSum}</b></div>`;
|
||
$('vizArea').innerHTML = viz;
|
||
let detail = '<div class="calc-block">' + s.msg + '</div>';
|
||
if (s.triplets.length > 0) { s.triplets.forEach((t,i)=>{ detail += `<div><code>${i+1}. [${t.join(', ')}]</code></div>`; }); }
|
||
$('detailContent').innerHTML = detail;
|
||
if (s.stage === 'done') {
|
||
if (s.triplets.length > 0) $('resultContent').innerHTML = `<div class="final-answer">返回 <b>${JSON.stringify(s.triplets)}</b></div>`;
|
||
else $('resultContent').innerHTML = '<div class="final-answer" style="border-color:#f87171;background:#fef2f2;">未找到</div>';
|
||
}
|
||
$('hintText').textContent = s.msg;
|
||
const stages = ['sort→排序','fix→固定','calc→计算','found→找到','done→完成'];
|
||
$('pipeline').innerHTML = stages.map(st => { const [k,l]=st.split('→'); return `<span class="pipe-step ${s.stage===k?'active':''}">${l}</span>`; }).join('<i>→</i>');
|
||
}
|
||
|
||
function init() {
|
||
const sel = $('exampleSelect');
|
||
examples.forEach((e,i) => { sel.innerHTML += `<option value="${i}">${e.label}</option>`; });
|
||
$('inputArea').value = '[-1,0,1,2,-1,-4]';
|
||
buildSteps(examples[0].input);
|
||
stepCtrl = new StepController({onStep: render});
|
||
stepCtrl.setSteps(steps.map((_,i)=>i));
|
||
$('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
stepCtrl.onStep = (idx) => { render(idx); $('stepInfo').textContent = `步骤 ${idx+1} / ${steps.length}`; };
|
||
$('applyBtn').onclick = () => {
|
||
try { const arr = JSON.parse($('inputArea').value); buildSteps(arr); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0); $('stepInfo').textContent = '步骤 1 / ' + steps.length; }
|
||
catch(e) { alert('请输入合法 JSON 数组'); }
|
||
};
|
||
$('exampleSelect').onchange = () => {
|
||
const e = examples[parseInt($('exampleSelect').value)];
|
||
$('inputArea').value = JSON.stringify(e.input); buildSteps(e.input); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0);
|
||
};
|
||
$('prevBtn').onclick = () => stepCtrl.prev();
|
||
$('nextBtn').onclick = () => stepCtrl.next();
|
||
$('jumpBtn').onclick = () => stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick = () => { const on = stepCtrl.toggleAuto(); $('autoBtn').textContent = on ? '暂停' : '自动播放'; };
|
||
$('resetBtn').onclick = () => { stepCtrl.reset(); $('autoBtn').textContent = '自动播放'; };
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`def threeSum(nums):
|
||
nums.sort()
|
||
res = []
|
||
for i in range(len(nums) - 2):
|
||
if i > 0 and nums[i] == nums[i-1]:
|
||
continue
|
||
l, r = i + 1, len(nums) - 1
|
||
while l < r:
|
||
s = nums[i] + nums[l] + nums[r]
|
||
if s == 0:
|
||
res.append([nums[i], nums[l], nums[r]])
|
||
while l < r and nums[l] == nums[l+1]: l += 1
|
||
while l < r and nums[r] == nums[r-1]: r -= 1
|
||
l += 1; r -= 1
|
||
elif s < 0: l += 1
|
||
else: r -= 1
|
||
return res`, {lang:'Python'});
|
||
'''
|
||
|
||
def js_trapping_rain_water():
|
||
return r'''
|
||
const examples = [
|
||
{input: [0,1,0,2,1,0,1,3,2,1,2,1], label: '示例1: [0,1,0,2,1,0,1,3,2,1,2,1]'},
|
||
{input: [4,2,0,3,2,5], label: '示例2: [4,2,0,3,2,5]'},
|
||
];
|
||
let height, steps, stepCtrl;
|
||
|
||
function buildSteps(arr) {
|
||
height = [...arr]; steps = [];
|
||
let left = 0, right = arr.length - 1;
|
||
let leftMax = arr[left], rightMax = arr[right];
|
||
let totalWater = 0;
|
||
const waterAt = new Array(arr.length).fill(0);
|
||
steps.push({stage:'init', msg:`双指针从两端开始，left_max=${leftMax}，right_max=${rightMax}`, left, right, leftMax, rightMax, totalWater, waterAt:[...waterAt]});
|
||
while (left < right) {
|
||
if (leftMax <= rightMax) {
|
||
const water = Math.max(0, leftMax - arr[left]);
|
||
waterAt[left] = water; totalWater += water;
|
||
steps.push({stage:'calcL', msg:`左端: min(${leftMax},${rightMax})=${leftMax}, h[${left}]=${arr[left]}, 储水=${water}`, left, right, leftMax, rightMax, totalWater, waterAt:[...waterAt]});
|
||
left++; leftMax = Math.max(leftMax, arr[left]);
|
||
} else {
|
||
const water = Math.max(0, rightMax - arr[right]);
|
||
waterAt[right] = water; totalWater += water;
|
||
steps.push({stage:'calcR', msg:`右端: min(${leftMax},${rightMax})=${rightMax}, h[${right}]=${arr[right]}, 储水=${water}`, left, right, leftMax, rightMax, totalWater, waterAt:[...waterAt]});
|
||
right--; rightMax = Math.max(rightMax, arr[right]);
|
||
}
|
||
}
|
||
steps.push({stage:'done', msg:`总储水量=${totalWater}`, left, right, leftMax, rightMax, totalWater, waterAt:[...waterAt]});
|
||
}
|
||
|
||
function render(step) {
|
||
const s = steps[step];
|
||
const maxH = Math.max(...height);
|
||
const chartH = 160; const unitH = chartH / (maxH||1); const barW = 36;
|
||
let viz = '<div style="position:relative;display:flex;align-items:flex-end;gap:2px;height:' + (chartH+30) + 'px;padding:0 4px;margin-top:8px;">';
|
||
height.forEach((h, i) => {
|
||
const barH = h * unitH; const waterH = s.waterAt[i] * unitH;
|
||
const isL = i===s.left, isR = i===s.right;
|
||
const barBg = isL ? 'var(--blue)' : isR ? 'var(--purple)' : '#94a3b8';
|
||
viz += `<div style="position:relative;width:${barW}px;display:flex;flex-direction:column;align-items:stretch;">`;
|
||
if (waterH > 0) viz += `<div style="height:${waterH}px;background:rgba(59,130,246,0.25);border-radius:2px 2px 0 0;border-top:2px solid rgba(59,130,246,0.5);"></div>`;
|
||
viz += `<div style="height:${barH}px;background:${barBg};border-radius:3px 3px 0 0;display:flex;align-items:flex-start;justify-content:center;font-size:11px;font-weight:700;color:${isL||isR?'white':'#334155'};padding-top:2px;min-height:2px;">${h>0?h:''}</div>`;
|
||
viz += `<div style="text-align:center;font-size:10px;color:var(--text-muted);margin-top:2px;">${i}</div></div>`;
|
||
});
|
||
viz += '</div>';
|
||
viz += `<div style="margin-top:10px;display:flex;gap:16px;"><span style="color:var(--blue);">■ left_max=${s.leftMax}</span><span style="color:var(--purple);">■ right_max=${s.rightMax}</span><span style="color:var(--green);">💧 储水=${s.totalWater}</span></div>`;
|
||
$('vizArea').innerHTML = viz;
|
||
$('detailContent').innerHTML = '<div class="calc-block">' + s.msg + '</div>';
|
||
if (s.stage === 'done') $('resultContent').innerHTML = `<div class="final-answer">总储水量 = <b>${s.totalWater}</b></div>`;
|
||
$('hintText').textContent = s.msg;
|
||
const stages = ['init→初始化','calcL→左端','calcR→右端','done→完成'];
|
||
$('pipeline').innerHTML = stages.map(st => { const [k,l]=st.split('→'); return `<span class="pipe-step ${s.stage===k?'active':''}">${l}</span>`; }).join('<i>→</i>');
|
||
}
|
||
|
||
function init() {
|
||
const sel = $('exampleSelect');
|
||
examples.forEach((e,i) => { sel.innerHTML += `<option value="${i}">${e.label}</option>`; });
|
||
$('inputArea').value = '[0,1,0,2,1,0,1,3,2,1,2,1]';
|
||
buildSteps(examples[0].input);
|
||
stepCtrl = new StepController({onStep: render});
|
||
stepCtrl.setSteps(steps.map((_,i)=>i));
|
||
$('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
stepCtrl.onStep = (idx) => { render(idx); $('stepInfo').textContent = `步骤 ${idx+1} / ${steps.length}`; };
|
||
$('applyBtn').onclick = () => {
|
||
try { const arr = JSON.parse($('inputArea').value); buildSteps(arr); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0); $('stepInfo').textContent = '步骤 1 / ' + steps.length; }
|
||
catch(e) { alert('请输入合法 JSON 数组'); }
|
||
};
|
||
$('exampleSelect').onchange = () => {
|
||
const e = examples[parseInt($('exampleSelect').value)];
|
||
$('inputArea').value = JSON.stringify(e.input); buildSteps(e.input); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0);
|
||
};
|
||
$('prevBtn').onclick = () => stepCtrl.prev();
|
||
$('nextBtn').onclick = () => stepCtrl.next();
|
||
$('jumpBtn').onclick = () => stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick = () => { const on = stepCtrl.toggleAuto(); $('autoBtn').textContent = on ? '暂停' : '自动播放'; };
|
||
$('resetBtn').onclick = () => { stepCtrl.reset(); $('autoBtn').textContent = '自动播放'; };
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`def trap(height):
|
||
left, right = 0, len(height) - 1
|
||
left_max, right_max = height[left], height[right]
|
||
water = 0
|
||
while left < right:
|
||
if left_max <= right_max:
|
||
water += left_max - height[left]
|
||
left += 1
|
||
left_max = max(left_max, height[left])
|
||
else:
|
||
water += right_max - height[right]
|
||
right -= 1
|
||
right_max = max(right_max, height[right])
|
||
return water`, {lang:'Python'});
|
||
'''
|
||
|
||
|
||
# ==================== 图论 4 题 ====================
|
||
|
||
def js_number_of_islands():
|
||
return r'''
|
||
const examples = [
|
||
{grid: [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]], label: '示例1: 4×5 3个岛'},
|
||
{grid: [["1","1","1"],["0","1","0"],["1","1","1"]], label: '示例2: 3×3 1个岛'},
|
||
];
|
||
let grid, R, C, steps, stepCtrl, islandColors, finalMap;
|
||
|
||
function buildSteps(g) {
|
||
grid = g.map(r=>[...r]); R = grid.length; C = grid[0].length;
|
||
steps = []; islandColors = {}; finalMap = {};
|
||
const visited = Array.from({length:R},()=>Array(C).fill(false));
|
||
let islands = 0;
|
||
const islandColorList = ['blue','green','purple','orange','cyan','red'];
|
||
|
||
steps.push({stage:'start', msg:'遍历网格，遇到未访问的陆地进行DFS染色', hl:{}, im:{}, islands:0});
|
||
|
||
for (let r=0; r<R; r++) {
|
||
for (let c=0; c<C; c++) {
|
||
if (grid[r][c]==='1' && !visited[r][c]) {
|
||
islands++;
|
||
const color = islandColorList[(islands-1) % islandColorList.length];
|
||
islandColors[islands] = color;
|
||
steps.push({stage:'new_island', msg:`发现岛屿 #${islands}，从 (${r},${c}) 开始DFS`, hl:{[r+','+c]:'current'}, im:JSON.parse(JSON.stringify(finalMap)), islands});
|
||
|
||
const stack = [[r,c]];
|
||
visited[r][c] = true;
|
||
finalMap[r+','+c] = islands;
|
||
|
||
while (stack.length > 0) {
|
||
const [cr, cc] = stack.pop();
|
||
const dirs = [[0,1],[0,-1],[1,0],[-1,0]];
|
||
for (const [dr,dc] of dirs) {
|
||
const nr=cr+dr, nc=cc+dc;
|
||
if (nr>=0 && nr<R && nc>=0 && nc<C && grid[nr][nc]==='1' && !visited[nr][nc]) {
|
||
visited[nr][nc] = true;
|
||
stack.push([nr,nc]);
|
||
finalMap[nr+','+nc] = islands;
|
||
const hl2 = {}; hl2[nr+','+nc] = 'current';
|
||
steps.push({stage:'dfs', msg:`DFS: (${cr},${cc}) → (${nr},${nc}) 染色为岛 #${islands}`, hl:hl2, im:JSON.parse(JSON.stringify(finalMap)), islands});
|
||
}
|
||
}
|
||
}
|
||
steps.push({stage:'island_done', msg:`岛屿 #${islands} DFS完成`, hl:{}, im:JSON.parse(JSON.stringify(finalMap)), islands});
|
||
}
|
||
}
|
||
}
|
||
steps.push({stage:'done', msg:`遍历完毕，共 ${islands} 个岛屿`, hl:{}, im:JSON.parse(JSON.stringify(finalMap)), islands});
|
||
}
|
||
|
||
function render(step) {
|
||
const s = steps[step];
|
||
const cellClass = (val,r,c) => {
|
||
if (val==='0') return 'water';
|
||
const key = r+','+c;
|
||
const iid = s.im[key];
|
||
if (iid) return islandColors[iid] || 'island';
|
||
return 'default';
|
||
};
|
||
const cellStyle = (val,r,c) => {
|
||
if (val==='0') return 'background:#e0f2fe;color:#0369a1;';
|
||
const key = r+','+c;
|
||
const iid = s.im[key];
|
||
const colorMap = {blue:'background:#dbeafe;color:#1e40af;',green:'background:#dcfce7;color:#166534;',purple:'background:#ede9fe;color:#5b21b6;',orange:'background:#fff7ed;color:#9a3412;',cyan:'background:#cffafe;color:#155e75;',red:'background:#fee2e2;color:#991b1b;'};
|
||
if (iid && colorMap[islandColors[iid]]) return colorMap[islandColors[iid]];
|
||
return 'background:#f1f5f9;color:#475569;';
|
||
};
|
||
let viz = renderGrid(grid, {highlights:s.hl, cellSize:48, cellClass, cellStyle});
|
||
viz += `<div style="margin-top:8px;">🏝️ 岛屿数量：${s.islands}</div>`;
|
||
$('vizArea').innerHTML = viz;
|
||
$('detailContent').innerHTML = '<div class="calc-block">' + s.msg + '</div>';
|
||
if (s.stage==='done') {
|
||
let det = `<div class="final-answer">岛屿数量 = <b>${s.islands}</b></div>`;
|
||
det += '<div style="margin-top:8px;">';
|
||
for (let i=1; i<=s.islands; i++) det += `<span style="margin-right:12px;"><span style="display:inline-block;width:14px;height:14px;border-radius:3px;${islandColors[i]==='blue'?'background:#dbeafe':islandColors[i]==='green'?'background:#dcfce7':islandColors[i]==='purple'?'background:#ede9fe':'background:#fff7ed'};vertical-align:middle;"></span> 岛屿 #${i}</span>`;
|
||
det += '</div>';
|
||
$('resultContent').innerHTML = det;
|
||
}
|
||
$('hintText').textContent = s.msg;
|
||
const stages = ['start→开始','new_island→发现岛屿','dfs→DFS染色','island_done→岛屿完成','done→完成'];
|
||
$('pipeline').innerHTML = stages.map(st => { const [k,l]=st.split('→'); return `<span class="pipe-step ${s.stage===k?'active':''}">${l}</span>`; }).join('<i>→</i>');
|
||
}
|
||
|
||
function init() {
|
||
const sel = $('exampleSelect');
|
||
examples.forEach((e,i) => { sel.innerHTML += `<option value="${i}">${e.label}</option>`; });
|
||
$('inputArea').value = '[["1","1","0"],["0","1","0"],["0","0","1"]]';
|
||
buildSteps(examples[0].grid);
|
||
stepCtrl = new StepController({onStep: render});
|
||
stepCtrl.setSteps(steps.map((_,i)=>i));
|
||
$('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
stepCtrl.onStep = (idx) => { render(idx); $('stepInfo').textContent = `步骤 ${idx+1} / ${steps.length}`; };
|
||
$('applyBtn').onclick = () => {
|
||
try { const g = JSON.parse($('inputArea').value); buildSteps(g); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0); $('stepInfo').textContent = '步骤 1 / ' + steps.length; }
|
||
catch(e) { alert('请输入合法 JSON 二维数组'); }
|
||
};
|
||
$('exampleSelect').onchange = () => {
|
||
const e = examples[parseInt($('exampleSelect').value)];
|
||
buildSteps(e.grid); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0);
|
||
};
|
||
$('prevBtn').onclick = () => stepCtrl.prev();
|
||
$('nextBtn').onclick = () => stepCtrl.next();
|
||
$('jumpBtn').onclick = () => stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick = () => { const on = stepCtrl.toggleAuto(); $('autoBtn').textContent = on ? '暂停' : '自动播放'; };
|
||
$('resetBtn').onclick = () => { stepCtrl.reset(); $('autoBtn').textContent = '自动播放'; };
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`def numIslands(grid):
|
||
if not grid: return 0
|
||
rows, cols = len(grid), len(grid[0])
|
||
def dfs(r, c):
|
||
if r<0 or r>=rows or c<0 or c>=cols or grid[r][c]!='1':
|
||
return
|
||
grid[r][c] = '2'
|
||
dfs(r+1,c); dfs(r-1,c)
|
||
dfs(r,c+1); dfs(r,c-1)
|
||
islands = 0
|
||
for r in range(rows):
|
||
for c in range(cols):
|
||
if grid[r][c] == '1':
|
||
islands += 1
|
||
dfs(r, c)
|
||
return islands`, {lang:'Python'});
|
||
'''
|
||
|
||
def js_rotting_oranges():
|
||
return r'''
|
||
const examples = [
|
||
{grid: [[2,1,1],[1,1,0],[0,1,1]], label: '示例1: 3×3'},
|
||
{grid: [[2,1,1],[0,1,1],[1,0,1]], label: '示例2: 有不可达'},
|
||
{grid: [[0,2]], label: '示例3: 无橘子'},
|
||
];
|
||
let grid, R, C, steps, stepCtrl;
|
||
|
||
function buildSteps(g) {
|
||
grid = g.map(r=>[...r]); R = grid.length; C = grid[0].length;
|
||
steps = [];
|
||
const queue = [];
|
||
let fresh = 0;
|
||
for (let r=0; r<R; r++) for (let c=0; c<C; c++) {
|
||
if (grid[r][c]===2) queue.push([r,c]);
|
||
else if (grid[r][c]===1) fresh++;
|
||
}
|
||
steps.push({stage:'init', msg:`BFS多源最短路径：${queue.length}个腐烂源，${fresh}个新鲜橘子`, grid:grid.map(r=>[...r]), minutes:0, fresh});
|
||
if (fresh === 0) { steps.push({stage:'done', msg:'没有新鲜橘子，返回0', grid:grid.map(r=>[...r]), minutes:0, fresh:0}); return; }
|
||
let minutes = 0;
|
||
const dirs = [[0,1],[0,-1],[1,0],[-1,0]];
|
||
while (queue.length > 0 && fresh > 0) {
|
||
const size = queue.length;
|
||
const newlyRotten = [];
|
||
for (let i=0; i<size; i++) {
|
||
const [r,c] = queue.shift();
|
||
for (const [dr,dc] of dirs) {
|
||
const nr=r+dr, nc=c+dc;
|
||
if (nr>=0 && nr<R && nc>=0 && nc<C && grid[nr][nc]===1) {
|
||
grid[nr][nc] = 2;
|
||
fresh--;
|
||
queue.push([nr,nc]);
|
||
newlyRotten.push([nr,nc]);
|
||
}
|
||
}
|
||
}
|
||
if (newlyRotten.length > 0) {
|
||
minutes++;
|
||
steps.push({stage:'rot', msg:`第 ${minutes} 分钟：${newlyRotten.length}个橘子腐烂 (剩余${fresh}个新鲜)`, grid:grid.map(r=>[...r]), minutes, fresh, newlyRotten});
|
||
}
|
||
}
|
||
if (fresh > 0) steps.push({stage:'impossible', msg:`仍有${fresh}个新鲜橘子无法腐烂`, grid:grid.map(r=>[...r]), minutes, fresh});
|
||
else steps.push({stage:'done', msg:`所有橘子腐烂，用时 ${minutes} 分钟`, grid:grid.map(r=>[...r]), minutes, fresh:0});
|
||
}
|
||
|
||
function render(step) {
|
||
const s = steps[step];
|
||
const hl = {};
|
||
if (s.newlyRotten) s.newlyRotten.forEach(([r,c]) => { hl[r+','+c] = 'current'; });
|
||
const cellStyle = (val,r,c) => {
|
||
const key = r+','+c;
|
||
if (hl[key]) return 'background:#fbbf24;color:#78350f;box-shadow:0 0 0 3px rgba(245,158,11,0.4);';
|
||
if (val===2) return 'background:#fed7aa;color:#9a3412;';
|
||
if (val===1) return 'background:#dcfce7;color:#166534;';
|
||
return 'background:#f1f5f9;color:#94a3b8;';
|
||
};
|
||
let viz = renderGrid(s.grid, {highlights:hl, cellSize:52, cellStyle});
|
||
viz += '<div style="margin-top:8px;display:flex;gap:16px;">';
|
||
viz += '<span style="color:#9a3412;">🟠 腐烂</span>';
|
||
viz += '<span style="color:#166534;">🟢 新鲜</span>';
|
||
viz += '<span style="color:#94a3b8;">⬜ 空</span>';
|
||
viz += `<span style="color:var(--blue);">⏱ 分钟=${s.minutes}</span>`;
|
||
viz += '</div>';
|
||
$('vizArea').innerHTML = viz;
|
||
$('detailContent').innerHTML = '<div class="calc-block">' + s.msg + '</div>';
|
||
if (s.stage==='done') $('resultContent').innerHTML = `<div class="final-answer">经过 <b>${s.minutes}</b> 分钟，所有橘子腐烂</div>`;
|
||
if (s.stage==='impossible') $('resultContent').innerHTML = `<div class="final-answer" style="border-color:#f87171;background:#fef2f2;">返回 <b>-1</b>（有新鲜橘子无法腐烂）</div>`;
|
||
$('hintText').textContent = s.msg;
|
||
const stages = ['init→初始化','rot→腐烂传播','done→完成','impossible→不可能'];
|
||
$('pipeline').innerHTML = stages.map(st => { const [k,l]=st.split('→'); return `<span class="pipe-step ${s.stage===k?'active':''}">${l}</span>`; }).join('<i>→</i>');
|
||
}
|
||
|
||
function init() {
|
||
const sel = $('exampleSelect');
|
||
examples.forEach((e,i) => { sel.innerHTML += `<option value="${i}">${e.label}</option>`; });
|
||
$('inputArea').value = '[[2,1,1],[1,1,0],[0,1,1]]';
|
||
buildSteps(examples[0].grid);
|
||
stepCtrl = new StepController({onStep: render, autoInterval:800});
|
||
stepCtrl.setSteps(steps.map((_,i)=>i));
|
||
$('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
stepCtrl.onStep = (idx) => { render(idx); $('stepInfo').textContent = `步骤 ${idx+1} / ${steps.length}`; };
|
||
$('applyBtn').onclick = () => {
|
||
try { const g = JSON.parse($('inputArea').value); buildSteps(g); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0); $('stepInfo').textContent = '步骤 1 / ' + steps.length; }
|
||
catch(e) { alert('请输入合法 JSON 二维数组'); }
|
||
};
|
||
$('exampleSelect').onchange = () => {
|
||
const e = examples[parseInt($('exampleSelect').value)];
|
||
buildSteps(e.grid); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0);
|
||
};
|
||
$('prevBtn').onclick = () => stepCtrl.prev();
|
||
$('nextBtn').onclick = () => stepCtrl.next();
|
||
$('jumpBtn').onclick = () => stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick = () => { const on = stepCtrl.toggleAuto(); $('autoBtn').textContent = on ? '暂停' : '自动播放'; };
|
||
$('resetBtn').onclick = () => { stepCtrl.reset(); $('autoBtn').textContent = '自动播放'; };
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`def orangesRotting(grid):
|
||
rows, cols = len(grid), len(grid[0])
|
||
queue = deque()
|
||
fresh = 0
|
||
for r in range(rows):
|
||
for c in range(cols):
|
||
if grid[r][c] == 2:
|
||
queue.append((r, c))
|
||
elif grid[r][c] == 1:
|
||
fresh += 1
|
||
minutes = 0
|
||
while queue and fresh > 0:
|
||
for _ in range(len(queue)):
|
||
r, c = queue.popleft()
|
||
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
|
||
nr, nc = r+dr, c+dc
|
||
if 0<=nr<rows and 0<=nc<cols and grid[nr][nc]==1:
|
||
grid[nr][nc] = 2
|
||
fresh -= 1
|
||
queue.append((nr, nc))
|
||
minutes += 1
|
||
return minutes if fresh == 0 else -1`, {lang:'Python'});
|
||
'''
|
||
|
||
def js_course_schedule():
|
||
return r'''
|
||
const examples = [
|
||
{numCourses: 4, prerequisites: [[1,0],[2,0],[3,1],[3,2]], label: '示例1: 4门课, [1,0],[2,0],[3,1],[3,2]'},
|
||
{numCourses: 2, prerequisites: [[1,0],[0,1]], label: '示例2: 2门课, 有环'},
|
||
{numCourses: 3, prerequisites: [[1,0],[2,1]], label: '示例3: 3门课, 无环'},
|
||
];
|
||
let N, edges, steps, stepCtrl, adj, stateMap;
|
||
|
||
function buildSteps(n, prereq) {
|
||
N = n; edges = prereq; steps = [];
|
||
adj = Array.from({length:n}, ()=>[]);
|
||
for (const [a,b] of prereq) adj[a].push(b);
|
||
stateMap = new Array(n).fill(0); // 0=未访问, 1=进行中, 2=完成
|
||
|
||
steps.push({stage:'init', msg:`DFS环检测: ${n}门课程, ${prereq.length}条依赖`, node:-1, state:[...stateMap], topo:[], hasCycle:false});
|
||
let hasCycle = false;
|
||
const topoOrder = [];
|
||
|
||
function dfs(node) {
|
||
stateMap[node] = 1;
|
||
steps.push({stage:'visiting', msg:`访问课程 ${node}，标记为"进行中"`, node, state:[...stateMap], topo:[...topoOrder], hasCycle:false});
|
||
for (const nb of adj[node]) {
|
||
if (stateMap[nb] === 1) {
|
||
hasCycle = true;
|
||
steps.push({stage:'cycle', msg:`课程 ${nb} 正在访问中！检测到环 ${node}→${nb}`, node:nb, state:[...stateMap], topo:[...topoOrder], hasCycle:true});
|
||
return true;
|
||
}
|
||
if (stateMap[nb] === 0) {
|
||
if (dfs(nb)) return true;
|
||
}
|
||
}
|
||
stateMap[node] = 2;
|
||
topoOrder.push(node);
|
||
steps.push({stage:'done', msg:`课程 ${node} 完成，加入拓扑序列`, node, state:[...stateMap], topo:[...topoOrder], hasCycle:false});
|
||
return false;
|
||
}
|
||
|
||
for (let i=0; i<n; i++) {
|
||
if (stateMap[i] === 0) {
|
||
if (dfs(i)) break;
|
||
}
|
||
}
|
||
if (hasCycle) steps.push({stage:'result', msg:'检测到环，无法完成所有课程', node:-1, state:[...stateMap], topo:[...topoOrder], hasCycle:true});
|
||
else steps.push({stage:'result', msg:'无环，可以完成所有课程！拓扑序: [' + topoOrder.reverse().join(', ') + ']', node:-1, state:[...stateMap], topo:[...topoOrder], hasCycle:false});
|
||
}
|
||
|
||
function render(step) {
|
||
const s = steps[step];
|
||
const stateColors = {0:'#e2e8f0', 1:'#fef3c7', 2:'#dcfce7'};
|
||
const stateText = {0:'未访问', 1:'进行中', 2:'已完成'};
|
||
const stateBorder = {0:'#94a3b8', 1:'#f59e0b', 2:'#16a34a'};
|
||
|
||
let viz = '<div style="display:flex;gap:16px;flex-wrap:wrap;margin-bottom:12px;">';
|
||
for (let i=0; i<N; i++) {
|
||
const bg = stateColors[s.state[i]];
|
||
const border = stateBorder[s.state[i]];
|
||
const isCurr = i===s.node;
|
||
viz += `<div style="width:60px;height:60px;border-radius:50%;display:flex;flex-direction:column;align-items:center;justify-content:center;background:${bg};border:3px solid ${border};font-weight:700;transition:all 0.3s;${isCurr?'transform:scale(1.15);box-shadow:0 0 0 4px rgba(59,130,246,0.3);':''}">${i}<span style="font-size:10px;font-weight:400;">${stateText[s.state[i]]}</span></div>`;
|
||
}
|
||
viz += '</div>';
|
||
viz += '<div style="margin-top:8px;"><b>依赖关系：</b></div>';
|
||
for (const [a,b] of edges) viz += `<span style="margin-right:12px;"><code>${a}←${b}</code></span>`;
|
||
if (s.topo.length > 0) viz += `<div style="margin-top:8px;"><b>拓扑序：</b>${s.topo.join(' → ')}</div>`;
|
||
$('vizArea').innerHTML = viz;
|
||
$('detailContent').innerHTML = '<div class="calc-block">' + s.msg + '</div>';
|
||
if (s.stage==='result') {
|
||
if (s.hasCycle) $('resultContent').innerHTML = '<div class="final-answer" style="border-color:#f87171;background:#fef2f2;">返回 <b>False</b>（检测到环，无法完成）</div>';
|
||
else $('resultContent').innerHTML = `<div class="final-answer">返回 <b>True</b>（可以完成所有课程）<br>拓扑序: ${s.topo.join(' → ')}</div>`;
|
||
}
|
||
$('hintText').textContent = s.msg;
|
||
const stages = ['init→初始化','visiting→访问中','done→完成','cycle→检测到环','result→结果'];
|
||
$('pipeline').innerHTML = stages.map(st => { const [k,l]=st.split('→'); return `<span class="pipe-step ${s.stage===k?'active':''}">${l}</span>`; }).join('<i>→</i>');
|
||
}
|
||
|
||
function init() {
|
||
const sel = $('exampleSelect');
|
||
examples.forEach((e,i) => { sel.innerHTML += `<option value="${i}">${e.label}</option>`; });
|
||
$('inputArea').value = '4, [[1,0],[2,0],[3,1],[3,2]]';
|
||
buildSteps(examples[0].numCourses, examples[0].prerequisites);
|
||
stepCtrl = new StepController({onStep: render});
|
||
stepCtrl.setSteps(steps.map((_,i)=>i));
|
||
$('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
stepCtrl.onStep = (idx) => { render(idx); $('stepInfo').textContent = `步骤 ${idx+1} / ${steps.length}`; };
|
||
$('applyBtn').onclick = () => {
|
||
try {
|
||
const m = $('inputArea').value.match(/(\d+),\s*(\[[\s\S]*\])/);
|
||
if (!m) { alert('格式: numCourses, [[1,0],[2,0]]'); return; }
|
||
buildSteps(parseInt(m[1]), JSON.parse(m[2]));
|
||
stepCtrl.setSteps(steps.map((_,i)=>i)); render(0); $('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
} catch(e) { alert('输入格式错误'); }
|
||
};
|
||
$('exampleSelect').onchange = () => {
|
||
const e = examples[parseInt($('exampleSelect').value)];
|
||
buildSteps(e.numCourses, e.prerequisites); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0);
|
||
};
|
||
$('prevBtn').onclick = () => stepCtrl.prev();
|
||
$('nextBtn').onclick = () => stepCtrl.next();
|
||
$('jumpBtn').onclick = () => stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick = () => { const on = stepCtrl.toggleAuto(); $('autoBtn').textContent = on ? '暂停' : '自动播放'; };
|
||
$('resetBtn').onclick = () => { stepCtrl.reset(); $('autoBtn').textContent = '自动播放'; };
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`def canFinish(numCourses, prerequisites):
|
||
adj = [[] for _ in range(numCourses)]
|
||
for a, b in prerequisites:
|
||
adj[a].append(b)
|
||
state = [0] * numCourses # 0=未访问 1=进行中 2=完成
|
||
def dfs(node):
|
||
state[node] = 1
|
||
for nb in adj[node]:
|
||
if state[nb] == 1:
|
||
return True # 环
|
||
if state[nb] == 0 and dfs(nb):
|
||
return True
|
||
state[node] = 2
|
||
return False
|
||
for i in range(numCourses):
|
||
if state[i] == 0 and dfs(i):
|
||
return False
|
||
return True`, {lang:'Python'});
|
||
'''
|
||
|
||
def js_implement_trie_prefix_tree():
|
||
return r'''
|
||
const examples = [
|
||
{ops: ['insert("apple")','search("apple")','search("app")','startsWith("app")','insert("app")','search("app")'], label: '示例1: apple/app'},
|
||
{ops: ['insert("dog")','insert("deer")','search("dog")','startsWith("de")'], label: '示例2: dog/deer'},
|
||
];
|
||
let steps, stepCtrl, trieNodes;
|
||
|
||
function buildSteps(ops) {
|
||
steps = [];
|
||
trieNodes = [{id:0, char:'ROOT', children:{}, isEnd:false, depth:0}];
|
||
steps.push({stage:'init', msg:'初始化Trie根节点', path:[], currentNode:-1, nodes:JSON.parse(JSON.stringify(trieNodes)), op:'init'});
|
||
|
||
for (const op of ops) {
|
||
const insertM = op.match(/insert\("(\w+)"\)/);
|
||
const searchM = op.match(/search\("(\w+)"\)/);
|
||
const startsM = op.match(/startsWith\("(\w+)"\)/);
|
||
|
||
if (insertM) {
|
||
const word = insertM[1];
|
||
steps.push({stage:'op_start', msg:`操作: insert("${word}")`, path:[], currentNode:0, nodes:JSON.parse(JSON.stringify(trieNodes)), op:'insert("'+word+'")'});
|
||
let cur = 0;
|
||
const path = [0];
|
||
for (let i=0; i<word.length; i++) {
|
||
const ch = word[i];
|
||
if (!trieNodes[cur].children[ch]) {
|
||
const newId = trieNodes.length;
|
||
trieNodes.push({id:newId, char:ch, children:{}, isEnd:false, depth:i+1});
|
||
trieNodes[cur].children[ch] = newId;
|
||
steps.push({stage:'create', msg:`创建新节点 '${ch}'（不存在）`, path:[...path], currentNode:newId, nodes:JSON.parse(JSON.stringify(trieNodes)), op:'insert("'+word+'")'});
|
||
} else {
|
||
steps.push({stage:'traverse', msg:`节点 '${ch}' 已存在，沿路径前进`, path:[...path], currentNode:trieNodes[cur].children[ch], nodes:JSON.parse(JSON.stringify(trieNodes)), op:'insert("'+word+'")'});
|
||
}
|
||
cur = trieNodes[cur].children[ch];
|
||
path.push(cur);
|
||
}
|
||
trieNodes[cur].isEnd = true;
|
||
steps.push({stage:'mark_end', msg:`标记节点为单词结尾 (${word})`, path:[...path], currentNode:cur, nodes:JSON.parse(JSON.stringify(trieNodes)), op:'insert("'+word+'")'});
|
||
} else if (searchM) {
|
||
const word = searchM[1];
|
||
steps.push({stage:'op_start', msg:`操作: search("${word}")`, path:[], currentNode:0, nodes:JSON.parse(JSON.stringify(trieNodes)), op:'search("'+word+'")'});
|
||
let cur = 0; let found = true;
|
||
const path = [0];
|
||
for (let i=0; i<word.length; i++) {
|
||
const ch = word[i];
|
||
if (!trieNodes[cur].children[ch]) {
|
||
found = false;
|
||
steps.push({stage:'not_found', msg:`节点 '${ch}' 不存在，搜索失败`, path:[...path], currentNode:-1, nodes:JSON.parse(JSON.stringify(trieNodes)), op:'search("'+word+'")'});
|
||
break;
|
||
}
|
||
cur = trieNodes[cur].children[ch];
|
||
path.push(cur);
|
||
steps.push({stage:'traverse', msg:`沿 '${ch}' 前进`, path:[...path], currentNode:cur, nodes:JSON.parse(JSON.stringify(trieNodes)), op:'search("'+word+'")'});
|
||
}
|
||
if (found) {
|
||
if (trieNodes[cur].isEnd) steps.push({stage:'found', msg:`"${word}" 存在且为完整单词 ✓`, path:[...path], currentNode:cur, nodes:JSON.parse(JSON.stringify(trieNodes)), op:'search("'+word+'")'});
|
||
else steps.push({stage:'prefix_only', msg:`"${word}" 只是前缀，不是完整单词`, path:[...path], currentNode:cur, nodes:JSON.parse(JSON.stringify(trieNodes)), op:'search("'+word+'")'});
|
||
}
|
||
} else if (startsM) {
|
||
const prefix = startsM[1];
|
||
steps.push({stage:'op_start', msg:`操作: startsWith("${prefix}")`, path:[], currentNode:0, nodes:JSON.parse(JSON.stringify(trieNodes)), op:'startsWith("'+prefix+'")'});
|
||
let cur = 0; let found = true;
|
||
const path = [0];
|
||
for (let i=0; i<prefix.length; i++) {
|
||
const ch = prefix[i];
|
||
if (!trieNodes[cur].children[ch]) {
|
||
found = false;
|
||
steps.push({stage:'not_found', msg:`节点 '${ch}' 不存在，前缀不存在`, path:[...path], currentNode:-1, nodes:JSON.parse(JSON.stringify(trieNodes)), op:'startsWith("'+prefix+'")'});
|
||
break;
|
||
}
|
||
cur = trieNodes[cur].children[ch];
|
||
path.push(cur);
|
||
steps.push({stage:'traverse', msg:`沿 '${ch}' 前进`, path:[...path], currentNode:cur, nodes:JSON.parse(JSON.stringify(trieNodes)), op:'startsWith("'+prefix+'")'});
|
||
}
|
||
if (found) steps.push({stage:'found', msg:`前缀 "${prefix}" 存在 ✓`, path:[...path], currentNode:cur, nodes:JSON.parse(JSON.stringify(trieNodes)), op:'startsWith("'+prefix+'")'});
|
||
}
|
||
}
|
||
steps.push({stage:'done', msg:'所有操作完成', path:[], currentNode:-1, nodes:JSON.parse(JSON.stringify(trieNodes)), op:'done'});
|
||
}
|
||
|
||
function renderTrie(nodes, path, current) {
|
||
const pathSet = new Set(path);
|
||
// Build adjacency from nodes
|
||
function buildTree(nodeId) {
|
||
const node = nodes[nodeId];
|
||
const childKeys = Object.keys(node.children);
|
||
if (childKeys.length === 0) return `<div class="tree-node"><div class="node-circle ${pathSet.has(nodeId)?(nodeId===current?'current':'visited'):''}${node.isEnd?' selected':''}">${node.char==='ROOT'?'⊘':node.char}</div>${node.isEnd?'<span style="font-size:9px;color:var(--green);">●</span>':''}</div>`;
|
||
const children = childKeys.map(k => buildTree(node.children[k]));
|
||
return `<div class="tree-node"><div class="node-circle ${pathSet.has(nodeId)?(nodeId===current?'current':'visited'):''}${node.isEnd?' selected':''}">${node.char==='ROOT'?'⊘':node.char}</div>${node.isEnd?'<span style="font-size:9px;color:var(--green);">●</span>':''}<div class="tree-children">${children.join('')}</div></div>`;
|
||
}
|
||
return '<div class="tree-container">' + buildTree(0) + '</div>';
|
||
}
|
||
|
||
function render(step) {
|
||
const s = steps[step];
|
||
let viz = renderTrie(s.nodes, s.path, s.currentNode);
|
||
viz += `<div style="margin-top:8px;"><b>当前操作：</b><code>${s.op}</code></div>`;
|
||
viz += '<div style="margin-top:4px;display:flex;gap:12px;font-size:13px;"><span style="color:var(--green);">● 单词结尾</span><span style="color:#fef3c7;border:2px solid #f59e0b;border-radius:50%;width:14px;height:14px;display:inline-block;"></span> 当前路径</div>';
|
||
$('vizArea').innerHTML = viz;
|
||
$('detailContent').innerHTML = '<div class="calc-block">' + s.msg + '</div>';
|
||
if (s.stage==='done') {
|
||
$('resultContent').innerHTML = '<div class="final-answer">所有操作完成 ✓</div>';
|
||
}
|
||
$('hintText').textContent = s.msg;
|
||
const stages = ['init→初始化','op_start→开始操作','create→创建节点','traverse→遍历','mark_end→标记结尾','found→找到','not_found→未找到','prefix_only→仅前缀','done→完成'];
|
||
$('pipeline').innerHTML = stages.map(st => { const [k,l]=st.split('→'); return `<span class="pipe-step ${s.stage===k?'active':''}">${l}</span>`; }).join('<i>→</i>');
|
||
}
|
||
|
||
function init() {
|
||
const sel = $('exampleSelect');
|
||
examples.forEach((e,i) => { sel.innerHTML += `<option value="${i}">${e.label}</option>`; });
|
||
buildSteps(examples[0].ops);
|
||
stepCtrl = new StepController({onStep: render, autoInterval:700});
|
||
stepCtrl.setSteps(steps.map((_,i)=>i));
|
||
$('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
stepCtrl.onStep = (idx) => { render(idx); $('stepInfo').textContent = `步骤 ${idx+1} / ${steps.length}`; };
|
||
$('applyBtn').onclick = () => {
|
||
try {
|
||
const ops = JSON.parse($('inputArea').value);
|
||
buildSteps(ops); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0); $('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
} catch(e) { alert('请输入操作数组，如 ["insert(\\"apple\\")","search(\\"app\\")"]'); }
|
||
};
|
||
$('exampleSelect').onchange = () => {
|
||
const e = examples[parseInt($('exampleSelect').value)];
|
||
buildSteps(e.ops); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0);
|
||
};
|
||
$('prevBtn').onclick = () => stepCtrl.prev();
|
||
$('nextBtn').onclick = () => stepCtrl.next();
|
||
$('jumpBtn').onclick = () => stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick = () => { const on = stepCtrl.toggleAuto(); $('autoBtn').textContent = on ? '暂停' : '自动播放'; };
|
||
$('resetBtn').onclick = () => { stepCtrl.reset(); $('autoBtn').textContent = '自动播放'; };
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`class TrieNode:
|
||
def __init__(self):
|
||
self.children = {}
|
||
self.is_end = False
|
||
|
||
class Trie:
|
||
def __init__(self):
|
||
self.root = TrieNode()
|
||
|
||
def insert(self, word):
|
||
node = self.root
|
||
for ch in word:
|
||
if ch not in node.children:
|
||
node.children[ch] = TrieNode()
|
||
node = node.children[ch]
|
||
node.is_end = True
|
||
|
||
def search(self, word):
|
||
node = self._find(word)
|
||
return node is not None and node.is_end
|
||
|
||
def startsWith(self, prefix):
|
||
return self._find(prefix) is not None
|
||
|
||
def _find(self, prefix):
|
||
node = self.root
|
||
for ch in prefix:
|
||
if ch not in node.children:
|
||
return None
|
||
node = node.children[ch]
|
||
return node`, {lang:'Python'});
|
||
'''
|
||
|
||
|
||
# ==================== 回溯 8 题 ====================
|
||
|
||
def js_permutations():
|
||
return r'''
|
||
const examples = [
|
||
{input: [1,2,3], label: '示例1: [1,2,3]'},
|
||
{input: [0,1], label: '示例2: [0,1]'},
|
||
{input: [1], label: '示例3: [1]'},
|
||
];
|
||
let nums, steps, stepCtrl;
|
||
|
||
function buildSteps(arr) {
|
||
nums = [...arr]; steps = [];
|
||
const result = [];
|
||
const path = [];
|
||
|
||
function backtrack(first) {
|
||
if (first === nums.length) {
|
||
result.push([...nums]);
|
||
steps.push({stage:'collect', msg:`排列完成: [${nums}]`, arr:[...nums], first, swapping:null, result:JSON.parse(JSON.stringify(result))});
|
||
return;
|
||
}
|
||
for (let i = first; i < nums.length; i++) {
|
||
steps.push({stage:'try', msg:`first=${first}，尝试交换位置 ${first}↔${i}`, arr:[...nums], first, swapping:[first,i], result:JSON.parse(JSON.stringify(result))});
|
||
[nums[first], nums[i]] = [nums[i], nums[first]];
|
||
steps.push({stage:'swap', msg:`交换 nums[${first}]↔nums[${i}] → [${nums}]`, arr:[...nums], first, swapping:null, result:JSON.parse(JSON.stringify(result))});
|
||
backtrack(first + 1);
|
||
[nums[first], nums[i]] = [nums[i], nums[first]];
|
||
steps.push({stage:'undo', msg:`回溯：恢复交换 → [${nums}]`, arr:[...nums], first, swapping:null, result:JSON.parse(JSON.stringify(result))});
|
||
}
|
||
}
|
||
steps.push({stage:'start', msg:'回溯交换法生成全排列', arr:[...nums], first:0, swapping:null, result:[]});
|
||
backtrack(0);
|
||
steps.push({stage:'done', msg:`共 ${result.length} 个排列`, arr:[...nums], first:-1, swapping:null, result:JSON.parse(JSON.stringify(result))});
|
||
}
|
||
|
||
function render(step) {
|
||
const s = steps[step];
|
||
const hl = {};
|
||
if (s.swapping) { hl[s.swapping[0]] = 'orange'; hl[s.swapping[1]] = 'orange'; }
|
||
else if (s.first >= 0) { hl[s.first] = 'purple'; }
|
||
if (s.stage==='collect') for (let i=0;i<s.arr.length;i++) hl[i]='green';
|
||
let viz = renderArray(s.arr, {highlights:hl});
|
||
viz += `<div style="margin-top:8px;">first = ${s.first >= 0 ? s.first : '完成'}</div>`;
|
||
if (s.result.length > 0) {
|
||
viz += '<div style="margin-top:8px;"><b>已找到：</b></div><div style="display:flex;flex-wrap:wrap;gap:6px;">';
|
||
s.result.forEach(r => { viz += `<span class="chip green" style="min-width:auto;padding:2px 8px;font-size:12px;">[${r}]</span>`; });
|
||
viz += '</div>';
|
||
}
|
||
$('vizArea').innerHTML = viz;
|
||
$('detailContent').innerHTML = '<div class="calc-block">' + s.msg + '</div>';
|
||
if (s.stage==='done') $('resultContent').innerHTML = `<div class="final-answer">共 <b>${s.result.length}</b> 个排列<br>${s.result.map(r=>'['+r+']').join(', ')}</div>`;
|
||
$('hintText').textContent = s.msg;
|
||
const stages = ['start→开始','try→尝试','swap→交换','collect→收集','undo→回溯','done→完成'];
|
||
$('pipeline').innerHTML = stages.map(st => { const [k,l]=st.split('→'); return `<span class="pipe-step ${s.stage===k?'active':''}">${l}</span>`; }).join('<i>→</i>');
|
||
}
|
||
|
||
function init() {
|
||
const sel = $('exampleSelect');
|
||
examples.forEach((e,i) => { sel.innerHTML += `<option value="${i}">${e.label}</option>`; });
|
||
$('inputArea').value = '[1,2,3]';
|
||
buildSteps(examples[0].input);
|
||
stepCtrl = new StepController({onStep: render});
|
||
stepCtrl.setSteps(steps.map((_,i)=>i));
|
||
$('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
stepCtrl.onStep = (idx) => { render(idx); $('stepInfo').textContent = `步骤 ${idx+1} / ${steps.length}`; };
|
||
$('applyBtn').onclick = () => {
|
||
try { const arr = JSON.parse($('inputArea').value); buildSteps(arr); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0); $('stepInfo').textContent = '步骤 1 / ' + steps.length; }
|
||
catch(e) { alert('请输入合法 JSON 数组'); }
|
||
};
|
||
$('exampleSelect').onchange = () => {
|
||
const e = examples[parseInt($('exampleSelect').value)];
|
||
buildSteps(e.input); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0);
|
||
};
|
||
$('prevBtn').onclick = () => stepCtrl.prev();
|
||
$('nextBtn').onclick = () => stepCtrl.next();
|
||
$('jumpBtn').onclick = () => stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick = () => { const on = stepCtrl.toggleAuto(); $('autoBtn').textContent = on ? '暂停' : '自动播放'; };
|
||
$('resetBtn').onclick = () => { stepCtrl.reset(); $('autoBtn').textContent = '自动播放'; };
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`def permute(nums):
|
||
res = []
|
||
def backtrack(first):
|
||
if first == len(nums):
|
||
res.append(nums[:])
|
||
return
|
||
for i in range(first, len(nums)):
|
||
nums[first], nums[i] = nums[i], nums[first]
|
||
backtrack(first + 1)
|
||
nums[first], nums[i] = nums[i], nums[first]
|
||
backtrack(0)
|
||
return res`, {lang:'Python'});
|
||
'''
|
||
|
||
def js_subsets():
|
||
return r'''
|
||
const examples = [
|
||
{input: [1,2,3], label: '示例1: [1,2,3]'},
|
||
{input: [0], label: '示例2: [0]'},
|
||
];
|
||
let nums, steps, stepCtrl;
|
||
|
||
function buildSteps(arr) {
|
||
nums = [...arr]; steps = [];
|
||
const result = [];
|
||
const path = [];
|
||
|
||
function backtrack(idx) {
|
||
if (idx === nums.length) {
|
||
result.push([...path]);
|
||
steps.push({stage:'collect', msg:`收集子集: [${path}]`, path:[...path], idx, choosing:-1, result:JSON.parse(JSON.stringify(result))});
|
||
return;
|
||
}
|
||
// 不选 nums[idx]
|
||
steps.push({stage:'skip', msg:`位置${idx}: 不选 ${nums[idx]}`, path:[...path], idx, choosing:idx, result:JSON.parse(JSON.stringify(result))});
|
||
backtrack(idx + 1);
|
||
// 选 nums[idx]
|
||
path.push(nums[idx]);
|
||
steps.push({stage:'choose', msg:`位置${idx}: 选择 ${nums[idx]}`, path:[...path], idx, choosing:idx, result:JSON.parse(JSON.stringify(result))});
|
||
backtrack(idx + 1);
|
||
path.pop();
|
||
steps.push({stage:'undo', msg:`回溯：移除 ${nums[idx]}`, path:[...path], idx, choosing:-1, result:JSON.parse(JSON.stringify(result))});
|
||
}
|
||
steps.push({stage:'start', msg:'回溯法：对每个元素选/不选', path:[], idx:0, choosing:-1, result:[]});
|
||
backtrack(0);
|
||
steps.push({stage:'done', msg:`共 ${result.length} 个子集`, path:[], idx:-1, choosing:-1, result:JSON.parse(JSON.stringify(result))});
|
||
}
|
||
|
||
function render(step) {
|
||
const s = steps[step];
|
||
let viz = '<div style="margin-bottom:8px;"><b>原始数组：</b></div>';
|
||
const hl = {};
|
||
if (s.choosing >= 0) hl[s.choosing] = 'orange';
|
||
for (let i=s.idx; i<nums.length; i++) if(i>=s.idx) hl[i] = hl[i] || 'default';
|
||
viz += renderArray(nums, {highlights:hl});
|
||
viz += `<div style="margin-top:10px;"><b>当前路径：</b><span class="chip purple" style="min-width:auto;padding:2px 10px;">[${s.path.join(', ')}]</span></div>`;
|
||
if (s.result.length > 0) {
|
||
viz += '<div style="margin-top:8px;"><b>已找到：</b></div><div style="display:flex;flex-wrap:wrap;gap:4px;">';
|
||
s.result.forEach(r => { viz += `<span class="chip green" style="min-width:auto;padding:2px 8px;font-size:11px;">[${r.length?r.join(','):''}]</span>`; });
|
||
viz += '</div>';
|
||
}
|
||
$('vizArea').innerHTML = viz;
|
||
$('detailContent').innerHTML = '<div class="calc-block">' + s.msg + '</div>';
|
||
if (s.stage==='done') $('resultContent').innerHTML = `<div class="final-answer">共 <b>${s.result.length}</b> 个子集</div>`;
|
||
$('hintText').textContent = s.msg;
|
||
const stages = ['start→开始','skip→不选','choose→选择','collect→收集','undo→回溯','done→完成'];
|
||
$('pipeline').innerHTML = stages.map(st => { const [k,l]=st.split('→'); return `<span class="pipe-step ${s.stage===k?'active':''}">${l}</span>`; }).join('<i>→</i>');
|
||
}
|
||
|
||
function init() {
|
||
const sel = $('exampleSelect');
|
||
examples.forEach((e,i) => { sel.innerHTML += `<option value="${i}">${e.label}</option>`; });
|
||
$('inputArea').value = '[1,2,3]';
|
||
buildSteps(examples[0].input);
|
||
stepCtrl = new StepController({onStep: render});
|
||
stepCtrl.setSteps(steps.map((_,i)=>i));
|
||
$('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
stepCtrl.onStep = (idx) => { render(idx); $('stepInfo').textContent = `步骤 ${idx+1} / ${steps.length}`; };
|
||
$('applyBtn').onclick = () => {
|
||
try { const arr = JSON.parse($('inputArea').value); buildSteps(arr); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0); $('stepInfo').textContent = '步骤 1 / ' + steps.length; }
|
||
catch(e) { alert('请输入合法 JSON 数组'); }
|
||
};
|
||
$('exampleSelect').onchange = () => {
|
||
const e = examples[parseInt($('exampleSelect').value)];
|
||
buildSteps(e.input); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0);
|
||
};
|
||
$('prevBtn').onclick = () => stepCtrl.prev();
|
||
$('nextBtn').onclick = () => stepCtrl.next();
|
||
$('jumpBtn').onclick = () => stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick = () => { const on = stepCtrl.toggleAuto(); $('autoBtn').textContent = on ? '暂停' : '自动播放'; };
|
||
$('resetBtn').onclick = () => { stepCtrl.reset(); $('autoBtn').textContent = '自动播放'; };
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`def subsets(nums):
|
||
res = []
|
||
def backtrack(idx, path):
|
||
if idx == len(nums):
|
||
res.append(path[:])
|
||
return
|
||
backtrack(idx + 1, path) # 不选
|
||
path.append(nums[idx])
|
||
backtrack(idx + 1, path) # 选
|
||
path.pop()
|
||
backtrack(0, [])
|
||
return res`, {lang:'Python'});
|
||
'''
|
||
|
||
def js_letter_combinations_of_a_phone_number():
|
||
return r'''
|
||
const examples = [
|
||
{input: "23", label: '示例1: "23"'},
|
||
{input: "", label: '示例2: 空'},
|
||
{input: "2", label: '示例3: "2"'},
|
||
];
|
||
const digitMap = {'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'};
|
||
let digits, steps, stepCtrl;
|
||
|
||
function buildSteps(d) {
|
||
digits = d; steps = [];
|
||
const result = [];
|
||
const path = [];
|
||
|
||
if (d.length === 0) {
|
||
steps.push({stage:'done', msg:'输入为空，返回空列表', path:[], digitIdx:-1, result:[]});
|
||
return;
|
||
}
|
||
|
||
steps.push({stage:'start', msg:`输入: "${d}"，数字对应字母: ${d.split('').map(c=>c+'→'+digitMap[c]).join(' ')}`, path:[], digitIdx:0, result:[]});
|
||
|
||
function backtrack(idx) {
|
||
if (idx === digits.length) {
|
||
result.push(path.join(''));
|
||
steps.push({stage:'collect', msg:`组合完成: "${path.join('')}"`, path:[...path], digitIdx:idx, result:JSON.parse(JSON.stringify(result))});
|
||
return;
|
||
}
|
||
const letters = digitMap[digits[idx]];
|
||
for (const ch of letters) {
|
||
path.push(ch);
|
||
steps.push({stage:'choose', msg:`位置${idx}(数字${digits[idx]}): 选择字母 '${ch}'`, path:[...path], digitIdx:idx, result:JSON.parse(JSON.stringify(result))});
|
||
backtrack(idx + 1);
|
||
path.pop();
|
||
steps.push({stage:'undo', msg:`回溯：移除 '${ch}'，尝试下一个字母`, path:[...path], digitIdx:idx, result:JSON.parse(JSON.stringify(result))});
|
||
}
|
||
}
|
||
backtrack(0);
|
||
steps.push({stage:'done', msg:`共 ${result.length} 个组合`, path:[], digitIdx:-1, result:JSON.parse(JSON.stringify(result))});
|
||
}
|
||
|
||
function render(step) {
|
||
const s = steps[step];
|
||
let viz = '<div style="display:flex;gap:12px;margin-bottom:12px;">';
|
||
digits.split('').forEach((d,i) => {
|
||
const isCurr = i===s.digitIdx;
|
||
viz += `<div style="text-align:center;padding:8px 12px;border-radius:10px;border:2px solid ${isCurr?'var(--orange)':'var(--border)'};background:${isCurr?'#fff7ed':'white'};">
|
||
<div style="font-size:20px;font-weight:700;">${d}</div>
|
||
<div style="font-size:12px;color:var(--text-secondary);">${digitMap[d]}</div>
|
||
</div>`;
|
||
});
|
||
viz += '</div>';
|
||
viz += `<div style="margin-top:8px;"><b>当前路径：</b><span style="font-size:18px;font-weight:700;letter-spacing:2px;color:var(--purple);">${s.path.join('')}</span><span style="color:var(--text-muted);">_`.repeat(Math.max(0, digits.length - s.path.length)) + '</span></div>';
|
||
if (s.result.length > 0) {
|
||
viz += '<div style="margin-top:8px;"><b>已找到：</b></div><div style="display:flex;flex-wrap:wrap;gap:4px;">';
|
||
s.result.forEach(r => { viz += `<span class="chip green" style="min-width:auto;padding:2px 8px;font-size:12px;">${r}</span>`; });
|
||
viz += '</div>';
|
||
}
|
||
$('vizArea').innerHTML = viz;
|
||
$('detailContent').innerHTML = '<div class="calc-block">' + s.msg + '</div>';
|
||
if (s.stage==='done' && s.result.length > 0) $('resultContent').innerHTML = `<div class="final-answer">共 <b>${s.result.length}</b> 个组合<br>[${s.result.map(r=>'"'+r+'"').join(', ')}]</div>`;
|
||
if (s.stage==='done' && s.result.length===0) $('resultContent').innerHTML = '<div class="final-answer">返回 []</div>';
|
||
$('hintText').textContent = s.msg;
|
||
const stages = ['start→开始','choose→选择字母','collect→收集','undo→回溯','done→完成'];
|
||
$('pipeline').innerHTML = stages.map(st => { const [k,l]=st.split('→'); return `<span class="pipe-step ${s.stage===k?'active':''}">${l}</span>`; }).join('<i>→</i>');
|
||
}
|
||
|
||
function init() {
|
||
const sel = $('exampleSelect');
|
||
examples.forEach((e,i) => { sel.innerHTML += `<option value="${i}">${e.label}</option>`; });
|
||
$('inputArea').value = '"23"';
|
||
buildSteps(examples[0].input);
|
||
stepCtrl = new StepController({onStep: render});
|
||
stepCtrl.setSteps(steps.map((_,i)=>i));
|
||
$('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
stepCtrl.onStep = (idx) => { render(idx); $('stepInfo').textContent = `步骤 ${idx+1} / ${steps.length}`; };
|
||
$('applyBtn').onclick = () => {
|
||
const v = $('inputArea').value.replace(/"/g,'').trim();
|
||
buildSteps(v); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0); $('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
};
|
||
$('exampleSelect').onchange = () => {
|
||
const e = examples[parseInt($('exampleSelect').value)];
|
||
buildSteps(e.input); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0);
|
||
};
|
||
$('prevBtn').onclick = () => stepCtrl.prev();
|
||
$('nextBtn').onclick = () => stepCtrl.next();
|
||
$('jumpBtn').onclick = () => stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick = () => { const on = stepCtrl.toggleAuto(); $('autoBtn').textContent = on ? '暂停' : '自动播放'; };
|
||
$('resetBtn').onclick = () => { stepCtrl.reset(); $('autoBtn').textContent = '自动播放'; };
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`def letterCombinations(digits):
|
||
if not digits:
|
||
return []
|
||
mapping = {'2':'abc','3':'def','4':'ghi','5':'jkl',
|
||
'6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}
|
||
res = []
|
||
def backtrack(idx, path):
|
||
if idx == len(digits):
|
||
res.append(''.join(path))
|
||
return
|
||
for ch in mapping[digits[idx]]:
|
||
path.append(ch)
|
||
backtrack(idx + 1, path)
|
||
path.pop()
|
||
backtrack(0, [])
|
||
return res`, {lang:'Python'});
|
||
'''
|
||
|
||
def js_combination_sum():
|
||
return r'''
|
||
const examples = [
|
||
{candidates: [2,3,6,7], target: 7, label: '示例1: [2,3,6,7] target=7'},
|
||
{candidates: [2,3,5], target: 8, label: '示例2: [2,3,5] target=8'},
|
||
{candidates: [2], target: 1, label: '示例3: [2] target=1'},
|
||
];
|
||
let cands, target, steps, stepCtrl;
|
||
|
||
function buildSteps(arr, tgt) {
|
||
cands = [...arr].sort((a,b)=>a-b); target = tgt; steps = [];
|
||
const result = [];
|
||
const path = [];
|
||
|
||
steps.push({stage:'start', msg:`排序后: [${cands}], 目标: ${tgt}`, path:[], sum:0, remain:tgt, start:0, result:[]});
|
||
|
||
function backtrack(start, sum) {
|
||
if (sum === target) {
|
||
result.push([...path]);
|
||
steps.push({stage:'found', msg:`和=${target}，找到组合 [${path}]`, path:[...path], sum, remain:0, start, result:JSON.parse(JSON.stringify(result))});
|
||
return;
|
||
}
|
||
for (let i = start; i < cands.length; i++) {
|
||
if (sum + cands[i] > target) {
|
||
steps.push({stage:'prune', msg:`${sum}+${cands[i]}=${sum+cands[i]} > ${target}，剪枝 ✂️`, path:[...path], sum, remain:target-sum, start:i, result:JSON.parse(JSON.stringify(result))});
|
||
break; // sorted, so all following are larger
|
||
}
|
||
path.push(cands[i]);
|
||
steps.push({stage:'choose', msg:`选择 ${cands[i]}，sum=${sum}+${cands[i]}=${sum+cands[i]}，remain=${target-sum-cands[i]}`, path:[...path], sum:sum+cands[i], remain:target-sum-cands[i], start:i, result:JSON.parse(JSON.stringify(result))});
|
||
backtrack(i, sum + cands[i]);
|
||
path.pop();
|
||
steps.push({stage:'undo', msg:`回溯：移除 ${cands[i]}`, path:[...path], sum, remain:target-sum, start:i, result:JSON.parse(JSON.stringify(result))});
|
||
}
|
||
}
|
||
backtrack(0, 0);
|
||
steps.push({stage:'done', msg:`共 ${result.length} 个组合`, path:[], sum:0, remain:target, start:-1, result:JSON.parse(JSON.stringify(result))});
|
||
}
|
||
|
||
function render(step) {
|
||
const s = steps[step];
|
||
const hl = {};
|
||
if (s.start >= 0) for (let i=s.start; i<cands.length; i++) hl[i] = i===s.start?'orange':'default';
|
||
let viz = '<div style="margin-bottom:8px;"><b>候选数：</b></div>';
|
||
viz += renderArray(cands, {highlights:hl});
|
||
viz += `<div style="margin-top:10px;display:flex;gap:16px;">
|
||
<span><b>当前组合：</b><span class="chip purple" style="min-width:auto;padding:2px 10px;">[${s.path.join(', ')}]</span></span>
|
||
<span><b>sum：</b>${s.sum}</span>
|
||
<span><b>remain：</b><span style="color:${s.remain===0?'var(--green)':'var(--blue)'};">${s.remain}</span></span>
|
||
</div>`;
|
||
if (s.result.length > 0) {
|
||
viz += '<div style="margin-top:8px;"><b>已找到：</b></div><div style="display:flex;flex-wrap:wrap;gap:4px;">';
|
||
s.result.forEach(r => { viz += `<span class="chip green" style="min-width:auto;padding:2px 8px;font-size:12px;">[${r.join(',')}]</span>`; });
|
||
viz += '</div>';
|
||
}
|
||
$('vizArea').innerHTML = viz;
|
||
$('detailContent').innerHTML = '<div class="calc-block">' + s.msg + '</div>';
|
||
if (s.stage==='done') $('resultContent').innerHTML = `<div class="final-answer">共 <b>${s.result.length}</b> 个组合</div>`;
|
||
$('hintText').textContent = s.msg;
|
||
const stages = ['start→开始','choose→选择','found→找到','prune→剪枝','undo→回溯','done→完成'];
|
||
$('pipeline').innerHTML = stages.map(st => { const [k,l]=st.split('→'); return `<span class="pipe-step ${s.stage===k?'active':''}">${l}</span>`; }).join('<i>→</i>');
|
||
}
|
||
|
||
function init() {
|
||
const sel = $('exampleSelect');
|
||
examples.forEach((e,i) => { sel.innerHTML += `<option value="${i}">${e.label}</option>`; });
|
||
$('inputArea').value = '[2,3,6,7], target=7';
|
||
buildSteps(examples[0].candidates, examples[0].target);
|
||
stepCtrl = new StepController({onStep: render});
|
||
stepCtrl.setSteps(steps.map((_,i)=>i));
|
||
$('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
stepCtrl.onStep = (idx) => { render(idx); $('stepInfo').textContent = `步骤 ${idx+1} / ${steps.length}`; };
|
||
$('applyBtn').onclick = () => {
|
||
const m = $('inputArea').value.match(/\[([^\]]+)\].*?(\d+)/);
|
||
if (!m) { alert('格式: [2,3,6,7], target=7'); return; }
|
||
const arr = m[1].split(',').map(Number);
|
||
buildSteps(arr, parseInt(m[2])); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0); $('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
};
|
||
$('exampleSelect').onchange = () => {
|
||
const e = examples[parseInt($('exampleSelect').value)];
|
||
buildSteps(e.candidates, e.target); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0);
|
||
};
|
||
$('prevBtn').onclick = () => stepCtrl.prev();
|
||
$('nextBtn').onclick = () => stepCtrl.next();
|
||
$('jumpBtn').onclick = () => stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick = () => { const on = stepCtrl.toggleAuto(); $('autoBtn').textContent = on ? '暂停' : '自动播放'; };
|
||
$('resetBtn').onclick = () => { stepCtrl.reset(); $('autoBtn').textContent = '自动播放'; };
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`def combinationSum(candidates, target):
|
||
candidates.sort()
|
||
res = []
|
||
def backtrack(start, path, remaining):
|
||
if remaining == 0:
|
||
res.append(path[:])
|
||
return
|
||
for i in range(start, len(candidates)):
|
||
if candidates[i] > remaining:
|
||
break # 剪枝
|
||
path.append(candidates[i])
|
||
backtrack(i, path, remaining - candidates[i])
|
||
path.pop()
|
||
backtrack(0, [], target)
|
||
return res`, {lang:'Python'});
|
||
'''
|
||
|
||
def js_generate_parentheses():
|
||
return r'''
|
||
const examples = [
|
||
{input: 3, label: '示例1: n=3'},
|
||
{input: 1, label: '示例2: n=1'},
|
||
{input: 2, label: '示例3: n=2'},
|
||
];
|
||
let n, steps, stepCtrl;
|
||
|
||
function buildSteps(nn) {
|
||
n = nn; steps = [];
|
||
const result = [];
|
||
const path = [];
|
||
|
||
steps.push({stage:'start', msg:`生成 ${n} 对括号的有效组合`, path:[], open:0, close:0, result:[]});
|
||
|
||
function backtrack(open, close) {
|
||
if (path.length === 2 * n) {
|
||
result.push(path.join(''));
|
||
steps.push({stage:'collect', msg:`组合完成: "${path.join('')}"`, path:[...path], open, close, result:JSON.parse(JSON.stringify(result))});
|
||
return;
|
||
}
|
||
if (open < n) {
|
||
path.push('(');
|
||
steps.push({stage:'add_open', msg:`open(${open})<${n}，添加 '(' → open=${open+1}`, path:[...path], open:open+1, close, result:JSON.parse(JSON.stringify(result))});
|
||
backtrack(open + 1, close);
|
||
path.pop();
|
||
steps.push({stage:'undo', msg:`回溯 '('，open=${open}`, path:[...path], open, close, result:JSON.parse(JSON.stringify(result))});
|
||
}
|
||
if (close < open) {
|
||
path.push(')');
|
||
steps.push({stage:'add_close', msg:`close(${close})<open(${open})，添加 ')' → close=${close+1}`, path:[...path], open, close:close+1, result:JSON.parse(JSON.stringify(result))});
|
||
backtrack(open, close + 1);
|
||
path.pop();
|
||
steps.push({stage:'undo', msg:`回溯 ')'，close=${close}`, path:[...path], open, close, result:JSON.parse(JSON.stringify(result))});
|
||
}
|
||
}
|
||
backtrack(0, 0);
|
||
steps.push({stage:'done', msg:`共 ${result.length} 个有效组合`, path:[], open:0, close:0, result:JSON.parse(JSON.stringify(result))});
|
||
}
|
||
|
||
function render(step) {
|
||
const s = steps[step];
|
||
let viz = `<div style="font-size:28px;font-weight:700;letter-spacing:4px;margin:12px 0;font-family:monospace;">`;
|
||
const str = s.path.join('');
|
||
for (let i=0; i<str.length; i++) {
|
||
const ch = str[i];
|
||
viz += `<span style="color:${ch==='('?'var(--blue)':'var(--green)'};">${ch}</span>`;
|
||
}
|
||
viz += '<span style="color:var(--text-muted);">_'.repeat(Math.max(0, 2*n - str.length)) + '</span></div>';
|
||
viz += `<div style="display:flex;gap:16px;margin-top:8px;">
|
||
<span style="color:var(--blue);font-weight:700;">open = ${s.open} / ${n}</span>
|
||
<span style="color:var(--green);font-weight:700;">close = ${s.close} / ${s.open}</span>
|
||
</div>`;
|
||
// visual bar
|
||
viz += `<div style="margin-top:8px;display:flex;gap:4px;">`;
|
||
for (let i=0; i<n; i++) viz += `<div style="width:24px;height:8px;border-radius:4px;background:${i<s.open?'var(--blue)':'#e2e8f0'};"></div>`;
|
||
viz += `<span style="margin:0 8px;font-size:14px;">(</span>`;
|
||
for (let i=0; i<n; i++) viz += `<div style="width:24px;height:8px;border-radius:4px;background:${i<s.close?'var(--green)':'#e2e8f0'};"></div>`;
|
||
viz += `<span style="margin-left:8px;font-size:14px;">)</span></div>`;
|
||
if (s.result.length > 0) {
|
||
viz += '<div style="margin-top:8px;"><b>已找到：</b></div><div style="display:flex;flex-wrap:wrap;gap:4px;">';
|
||
s.result.forEach(r => { viz += `<span class="chip green" style="min-width:auto;padding:2px 10px;font-size:13px;font-family:monospace;">${r}</span>`; });
|
||
viz += '</div>';
|
||
}
|
||
$('vizArea').innerHTML = viz;
|
||
$('detailContent').innerHTML = '<div class="calc-block">' + s.msg + '</div>';
|
||
if (s.stage==='done') $('resultContent').innerHTML = `<div class="final-answer">共 <b>${s.result.length}</b> 个组合<br>[${s.result.map(r=>'"'+r+'"').join(', ')}]</div>`;
|
||
$('hintText').textContent = s.msg;
|
||
const stages = ['start→开始','add_open→加左括号','add_close→加右括号','collect→收集','undo→回溯','done→完成'];
|
||
$('pipeline').innerHTML = stages.map(st => { const [k,l]=st.split('→'); return `<span class="pipe-step ${s.stage===k?'active':''}">${l}</span>`; }).join('<i>→</i>');
|
||
}
|
||
|
||
function init() {
|
||
const sel = $('exampleSelect');
|
||
examples.forEach((e,i) => { sel.innerHTML += `<option value="${i}">${e.label}</option>`; });
|
||
$('inputArea').value = '3';
|
||
buildSteps(examples[0].input);
|
||
stepCtrl = new StepController({onStep: render});
|
||
stepCtrl.setSteps(steps.map((_,i)=>i));
|
||
$('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
stepCtrl.onStep = (idx) => { render(idx); $('stepInfo').textContent = `步骤 ${idx+1} / ${steps.length}`; };
|
||
$('applyBtn').onclick = () => {
|
||
const v = parseInt($('inputArea').value);
|
||
if (isNaN(v)||v<1||v>6) { alert('请输入1-6的整数'); return; }
|
||
buildSteps(v); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0); $('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
};
|
||
$('exampleSelect').onchange = () => {
|
||
const e = examples[parseInt($('exampleSelect').value)];
|
||
buildSteps(e.input); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0);
|
||
};
|
||
$('prevBtn').onclick = () => stepCtrl.prev();
|
||
$('nextBtn').onclick = () => stepCtrl.next();
|
||
$('jumpBtn').onclick = () => stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick = () => { const on = stepCtrl.toggleAuto(); $('autoBtn').textContent = on ? '暂停' : '自动播放'; };
|
||
$('resetBtn').onclick = () => { stepCtrl.reset(); $('autoBtn').textContent = '自动播放'; };
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`def generateParenthesis(n):
|
||
res = []
|
||
def backtrack(path, open, close):
|
||
if len(path) == 2 * n:
|
||
res.append(''.join(path))
|
||
return
|
||
if open < n:
|
||
path.append('(')
|
||
backtrack(path, open + 1, close)
|
||
path.pop()
|
||
if close < open:
|
||
path.append(')')
|
||
backtrack(path, open, close + 1)
|
||
path.pop()
|
||
backtrack([], 0, 0)
|
||
return res`, {lang:'Python'});
|
||
'''
|
||
|
||
def js_word_search():
|
||
return r'''
|
||
const examples = [
|
||
{board: [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word: "ABCCED", label: '示例1: ABCCED'},
|
||
{board: [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word: "SEE", label: '示例2: SEE'},
|
||
{board: [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word: "ABCB", label: '示例3: ABCB(不存在)'},
|
||
];
|
||
let board, word, R, C, steps, stepCtrl;
|
||
|
||
function buildSteps(b, w) {
|
||
board = b.map(r=>[...r]); R = board.length; C = board[0].length; word = w;
|
||
steps = [];
|
||
let found = false;
|
||
|
||
steps.push({stage:'start', msg:`在网格中搜索单词 "${word}"`, hl:{}, path:[], charIdx:0, found:false});
|
||
|
||
function dfs(r, c, idx, path, visited) {
|
||
if (idx === word.length) {
|
||
found = true;
|
||
steps.push({stage:'found', msg:`找到单词 "${word}"！`, hl:{}, path:[...path], charIdx:idx, found:true});
|
||
return true;
|
||
}
|
||
if (r<0||r>=R||c<0||c>=C||visited.has(r+','+c)||board[r][c]!==word[idx]) {
|
||
if (r>=0&&r<R&&c>=0&&c<C&&board[r][c]!==word[idx])
|
||
steps.push({stage:'mismatch', msg:`(${r},${c})='${board[r][c]}' ≠ '${word[idx]}'，跳过`, hl:{[r+','+c]:'wall'}, path:[...path], charIdx:idx, found:false});
|
||
return false;
|
||
}
|
||
|
||
visited.add(r+','+c);
|
||
path.push(r+','+c);
|
||
const hl = {}; hl[r+','+c] = 'current';
|
||
// show visited cells
|
||
visited.forEach(k => { if(k!==r+','+c) hl[k]='visited'; });
|
||
steps.push({stage:'match', msg:`(${r},${c})='${board[r][c]}' = '${word[idx]}' 匹配 ✓ (第${idx+1}/${word.length}个)`, hl, path:[...path], charIdx:idx+1, found:false});
|
||
|
||
const dirs = [[0,1],[0,-1],[1,0],[-1,0]];
|
||
for (const [dr,dc] of dirs) {
|
||
if (dfs(r+dr, c+dc, idx+1, path, visited)) return true;
|
||
}
|
||
|
||
visited.delete(r+','+c);
|
||
path.pop();
|
||
steps.push({stage:'backtrack', msg:`从 (${r},${c}) 回溯`, hl:{}, path:[...path], charIdx:idx, found:false});
|
||
return false;
|
||
}
|
||
|
||
for (let r=0; r<R && !found; r++) {
|
||
for (let c=0; c<C && !found; c++) {
|
||
if (board[r][c] === word[0]) {
|
||
const hl = {}; hl[r+','+c] = 'current';
|
||
steps.push({stage:'start_pos', msg:`找到起始点 (${r},${c})='${word[0]}'`, hl, path:[], charIdx:0, found:false});
|
||
const path = [];
|
||
const visited = new Set();
|
||
dfs(r, c, 0, path, visited);
|
||
}
|
||
}
|
||
}
|
||
if (!found) steps.push({stage:'not_found', msg:`未找到单词 "${word}"`, hl:{}, path:[], charIdx:-1, found:false});
|
||
}
|
||
|
||
function render(step) {
|
||
const s = steps[step];
|
||
const cellStyle = (val,r,c) => {
|
||
const key = r+','+c;
|
||
if (s.hl[key]==='current') return 'background:#fef3c7;border-color:var(--orange);box-shadow:0 0 0 3px rgba(245,158,11,0.3);color:#92400e;font-weight:700;';
|
||
if (s.hl[key]==='visited') return 'background:#dcfce7;border-color:var(--green);color:#166534;';
|
||
if (s.hl[key]==='wall') return 'background:#fee2e2;color:#991b1b;';
|
||
return 'background:white;color:var(--text);';
|
||
};
|
||
let viz = renderGrid(board, {highlights:s.hl, cellSize:48, cellStyle});
|
||
viz += `<div style="margin-top:8px;"><b>搜索词：</b>`;
|
||
for (let i=0; i<word.length; i++) {
|
||
const matched = i < s.charIdx;
|
||
viz += `<span style="font-weight:700;font-size:16px;color:${matched?'var(--green)':'var(--text-muted)'};${i===s.charIdx?'text-decoration:underline;':''}">${word[i]}</span>`;
|
||
}
|
||
viz += '</div>';
|
||
if (s.path.length > 0) viz += `<div style="margin-top:4px;">路径: ${s.path.map(p=>'('+p+')').join(' → ')}</div>`;
|
||
$('vizArea').innerHTML = viz;
|
||
$('detailContent').innerHTML = '<div class="calc-block">' + s.msg + '</div>';
|
||
if (s.stage==='found') $('resultContent').innerHTML = `<div class="final-answer">返回 <b>True</b>，路径: ${s.path.map(p=>'('+p+')').join('→')}</div>`;
|
||
if (s.stage==='not_found') $('resultContent').innerHTML = '<div class="final-answer" style="border-color:#f87171;background:#fef2f2;">返回 <b>False</b></div>';
|
||
$('hintText').textContent = s.msg;
|
||
const stages = ['start→开始','start_pos→起始点','match→匹配','mismatch→不匹配','backtrack→回溯','found→找到','not_found→未找到'];
|
||
$('pipeline').innerHTML = stages.map(st => { const [k,l]=st.split('→'); return `<span class="pipe-step ${s.stage===k?'active':''}">${l}</span>`; }).join('<i>→</i>');
|
||
}
|
||
|
||
function init() {
|
||
const sel = $('exampleSelect');
|
||
examples.forEach((e,i) => { sel.innerHTML += `<option value="${i}">${e.label}</option>`; });
|
||
$('inputArea').value = 'ABCCED';
|
||
buildSteps(examples[0].board, examples[0].word);
|
||
stepCtrl = new StepController({onStep: render});
|
||
stepCtrl.setSteps(steps.map((_,i)=>i));
|
||
$('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
stepCtrl.onStep = (idx) => { render(idx); $('stepInfo').textContent = `步骤 ${idx+1} / ${steps.length}`; };
|
||
$('applyBtn').onclick = () => {
|
||
buildSteps(examples[0].board, $('inputArea').value.trim());
|
||
stepCtrl.setSteps(steps.map((_,i)=>i)); render(0); $('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
};
|
||
$('exampleSelect').onchange = () => {
|
||
const e = examples[parseInt($('exampleSelect').value)];
|
||
buildSteps(e.board, e.word); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0);
|
||
};
|
||
$('prevBtn').onclick = () => stepCtrl.prev();
|
||
$('nextBtn').onclick = () => stepCtrl.next();
|
||
$('jumpBtn').onclick = () => stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick = () => { const on = stepCtrl.toggleAuto(); $('autoBtn').textContent = on ? '暂停' : '自动播放'; };
|
||
$('resetBtn').onclick = () => { stepCtrl.reset(); $('autoBtn').textContent = '自动播放'; };
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`def exist(board, word):
|
||
rows, cols = len(board), len(board[0])
|
||
def dfs(r, c, idx, visited):
|
||
if idx == len(word):
|
||
return True
|
||
if (r<0 or r>=rows or c<0 or c>=cols
|
||
or (r,c) in visited or board[r][c]!=word[idx]):
|
||
return False
|
||
visited.add((r, c))
|
||
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
|
||
if dfs(r+dr, c+dc, idx+1, visited):
|
||
return True
|
||
visited.remove((r, c))
|
||
return False
|
||
for r in range(rows):
|
||
for c in range(cols):
|
||
if dfs(r, c, 0, set()):
|
||
return True
|
||
return False`, {lang:'Python'});
|
||
'''
|
||
|
||
def js_palindrome_partitioning():
|
||
return r'''
|
||
const examples = [
|
||
{input: "aab", label: '示例1: "aab"'},
|
||
{input: "a", label: '示例2: "a"'},
|
||
{input: "racecar", label: '示例3: "racecar"'},
|
||
];
|
||
let s, steps, stepCtrl;
|
||
|
||
function isPalindrome(str, l, r) {
|
||
while (l < r) { if (str[l] !== str[r]) return false; l++; r--; }
|
||
return true;
|
||
}
|
||
|
||
function buildSteps(str) {
|
||
s = str; steps = [];
|
||
const result = [];
|
||
const path = [];
|
||
|
||
steps.push({stage:'start', msg:`对 "${str}" 进行回文分割`, path:[], start:0, checking:null, result:[]});
|
||
|
||
function backtrack(start) {
|
||
if (start === s.length) {
|
||
result.push([...path]);
|
||
steps.push({stage:'collect', msg:`分割完成: [${path.map(p=>'"'+p+'"').join(', ')}]`, path:[...path], start, checking:null, result:JSON.parse(JSON.stringify(result))});
|
||
return;
|
||
}
|
||
for (let end = start; end < s.length; end++) {
|
||
const sub = s.substring(start, end + 1);
|
||
const isPalin = isPalindrome(s, start, end);
|
||
steps.push({stage:'check', msg:`检查 "${sub}" (${start}..${end}): ${isPalin?'是回文 ✓':'不是回文 ✗'}`, path:[...path], start, checking:{from:start, to:end, isPalin}, result:JSON.parse(JSON.stringify(result))});
|
||
if (isPalin) {
|
||
path.push(sub);
|
||
steps.push({stage:'choose', msg:`选择 "${sub}" 加入路径`, path:[...path], start:end+1, checking:null, result:JSON.parse(JSON.stringify(result))});
|
||
backtrack(end + 1);
|
||
path.pop();
|
||
steps.push({stage:'undo', msg:`回溯：移除 "${sub}"`, path:[...path], start, checking:null, result:JSON.parse(JSON.stringify(result))});
|
||
}
|
||
}
|
||
}
|
||
backtrack(0);
|
||
steps.push({stage:'done', msg:`共 ${result.length} 种分割方案`, path:[], start:-1, checking:null, result:JSON.parse(JSON.stringify(result))});
|
||
}
|
||
|
||
function render(step) {
|
||
const st = steps[step];
|
||
let viz = `<div style="font-size:20px;font-family:monospace;letter-spacing:2px;margin:12px 0;">`;
|
||
// color the string by current path partitions
|
||
let pos = 0;
|
||
const parts = st.path;
|
||
const colors = ['#dbeafe','#dcfce7','#ede9fe','#fff7ed','#cffafe','#fee2e2'];
|
||
for (let pi=0; pi<parts.length; pi++) {
|
||
const part = parts[pi];
|
||
for (let j=0; j<part.length; j++) {
|
||
viz += `<span style="background:${colors[pi%colors.length]};padding:2px 1px;border-radius:3px;">${part[j]}</span>`;
|
||
pos++;
|
||
}
|
||
}
|
||
// remaining chars
|
||
for (let i=pos; i<s.length; i++) {
|
||
const isChecking = st.checking && i>=st.checking.from && i<=st.checking.to;
|
||
viz += `<span style="${isChecking?(st.checking.isPalin?'background:#dcfce7;':'background:#fee2e2;'):''}padding:2px 1px;border-radius:3px;">${s[i]}</span>`;
|
||
}
|
||
viz += '</div>';
|
||
// path
|
||
viz += `<div style="margin-top:8px;"><b>当前分割：</b>`;
|
||
if (st.path.length > 0) {
|
||
st.path.forEach((p,i) => { viz += `<span class="chip" style="min-width:auto;padding:2px 8px;background:${colors[i%colors.length]};font-size:12px;">"${p}"</span>`; });
|
||
} else viz += '<span style="color:var(--text-muted);">空</span>';
|
||
viz += '</div>';
|
||
if (st.result.length > 0) {
|
||
viz += '<div style="margin-top:8px;"><b>已找到：</b></div><div style="display:flex;flex-wrap:wrap;gap:4px;">';
|
||
st.result.forEach(r => { viz += `<span class="chip green" style="min-width:auto;padding:2px 8px;font-size:11px;">[${r.map(x=>'"'+x+'"').join(',')}]</span>`; });
|
||
viz += '</div>';
|
||
}
|
||
$('vizArea').innerHTML = viz;
|
||
$('detailContent').innerHTML = '<div class="calc-block">' + st.msg + '</div>';
|
||
if (st.stage==='done') $('resultContent').innerHTML = `<div class="final-answer">共 <b>${st.result.length}</b> 种分割方案</div>`;
|
||
$('hintText').textContent = st.msg;
|
||
const stages = ['start→开始','check→检查回文','choose→选择','collect→收集','undo→回溯','done→完成'];
|
||
$('pipeline').innerHTML = stages.map(stt => { const [k,l]=stt.split('→'); return `<span class="pipe-step ${st.stage===k?'active':''}">${l}</span>`; }).join('<i>→</i>');
|
||
}
|
||
|
||
function init() {
|
||
const sel = $('exampleSelect');
|
||
examples.forEach((e,i) => { sel.innerHTML += `<option value="${i}">${e.label}</option>`; });
|
||
$('inputArea').value = '"aab"';
|
||
buildSteps(examples[0].input);
|
||
stepCtrl = new StepController({onStep: render});
|
||
stepCtrl.setSteps(steps.map((_,i)=>i));
|
||
$('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
stepCtrl.onStep = (idx) => { render(idx); $('stepInfo').textContent = `步骤 ${idx+1} / ${steps.length}`; };
|
||
$('applyBtn').onclick = () => {
|
||
const v = $('inputArea').value.replace(/"/g,'').trim();
|
||
buildSteps(v); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0); $('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
};
|
||
$('exampleSelect').onchange = () => {
|
||
const e = examples[parseInt($('exampleSelect').value)];
|
||
buildSteps(e.input); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0);
|
||
};
|
||
$('prevBtn').onclick = () => stepCtrl.prev();
|
||
$('nextBtn').onclick = () => stepCtrl.next();
|
||
$('jumpBtn').onclick = () => stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick = () => { const on = stepCtrl.toggleAuto(); $('autoBtn').textContent = on ? '暂停' : '自动播放'; };
|
||
$('resetBtn').onclick = () => { stepCtrl.reset(); $('autoBtn').textContent = '自动播放'; };
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`def partition(s):
|
||
res = []
|
||
def is_palindrome(sub, l, r):
|
||
while l < r:
|
||
if sub[l] != sub[r]: return False
|
||
l += 1; r -= 1
|
||
return True
|
||
def backtrack(start, path):
|
||
if start == len(s):
|
||
res.append(path[:])
|
||
return
|
||
for end in range(start, len(s)):
|
||
if is_palindrome(s, start, end):
|
||
path.append(s[start:end+1])
|
||
backtrack(end + 1, path)
|
||
path.pop()
|
||
backtrack(0, [])
|
||
return res`, {lang:'Python'});
|
||
'''
|
||
|
||
def js_n_queens():
|
||
return r'''
|
||
const examples = [
|
||
{input: 4, label: '示例1: n=4'},
|
||
{input: 1, label: '示例2: n=1'},
|
||
{input: 6, label: '示例3: n=6'},
|
||
];
|
||
let n, steps, stepCtrl;
|
||
|
||
function buildSteps(nn) {
|
||
n = nn; steps = [];
|
||
const result = [];
|
||
const queens = []; // queens[row] = col
|
||
|
||
steps.push({stage:'start', msg:`${n}皇后问题：逐行放置，检查列和对角线冲突`, queens:[], row:-1, col:-1, result:[]});
|
||
|
||
function isValid(row, col) {
|
||
for (let r = 0; r < queens.length; r++) {
|
||
const c = queens[r];
|
||
if (c === col || r + c === row + col || r - c === row - col) return false;
|
||
}
|
||
return true;
|
||
}
|
||
|
||
function backtrack(row) {
|
||
if (row === n) {
|
||
result.push([...queens]);
|
||
const board = queensToBoard(queens);
|
||
steps.push({stage:'collect', msg:`找到解！皇后位置: ${queens.map((c,r)=>`(${r},${c})`).join(' ')}`, queens:[...queens], row, col:-1, result:JSON.parse(JSON.stringify(result))});
|
||
return;
|
||
}
|
||
for (let col = 0; col < n; col++) {
|
||
const valid = isValid(row, col);
|
||
if (valid) {
|
||
steps.push({stage:'try_valid', msg:`行${row} 列${col}: 无冲突 ✓，放置皇后`, queens:[...queens], row, col, result:JSON.parse(JSON.stringify(result))});
|
||
queens.push(col);
|
||
backtrack(row + 1);
|
||
queens.pop();
|
||
steps.push({stage:'undo', msg:`回溯行${row}，移除列${col}皇后`, queens:[...queens], row, col, result:JSON.parse(JSON.stringify(result))});
|
||
} else {
|
||
steps.push({stage:'conflict', msg:`行${row} 列${col}: 冲突 ✗（列/对角线已有皇后）`, queens:[...queens], row, col, result:JSON.parse(JSON.stringify(result))});
|
||
}
|
||
}
|
||
}
|
||
backtrack(0);
|
||
steps.push({stage:'done', msg:`共 ${result.length} 个解`, queens:[], row:-1, col:-1, result:JSON.parse(JSON.stringify(result))});
|
||
}
|
||
|
||
function queensToBoard(q) {
|
||
return q.map(c => { let row = '.'.repeat(n); return row.substring(0,c) + 'Q' + row.substring(c+1); });
|
||
}
|
||
|
||
function render(step) {
|
||
const s = steps[step];
|
||
const qSet = new Set(s.queens.map((c,r) => r+','+c));
|
||
const tryKey = s.row >= 0 && s.col >= 0 ? s.row+','+s.col : null;
|
||
|
||
// Build chess board
|
||
let viz = `<div style="display:inline-grid;grid-template-columns:repeat(${n},42px);gap:2px;padding:8px;border-radius:8px;background:#1e293b;">`;
|
||
for (let r = 0; r < n; r++) {
|
||
for (let c = 0; c < n; c++) {
|
||
const isQueen = s.queens[r] === c;
|
||
const isTry = r === s.row && c === s.col;
|
||
const isConflict = isTry && s.stage === 'conflict';
|
||
let bg = (r+c) % 2 === 0 ? '#f0f9ff' : '#e0f2fe';
|
||
if (isQueen) bg = '#dbeafe';
|
||
if (isConflict) bg = '#fee2e2';
|
||
else if (isTry && s.stage === 'try_valid') bg = '#fef3c7';
|
||
const content = isQueen ? '♛' : '';
|
||
const border = isTry ? `2px solid ${isConflict?'var(--red)':'var(--orange)'}` : isQueen ? '2px solid var(--blue)' : '1px solid #94a3b8';
|
||
viz += `<div style="width:42px;height:42px;display:flex;align-items:center;justify-content:center;background:${bg};border:${border};border-radius:4px;font-size:20px;cursor:default;${isQueen?'color:var(--blue-dark);font-weight:700;':''}">${content}</div>`;
|
||
}
|
||
}
|
||
viz += '</div>';
|
||
|
||
// Conflict lines for current try
|
||
if (s.stage === 'conflict' && s.row >= 0) {
|
||
viz += '<div style="margin-top:8px;color:var(--red);font-size:13px;">';
|
||
for (let r=0; r<s.queens.length; r++) {
|
||
const c = s.queens[r];
|
||
if (c === s.col) viz += `列冲突: 行${r}列${c} ↔ 行${s.row}列${s.col} `;
|
||
if (r+c === s.row+s.col) viz += `↗对角线冲突: (${r},${c}) ↔ (${s.row},${s.col}) `;
|
||
if (r-c === s.row-s.col) viz += `↘对角线冲突: (${r},${c}) ↔ (${s.row},${s.col}) `;
|
||
}
|
||
viz += '</div>';
|
||
}
|
||
|
||
viz += `<div style="margin-top:8px;"><b>当前放置：</b> ${s.queens.length > 0 ? s.queens.map((c,r)=>`行${r}=列${c}`).join(', ') : '无'}</div>`;
|
||
if (s.result.length > 0) {
|
||
viz += `<div style="margin-top:8px;"><b>已找到 ${s.result.length} 个解</b></div>`;
|
||
}
|
||
$('vizArea').innerHTML = viz;
|
||
$('detailContent').innerHTML = '<div class="calc-block">' + s.msg + '</div>';
|
||
if (s.stage==='done') $('resultContent').innerHTML = `<div class="final-answer">共 <b>${s.result.length}</b> 个解</div>`;
|
||
$('hintText').textContent = s.msg;
|
||
const stages = ['start→开始','try_valid→尝试放置','conflict→冲突','collect→收集解','undo→回溯','done→完成'];
|
||
$('pipeline').innerHTML = stages.map(st => { const [k,l]=st.split('→'); return `<span class="pipe-step ${s.stage===k?'active':''}">${l}</span>`; }).join('<i>→</i>');
|
||
}
|
||
|
||
function init() {
|
||
const sel = $('exampleSelect');
|
||
examples.forEach((e,i) => { sel.innerHTML += `<option value="${i}">${e.label}</option>`; });
|
||
$('inputArea').value = '4';
|
||
buildSteps(examples[0].input);
|
||
stepCtrl = new StepController({onStep: render});
|
||
stepCtrl.setSteps(steps.map((_,i)=>i));
|
||
$('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
stepCtrl.onStep = (idx) => { render(idx); $('stepInfo').textContent = `步骤 ${idx+1} / ${steps.length}`; };
|
||
$('applyBtn').onclick = () => {
|
||
const v = parseInt($('inputArea').value);
|
||
if (isNaN(v)||v<1||v>8) { alert('请输入1-8的整数（8以上步骤过多）'); return; }
|
||
buildSteps(v); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0); $('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
};
|
||
$('exampleSelect').onchange = () => {
|
||
const e = examples[parseInt($('exampleSelect').value)];
|
||
buildSteps(e.input); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0);
|
||
};
|
||
$('prevBtn').onclick = () => stepCtrl.prev();
|
||
$('nextBtn').onclick = () => stepCtrl.next();
|
||
$('jumpBtn').onclick = () => stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick = () => { const on = stepCtrl.toggleAuto(); $('autoBtn').textContent = on ? '暂停' : '自动播放'; };
|
||
$('resetBtn').onclick = () => { stepCtrl.reset(); $('autoBtn').textContent = '自动播放'; };
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`def solveNQueens(n):
|
||
res = []
|
||
def backtrack(row, queens):
|
||
if row == n:
|
||
res.append(queens[:])
|
||
return
|
||
for col in range(n):
|
||
valid = True
|
||
for r, c in enumerate(queens):
|
||
if c == col or r+c == row+col or r-c == row-col:
|
||
valid = False; break
|
||
if valid:
|
||
queens.append(col)
|
||
backtrack(row + 1, queens)
|
||
queens.pop()
|
||
backtrack(0, [])
|
||
return [['.'*c + 'Q' + '.'*(n-c-1) for c in sol] for sol in res]`, {lang:'Python'});
|
||
'''
|
||
|
||
|
||
# ========== 多维动态规划 ==========
|
||
|
||
def js_unique_paths():
|
||
return r'''
|
||
const examples = [
|
||
{m:3, n:7, label: '示例1: m=3, n=7'},
|
||
{m:3, n:2, label: '示例2: m=3, n=2'},
|
||
{m:3, n:3, label: '示例3: m=3, n=3'},
|
||
];
|
||
let steps, stepCtrl, m, n;
|
||
function buildSteps(rows, cols) {
|
||
m = rows; n = cols; steps = [];
|
||
const dp = [];
|
||
for (let i = 0; i < m; i++) dp[i] = new Array(n).fill(0);
|
||
steps.push({stage:'init', msg:`创建 ${m}×${n} DP 表，dp[i][j] = 从(0,0)到(i,j)的路径数`, dp:dp.map(r=>[...r]), row:-1, col:-1});
|
||
for (let j = 0; j < n; j++) { dp[0][j] = 1; steps.push({stage:'fill', msg:`第一行 dp[0][${j}]=1（只能向右）`, dp:dp.map(r=>[...r]), row:0, col:j}); }
|
||
for (let i = 0; i < m; i++) { dp[i][0] = 1; steps.push({stage:'fill', msg:`第一列 dp[${i}][0]=1（只能向下）`, dp:dp.map(r=>[...r]), row:i, col:0}); }
|
||
for (let i = 1; i < m; i++) for (let j = 1; j < n; j++) {
|
||
dp[i][j] = dp[i-1][j] + dp[i][j-1];
|
||
steps.push({stage:'fill', msg:`dp[${i}][${j}] = dp[${i-1}][${j}] + dp[${i}][${j-1}] = ${dp[i-1][j]} + ${dp[i][j-1]} = ${dp[i][j]}`, dp:dp.map(r=>[...r]), row:i, col:j});
|
||
}
|
||
steps.push({stage:'done', msg:`不同路径共 ${dp[m-1][n-1]} 条`, dp:dp.map(r=>[...r]), row:m-1, col:n-1});
|
||
}
|
||
function render(step) {
|
||
const s = steps[step]; const hl = {};
|
||
if (s.row >= 0 && s.col >= 0) hl[`${s.row},${s.col}`] = 'current';
|
||
for (let i=0;i<m;i++) for (let j=0;j<n;j++) if (s.dp[i][j]>0 && !(s.row===i&&s.col===j)) hl[`${i},${j}`]='visited';
|
||
let viz = renderGrid(s.dp, {highlights:hl, cellSize:44, cellStyle:(v)=>v===0?'color:#94a3b8;':'font-weight:700;'});
|
||
$('vizArea').innerHTML = viz;
|
||
$('detailContent').innerHTML = '<div class="calc-block">'+s.msg+'</div>';
|
||
if (s.dp[m-1][n-1]>0) $('detailContent').innerHTML += `<div class="current-answer">dp[${m-1}][${n-1}] = <b>${s.dp[m-1][n-1]}</b></div>`;
|
||
if (s.stage==='done') $('resultContent').innerHTML = `<div class="final-answer">不同路径数 = <b>${s.dp[m-1][n-1]}</b></div>`;
|
||
$('hintText').textContent = s.msg;
|
||
const stages = ['init→初始化','fill→填充','done→完成'];
|
||
$('pipeline').innerHTML = stages.map(x=>{const[k,l]=x.split('→');return`<span class="pipe-step ${s.stage===k?'active':''}">${l}</span>`;}).join('<i>→</i>');
|
||
}
|
||
function init() {
|
||
const sel=$('exampleSelect'); examples.forEach((e,i)=>{sel.innerHTML+=`<option value="${i}">${e.label}</option>`;});
|
||
$('inputArea').value='m=3, n=7'; buildSteps(examples[0].m, examples[0].n);
|
||
stepCtrl = new StepController({onStep:render}); stepCtrl.setSteps(steps.map((_,i)=>i));
|
||
$('stepInfo').textContent='步骤 1 / '+steps.length;
|
||
stepCtrl.onStep=(idx)=>{render(idx);$('stepInfo').textContent=`步骤 ${idx+1} / ${steps.length}`;};
|
||
$('applyBtn').onclick=()=>{const v=$('inputArea').value.match(/m\s*=\s*(\d+).*n\s*=\s*(\d+)/);if(!v){alert('格式: m=3, n=7');return;}buildSteps(parseInt(v[1]),parseInt(v[2]));stepCtrl.setSteps(steps.map((_,i)=>i));render(0);$('stepInfo').textContent='步骤 1 / '+steps.length;};
|
||
$('exampleSelect').onchange=()=>{const e=examples[parseInt($('exampleSelect').value)];$('inputArea').value=`m=${e.m}, n=${e.n}`;buildSteps(e.m,e.n);stepCtrl.setSteps(steps.map((_,i)=>i));render(0);};
|
||
$('prevBtn').onclick=()=>stepCtrl.prev();$('nextBtn').onclick=()=>stepCtrl.next();$('jumpBtn').onclick=()=>stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick=()=>{const on=stepCtrl.toggleAuto();$('autoBtn').textContent=on?'暂停':'自动播放';};
|
||
$('resetBtn').onclick=()=>{stepCtrl.reset();$('autoBtn').textContent='自动播放';};
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`def uniquePaths(m, n):
|
||
dp = [[0]*n for _ in range(m)]
|
||
for i in range(m): dp[i][0] = 1
|
||
for j in range(n): dp[0][j] = 1
|
||
for i in range(1, m):
|
||
for j in range(1, n):
|
||
dp[i][j] = dp[i-1][j] + dp[i][j-1]
|
||
return dp[m-1][n-1]`, {lang:'Python'});
|
||
'''
|
||
|
||
def js_minimum_path_sum():
|
||
return r'''
|
||
const examples = [
|
||
{input:[[1,3,1],[1,5,1],[4,2,1]], label:'示例1'},
|
||
{input:[[1,2,3],[4,5,6]], label:'示例2'},
|
||
];
|
||
let steps, stepCtrl, grid, m, n;
|
||
function buildSteps(g) {
|
||
grid=g.map(r=>[...r]); m=g.length; n=g[0].length; steps=[];
|
||
const dp=[]; for(let i=0;i<m;i++) dp[i]=new Array(n).fill(0);
|
||
steps.push({stage:'init',msg:`创建 ${m}×${n} DP 表`,dp:dp.map(r=>[...r]),row:-1,col:-1,pathCells:[]});
|
||
dp[0][0]=grid[0][0]; steps.push({stage:'fill',msg:`dp[0][0]=${grid[0][0]}`,dp:dp.map(r=>[...r]),row:0,col:0,pathCells:['0,0']});
|
||
for(let j=1;j<n;j++){dp[0][j]=dp[0][j-1]+grid[0][j];steps.push({stage:'fill',msg:`dp[0][${j}]=${dp[0][j-1]}+${grid[0][j]}=${dp[0][j]}`,dp:dp.map(r=>[...r]),row:0,col:j,pathCells:Array.from({length:j+1},(_,k)=>`0,${k}`)});}
|
||
for(let i=1;i<m;i++){dp[i][0]=dp[i-1][0]+grid[i][0];steps.push({stage:'fill',msg:`dp[${i}][0]=${dp[i-1][0]}+${grid[i][0]}=${dp[i][0]}`,dp:dp.map(r=>[...r]),row:i,col:0,pathCells:Array.from({length:i+1},(_,k)=>`${k},0`)});}
|
||
for(let i=1;i<m;i++) for(let j=1;j<n;j++){
|
||
const ft=dp[i-1][j],fl=dp[i][j-1]; dp[i][j]=Math.min(ft,fl)+grid[i][j];
|
||
steps.push({stage:'fill',msg:`dp[${i}][${j}]=min(${ft},${fl})+${grid[i][j]}=${dp[i][j]} ←${ft<=fl?'上':'左'}`,dp:dp.map(r=>[...r]),row:i,col:j,pathCells:[]});
|
||
}
|
||
const path=[];let pi=m-1,pj=n-1;path.unshift(`${pi},${pj}`);while(pi>0||pj>0){if(pi===0)pj--;else if(pj===0)pi--;else{dp[pi-1][pj]<=dp[pi][pj-1]?pi--:pj--;}path.unshift(`${pi},${pj}`);}
|
||
steps.push({stage:'done',msg:`最小路径和=${dp[m-1][n-1]}`,dp:dp.map(r=>[...r]),row:m-1,col:n-1,pathCells:path});
|
||
}
|
||
function render(step) {
|
||
const s=steps[step]; const hl={};
|
||
if(s.row>=0&&s.col>=0) hl[`${s.row},${s.col}`]='current';
|
||
s.pathCells.forEach(k=>{if(!(s.row+','+s.col===k))hl[k]='visited';});
|
||
for(let i=0;i<m;i++) for(let j=0;j<n;j++) if(s.dp[i][j]>0&&!hl[`${i},${j}`]&&!(s.row===i&&s.col===j)) hl[`${i},${j}`]='visited';
|
||
let viz='<div style="margin-bottom:8px;font-weight:600;color:#64748b;">原始网格：</div>'+renderGrid(grid,{cellSize:40});
|
||
viz+='<div style="margin:12px 0;font-weight:600;color:#64748b;">DP 表：</div>'+renderGrid(s.dp,{highlights:hl,cellSize:44,cellStyle:(v)=>v===0?'color:#94a3b8;':'font-weight:700;'});
|
||
if(s.pathCells.length>1) viz+='<div style="margin-top:8px;color:#8b5cf6;">路径: '+s.pathCells.map(p=>`(${p})`).join(' → ')+'</div>';
|
||
$('vizArea').innerHTML=viz;
|
||
$('detailContent').innerHTML='<div class="calc-block">'+s.msg+'</div>';
|
||
if(s.dp[m-1]&&s.dp[m-1][n-1]>0) $('detailContent').innerHTML+=`<div class="current-answer">dp[${m-1}][${n-1}] = <b>${s.dp[m-1][n-1]}</b></div>`;
|
||
if(s.stage==='done') $('resultContent').innerHTML=`<div class="final-answer">最小路径和 = <b>${s.dp[m-1][n-1]}</b></div>`;
|
||
$('hintText').textContent=s.msg;
|
||
const stages=['init→初始化','fill→填充','done→完成'];
|
||
$('pipeline').innerHTML=stages.map(x=>{const[k,l]=x.split('→');return`<span class="pipe-step ${s.stage===k?'active':''}">${l}</span>`;}).join('<i>→</i>');
|
||
}
|
||
function init() {
|
||
const sel=$('exampleSelect');examples.forEach((e,i)=>{sel.innerHTML+=`<option value="${i}">${e.label}</option>`;});
|
||
$('inputArea').value='[[1,3,1],[1,5,1],[4,2,1]]';buildSteps(examples[0].input);
|
||
stepCtrl=new StepController({onStep:render});stepCtrl.setSteps(steps.map((_,i)=>i));
|
||
$('stepInfo').textContent='步骤 1 / '+steps.length;stepCtrl.onStep=(idx)=>{render(idx);$('stepInfo').textContent=`步骤 ${idx+1} / ${steps.length}`;};
|
||
$('applyBtn').onclick=()=>{try{const g=JSON.parse($('inputArea').value);buildSteps(g);stepCtrl.setSteps(steps.map((_,i)=>i));render(0);}catch(e){alert('请输入合法JSON二维数组');}};
|
||
$('exampleSelect').onchange=()=>{const e=examples[parseInt($('exampleSelect').value)];$('inputArea').value=JSON.stringify(e.input);buildSteps(e.input);stepCtrl.setSteps(steps.map((_,i)=>i));render(0);};
|
||
$('prevBtn').onclick=()=>stepCtrl.prev();$('nextBtn').onclick=()=>stepCtrl.next();$('jumpBtn').onclick=()=>stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick=()=>{const on=stepCtrl.toggleAuto();$('autoBtn').textContent=on?'暂停':'自动播放';};
|
||
$('resetBtn').onclick=()=>{stepCtrl.reset();$('autoBtn').textContent='自动播放';};
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`def minPathSum(grid):
|
||
m, n = len(grid), len(grid[0])
|
||
dp = [[0]*n for _ in range(m)]
|
||
dp[0][0] = grid[0][0]
|
||
for j in range(1, n): dp[0][j] = dp[0][j-1] + grid[0][j]
|
||
for i in range(1, m): dp[i][0] = dp[i-1][0] + grid[i][0]
|
||
for i in range(1, m):
|
||
for j in range(1, n):
|
||
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
|
||
return dp[m-1][n-1]`, {lang:'Python'});
|
||
'''
|
||
|
||
def js_longest_palindromic_substring():
|
||
return r'''
|
||
const examples = [
|
||
{input:'babad', label:'示例1: "babad"'},
|
||
{input:'cbbd', label:'示例2: "cbbd"'},
|
||
{input:'aacabdkacaa', label:'示例3: "aacabdkacaa"'},
|
||
];
|
||
let steps, stepCtrl, s;
|
||
function buildSteps(str) {
|
||
s=str; steps=[]; let bestL=0, bestR=0;
|
||
steps.push({stage:'init',msg:'中心扩展：以每个字符/对为中心向两边扩展',center:-1,isEven:false,bestL:0,bestR:0,expandPairs:[]});
|
||
for(let i=0;i<str.length;i++){
|
||
let l=i,r=i;const op=[];
|
||
while(l>=0&&r<str.length&&str[l]===str[r]){op.push({l,r});if(r-l>bestR-bestL){bestL=l;bestR=r;}steps.push({stage:'expand',msg:`奇数中心i=${i}: str[${l}]='${str[l]}'==str[${r}]='${str[r]}' ✓ [${l},${r}] len=${r-l+1}`,center:i,isEven:false,bestL,bestR,expandPairs:[...op]});l--;r++;}
|
||
l=i;r=i+1;const ep=[];
|
||
if(r<str.length){while(l>=0&&r<str.length&&str[l]===str[r]){ep.push({l,r});if(r-l>bestR-bestL){bestL=l;bestR=r;}steps.push({stage:'expand',msg:`偶数中心i=${i}: str[${l}]='${str[l]}'==str[${r}]='${str[r]}' ✓ [${l},${r}] len=${r-l+1}`,center:i,isEven:true,bestL,bestR,expandPairs:[...ep]});l--;r++;}
|
||
if(ep.length===0) steps.push({stage:'skip',msg:`偶数中心i=${i}: str[${i}]='${str[i]}'≠str[${i+1}]='${str[i+1]}' ✗`,center:i,isEven:true,bestL,bestR,expandPairs:[]});}
|
||
}
|
||
steps.push({stage:'done',msg:`最长回文: s[${bestL}..${bestR}]="${s.substring(bestL,bestR+1)}" 长度=${bestR-bestL+1}`,center:-1,isEven:false,bestL,bestR,expandPairs:[]});
|
||
}
|
||
function render(step) {
|
||
const st=steps[step];const hl={};
|
||
if(st.expandPairs) st.expandPairs.forEach(p=>{for(let k=p.l;k<=p.r;k++)hl[k]='orange';});
|
||
for(let k=st.bestL;k<=st.bestR;k++) hl[k]='green';
|
||
if(st.center>=0) hl[st.center]='purple';
|
||
let viz='<div class="nums-line">';s.split('').forEach((ch,i)=>{viz+=`<span class="chip-group"><span class="chip ${hl[i]||'default'}">${ch}</span><span class="chip-index">${i}</span></span>`;});viz+='</div>';
|
||
if(st.expandPairs&&st.expandPairs.length>0){const p=st.expandPairs[st.expandPairs.length-1];viz+=`<div style="margin-top:8px;color:#ea580c;">当前回文: [${p.l},${p.r}]="${s.substring(p.l,p.r+1)}"</div>`;}
|
||
viz+=`<div style="margin-top:4px;color:#16a34a;">最长回文: [${st.bestL},${st.bestR}]="${s.substring(st.bestL,st.bestR+1)}"</div>`;
|
||
$('vizArea').innerHTML=viz;
|
||
$('detailContent').innerHTML='<div class="calc-block">'+st.msg+'</div>'+`<div class="current-answer">最长回文: <b>"${s.substring(st.bestL,st.bestR+1)}"</b> (len ${st.bestR-st.bestL+1})</div>`;
|
||
if(st.stage==='done') $('resultContent').innerHTML=`<div class="final-answer">最长回文子串 = <b>"${s.substring(st.bestL,st.bestR+1)}"</b><br>长度=${st.bestR-st.bestL+1}</div>`;
|
||
$('hintText').textContent=st.msg;
|
||
const stages=['init→初始化','expand→扩展','skip→跳过','done→完成'];
|
||
$('pipeline').innerHTML=stages.map(x=>{const[k,l]=x.split('→');return`<span class="pipe-step ${st.stage===k?'active':''}">${l}</span>`;}).join('<i>→</i>');
|
||
}
|
||
function init() {
|
||
const sel=$('exampleSelect');examples.forEach((e,i)=>{sel.innerHTML+=`<option value="${i}">${e.label}</option>`;});
|
||
$('inputArea').value='"babad"';buildSteps(examples[0].input);
|
||
stepCtrl=new StepController({onStep:render});stepCtrl.setSteps(steps.map((_,i)=>i));
|
||
$('stepInfo').textContent='步骤 1 / '+steps.length;stepCtrl.onStep=(idx)=>{render(idx);$('stepInfo').textContent=`步骤 ${idx+1} / ${steps.length}`;};
|
||
$('applyBtn').onclick=()=>{const v=$('inputArea').value.trim().replace(/^["']|["']$/g,'');if(!v){alert('请输入字符串');return;}buildSteps(v);stepCtrl.setSteps(steps.map((_,i)=>i));render(0);};
|
||
$('exampleSelect').onchange=()=>{const e=examples[parseInt($('exampleSelect').value)];$('inputArea').value=`"${e.input}"`;buildSteps(e.input);stepCtrl.setSteps(steps.map((_,i)=>i));render(0);};
|
||
$('prevBtn').onclick=()=>stepCtrl.prev();$('nextBtn').onclick=()=>stepCtrl.next();$('jumpBtn').onclick=()=>stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick=()=>{const on=stepCtrl.toggleAuto();$('autoBtn').textContent=on?'暂停':'自动播放';};
|
||
$('resetBtn').onclick=()=>{stepCtrl.reset();$('autoBtn').textContent='自动播放';};
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`def longestPalindrome(s):
|
||
best_l, best_r = 0, 0
|
||
for i in range(len(s)):
|
||
l, r = i, i
|
||
while l >= 0 and r < len(s) and s[l] == s[r]:
|
||
if r - l > best_r - best_l: best_l, best_r = l, r
|
||
l -= 1; r += 1
|
||
l, r = i, i + 1
|
||
while l >= 0 and r < len(s) and s[l] == s[r]:
|
||
if r - l > best_r - best_l: best_l, best_r = l, r
|
||
l -= 1; r += 1
|
||
return s[best_l:best_r+1]`, {lang:'Python'});
|
||
'''
|
||
|
||
def js_longest_common_subsequence():
|
||
return r'''
|
||
const examples = [
|
||
{s1:'abcde', s2:'ace', label:'示例1: "abcde","ace"'},
|
||
{s1:'abc', s2:'abc', label:'示例2: "abc","abc"'},
|
||
{s1:'abc', s2:'def', label:'示例3: "abc","def"'},
|
||
];
|
||
let steps, stepCtrl, str1, str2, m, n;
|
||
function buildSteps(a, b) {
|
||
str1=a;str2=b;m=a.length;n=b.length;steps=[];
|
||
const dp=[];for(let i=0;i<=m;i++) dp[i]=new Array(n+1).fill(0);
|
||
steps.push({stage:'init',msg:`构建 (${m}+1)×(${n}+1) DP 表`,dp:dp.map(r=>[...r]),row:-1,col:-1});
|
||
for(let i=1;i<=m;i++) for(let j=1;j<=n;j++){
|
||
if(a[i-1]===b[j-1]){dp[i][j]=dp[i-1][j-1]+1;steps.push({stage:'match',msg:`s1[${i-1}]='${a[i-1]}'==s2[${j-1}]='${b[j-1]}'→dp[${i}][${j}]=${dp[i][j]}`,dp:dp.map(r=>[...r]),row:i,col:j,i1:i-1,i2:j-1});}
|
||
else{dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);steps.push({stage:'no_match',msg:`s1[${i-1}]='${a[i-1]}'≠s2[${j-1}]='${b[j-1]}'→dp[${i}][${j}]=max(${dp[i-1][j]},${dp[i][j-1]})=${dp[i][j]}`,dp:dp.map(r=>[...r]),row:i,col:j,i1:i-1,i2:j-1});}
|
||
}
|
||
const lcs=[];let ti=m,tj=n;while(ti>0&&tj>0){if(a[ti-1]===b[tj-1]){lcs.unshift(a[ti-1]);ti--;tj--;}else if(dp[ti-1][tj]>=dp[ti][tj-1])ti--;else tj--;}
|
||
steps.push({stage:'done',msg:`LCS=${dp[m][n]}，子序列="${lcs.join('')}"`,dp:dp.map(r=>[...r]),row:m,col:n,lcs:[...lcs]});
|
||
}
|
||
function render(step) {
|
||
const s=steps[step];const hl={};if(s.row>=0&&s.col>=0)hl[`${s.row},${s.col}`]='current';
|
||
for(let i=1;i<=m;i++)for(let j=1;j<=n;j++)if(s.dp[i][j]>0&&!(s.row===i&&s.col===j))hl[`${i},${j}`]='visited';
|
||
let viz='<div style="display:flex;gap:24px;"><div><b>s1:</b> ';
|
||
str1.split('').forEach((ch,i)=>{viz+=`<span class="chip ${s.i1===i?'purple':'default'}" style="width:32px;">${ch}</span>`;});
|
||
viz+='</div><div><b>s2:</b> ';
|
||
str2.split('').forEach((ch,j)=>{viz+=`<span class="chip ${s.i2===j?'purple':'default'}" style="width:32px;">${ch}</span>`;});
|
||
viz+='</div></div><div style="margin-top:12px;overflow-x:auto;"><table style="border-collapse:collapse;font-size:14px;">';
|
||
viz+='<tr><td style="border:1px solid #e2e8f0;padding:6px 10px;background:#f1f5f9;"></td><td style="border:1px solid #e2e8f0;padding:6px 10px;background:#f1f5f9;">∅</td>';
|
||
for(let j=0;j<n;j++) viz+=`<td style="border:1px solid #e2e8f0;padding:6px 10px;background:#f1f5f9;">${str2[j]}</td>`;
|
||
viz+='</tr>';
|
||
for(let i=0;i<=m;i++){viz+='<tr>';viz+=`<td style="border:1px solid #e2e8f0;padding:6px 10px;background:#f1f5f9;">${i===0?'∅':str1[i-1]}</td>`;
|
||
for(let j=0;j<=n;j++){const key=`${i},${j}`;let bg='white',fw='normal';if(hl[key]==='current'){bg='#fef3c7';fw='bold';}else if(hl[key]==='visited'){bg='#ecfdf5';}else if(i===0||j===0){bg='#f1f5f9';}
|
||
viz+=`<td style="border:1px solid #e2e8f0;padding:6px 10px;text-align:center;background:${bg};font-weight:${fw};min-width:40px;">${s.dp[i][j]}</td>`;}
|
||
viz+='</tr>';}
|
||
viz+='</table></div>';$('vizArea').innerHTML=viz;
|
||
let detail='<div class="calc-block">'+s.msg+'</div>';if(s.lcs)detail+=`<div class="current-answer">LCS=<b>"${s.lcs.join('')}"</b></div>`;$('detailContent').innerHTML=detail;
|
||
if(s.stage==='done') $('resultContent').innerHTML=`<div class="final-answer">LCS长度=<b>${s.dp[m][n]}</b><br>子序列="${s.lcs.join('')}"</div>`;
|
||
$('hintText').textContent=s.msg;
|
||
const stages=['init→初始化','match→匹配','no_match→不匹配','done→完成'];
|
||
$('pipeline').innerHTML=stages.map(x=>{const[k,l]=x.split('→');return`<span class="pipe-step ${s.stage===k?'active':''}">${l}</span>`;}).join('<i>→</i>');
|
||
}
|
||
function init() {
|
||
const sel=$('exampleSelect');examples.forEach((e,i)=>{sel.innerHTML+=`<option value="${i}">${e.label}</option>`;});
|
||
$('inputArea').value='s1="abcde", s2="ace"';buildSteps(examples[0].s1,examples[0].s2);
|
||
stepCtrl=new StepController({onStep:render});stepCtrl.setSteps(steps.map((_,i)=>i));
|
||
$('stepInfo').textContent='步骤 1 / '+steps.length;stepCtrl.onStep=(idx)=>{render(idx);$('stepInfo').textContent=`步骤 ${idx+1} / ${steps.length}`;};
|
||
$('applyBtn').onclick=()=>{const v=$('inputArea').value.match(/s1\s*=\s*"([^"]+)".*s2\s*=\s*"([^"]+)"/);if(!v){alert('格式: s1="abcde", s2="ace"');return;}buildSteps(v[1],v[2]);stepCtrl.setSteps(steps.map((_,i)=>i));render(0);};
|
||
$('exampleSelect').onchange=()=>{const e=examples[parseInt($('exampleSelect').value)];$('inputArea').value=`s1="${e.s1}", s2="${e.s2}"`;buildSteps(e.s1,e.s2);stepCtrl.setSteps(steps.map((_,i)=>i));render(0);};
|
||
$('prevBtn').onclick=()=>stepCtrl.prev();$('nextBtn').onclick=()=>stepCtrl.next();$('jumpBtn').onclick=()=>stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick=()=>{const on=stepCtrl.toggleAuto();$('autoBtn').textContent=on?'暂停':'自动播放';};
|
||
$('resetBtn').onclick=()=>{stepCtrl.reset();$('autoBtn').textContent='自动播放';};
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`def longestCommonSubsequence(s1, s2):
|
||
m, n = len(s1), len(s2)
|
||
dp = [[0]*(n+1) for _ in range(m+1)]
|
||
for i in range(1, m+1):
|
||
for j in range(1, n+1):
|
||
if s1[i-1] == s2[j-1]:
|
||
dp[i][j] = dp[i-1][j-1] + 1
|
||
else:
|
||
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
|
||
return dp[m][n]`, {lang:'Python'});
|
||
'''
|
||
|
||
def js_edit_distance():
|
||
return r'''
|
||
const examples = [
|
||
{s1:'horse', s2:'ros', label:'示例1: "horse"→"ros"'},
|
||
{s1:'intention', s2:'execution', label:'示例2: "intention"→"execution"'},
|
||
{s1:'kitten', s2:'sitting', label:'示例3: "kitten"→"sitting"'},
|
||
];
|
||
let steps, stepCtrl, str1, str2, m, n;
|
||
function buildSteps(a, b) {
|
||
str1=a;str2=b;m=a.length;n=b.length;steps=[];
|
||
const dp=[];for(let i=0;i<=m;i++) dp[i]=new Array(n+1).fill(0);
|
||
steps.push({stage:'init',msg:`构建 (${m}+1)×(${n}+1) DP 表`,dp:dp.map(r=>[...r]),row:-1,col:-1});
|
||
for(let i=0;i<=m;i++)dp[i][0]=i;for(let j=0;j<=n;j++)dp[0][j]=j;
|
||
steps.push({stage:'base',msg:'边界: dp[i][0]=i(删除), dp[0][j]=j(插入)',dp:dp.map(r=>[...r]),row:-1,col:-1});
|
||
for(let i=1;i<=m;i++) for(let j=1;j<=n;j++){
|
||
if(a[i-1]===b[j-1]){dp[i][j]=dp[i-1][j-1];steps.push({stage:'match',msg:`w1[${i-1}]='${a[i-1]}'==w2[${j-1}]='${b[j-1]}'→dp=${dp[i][j]}`,dp:dp.map(r=>[...r]),row:i,col:j,op:'match'});}
|
||
else{const ins=dp[i][j-1]+1,del=dp[i-1][j]+1,rep=dp[i-1][j-1]+1;dp[i][j]=Math.min(ins,del,rep);
|
||
let opN=rep<=Math.min(ins,del)?'替换':(ins<=del?'插入':'删除');
|
||
steps.push({stage:'op',msg:`'${a[i-1]}'≠'${b[j-1]}'→插=${ins}删=${del}替=${rep}→${dp[i][j]}(${opN})`,dp:dp.map(r=>[...r]),row:i,col:j,op:opN});}
|
||
}
|
||
const ops=[];let ti=m,tj=n;while(ti>0||tj>0){if(ti>0&&tj>0&&a[ti-1]===b[tj-1]){ti--;tj--;}else if(ti>0&&tj>0&&dp[ti][tj]===dp[ti-1][tj-1]+1){ops.unshift(`替换 '${a[ti-1]}'→'${b[tj-1]}'`);ti--;tj--;}else if(tj>0&&dp[ti][tj]===dp[ti][tj-1]+1){ops.unshift(`插入 '${b[tj-1]}'`);tj--;}else{ops.unshift(`删除 '${a[ti-1]}'`);ti--;}}
|
||
steps.push({stage:'done',msg:`编辑距离=${dp[m][n]}`,dp:dp.map(r=>[...r]),row:m,col:n,ops:[...ops]});
|
||
}
|
||
function render(step) {
|
||
const s=steps[step];
|
||
let viz='<div style="overflow-x:auto;"><table style="border-collapse:collapse;font-size:14px;">';
|
||
viz+='<tr><td style="border:1px solid #e2e8f0;padding:6px 10px;background:#f1f5f9;"></td><td style="border:1px solid #e2e8f0;padding:6px 10px;background:#f1f5f9;">∅</td>';
|
||
for(let j=0;j<n;j++) viz+=`<td style="border:1px solid #e2e8f0;padding:6px 10px;background:#f1f5f9;">${str2[j]}</td>`;
|
||
viz+='</tr>';
|
||
for(let i=0;i<=m;i++){viz+='<tr>';viz+=`<td style="border:1px solid #e2e8f0;padding:6px 10px;background:#f1f5f9;">${i===0?'∅':str1[i-1]}</td>`;
|
||
for(let j=0;j<=n;j++){let bg='white',fw='normal';if(s.row===i&&s.col===j){bg='#fef3c7';fw='bold';}else if(s.dp[i][j]>0&&!(i===0&&j===0)){bg='#ecfdf5';}else if(i===0||j===0){bg='#f1f5f9';}
|
||
const ic=s.row===i&&s.col===j&&s.op==='match'?' ✅':s.row===i&&s.col===j&&s.op==='替换'?' 🔄':s.row===i&&s.col===j&&s.op==='插入'?' ➕':s.row===i&&s.col===j&&s.op==='删除'?' ➖':'';
|
||
viz+=`<td style="border:1px solid #e2e8f0;padding:6px 10px;text-align:center;background:${bg};font-weight:${fw};min-width:40px;">${s.dp[i][j]}${ic}</td>`;}
|
||
viz+='</tr>';}
|
||
viz+='</table></div><div style="margin-top:10px;display:flex;gap:12px;font-size:12px;color:#64748b;"><span>✅相同</span><span>🔄替换</span><span>➕插入</span><span>➖删除</span></div>';
|
||
$('vizArea').innerHTML=viz;
|
||
let detail='<div class="calc-block">'+s.msg+'</div>';if(s.ops){detail+='<div style="margin-top:8px;"><b>操作：</b></div>';s.ops.forEach((o,i)=>{detail+=`<div>${i+1}. ${o}</div>`;});}$('detailContent').innerHTML=detail;
|
||
if(s.stage==='done') $('resultContent').innerHTML=`<div class="final-answer">编辑距离=<b>${s.dp[m][n]}</b><br>${s.ops.join(' → ')}</div>`;
|
||
$('hintText').textContent=s.msg;
|
||
const stages=['init→初始化','base→边界','match→匹配','op→操作','done→完成'];
|
||
$('pipeline').innerHTML=stages.map(x=>{const[k,l]=x.split('→');return`<span class="pipe-step ${s.stage===k?'active':''}">${l}</span>`;}).join('<i>→</i>');
|
||
}
|
||
function init() {
|
||
const sel=$('exampleSelect');examples.forEach((e,i)=>{sel.innerHTML+=`<option value="${i}">${e.label}</option>`;});
|
||
$('inputArea').value='word1="horse", word2="ros"';buildSteps(examples[0].s1,examples[0].s2);
|
||
stepCtrl=new StepController({onStep:render});stepCtrl.setSteps(steps.map((_,i)=>i));
|
||
$('stepInfo').textContent='步骤 1 / '+steps.length;stepCtrl.onStep=(idx)=>{render(idx);$('stepInfo').textContent=`步骤 ${idx+1} / ${steps.length}`;};
|
||
$('applyBtn').onclick=()=>{const v=$('inputArea').value.match(/word1\s*=\s*"([^"]+)".*word2\s*=\s*"([^"]+)"/);if(!v){alert('格式: word1="horse", word2="ros"');return;}buildSteps(v[1],v[2]);stepCtrl.setSteps(steps.map((_,i)=>i));render(0);};
|
||
$('exampleSelect').onchange=()=>{const e=examples[parseInt($('exampleSelect').value)];$('inputArea').value=`word1="${e.s1}", word2="${e.s2}"`;buildSteps(e.s1,e.s2);stepCtrl.setSteps(steps.map((_,i)=>i));render(0);};
|
||
$('prevBtn').onclick=()=>stepCtrl.prev();$('nextBtn').onclick=()=>stepCtrl.next();$('jumpBtn').onclick=()=>stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick=()=>{const on=stepCtrl.toggleAuto();$('autoBtn').textContent=on?'暂停':'自动播放';};
|
||
$('resetBtn').onclick=()=>{stepCtrl.reset();$('autoBtn').textContent='自动播放';};
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`def minDistance(word1, word2):
|
||
m, n = len(word1), len(word2)
|
||
dp = [[0]*(n+1) for _ in range(m+1)]
|
||
for i in range(m+1): dp[i][0] = i
|
||
for j in range(n+1): dp[0][j] = j
|
||
for i in range(1, m+1):
|
||
for j in range(1, n+1):
|
||
if word1[i-1] == word2[j-1]:
|
||
dp[i][j] = dp[i-1][j-1]
|
||
else:
|
||
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
|
||
return dp[m][n]`, {lang:'Python'});
|
||
'''
|
||
|
||
# ========== 技巧 ==========
|
||
|
||
def js_single_number():
|
||
return r'''
|
||
const examples = [
|
||
{input:[2,2,1], label:'示例1: [2,2,1]'},
|
||
{input:[4,1,2,1,2], label:'示例2: [4,1,2,1,2]'},
|
||
{input:[1], label:'示例3: [1]'},
|
||
];
|
||
let nums, steps, stepCtrl;
|
||
function toBin(n,bits){return(n>>>0).toString(2).padStart(bits,'0');}
|
||
function buildSteps(arr) {
|
||
nums=[...arr];steps=[];let xor=0;const bits=Math.max(4,Math.ceil(Math.log2(Math.max(...arr)+1)));
|
||
steps.push({stage:'init',msg:'a⊕a=0, a⊕0=a，异或消除成对数',idx:-1,xorResult:0,xorBin:toBin(0,bits)});
|
||
for(let i=0;i<arr.length;i++){const prev=xor;xor^=arr[i];steps.push({stage:'xor',msg:`${prev} ⊕ ${arr[i]} = ${toBin(prev,bits)} ⊕ ${toBin(arr[i],bits)} = ${toBin(xor,bits)} = ${xor}`,idx:i,xorResult:xor,xorBin:toBin(xor,bits),prevBin:toBin(prev,bits),curBin:toBin(arr[i],bits)});}
|
||
steps.push({stage:'done',msg:`结果=${xor}`,idx:-1,xorResult:xor,xorBin:toBin(xor,bits)});
|
||
}
|
||
function render(step) {
|
||
const s=steps[step];const hl={};if(s.idx>=0)hl[s.idx]='orange';for(let i=0;i<s.idx;i++)hl[i]='blue';
|
||
let viz=renderArray(nums,{highlights:hl});
|
||
viz+=`<div style="margin-top:12px;padding:12px;background:#f8fafc;border-radius:8px;"><div>XOR = <b style="color:var(--blue);font-size:18px;">${s.xorResult}</b></div>`;
|
||
if(s.stage==='xor'){viz+=`<div style="display:flex;gap:8px;align-items:center;font-family:monospace;margin-top:8px;"><div style="padding:6px 12px;background:#e0e7ff;border-radius:6px;">${s.prevBin}</div><div style="font-weight:700;">⊕</div><div style="padding:6px 12px;background:#fef3c7;border-radius:6px;">${s.curBin}</div><div style="font-weight:700;">=</div><div style="padding:6px 12px;background:#dcfce7;border-radius:6px;font-weight:700;">${s.xorBin}</div></div><div style="margin-top:6px;font-size:12px;color:#64748b;">逐位异或：相同为0，不同为1</div>`;}
|
||
viz+='</div>';$('vizArea').innerHTML=viz;
|
||
$('detailContent').innerHTML='<div class="calc-block">'+s.msg+'</div>'+`<div class="current-answer">XOR = <b>${s.xorResult}</b></div>`;
|
||
if(s.stage==='done') $('resultContent').innerHTML=`<div class="final-answer">只出现一次的数字 = <b>${s.xorResult}</b></div>`;
|
||
$('hintText').textContent=s.msg;
|
||
const stages=['init→初始化','xor→异或','done→完成'];
|
||
$('pipeline').innerHTML=stages.map(x=>{const[k,l]=x.split('→');return`<span class="pipe-step ${s.stage===k?'active':''}">${l}</span>`;}).join('<i>→</i>');
|
||
}
|
||
function init() {
|
||
const sel=$('exampleSelect');examples.forEach((e,i)=>{sel.innerHTML+=`<option value="${i}">${e.label}</option>`;});
|
||
$('inputArea').value='[2,2,1]';buildSteps(examples[0].input);
|
||
stepCtrl=new StepController({onStep:render});stepCtrl.setSteps(steps.map((_,i)=>i));
|
||
$('stepInfo').textContent='步骤 1 / '+steps.length;stepCtrl.onStep=(idx)=>{render(idx);$('stepInfo').textContent=`步骤 ${idx+1} / ${steps.length}`;};
|
||
$('applyBtn').onclick=()=>{try{const a=JSON.parse($('inputArea').value);buildSteps(a);stepCtrl.setSteps(steps.map((_,i)=>i));render(0);}catch(e){alert('请输入合法JSON数组');}};
|
||
$('exampleSelect').onchange=()=>{const e=examples[parseInt($('exampleSelect').value)];$('inputArea').value=JSON.stringify(e.input);buildSteps(e.input);stepCtrl.setSteps(steps.map((_,i)=>i));render(0);};
|
||
$('prevBtn').onclick=()=>stepCtrl.prev();$('nextBtn').onclick=()=>stepCtrl.next();$('jumpBtn').onclick=()=>stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick=()=>{const on=stepCtrl.toggleAuto();$('autoBtn').textContent=on?'暂停':'自动播放';};
|
||
$('resetBtn').onclick=()=>{stepCtrl.reset();$('autoBtn').textContent='自动播放';};
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`def singleNumber(nums):
|
||
result = 0
|
||
for num in nums:
|
||
result ^= num
|
||
return result`, {lang:'Python'});
|
||
'''
|
||
|
||
def js_majority_element():
|
||
return r'''
|
||
const examples = [
|
||
{input:[3,2,3], label:'示例1: [3,2,3]'},
|
||
{input:[2,2,1,1,1,2,2], label:'示例2: [2,2,1,1,1,2,2]'},
|
||
{input:[1], label:'示例3: [1]'},
|
||
];
|
||
let nums, steps, stepCtrl;
|
||
function buildSteps(arr) {
|
||
nums=[...arr];steps=[];let c=null,cnt=0;const hist=[];
|
||
steps.push({stage:'init',msg:'Boyer-Moore投票：同+1异-1，为0换人',idx:-1,candidate:null,count:0,history:[]});
|
||
for(let i=0;i<arr.length;i++){
|
||
if(cnt===0){c=arr[i];cnt=1;hist.push({i,v:arr[i],c:cnt,a:'换'});steps.push({stage:'change',msg:`计数器0→换候选者为${arr[i]}`,idx:i,candidate:c,count:cnt,history:[...hist]});}
|
||
else if(arr[i]===c){cnt++;hist.push({i,v:arr[i],c:cnt,a:'同'});steps.push({stage:'same',msg:`${arr[i]}==${c}→+1 count=${cnt}`,idx:i,candidate:c,count:cnt,history:[...hist]});}
|
||
else{cnt--;hist.push({i,v:arr[i],c:cnt,a:'异'});steps.push({stage:'diff',msg:`${arr[i]}≠${c}→-1 count=${cnt}`,idx:i,candidate:c,count:cnt,history:[...hist]});}
|
||
}
|
||
steps.push({stage:'done',msg:`多数元素=${c}`,idx:-1,candidate:c,count:cnt,history:[...hist]});
|
||
}
|
||
function render(step) {
|
||
const s=steps[step];const hl={};if(s.idx>=0)hl[s.idx]='orange';for(let i=0;i<=Math.min(s.idx,nums.length-1);i++){if(nums[i]===s.candidate&&!hl[i])hl[i]='green';}
|
||
let viz=renderArray(nums,{highlights:hl});
|
||
viz+=`<div style="margin-top:12px;padding:12px;background:#f8fafc;border-radius:8px;display:flex;gap:16px;align-items:center;"><div><b>候选者：</b><span style="font-size:24px;font-weight:700;color:var(--blue);">${s.candidate!==null?s.candidate:'—'}</span></div><div><b>计数：</b><div style="display:flex;align-items:center;gap:4px;"><div style="width:${Math.max(0,s.count*28)}px;height:20px;background:var(--blue);border-radius:4px;"></div><span style="font-weight:700;">${s.count}</span></div></div></div>`;
|
||
if(s.history&&s.history.length>0){viz+='<div style="margin-top:12px;"><b>投票历史：</b></div><div style="display:flex;align-items:flex-end;gap:4px;height:60px;margin-top:4px;">';const mx=Math.max(...s.history.map(h=>Math.abs(h.c)),1);s.history.forEach(h=>{const pct=Math.max(4,(Math.abs(h.c)/mx)*50);const bg=h.a==='换'?'var(--orange)':h.a==='同'?'var(--green)':'var(--red)';viz+=`<div style="width:28px;height:${pct}px;background:${bg};border-radius:3px 3px 0 0;"></div>`;});viz+='</div><div style="display:flex;gap:4px;">';s.history.forEach(h=>{viz+=`<div style="width:28px;text-align:center;font-size:9px;">${h.v}</div>`;});viz+='</div>';}
|
||
$('vizArea').innerHTML=viz;
|
||
$('detailContent').innerHTML='<div class="calc-block">'+s.msg+'</div>'+`<div class="current-answer">候选:<b>${s.candidate}</b> 计数:<b>${s.count}</b></div>`;
|
||
if(s.stage==='done') $('resultContent').innerHTML=`<div class="final-answer">多数元素=<b>${s.candidate}</b></div>`;
|
||
$('hintText').textContent=s.msg;
|
||
const stages=['init→初始化','change→更换','same→相同','diff→不同','done→完成'];
|
||
$('pipeline').innerHTML=stages.map(x=>{const[k,l]=x.split('→');return`<span class="pipe-step ${s.stage===k?'active':''}">${l}</span>`;}).join('<i>→</i>');
|
||
}
|
||
function init() {
|
||
const sel=$('exampleSelect');examples.forEach((e,i)=>{sel.innerHTML+=`<option value="${i}">${e.label}</option>`;});
|
||
$('inputArea').value='[3,2,3]';buildSteps(examples[0].input);
|
||
stepCtrl=new StepController({onStep:render});stepCtrl.setSteps(steps.map((_,i)=>i));
|
||
$('stepInfo').textContent='步骤 1 / '+steps.length;stepCtrl.onStep=(idx)=>{render(idx);$('stepInfo').textContent=`步骤 ${idx+1} / ${steps.length}`;};
|
||
$('applyBtn').onclick=()=>{try{const a=JSON.parse($('inputArea').value);buildSteps(a);stepCtrl.setSteps(steps.map((_,i)=>i));render(0);}catch(e){alert('请输入合法JSON数组');}};
|
||
$('exampleSelect').onchange=()=>{const e=examples[parseInt($('exampleSelect').value)];$('inputArea').value=JSON.stringify(e.input);buildSteps(e.input);stepCtrl.setSteps(steps.map((_,i)=>i));render(0);};
|
||
$('prevBtn').onclick=()=>stepCtrl.prev();$('nextBtn').onclick=()=>stepCtrl.next();$('jumpBtn').onclick=()=>stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick=()=>{const on=stepCtrl.toggleAuto();$('autoBtn').textContent=on?'暂停':'自动播放';};
|
||
$('resetBtn').onclick=()=>{stepCtrl.reset();$('autoBtn').textContent='自动播放';};
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`def majorityElement(nums):
|
||
candidate = None
|
||
count = 0
|
||
for num in nums:
|
||
if count == 0:
|
||
candidate = num
|
||
count += (1 if num == candidate else -1)
|
||
return candidate`, {lang:'Python'});
|
||
'''
|
||
|
||
def js_sort_colors():
|
||
return r'''
|
||
const examples = [
|
||
{input:[2,0,2,1,1,0], label:'示例1: [2,0,2,1,1,0]'},
|
||
{input:[2,0,1], label:'示例2: [2,0,1]'},
|
||
{input:[0,0,1,1,2,2], label:'示例3: 已排序'},
|
||
];
|
||
let nums, steps, stepCtrl;
|
||
const CM={0:['#fee2e2','#ef4444'],1:['#fef9c3','#eab308'],2:['#dbeafe','#3b82f6']};
|
||
function buildSteps(arr) {
|
||
nums=[...arr];steps=[];let lo=0,mid=0,hi=arr.length-1;
|
||
steps.push({stage:'init',msg:'荷兰国旗三指针: lo左全0, mid~hi待处理, hi右全2',arr:[...nums],lo,mid,hi});
|
||
while(mid<=hi){
|
||
if(nums[mid]===0){steps.push({stage:'check0',msg:`nums[${mid}]=0→交换lo=${lo}`,arr:[...nums],lo,mid,hi});[nums[lo],nums[mid]]=[nums[mid],nums[lo]];lo++;mid++;steps.push({stage:'swap',msg:`→[${nums}] lo=${lo} mid=${mid}`,arr:[...nums],lo,mid,hi});}
|
||
else if(nums[mid]===1){steps.push({stage:'skip',msg:`nums[${mid}]=1→跳过`,arr:[...nums],lo,mid,hi});mid++;steps.push({stage:'advance',msg:`mid→${mid}`,arr:[...nums],lo,mid,hi});}
|
||
else{steps.push({stage:'check2',msg:`nums[${mid}]=2→交换hi=${hi}`,arr:[...nums],lo,mid,hi});[nums[mid],nums[hi]]=[nums[hi],nums[mid]];hi--;steps.push({stage:'swap',msg:`→[${nums}] hi=${hi}`,arr:[...nums],lo,mid,hi});}
|
||
}
|
||
steps.push({stage:'done',msg:`完成: [${nums}]`,arr:[...nums],lo,mid,hi});
|
||
}
|
||
function render(step) {
|
||
const s=steps[step];
|
||
let viz='<div class="nums-line">';s.arr.forEach((v,i)=>{const[bg,fg]=CM[v];let bd='2px solid transparent';if(i===s.lo)bd='2px solid var(--blue)';else if(i===s.mid&&s.mid<=s.hi)bd='2px solid var(--green)';else if(i===s.hi)bd='2px solid var(--purple)';viz+=`<span class="chip-group"><span class="chip" style="background:${bg};color:${fg};border:${bd};min-width:40px;">${v}</span><span class="chip-index">${i}</span></span>`;});viz+='</div>';
|
||
viz+='<div class="nums-line" style="margin-top:-4px;">';s.arr.forEach((v,i)=>{let lb='';if(i===s.lo)lb='lo';if(i===s.mid&&s.mid<=s.hi)lb=lb?lb+'/mid':'mid';if(i===s.hi)lb=lb?lb+'/hi':'hi';viz+=`<span style="min-width:40px;text-align:center;font-size:10px;font-weight:700;color:${i===s.lo?'var(--blue)':i===s.mid&&s.mid<=s.hi?'var(--green)':i===s.hi?'var(--purple)':'transparent'};">${lb}</span>`;});viz+='</div>';
|
||
viz+='<div style="margin-top:8px;font-size:12px;display:flex;gap:12px;"><span style="color:#ef4444;">■0红</span><span style="color:#eab308;">■1白</span><span style="color:#3b82f6;">■2蓝</span></div>';
|
||
$('vizArea').innerHTML=viz;$('detailContent').innerHTML='<div class="calc-block">'+s.msg+'</div>';
|
||
if(s.stage==='done') $('resultContent').innerHTML=`<div class="final-answer">排序=<b>[${s.arr}]</b></div>`;
|
||
else $('resultContent').innerHTML=`<div class="current-answer">[${s.arr}] lo=${s.lo} mid=${s.mid} hi=${s.hi}</div>`;
|
||
$('hintText').textContent=s.msg;
|
||
const stages=['init→初始化','check0→0','check2→2','swap→交换','skip→跳过','advance→前进','done→完成'];
|
||
$('pipeline').innerHTML=stages.map(x=>{const[k,l]=x.split('→');return`<span class="pipe-step ${s.stage===k?'active':''}">${l}</span>`;}).join('<i>→</i>');
|
||
}
|
||
function init() {
|
||
const sel=$('exampleSelect');examples.forEach((e,i)=>{sel.innerHTML+=`<option value="${i}">${e.label}</option>`;});
|
||
$('inputArea').value='[2,0,2,1,1,0]';buildSteps(examples[0].input);
|
||
stepCtrl=new StepController({onStep:render});stepCtrl.setSteps(steps.map((_,i)=>i));
|
||
$('stepInfo').textContent='步骤 1 / '+steps.length;stepCtrl.onStep=(idx)=>{render(idx);$('stepInfo').textContent=`步骤 ${idx+1} / ${steps.length}`;};
|
||
$('applyBtn').onclick=()=>{try{const a=JSON.parse($('inputArea').value);buildSteps(a);stepCtrl.setSteps(steps.map((_,i)=>i));render(0);}catch(e){alert('请输入0,1,2的JSON数组');}};
|
||
$('exampleSelect').onchange=()=>{const e=examples[parseInt($('exampleSelect').value)];$('inputArea').value=JSON.stringify(e.input);buildSteps(e.input);stepCtrl.setSteps(steps.map((_,i)=>i));render(0);};
|
||
$('prevBtn').onclick=()=>stepCtrl.prev();$('nextBtn').onclick=()=>stepCtrl.next();$('jumpBtn').onclick=()=>stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick=()=>{const on=stepCtrl.toggleAuto();$('autoBtn').textContent=on?'暂停':'自动播放';};
|
||
$('resetBtn').onclick=()=>{stepCtrl.reset();$('autoBtn').textContent='自动播放';};
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`def sortColors(nums):
|
||
lo, mid, hi = 0, 0, len(nums) - 1
|
||
while mid <= hi:
|
||
if nums[mid] == 0:
|
||
nums[lo], nums[mid] = nums[mid], nums[lo]
|
||
lo += 1; mid += 1
|
||
elif nums[mid] == 1:
|
||
mid += 1
|
||
else:
|
||
nums[mid], nums[hi] = nums[hi], nums[mid]
|
||
hi -= 1`, {lang:'Python'});
|
||
'''
|
||
|
||
def js_next_permutation():
|
||
return r'''
|
||
const examples = [
|
||
{input:[1,2,3], label:'示例1: [1,2,3]'},
|
||
{input:[3,2,1], label:'示例2: [3,2,1]'},
|
||
{input:[1,1,5], label:'示例3: [1,1,5]'},
|
||
{input:[1,3,2], label:'示例4: [1,3,2]'},
|
||
];
|
||
let nums, steps, stepCtrl;
|
||
function buildSteps(arr) {
|
||
nums=[...arr];steps=[];const n=nums.length;
|
||
steps.push({stage:'init',msg:'①找下降点 ②找交换目标 ③反转后缀',arr:[...nums],phase:0,i:-1,j:-1});
|
||
let i=n-2;while(i>=0&&nums[i]>=nums[i+1])i--;
|
||
if(i<0){steps.push({stage:'no_desc',msg:'降序=最大排列，直接反转',arr:[...nums],phase:1,i:-1,j:-1});}
|
||
else{steps.push({stage:'found_desc',msg:`下降点: nums[${i}]=${nums[i]} < nums[${i+1}]=${nums[i+1]}`,arr:[...nums],phase:1,i,j:-1});
|
||
let j=n-1;while(nums[j]<=nums[i])j--;steps.push({stage:'found_swap',msg:`交换目标: nums[${j}]=${nums[j]}`,arr:[...nums],phase:2,i,j});
|
||
[nums[i],nums[j]]=[nums[j],nums[i]];steps.push({stage:'swap',msg:`交换→[${nums}]`,arr:[...nums],phase:2,i,j});}
|
||
let left=i+1,right=n-1;while(left<right){[nums[left],nums[right]]=[nums[right],nums[left]];steps.push({stage:'reverse',msg:`反转: swap[${left}],[${right}]→[${nums}]`,arr:[...nums],phase:3,i,j:left,k:right});left++;right--;}
|
||
steps.push({stage:'done',msg:`下一个排列[${nums}]`,arr:[...nums],phase:4,i:-1,j:-1});
|
||
}
|
||
function render(step) {
|
||
const s=steps[step];const hl={};
|
||
if(s.i>=0)hl[s.i]='orange';if(s.j>=0&&s.stage!=='reverse')hl[s.j]='purple';
|
||
if(s.stage==='reverse'){if(s.j>=0)hl[s.j]='blue';if(s.k>=0)hl[s.k]='blue';}
|
||
if(s.stage==='done'||s.stage==='reverse'){const ds=s.i>=0?s.i+1:0;for(let k=ds;k<s.arr.length;k++)if(!hl[k])hl[k]='green';}
|
||
let viz=renderArray(s.arr,{highlights:hl});
|
||
const phases=['①找下降点','②找交换','③反转','③反转','✅完成'];
|
||
viz+=`<div style="margin-top:10px;"><b>阶段：</b>${phases[Math.min(s.phase,4)]}</div>`;
|
||
$('vizArea').innerHTML=viz;$('detailContent').innerHTML='<div class="calc-block">'+s.msg+'</div>';
|
||
if(s.stage==='done') $('resultContent').innerHTML=`<div class="final-answer">下一个排列=<b>[${s.arr}]</b></div>`;
|
||
$('hintText').textContent=s.msg;
|
||
const stages=['init→初始化','found_desc→下降点','found_swap→目标','swap→交换','reverse→反转','no_desc→无下降','done→完成'];
|
||
$('pipeline').innerHTML=stages.map(x=>{const[k,l]=x.split('→');return`<span class="pipe-step ${s.stage===k?'active':''}">${l}</span>`;}).join('<i>→</i>');
|
||
}
|
||
function init() {
|
||
const sel=$('exampleSelect');examples.forEach((e,i)=>{sel.innerHTML+=`<option value="${i}">${e.label}</option>`;});
|
||
$('inputArea').value='[1,2,3]';buildSteps(examples[0].input);
|
||
stepCtrl=new StepController({onStep:render});stepCtrl.setSteps(steps.map((_,i)=>i));
|
||
$('stepInfo').textContent='步骤 1 / '+steps.length;stepCtrl.onStep=(idx)=>{render(idx);$('stepInfo').textContent=`步骤 ${idx+1} / ${steps.length}`;};
|
||
$('applyBtn').onclick=()=>{try{const a=JSON.parse($('inputArea').value);buildSteps(a);stepCtrl.setSteps(steps.map((_,i)=>i));render(0);}catch(e){alert('请输入合法JSON数组');}};
|
||
$('exampleSelect').onchange=()=>{const e=examples[parseInt($('exampleSelect').value)];$('inputArea').value=JSON.stringify(e.input);buildSteps(e.input);stepCtrl.setSteps(steps.map((_,i)=>i));render(0);};
|
||
$('prevBtn').onclick=()=>stepCtrl.prev();$('nextBtn').onclick=()=>stepCtrl.next();$('jumpBtn').onclick=()=>stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick=()=>{const on=stepCtrl.toggleAuto();$('autoBtn').textContent=on?'暂停':'自动播放';};
|
||
$('resetBtn').onclick=()=>{stepCtrl.reset();$('autoBtn').textContent='自动播放';};
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`def nextPermutation(nums):
|
||
i = len(nums) - 2
|
||
while i >= 0 and nums[i] >= nums[i+1]:
|
||
i -= 1
|
||
if i >= 0:
|
||
j = len(nums) - 1
|
||
while nums[j] <= nums[i]:
|
||
j -= 1
|
||
nums[i], nums[j] = nums[j], nums[i]
|
||
left, right = i + 1, len(nums) - 1
|
||
while left < right:
|
||
nums[left], nums[right] = nums[right], nums[left]
|
||
left += 1; right -= 1`, {lang:'Python'});
|
||
'''
|
||
|
||
def js_find_the_duplicate_number():
|
||
return r'''
|
||
const examples = [
|
||
{input:[1,3,4,2,2], label:'示例1: [1,3,4,2,2]'},
|
||
{input:[3,1,3,4,2], label:'示例2: [3,1,3,4,2]'},
|
||
{input:[3,3,3,3,3], label:'示例3: [3,3,3,3,3]'},
|
||
];
|
||
let nums, steps, stepCtrl;
|
||
function buildSteps(arr) {
|
||
nums=[...arr];steps=[];
|
||
steps.push({stage:'init',msg:'数组→链表 f(x)=nums[x]，必有环！快慢指针找环入口=重复数',arr:[...nums],slow:0,fast:0,phase:0});
|
||
let slow=0,fast=0;
|
||
steps.push({stage:'start',msg:'起点0',arr:[...nums],slow:0,fast:0,phase:1});
|
||
do{slow=arr[slow];fast=arr[arr[fast]];steps.push({stage:'move',msg:`慢→${slow} 快→${fast}`,arr:[...nums],slow,fast,phase:1});}while(slow!==fast);
|
||
steps.push({stage:'meet',msg:`相遇于${slow}！`,arr:[...nums],slow,fast,phase:1});
|
||
let p1=0,p2=slow;steps.push({stage:'phase2',msg:'阶段2:从0和相遇点同速走',arr:[...nums],slow:p1,fast:p2,phase:2});
|
||
while(p1!==p2){p1=arr[p1];p2=arr[p2];steps.push({stage:'seek',msg:`ptr1→${p1} ptr2→${p2}`,arr:[...nums],slow:p1,fast:p2,phase:2});}
|
||
steps.push({stage:'done',msg:`环入口=${p1}即重复数`,arr:[...nums],slow:p1,fast:p2,phase:3});
|
||
}
|
||
function render(step) {
|
||
const s=steps[step];
|
||
let viz='<div style="font-weight:600;color:#64748b;margin-bottom:8px;">数组→链表：</div><div class="nums-line">';
|
||
s.arr.forEach((v,i)=>{viz+=`<span class="chip-group"><span class="chip ${i===s.slow||i===s.fast?'purple':'default'}" style="min-width:40px;">${v}</span><span class="chip-index">${i}</span></span>`;});viz+='</div>';
|
||
viz+=`<div style="font-size:12px;color:#64748b;margin-top:4px;">f(index) = nums[index]</div>`;
|
||
viz+=`<div style="margin-top:12px;padding:12px;background:#f8fafc;border-radius:8px;">`;
|
||
if(s.phase===1){viz+=`<div><b>🏃慢：</b><span style="color:var(--blue);font-weight:700;font-size:18px;">${s.slow}</span></div><div><b>🐇快：</b><span style="color:var(--purple);font-weight:700;font-size:18px;">${s.fast}</span></div>`;}
|
||
else if(s.phase===2){viz+=`<div><b>📍ptr1：</b><span style="color:var(--blue);font-weight:700;font-size:18px;">${s.slow}</span></div><div><b>📍ptr2：</b><span style="color:var(--purple);font-weight:700;font-size:18px;">${s.fast}</span></div>`;}
|
||
else if(s.phase===3){viz+=`<div style="font-size:20px;font-weight:700;color:var(--green);">🎯重复数=${s.slow}</div>`;}
|
||
viz+='</div>';
|
||
if(s.phase>=1){viz+='<div style="margin-top:12px;"><b>链表路径：</b></div><div style="display:flex;flex-wrap:wrap;gap:4px;margin-top:4px;align-items:center;">';const path=[0];let cur=0;const seen=new Set([0]);for(let k=0;k<nums.length+2;k++){cur=nums[cur];path.push(cur);if(seen.has(cur))break;seen.add(cur);}
|
||
path.forEach((node,idx)=>{const isS=node===s.slow,isF=node===s.fast;let bg='#f1f5f9',bd='2px solid #e2e8f0';if(isS&&isF){bg='#dcfce7';bd='2px solid #16a34a';}else if(isS){bg='#dbeafe';bd='2px solid #3b82f6';}else if(isF){bg='#f3e8ff';bd='2px solid #8b5cf6';}
|
||
viz+=`<div style="padding:6px 12px;background:${bg};border:${bd};border-radius:8px;font-weight:700;">${node}</div>`;if(idx<path.length-1)viz+=`<div style="color:#94a3b8;">→</div>`;});viz+='</div>';}
|
||
$('vizArea').innerHTML=viz;
|
||
const pn=['准备','阶段1:找相遇','阶段2:找环入口','完成'];
|
||
$('detailContent').innerHTML='<div class="calc-block">'+s.msg+'</div>'+`<div class="current-answer">${pn[s.phase]}</div>`;
|
||
if(s.stage==='done') $('resultContent').innerHTML=`<div class="final-answer">重复数=<b>${s.slow}</b></div>`;
|
||
$('hintText').textContent=s.msg;
|
||
const stages=['init→初始化','start→出发','move→移动','meet→相遇','phase2→阶段2','seek→寻找','done→完成'];
|
||
$('pipeline').innerHTML=stages.map(x=>{const[k,l]=x.split('→');return`<span class="pipe-step ${s.stage===k?'active':''}">${l}</span>`;}).join('<i>→</i>');
|
||
}
|
||
function init() {
|
||
const sel=$('exampleSelect');examples.forEach((e,i)=>{sel.innerHTML+=`<option value="${i}">${e.label}</option>`;});
|
||
$('inputArea').value='[1,3,4,2,2]';buildSteps(examples[0].input);
|
||
stepCtrl=new StepController({onStep:render});stepCtrl.setSteps(steps.map((_,i)=>i));
|
||
$('stepInfo').textContent='步骤 1 / '+steps.length;stepCtrl.onStep=(idx)=>{render(idx);$('stepInfo').textContent=`步骤 ${idx+1} / ${steps.length}`;};
|
||
$('applyBtn').onclick=()=>{try{const a=JSON.parse($('inputArea').value);buildSteps(a);stepCtrl.setSteps(steps.map((_,i)=>i));render(0);}catch(e){alert('请输入1~n的n+1个数的JSON数组');}};
|
||
$('exampleSelect').onchange=()=>{const e=examples[parseInt($('exampleSelect').value)];$('inputArea').value=JSON.stringify(e.input);buildSteps(e.input);stepCtrl.setSteps(steps.map((_,i)=>i));render(0);};
|
||
$('prevBtn').onclick=()=>stepCtrl.prev();$('nextBtn').onclick=()=>stepCtrl.next();$('jumpBtn').onclick=()=>stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick=()=>{const on=stepCtrl.toggleAuto();$('autoBtn').textContent=on?'暂停':'自动播放';};
|
||
$('resetBtn').onclick=()=>{stepCtrl.reset();$('autoBtn').textContent='自动播放';};
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`def findDuplicate(nums):
|
||
slow = fast = 0
|
||
while True:
|
||
slow = nums[slow]
|
||
fast = nums[nums[fast]]
|
||
if slow == fast: break
|
||
slow = 0
|
||
while slow != fast:
|
||
slow = nums[slow]
|
||
fast = nums[fast]
|
||
return slow`, {lang:'Python'});
|
||
'''
|
||
|
||
|
||
|
||
# ========== Stubs for future algorithms ==========
|
||
|
||
# ========== Problem → JS generator mapping ==========
|
||
ALGO_MAP = {
|
||
'two-sum': js_two_sum,
|
||
'group-anagrams': js_group_anagrams,
|
||
'longest-consecutive-sequence': js_longest_consecutive,
|
||
'move-zeros': js_move_zeros,
|
||
'container-with-most-water': js_container_with_most_water,
|
||
'3sum': js_3sum,
|
||
'trapping-rain-water': js_trapping_rain_water,
|
||
# 图论
|
||
'number-of-islands': js_number_of_islands,
|
||
'rotting-oranges': js_rotting_oranges,
|
||
'course-schedule': js_course_schedule,
|
||
'implement-trie-prefix-tree': js_implement_trie_prefix_tree,
|
||
# 回溯
|
||
'permutations': js_permutations,
|
||
'subsets': js_subsets,
|
||
'letter-combinations-of-a-phone-number': js_letter_combinations_of_a_phone_number,
|
||
'combination-sum': js_combination_sum,
|
||
'generate-parentheses': js_generate_parentheses,
|
||
'word-search': js_word_search,
|
||
'palindrome-partitioning': js_palindrome_partitioning,
|
||
'n-queens': js_n_queens,
|
||
# 链表
|
||
'intersection-of-two-linked-lists': js_intersection_of_two_linked_lists,
|
||
'reverse-linked-list': js_reverse_linked_list,
|
||
'palindrome-linked-list': js_palindrome_linked_list,
|
||
'linked-list-cycle': js_linked_list_cycle,
|
||
'linked-list-cycle-ii': js_linked_list_cycle_ii,
|
||
'merge-two-sorted-lists': js_merge_two_sorted_lists,
|
||
'add-two-numbers': js_add_two_numbers,
|
||
'remove-nth-node-from-end-of-list': js_remove_nth_node_from_end_of_list,
|
||
'swap-nodes-in-pairs': js_swap_nodes_in_pairs,
|
||
'reverse-nodes-in-k-group': js_reverse_nodes_in_k_group,
|
||
'copy-list-with-random-pointer': js_copy_list_with_random_pointer,
|
||
'sort-list': js_sort_list,
|
||
'merge-k-sorted-lists': js_merge_k_sorted_lists,
|
||
'lru-cache': js_lru_cache,
|
||
# 二叉树
|
||
'binary-tree-inorder-traversal': js_binary_tree_inorder_traversal,
|
||
'maximum-depth-of-binary-tree': js_maximum_depth_of_binary_tree,
|
||
'invert-binary-tree': js_invert_binary_tree,
|
||
'symmetric-tree': js_symmetric_tree,
|
||
'diameter-of-binary-tree': js_diameter_of_binary_tree,
|
||
'binary-tree-level-order-traversal': js_binary_tree_level_order_traversal,
|
||
'convert-sorted-array-to-bst': js_convert_sorted_array_to_bst,
|
||
'validate-binary-search-tree': js_validate_binary_search_tree,
|
||
'kth-smallest-element-in-a-bst': js_kth_smallest_element_in_a_bst,
|
||
'binary-tree-right-side-view': js_binary_tree_right_side_view,
|
||
'flatten-binary-tree-to-linked-list': js_flatten_binary_tree_to_linked_list,
|
||
'construct-binary-tree-from-preorder-and-inorder': js_construct_binary_tree_from_preorder_and_inorder,
|
||
'path-sum-iii': js_path_sum_iii,
|
||
'lowest-common-ancestor-of-a-binary-tree': js_lowest_common_ancestor_of_a_binary_tree,
|
||
'binary-tree-maximum-path-sum': js_binary_tree_maximum_path_sum,
|
||
# 多维动态规划
|
||
'unique-paths': js_unique_paths,
|
||
'minimum-path-sum': js_minimum_path_sum,
|
||
'longest-palindromic-substring': js_longest_palindromic_substring,
|
||
'longest-common-subsequence': js_longest_common_subsequence,
|
||
'edit-distance': js_edit_distance,
|
||
# 技巧
|
||
'single-number': js_single_number,
|
||
'majority-element': js_majority_element,
|
||
'sort-colors': js_sort_colors,
|
||
'next-permutation': js_next_permutation,
|
||
'find-the-duplicate-number': js_find_the_duplicate_number,
|
||
# 动态规划
|
||
'climbing-stairs': js_climbing_stairs,
|
||
'pascals-triangle': js_pascals_triangle,
|
||
'house-robber': js_house_robber,
|
||
'perfect-squares': js_perfect_squares,
|
||
'coin-change': js_coin_change,
|
||
'word-break': js_word_break,
|
||
'longest-increasing-subsequence': js_longest_increasing_subsequence,
|
||
'maximum-product-subarray': js_maximum_product_subarray,
|
||
'partition-equal-subset-sum': js_partition_equal_subset_sum,
|
||
'longest-valid-parentheses': js_longest_valid_parentheses,
|
||
}
|
||
|
||
# ========== Generate a generic template for problems without specific JS ==========
|
||
def js_generic():
|
||
return r'''
|
||
const examples = [{input: [], label: '默认示例'}]; // TODO
|
||
let steps, stepCtrl;
|
||
|
||
function buildSteps() {
|
||
steps = [];
|
||
steps.push({stage:'start', msg:'算法开始执行...'});
|
||
steps.push({stage:'done', msg:'算法执行完毕'});
|
||
}
|
||
|
||
function render(step) {
|
||
const s = steps[step];
|
||
$('vizArea').innerHTML = '<div class="formula-box">' + s.msg + '</div>';
|
||
$('detailContent').innerHTML = '<div class="calc-block">' + s.msg + '</div>';
|
||
if (s.stage === 'done') {
|
||
$('resultContent').innerHTML = '<div class="final-answer">完成！请参考代码实现。</div>';
|
||
}
|
||
$('hintText').textContent = s.msg;
|
||
}
|
||
|
||
function init() {
|
||
buildSteps();
|
||
stepCtrl = new StepController({onStep: render});
|
||
stepCtrl.setSteps(steps.map((_,i)=>i));
|
||
$('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
stepCtrl.onStep = (idx) => { render(idx); $('stepInfo').textContent = `步骤 ${idx+1} / ${steps.length}`; };
|
||
$('applyBtn').onclick = () => { buildSteps(); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0); };
|
||
$('prevBtn').onclick = () => stepCtrl.prev();
|
||
$('nextBtn').onclick = () => stepCtrl.next();
|
||
$('jumpBtn').onclick = () => stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick = () => { const on = stepCtrl.toggleAuto(); $('autoBtn').textContent = on ? '暂停' : '自动播放'; };
|
||
$('resetBtn').onclick = () => { stepCtrl.reset(); $('autoBtn').textContent = '自动播放'; };
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`# TODO: 待补充`, {lang:'Python'});
|
||
'''
|
||
|
||
|
||
def generate_problem(p):
|
||
slug = p['slug']
|
||
gen_fn = ALGO_MAP.get(slug)
|
||
if gen_fn:
|
||
algo_js = gen_fn()
|
||
else:
|
||
algo_js = js_generic()
|
||
html = gen_html(p, algo_js)
|
||
out_dir = os.path.join(BASE, slug)
|
||
os.makedirs(out_dir, exist_ok=True)
|
||
out_path = os.path.join(out_dir, 'index.html')
|
||
with open(out_path, 'w', encoding='utf-8') as f:
|
||
f.write(html)
|
||
return out_path
|
||
|
||
|
||
def main():
|
||
import argparse
|
||
parser = argparse.ArgumentParser()
|
||
parser.add_argument('--all', action='store_true')
|
||
parser.add_argument('--category', type=str, default=None)
|
||
parser.add_argument('--slugs', type=str, default=None)
|
||
args = parser.parse_args()
|
||
|
||
targets = ALL_PROBLEMS
|
||
if args.category:
|
||
targets = [p for p in targets if p['category'] == args.category]
|
||
elif args.slugs:
|
||
slug_list = [s.strip() for s in args.slugs.split(',')]
|
||
targets = [p for p in targets if p['slug'] in slug_list]
|
||
elif not args.all:
|
||
print("请指定 --all, --category, 或 --slugs")
|
||
sys.exit(1)
|
||
|
||
for p in targets:
|
||
path = generate_problem(p)
|
||
print(f'✅ {p["slug"]:50s} → {path}')
|
||
|
||
print(f'\n生成完成！共 {len(targets)} 个页面')
|
||
|
||
|
||
if __name__ == '__main__':
|
||
main()
|