228 lines
9.4 KiB
HTML
228 lines
9.4 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>078. 跳跃游戏 – 图解</title>
|
||
<link rel="stylesheet" href="../shared/style.css">
|
||
<style>.vis-area { min-height: 120px; padding: 16px 0; } .code-section { margin-top: 16px; }
|
||
.reach-bar{height:6px;border-radius:3px;margin-top:8px;background:var(--surface2);position:relative;overflow:hidden;}
|
||
.reach-fill{height:100%;border-radius:3px;background:linear-gradient(90deg,var(--blue),var(--green));transition:width .3s;}
|
||
</style>
|
||
</head>
|
||
<body><div class="container">
|
||
<h1>🟡 078. 跳跃游戏 <span class="badge medium">中等</span></h1>
|
||
<p class="subtitle">分类：贪心 ｜ LeetCode Hot 100</p>
|
||
<div class="controls" id="controls">
|
||
<label>输入：</label><input type="text" id="inputArea" value="[2,3,1,1,4]">
|
||
<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 CODE = `def canJump(nums):
|
||
max_reach = 0
|
||
for i, num in enumerate(nums):
|
||
if i > max_reach: # 当前位置不可达
|
||
return False
|
||
max_reach = max(max_reach, i + num)
|
||
if max_reach >= len(nums) - 1:
|
||
return True
|
||
return True`;
|
||
|
||
const EXAMPLES = [
|
||
{ name: '例1: [2,3,1,1,4]', input: '[2,3,1,1,4]' },
|
||
{ name: '例2: [3,2,1,0,4]', input: '[3,2,1,0,4]' },
|
||
{ name: '例3: [0]', input: '[0]' },
|
||
{ name: '例4: [1,2,3]', input: '[1,2,3]' },
|
||
];
|
||
|
||
let controller = null;
|
||
|
||
function genSteps(nums) {
|
||
const steps = [];
|
||
const n = nums.length;
|
||
let maxReach = 0;
|
||
let result = null;
|
||
|
||
steps.push({
|
||
desc: '初始化：maxReach = 0',
|
||
hint: '贪心维护最远可达位置 maxReach，若遍历到 i > maxReach 说明不可达。',
|
||
detail: '<b>思路</b>：遍历数组，维护最远可达下标。<br>• 若 i ≤ maxReach，位置可达，更新 maxReach = max(maxReach, i + nums[i])<br>• 若 i > maxReach，当前位置不可达，返回 False<br><br>时间 O(n)，空间 O(1)',
|
||
hlLine: -1,
|
||
curIdx: -1, maxReach: 0, result: null,
|
||
});
|
||
|
||
for (let i = 0; i < n; i++) {
|
||
if (i > maxReach) {
|
||
steps.push({
|
||
desc: `i=${i} > maxReach=${maxReach}，位置不可达！`,
|
||
hint: `当前位置 ${i} 超出最远可达范围 ${maxReach}，无法继续前进。`,
|
||
detail: `i = <b>${i}</b>, maxReach = <b>${maxReach}</b><br>i > maxReach → 不可达<br>返回 <b>False</b>`,
|
||
hlLine: 3,
|
||
curIdx: i, maxReach, result: false,
|
||
});
|
||
result = false;
|
||
break;
|
||
}
|
||
|
||
const newReach = Math.max(maxReach, i + nums[i]);
|
||
const canFinish = newReach >= n - 1;
|
||
|
||
steps.push({
|
||
desc: `i=${i}: nums[${i}]=${nums[i]}，可达范围 ${i}+${nums[i]}=${i + nums[i]}，maxReach: ${maxReach} → ${newReach}${canFinish ? ' ≥ ' + (n-1) + ' → 可达终点！' : ''}`,
|
||
hint: canFinish ? `最远可达 ${newReach} 已超终点，返回 True！` : `更新 maxReach = ${newReach}，继续遍历。`,
|
||
detail: `i = <b>${i}</b>, nums[${i}] = <b>${nums[i]}</b><br>可达范围 = i + nums[i] = ${i + nums[i]}<br>maxReach: ${maxReach} → <b>${newReach}</b>${canFinish ? '<br><span style="color:var(--green)">maxReach ≥ ' + (n-1) + ' → 可达终点！</span>' : ''}`,
|
||
hlLine: canFinish ? 6 : 5,
|
||
curIdx: i, maxReach: newReach, result: canFinish ? true : null,
|
||
});
|
||
|
||
maxReach = newReach;
|
||
if (canFinish) { result = true; break; }
|
||
}
|
||
|
||
if (result === null) {
|
||
steps.push({
|
||
desc: '遍历结束，可达终点',
|
||
hint: '所有位置都在可达范围内，返回 True。',
|
||
detail: '遍历完成，未遇到不可达位置。<br>返回 <b>True</b>',
|
||
hlLine: 8,
|
||
curIdx: -1, maxReach, result: true,
|
||
});
|
||
}
|
||
|
||
// final
|
||
steps.push({
|
||
desc: `最终结果：${result ? '可以' : '不可以'}到达最后一个下标`,
|
||
hint: result ? '贪心策略确保了只要可达，就能到达终点。' : '中间存在 0 且无法跳过，导致断裂。',
|
||
detail: `<b>结果</b>：${result ? '<span style="color:var(--green)">True</span>' : '<span style="color:var(--red)">False</span>'}<br>maxReach 最终 = ${maxReach}`,
|
||
hlLine: -1,
|
||
curIdx: -1, maxReach, result, isFinal: true,
|
||
});
|
||
|
||
return steps;
|
||
}
|
||
|
||
function renderStep(step) {
|
||
if (!step) {
|
||
$('vizArea').innerHTML = '<div style="color:var(--text2);text-align:center;padding:40px;">点击「生成图解」开始</div>';
|
||
$('detailContent').innerHTML = '';
|
||
$('resultContent').innerHTML = '';
|
||
$('stepInfo').textContent = '';
|
||
$('hintText').textContent = '';
|
||
return;
|
||
}
|
||
|
||
$('stepInfo').textContent = step.desc;
|
||
$('hintText').textContent = step.hint;
|
||
$('detailContent').innerHTML = step.detail;
|
||
|
||
const nums = parseInput($('inputArea').value);
|
||
const n = nums.length;
|
||
|
||
// render chips
|
||
const row = document.createElement('div');
|
||
row.className = 'jump-row';
|
||
nums.forEach((val, i) => {
|
||
const cell = document.createElement('div');
|
||
let cls = 'jump-cell';
|
||
if (i === step.curIdx) cls += ' current';
|
||
if (i <= step.maxReach && step.maxReach >= 0) cls += ' reachable';
|
||
if (i === step.maxReach && step.curIdx !== i) cls += ' max-reach';
|
||
cell.className = cls;
|
||
cell.innerHTML = `<div class="j-chip">${val}</div><div class="j-idx">${i}</div>`;
|
||
row.appendChild(cell);
|
||
});
|
||
$('vizArea').innerHTML = '';
|
||
$('vizArea').appendChild(row);
|
||
|
||
// reach bar
|
||
const bar = document.createElement('div');
|
||
bar.className = 'reach-bar';
|
||
const fill = document.createElement('div');
|
||
fill.className = 'reach-fill';
|
||
fill.style.width = (step.maxReach >= 0 ? Math.min(100, ((step.maxReach + 1) / n) * 100) : 0) + '%';
|
||
bar.appendChild(fill);
|
||
$('vizArea').appendChild(bar);
|
||
|
||
// legend + stats
|
||
const info = document.createElement('div');
|
||
info.style.cssText = 'text-align:center;margin-top:10px;font-family:var(--mono);font-size:.82rem;';
|
||
info.innerHTML = `maxReach = <span style="color:var(--green)">${step.maxReach}</span> / ${n - 1}${step.result === true ? ' ✅ 可达终点' : step.result === false ? ' ❌ 不可达' : ''}`;
|
||
$('vizArea').appendChild(info);
|
||
|
||
const legend = document.createElement('div');
|
||
legend.className = 'legend';
|
||
legend.innerHTML = `
|
||
<span class="legend-item"><span class="legend-dot" style="background:var(--blue)"></span> 可达范围</span>
|
||
<span class="legend-item"><span class="legend-dot" style="background:var(--orange)"></span> 当前位置</span>
|
||
<span class="legend-item"><span class="legend-dot" style="background:var(--green)"></span> 最远可达</span>
|
||
`;
|
||
$('vizArea').appendChild(legend);
|
||
|
||
renderCode($('codeArea'), CODE, step.hlLine);
|
||
|
||
if (step.isFinal) {
|
||
const r = step.result;
|
||
$('resultContent').innerHTML = `<div class="result-box" style="${r ? '' : 'background:var(--red-dim);border-color:rgba(240,96,96,.3);color:var(--red);'}">结果 = <span class="val">${r ? 'True' : 'False'}</span><br><small>${r ? '可以到达最后一个下标' : '无法到达最后一个下标'}</small></div>`;
|
||
} else {
|
||
$('resultContent').innerHTML = `<div style="color:var(--text2);font-size:.85rem;">等待遍历完成…</div>`;
|
||
}
|
||
}
|
||
|
||
function parseInput(s) {
|
||
try {
|
||
const a = JSON.parse(s.replace(/'/g, '"'));
|
||
if (Array.isArray(a) && a.every(x => typeof x === 'number')) return a;
|
||
} catch(e) {}
|
||
return [2,3,1,1,4];
|
||
}
|
||
|
||
function build() {
|
||
const nums = parseInput($('inputArea').value);
|
||
const steps = genSteps(nums);
|
||
if (controller) controller.stopAuto();
|
||
controller = new StepController(steps, { onRender: renderStep });
|
||
$('nextBtn').onclick = () => controller.next();
|
||
$('prevBtn').onclick = () => controller.prev();
|
||
$('jumpBtn').onclick = () => controller.jumpEnd();
|
||
$('resetBtn').onclick = () => controller.reset();
|
||
$('autoBtn').onclick = () => { if (controller.autoTimer) controller.stopAuto(); else controller.startAuto(); };
|
||
controller.next();
|
||
}
|
||
|
||
function init() {
|
||
const sel = $('exampleSelect');
|
||
EXAMPLES.forEach((ex, i) => {
|
||
const o = document.createElement('option');
|
||
o.value = i; o.textContent = ex.name;
|
||
sel.appendChild(o);
|
||
});
|
||
sel.onchange = () => { $('inputArea').value = EXAMPLES[sel.value].input; build(); };
|
||
$('applyBtn').onclick = build;
|
||
$('inputArea').onkeydown = e => { if (e.key === 'Enter') build(); };
|
||
build();
|
||
}
|
||
|
||
if (document.readyState === 'loading') document.addEventListener('DOMContentLoaded', init);
|
||
else init();
|
||
})()</script>
|
||
</body></html> |