230 lines
9.1 KiB
HTML
230 lines
9.1 KiB
HTML
|
<!DOCTYPE html>
|
|||
|
|
<html lang="zh-Hans">
|
|||
|
|
<head>
|
|||
|
|
<meta charset="UTF-8">
|
|||
|
|
<meta name="viewport" content="width=device-width, initial-scale=1.0">
|
|||
|
|
<title>069. 有效的括号 – 图解</title>
|
|||
|
|
<link rel="stylesheet" href="../shared/style.css">
|
|||
|
|
<style>
|
|||
|
|
.vis-area { min-height: 120px; padding: 16px 0; }
|
|||
|
|
.code-section { margin-top: 16px; }
|
|||
|
|
.char-box { display:inline-flex; align-items:center; justify-content:center; width:36px; height:36px; border-radius:8px; font-weight:700; font-size:16px; margin:2px; transition:all 0.25s; }
|
|||
|
|
.char-box.default { background:#e2e8f0; color:var(--text); }
|
|||
|
|
.char-box.current { background:#fef3c7; color:#92400e; box-shadow:0 0 0 3px rgba(245,158,11,0.3); transform:scale(1.15); }
|
|||
|
|
.char-box.matched { background:#dcfce7; color:#166534; }
|
|||
|
|
.char-box.error { background:#fee2e2; color:#991b1b; }
|
|||
|
|
.match-pair { display:inline-flex; gap:4px; padding:4px 8px; background:#f0fdf4; border-radius:6px; margin:2px; font-size:14px; }
|
|||
|
|
.dual-stack { display:flex; gap:16px; flex-wrap:wrap; }
|
|||
|
|
.dual-stack > div { flex:1; min-width:120px; }
|
|||
|
|
</style>
|
|||
|
|
</head>
|
|||
|
|
<body>
|
|||
|
|
<div class="container">
|
|||
|
|
<h1>🟢 069. 有效的括号 <span class="badge easy">简单</span></h1>
|
|||
|
|
<p class="subtitle">分类：栈 ｜ LeetCode Hot 100</p>
|
|||
|
|
|
|||
|
|
<div class="controls" id="controls">
|
|||
|
|
<label for="inputArea">输入：</label>
|
|||
|
|
<input type="text" id="inputArea" placeholder="s="()[]{}"">
|
|||
|
|
<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() {
|
|||
|
|
const examples = [
|
|||
|
|
{s:'()[]{}', label:'示例1: ()[]{}'},
|
|||
|
|
{s:'()', label:'示例2: ()'},
|
|||
|
|
{s:'([)]', label:'示例3: ([)] (无效)'},
|
|||
|
|
{s:'{[]}', label:'示例4: {[]}'},
|
|||
|
|
{s:'(]', label:'示例5: (] (无效)'},
|
|||
|
|
];
|
|||
|
|
let sStr, steps, stepCtrl;
|
|||
|
|
|
|||
|
|
function buildSteps(s) {
|
|||
|
|
sStr = s;
|
|||
|
|
steps = [];
|
|||
|
|
const stack = [];
|
|||
|
|
const matches = {'(':')', '[':']', '{':'}'};
|
|||
|
|
const matchList = [];
|
|||
|
|
|
|||
|
|
steps.push({stage:'init', msg:`开始遍历字符串 "${s}"`, idx:-1, stack:[], charStatus:{}, matchList:[], valid:true, error:false});
|
|||
|
|
|
|||
|
|
for (let i = 0; i < s.length; i++) {
|
|||
|
|
const c = s[i];
|
|||
|
|
const charStatus = {};
|
|||
|
|
for (let j = 0; j < i; j++) charStatus[j] = 'matched';
|
|||
|
|
charStatus[i] = 'current';
|
|||
|
|
|
|||
|
|
if (c in matches) {
|
|||
|
|
// Opening bracket
|
|||
|
|
stack.push(c);
|
|||
|
|
steps.push({stage:'push', msg:`'${c}' 是左括号，入栈。栈：[${stack.join(',')}]`, idx:i, stack:[...stack], charStatus, matchList:[...matchList.map(m=>[...m])], valid:true, error:false});
|
|||
|
|
} else {
|
|||
|
|
// Closing bracket
|
|||
|
|
if (stack.length === 0) {
|
|||
|
|
steps.push({stage:'error', msg:`'${c}' 是右括号，但栈为空，无匹配！无效。`, idx:i, stack:[], charStatus, matchList:[...matchList.map(m=>[...m])], valid:false, error:true});
|
|||
|
|
return;
|
|||
|
|
}
|
|||
|
|
const top = stack[stack.length - 1];
|
|||
|
|
if (matches[top] === c) {
|
|||
|
|
stack.pop();
|
|||
|
|
matchList.push([top, c]);
|
|||
|
|
charStatus[i] = 'matched';
|
|||
|
|
const matchIdx = i - 1; // approximate the paired bracket
|
|||
|
|
steps.push({stage:'match', msg:`'${c}' 匹配栈顶 '${top}' ✓，出栈。栈：[${stack.join(',')}]`, idx:i, stack:[...stack], charStatus, matchList:[...matchList.map(m=>[...m])], valid:true, error:false});
|
|||
|
|
} else {
|
|||
|
|
steps.push({stage:'error', msg:`'${c}' 不匹配栈顶 '${top}'（期望 '${matches[top]}'）✗ 无效！`, idx:i, stack:[...stack], charStatus, matchList:[...matchList.map(m=>[...m])], valid:false, error:true});
|
|||
|
|
return;
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
if (stack.length > 0) {
|
|||
|
|
steps.push({stage:'error', msg:`遍历完毕,但栈非空 [${stack.join(',')}]，括号不匹配！`, idx:s.length, stack:[...stack], charStatus:{}, matchList:[...matchList.map(m=>[...m])], valid:false, error:true});
|
|||
|
|
} else {
|
|||
|
|
steps.push({stage:'done', msg:`遍历完毕,栈为空，所有括号匹配 ✓`, idx:s.length, stack:[], charStatus:{}, matchList:[...matchList.map(m=>[...m])], valid:true, error:false});
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
function render(step) {
|
|||
|
|
const s = steps[step];
|
|||
|
|
const str = sStr;
|
|||
|
|
|
|||
|
|
// String visualization
|
|||
|
|
let viz = '<div style="margin-bottom:10px;"><b>字符串：</b><div class="nums-line">';
|
|||
|
|
for (let i = 0; i < str.length; i++) {
|
|||
|
|
const cls = s.charStatus[i] || 'default';
|
|||
|
|
viz += `<span class="char-box ${cls}">${str[i]}</span>`;
|
|||
|
|
}
|
|||
|
|
viz += '</div></div>';
|
|||
|
|
|
|||
|
|
// Stack + Matched pairs side by side
|
|||
|
|
viz += '<div class="dual-stack">';
|
|||
|
|
viz += '<div><b>栈：</b>';
|
|||
|
|
viz += renderStack(s.stack.map(c => c), {topIndex: s.stack.length - 1});
|
|||
|
|
viz += '</div>';
|
|||
|
|
if (s.matchList.length > 0) {
|
|||
|
|
viz += '<div><b>已匹配：</b><div style="margin-top:4px;">';
|
|||
|
|
s.matchList.forEach(([l,r]) => {
|
|||
|
|
viz += `<span class="match-pair">${l} ${r}</span>`;
|
|||
|
|
});
|
|||
|
|
viz += '</div></div>';
|
|||
|
|
}
|
|||
|
|
viz += '</div>';
|
|||
|
|
|
|||
|
|
if (s.error) {
|
|||
|
|
viz += `<div style="margin-top:10px;padding:8px 14px;background:#fee2e2;border-radius:8px;color:#991b1b;font-weight:600;">❌ 匹配失败</div>`;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
$('vizArea').innerHTML = viz;
|
|||
|
|
|
|||
|
|
let detail = `<div class="calc-block">${s.msg}</div>`;
|
|||
|
|
if (s.stack.length > 0) {
|
|||
|
|
detail += `<div style="margin-top:6px;font-size:13px;color:var(--text-secondary);">栈顶 = '${s.stack[s.stack.length-1]}'</div>`;
|
|||
|
|
}
|
|||
|
|
$('detailContent').innerHTML = detail;
|
|||
|
|
|
|||
|
|
if (s.stage === 'done') {
|
|||
|
|
$('resultContent').innerHTML = `<div class="final-answer">返回 <b>true</b><br>所有括号有效匹配<br>时间复杂度 O(n)</div>`;
|
|||
|
|
} else if (s.stage === 'error') {
|
|||
|
|
$('resultContent').innerHTML = `<div class="final-answer" style="border-color:#f87171;background:#fef2f2;">返回 <b>false</b><br>括号不匹配</div>`;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
$('hintText').textContent = s.msg;
|
|||
|
|
const stages = ['init→开始','push→入栈','match→匹配','error→失败','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 = 's="()[]{}"';
|
|||
|
|
|
|||
|
|
buildSteps(examples[0].s);
|
|||
|
|
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(/s="([^"]+)"/);
|
|||
|
|
if (!m) { alert('格式: s="()[]{}"'); return; }
|
|||
|
|
buildSteps(m[1]);
|
|||
|
|
stepCtrl.setSteps(steps.map((_,i)=>i)); render(0);
|
|||
|
|
$('stepInfo').textContent = `步骤 1 / ${steps.length}`;
|
|||
|
|
} catch(e) { alert('输入格式错误'); }
|
|||
|
|
};
|
|||
|
|
$('exampleSelect').onchange = () => {
|
|||
|
|
const e = examples[parseInt($('exampleSelect').value)];
|
|||
|
|
$('inputArea').value = `s="${e.s}"`;
|
|||
|
|
buildSteps(e.s);
|
|||
|
|
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 isValid(s: str) -> bool:
|
|||
|
|
stack = []
|
|||
|
|
mapping = {'(': ')', '[': ']', '{': '}'}
|
|||
|
|
for c in s:
|
|||
|
|
if c in mapping:
|
|||
|
|
stack.append(c)
|
|||
|
|
else:
|
|||
|
|
if not stack or mapping[stack.pop()] != c:
|
|||
|
|
return False
|
|||
|
|
return not stack`, {lang:'Python'});
|
|||
|
|
})();
|
|||
|
|
</script>
|
|||
|
|
</body>
|
|||
|
|
</html>
|