356 lines
15 KiB
HTML
356 lines
15 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>021. 搜索二维矩阵 II – 图解</title>
|
||
<link rel="stylesheet" href="../shared/style.css">
|
||
<style>
|
||
.vis-area { min-height: 120px; padding: 16px 0; }
|
||
.code-section { margin-top: 16px; }
|
||
.legend { display:flex; flex-wrap:wrap; gap:12px; margin:10px 0; font-size:13px; }
|
||
.legend span { display:inline-flex; align-items:center; gap:4px; }
|
||
.legend .dot { width:14px; height:14px; border-radius:4px; display:inline-block; }
|
||
.search-current { background:#fef3c7 !important; border-color:#f59e0b !important; color:#92400e; font-weight:700; box-shadow:0 0 0 3px rgba(245,158,11,.3); }
|
||
.search-visited { background:#dbeafe !important; border-color:#3b82f6 !important; color:#1e40af; }
|
||
.search-excluded { background:#f1f5f9 !important; color:#94a3b8 !important; border-color:#e2e8f0 !important; }
|
||
.search-found { background:#dcfce7 !important; border-color:#16a34a !important; color:#166534; font-weight:700; box-shadow:0 0 0 4px rgba(22,163,74,.25); }
|
||
.search-start { background:#ede9fe !important; border-color:#8b5cf6 !important; color:#5b21b6; font-weight:700; }
|
||
.comparison-box {
|
||
display:flex; align-items:center; gap:8px; padding:10px 16px;
|
||
border-radius:10px; margin-top:10px; font-size:14px; font-weight:600;
|
||
}
|
||
.comparison-box.greater { background:#fee2e2; color:#991b1b; }
|
||
.comparison-box.less { background:#dbeafe; color:#1e40af; }
|
||
.comparison-box.equal { background:#dcfce7; color:#166534; }
|
||
.move-arrow { font-size:20px; font-weight:800; }
|
||
.path-chip { font-size:12px; }
|
||
.excluded-info {
|
||
display:grid; grid-template-columns:1fr 1fr; gap:8px; margin-top:8px;
|
||
}
|
||
.excluded-item {
|
||
padding:6px 12px; border-radius:8px; font-size:12px; text-align:center;
|
||
}
|
||
.excluded-item.rows-ex { background:#fef3c7; color:#92400e; }
|
||
.excluded-item.cols-ex { background:#cffafe; color:#155e75; }
|
||
.excluded-item.active-row { background:#fef3c7; color:#92400e; font-weight:700; }
|
||
.excluded-item.active-col { background:#cffafe; color:#155e75; font-weight:700; }
|
||
</style>
|
||
</head>
|
||
<body>
|
||
<div class="container">
|
||
<h1>🔍 021. 搜索二维矩阵 II <span class="badge medium">中等</span></h1>
|
||
<p class="subtitle">分类：矩阵 ｜ LeetCode Hot 100</p>
|
||
|
||
<div class="controls" id="controls">
|
||
<label>矩阵：</label>
|
||
<input type="text" id="matrixInput" placeholder="默认示例" style="width:280px;">
|
||
<label style="margin-left:8px;">target：</label>
|
||
<input type="number" id="targetInput" value="5" style="width:80px;">
|
||
<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 = [
|
||
{input: [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target: 5, label: 'target=5 (存在)'},
|
||
{input: [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target: 20, label: 'target=20 (不存在)'},
|
||
{input: [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target: 1, label: 'target=1 (左上角)'},
|
||
{input: [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target: 30, label: 'target=30 (右下角)'},
|
||
];
|
||
|
||
let origMatrix, targetVal, steps, stepCtrl;
|
||
|
||
function buildSteps(mat, target) {
|
||
origMatrix = mat.map(r => [...r]);
|
||
targetVal = target;
|
||
steps = [];
|
||
const m = mat.length, n = mat[0].length;
|
||
const visited = []; // [{r, c, val, comparison}]
|
||
const excludedRows = new Set();
|
||
const excludedCols = new Set();
|
||
let found = false;
|
||
let foundPos = null;
|
||
|
||
// Build excluded cells: rows above visited that went down, columns right of visited that went left
|
||
function getExcludedCells() {
|
||
const cells = {};
|
||
// Exclude rows that were fully ruled out (rows above current that we moved down from)
|
||
for (const r of excludedRows) {
|
||
for (let c = 0; c < n; c++) {
|
||
cells[`${r},${c}`] = true;
|
||
}
|
||
}
|
||
// Exclude columns that were fully ruled out
|
||
for (const c of excludedCols) {
|
||
for (let r = 0; r < m; r++) {
|
||
cells[`${r},${c}`] = true;
|
||
}
|
||
}
|
||
return cells;
|
||
}
|
||
|
||
// Init
|
||
steps.push({
|
||
stage: 'init', msg: `从右上角 (0, ${n-1}) 开始搜索 target = ${target}。性质：每行左→右递增，每列上→下递增`,
|
||
pos: [0, n-1], visited: [], found: false, foundPos: null,
|
||
excludedCells: {}, excludedRows: new Set(), excludedCols: new Set(),
|
||
comparison: null, currentRow: 0, currentCol: n-1
|
||
});
|
||
|
||
let i = 0, j = n - 1;
|
||
while (i < m && j >= 0) {
|
||
const val = mat[i][j];
|
||
visited.push({r: i, c: j, val, comparison: val === target ? '=' : val > target ? '>' : '<'});
|
||
|
||
if (val === target) {
|
||
found = true;
|
||
foundPos = [i, j];
|
||
steps.push({
|
||
stage: 'found', msg: `找到！matrix[${i}][${j}] = ${val} === target = ${target}`,
|
||
pos: [i, j], visited: [...visited], found: true, foundPos: [i, j],
|
||
excludedCells: getExcludedCells(),
|
||
excludedRows: new Set(excludedRows), excludedCols: new Set(excludedCols),
|
||
comparison: '=', currentRow: i, currentCol: j
|
||
});
|
||
break;
|
||
} else if (val > target) {
|
||
// Value too large → move left (exclude this column)
|
||
excludedCols.add(j);
|
||
steps.push({
|
||
stage: 'move_left', msg: `matrix[${i}][${j}] = ${val} > ${target}，偏大 ← 向左移动，排除第${j}列`,
|
||
pos: [i, j], visited: [...visited], found: false, foundPos: null,
|
||
excludedCells: getExcludedCells(),
|
||
excludedRows: new Set(excludedRows), excludedCols: new Set(excludedCols),
|
||
comparison: '>', currentRow: i, currentCol: j, nextCol: j-1
|
||
});
|
||
j--;
|
||
} else {
|
||
// Value too small → move down (exclude this row)
|
||
excludedRows.add(i);
|
||
steps.push({
|
||
stage: 'move_down', msg: `matrix[${i}][${j}] = ${val} < ${target}，偏小 ↓ 向下移动，排除第${i}行`,
|
||
pos: [i, j], visited: [...visited], found: false, foundPos: null,
|
||
excludedCells: getExcludedCells(),
|
||
excludedRows: new Set(excludedRows), excludedCols: new Set(excludedCols),
|
||
comparison: '<', currentRow: i, currentCol: j, nextRow: i+1
|
||
});
|
||
i++;
|
||
}
|
||
|
||
// Step after moving
|
||
if (i < m && j >= 0) {
|
||
steps.push({
|
||
stage: 'arrived', msg: `到达 matrix[${i}][${j}] = ${mat[i][j]}`,
|
||
pos: [i, j], visited: [...visited], found: false, foundPos: null,
|
||
excludedCells: getExcludedCells(),
|
||
excludedRows: new Set(excludedRows), excludedCols: new Set(excludedCols),
|
||
comparison: null, currentRow: i, currentCol: j
|
||
});
|
||
}
|
||
}
|
||
|
||
if (!found) {
|
||
steps.push({
|
||
stage: 'not_found', msg: `越界，target = ${target} 不在矩阵中`,
|
||
pos: null, visited: [...visited], found: false, foundPos: null,
|
||
excludedCells: getExcludedCells(),
|
||
excludedRows: new Set(excludedRows), excludedCols: new Set(excludedCols),
|
||
comparison: null, currentRow: -1, currentCol: -1
|
||
});
|
||
}
|
||
}
|
||
|
||
function render(step) {
|
||
const s = steps[step];
|
||
const m = origMatrix.length, n = origMatrix[0].length;
|
||
|
||
// Build visited set
|
||
const visitedSet = {};
|
||
for (const v of s.visited) {
|
||
visitedSet[`${v.r},${v.c}`] = v;
|
||
}
|
||
|
||
function cellClass(val, r, c) {
|
||
const key = `${r},${c}`;
|
||
// Found
|
||
if (s.found && s.foundPos && r === s.foundPos[0] && c === s.foundPos[1]) return 'search-found';
|
||
// Current position
|
||
if (s.pos && r === s.pos[0] && c === s.pos[1]) return 'search-current';
|
||
// Visited
|
||
if (visitedSet[key]) return 'search-visited';
|
||
// Start position (top-right)
|
||
if (r === 0 && c === n-1 && !visitedSet[key] && s.stage === 'init') return 'search-start';
|
||
// Excluded
|
||
if (s.excludedCells[key]) return 'search-excluded';
|
||
return '';
|
||
}
|
||
|
||
// Legend
|
||
let viz = '<div class="legend">';
|
||
viz += '<span><span class="dot" style="background:#fef3c7;border:1px solid #f59e0b;"></span> 当前位置</span>';
|
||
viz += '<span><span class="dot" style="background:#dbeafe;border:1px solid #3b82f6;"></span> 搜索路径</span>';
|
||
viz += '<span><span class="dot" style="background:#f1f5f9;border:1px solid #e2e8f0;"></span> 已排除区域</span>';
|
||
viz += '<span><span class="dot" style="background:#dcfce7;border:1px solid #16a34a;"></span> 找到目标</span>';
|
||
viz += '</div>';
|
||
|
||
// Grid
|
||
viz += renderGrid(origMatrix, { cellClass, cellSize: 48 });
|
||
|
||
// Comparison box
|
||
if (s.comparison) {
|
||
const compClass = s.comparison === '>' ? 'greater' : s.comparison === '<' ? 'less' : 'equal';
|
||
const arrow = s.comparison === '>' ? '⬅ 向左' : s.comparison === '<' ? '⬇ 向下' : '✅ 匹配';
|
||
const val = s.pos ? origMatrix[s.pos[0]][s.pos[1]] : '?';
|
||
viz += `<div class="comparison-box ${compClass}">`;
|
||
viz += `matrix[${s.pos?s.pos[0]:'?'}][${s.pos?s.pos[1]:'?'}] = ${val} ${s.comparison} target=${targetVal}`;
|
||
viz += `<span class="move-arrow">${arrow}</span>`;
|
||
viz += '</div>';
|
||
}
|
||
|
||
// Excluded info
|
||
const exRows = s.excludedRows ? [...s.excludedRows] : [];
|
||
const exCols = s.excludedCols ? [...s.excludedCols] : [];
|
||
if (exRows.length > 0 || exCols.length > 0) {
|
||
viz += '<div class="excluded-info">';
|
||
viz += `<div class="excluded-item rows-ex">已排除行：[${exRows.join(', ')}]</div>`;
|
||
viz += `<div class="excluded-item cols-ex">已排除列：[${exCols.join(', ')}]</div>`;
|
||
const totalExcluded = exRows.length * n + exCols.length * m - exRows.length * exCols.length;
|
||
viz += `<div class="excluded-item rows-ex">已排除格子数：约 ${totalExcluded}</div>`;
|
||
viz += `<div class="excluded-item cols-ex">剩余搜索空间：${m*n - totalExcluded}</div>`;
|
||
viz += '</div>';
|
||
}
|
||
|
||
// Path chips
|
||
if (s.visited.length > 0) {
|
||
viz += '<div style="margin-top:12px;"><b>搜索路径：</b></div>';
|
||
viz += '<div style="display:flex;flex-wrap:wrap;gap:4px;margin-top:4px;">';
|
||
s.visited.forEach((v, idx) => {
|
||
const isCurrent = s.pos && v.r === s.pos[0] && v.c === s.pos[1];
|
||
const isFound = s.found && idx === s.visited.length - 1;
|
||
const chipCls = isFound ? 'green' : isCurrent ? 'orange' : 'blue';
|
||
const compSymbol = v.comparison === '>' ? ' >' : v.comparison === '<' ? ' <' : v.comparison === '=' ? ' =' : '';
|
||
viz += `<span class="chip ${chipCls} path-chip" style="min-width:auto;padding:4px 10px;font-size:12px;">[${v.r}][${v.c}]=${v.val}${compSymbol}</span>`;
|
||
if (idx < s.visited.length - 1) viz += '<span style="color:var(--text-muted);font-size:16px;">→</span>';
|
||
});
|
||
viz += '</div>';
|
||
}
|
||
|
||
$('vizArea').innerHTML = viz;
|
||
|
||
// Detail
|
||
let detail = '<div class="calc-block">' + s.msg + '</div>';
|
||
detail += `<div style="margin-top:6px;font-size:13px;">target = <b>${targetVal}</b> | 已搜索 ${s.visited.length} 个位置</div>`;
|
||
if (s.pos) {
|
||
detail += `<div style="margin-top:4px;font-size:13px;">当前位置：(${s.pos[0]}, ${s.pos[1]}) = ${origMatrix[s.pos[0]][s.pos[1]]}</div>`;
|
||
}
|
||
$('detailContent').innerHTML = detail;
|
||
|
||
// Result
|
||
if (s.stage === 'found') {
|
||
$('resultContent').innerHTML = `<div class="final-answer">找到 target=<b>${targetVal}</b>，位置 matrix[${s.foundPos[0]}][${s.foundPos[1]}]<div class="complexity">时间 O(m+n) | 空间 O(1)</div></div>`;
|
||
} else if (s.stage === 'not_found') {
|
||
$('resultContent').innerHTML = `<div class="final-answer" style="border-color:#f87171;background:#fef2f2;">target=<b>${targetVal}</b> 不在矩阵中<div class="complexity">时间 O(m+n) | 空间 O(1)</div></div>`;
|
||
}
|
||
|
||
$('hintText').textContent = s.msg;
|
||
const pipe = [['init','初始化'],['move_left','⬅ 向左'],['move_down','⬇ 向下'],['arrived','到达'],['found','✅ 找到'],['not_found','❌ 未找到']];
|
||
$('pipeline').innerHTML = pipe.map(([k,l]) =>
|
||
`<span class="pipe-step ${s.stage===k?'active':''}">${l}</span>`
|
||
).join('<i>→</i>');
|
||
}
|
||
|
||
function rebuild() {
|
||
try {
|
||
const mat = JSON.parse($('matrixInput').value);
|
||
const tgt = parseInt($('targetInput').value);
|
||
if (!Array.isArray(mat) || isNaN(tgt)) throw 0;
|
||
buildSteps(mat, tgt);
|
||
stepCtrl = new StepController({ onStep: render });
|
||
stepCtrl.setSteps(steps.map((_, i) => i));
|
||
render(0);
|
||
$('stepInfo').textContent = `步骤 1 / ${steps.length}`;
|
||
stepCtrl.onStep = (idx) => { render(idx); $('stepInfo').textContent = `步骤 ${idx + 1} / ${steps.length}`; };
|
||
} catch (e) { alert('请输入合法 JSON 二维数组和 target 数字'); }
|
||
}
|
||
|
||
function init() {
|
||
const sel = $('exampleSelect');
|
||
examples.forEach((e, i) => { sel.innerHTML += `<option value="${i}">${e.label}</option>`; });
|
||
$('matrixInput').value = JSON.stringify(examples[0].input);
|
||
$('targetInput').value = examples[0].target;
|
||
|
||
rebuild();
|
||
|
||
$('applyBtn').onclick = () => rebuild();
|
||
$('exampleSelect').onchange = () => {
|
||
const e = examples[parseInt($('exampleSelect').value)];
|
||
$('matrixInput').value = JSON.stringify(e.input);
|
||
$('targetInput').value = e.target;
|
||
rebuild();
|
||
};
|
||
$('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 searchMatrix(matrix, target):
|
||
m, n = len(matrix), len(matrix[0])
|
||
i, j = 0, n - 1 # 从右上角出发
|
||
while i < m and j >= 0:
|
||
if matrix[i][j] == target:
|
||
return True
|
||
elif matrix[i][j] > target:
|
||
j -= 1 # 偏大 → 向左
|
||
else:
|
||
i += 1 # 偏小 → 向下
|
||
return False`, { lang: 'Python' });
|
||
})();
|
||
</script>
|
||
</body>
|
||
</html> |