364 lines
14 KiB
HTML
364 lines
14 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>019. 螺旋矩阵 – 图解</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; }
|
||
.spiral-visited { background:#dcfce7 !important; border-color:#16a34a !important; color:#166534; position:relative; }
|
||
.spiral-current { background:#fef3c7 !important; border-color:#f59e0b !important; color:#92400e; box-shadow:0 0 0 3px rgba(245,158,11,.3); }
|
||
.spiral-boundary-top { border-top:3px solid #3b82f6 !important; }
|
||
.spiral-boundary-bottom { border-bottom:3px solid #ef4444 !important; }
|
||
.spiral-boundary-left { border-left:3px solid #8b5cf6 !important; }
|
||
.spiral-boundary-right { border-right:3px solid #f59e0b !important; }
|
||
.direction-badge {
|
||
display:inline-flex; align-items:center; gap:4px; padding:4px 12px;
|
||
border-radius:999px; font-size:14px; font-weight:700; margin:4px;
|
||
}
|
||
.direction-badge.top { background:#dbeafe; color:#1e40af; }
|
||
.direction-badge.right { background:#fef3c7; color:#92400e; }
|
||
.direction-badge.bottom { background:#fee2e2; color:#991b1b; }
|
||
.direction-badge.left { background:#ede9fe; color:#5b21b6; }
|
||
.boundary-info {
|
||
display:grid; grid-template-columns:1fr 1fr; gap:8px; margin-top:10px;
|
||
}
|
||
.boundary-item {
|
||
padding:6px 12px; border-radius:8px; font-size:13px; font-weight:600; text-align:center;
|
||
}
|
||
.boundary-item.top-b { background:#dbeafe; color:#1e40af; }
|
||
.boundary-item.bottom-b { background:#fee2e2; color:#991b1b; }
|
||
.boundary-item.left-b { background:#ede9fe; color:#5b21b6; }
|
||
.boundary-item.right-b { background:#fef3c7; color:#92400e; }
|
||
.order-overlay {
|
||
position:absolute; top:-6px; right:-6px; min-width:16px; height:16px;
|
||
border-radius:50%; background:#16a34a; color:#fff; font-size:9px;
|
||
display:flex; align-items:center; justify-content:center; font-weight:700;
|
||
line-height:1; padding:0 2px; z-index:2;
|
||
}
|
||
</style>
|
||
</head>
|
||
<body>
|
||
<div class="container">
|
||
<h1>🌀 019. 螺旋矩阵 <span class="badge medium">中等</span></h1>
|
||
<p class="subtitle">分类：矩阵 ｜ 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() {
|
||
const examples = [
|
||
{input: [[1,2,3],[4,5,6],[7,8,9]], label: '3×3'},
|
||
{input: [[1,2,3,4],[5,6,7,8],[9,10,11,12]], label: '3×4'},
|
||
{input: [[1,2,3],[4,5,6],[7,8,9],[10,11,12]], label: '4×3'},
|
||
{input: [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]], label: '4×4'},
|
||
];
|
||
|
||
let origMatrix, steps, stepCtrl, visitOrder;
|
||
|
||
// Pre-compute spiral visit order with positions
|
||
function computeVisitOrder(mat) {
|
||
const m = mat.length, n = mat[0].length;
|
||
const order = []; // [{r, c, val, direction, top, bottom, left, right}]
|
||
let top = 0, bottom = m - 1, left = 0, right = n - 1;
|
||
while (top <= bottom && left <= right) {
|
||
for (let j = left; j <= right; j++) order.push({r:top, c:j, val:mat[top][j], dir:'top', top, bottom, left, right});
|
||
top++;
|
||
if (top <= bottom) {
|
||
for (let i = top; i <= bottom; i++) order.push({r:i, c:right, val:mat[i][right], dir:'right', top:top-1, bottom, left, right});
|
||
}
|
||
right--;
|
||
if (top <= bottom && left <= right) {
|
||
for (let j = right; j >= left; j--) order.push({r:bottom, c:j, val:mat[bottom][j], dir:'bottom', top:top-1, bottom, left, right:right+1});
|
||
bottom--;
|
||
}
|
||
if (top <= bottom && left <= right) {
|
||
for (let i = bottom; i >= top; i--) order.push({r:i, c:left, val:mat[i][left], dir:'left', top, bottom:bottom+1, left, right:right+1});
|
||
left++;
|
||
}
|
||
}
|
||
return order;
|
||
}
|
||
|
||
function buildSteps(mat) {
|
||
origMatrix = mat.map(r => [...r]);
|
||
steps = [];
|
||
visitOrder = computeVisitOrder(mat);
|
||
const m = mat.length, n = mat[0].length;
|
||
|
||
// Step 0: Init
|
||
steps.push({
|
||
stage: 'init', msg: `按层螺旋遍历 ${m}×${n} 矩阵，维护 top/bottom/left/right 四个边界`,
|
||
visitedCount: 0, currentPos: null, direction: null,
|
||
top: 0, bottom: m-1, left: 0, right: n-1,
|
||
visitedSet: {}
|
||
});
|
||
|
||
// New layer step for each layer
|
||
let prevLayer = -1;
|
||
for (let idx = 0; idx < visitOrder.length; idx++) {
|
||
const v = visitOrder[idx];
|
||
const layerId = Math.min(v.r, v.c, m-1-v.r, n-1-v.c);
|
||
if (layerId > prevLayer) {
|
||
prevLayer = layerId;
|
||
steps.push({
|
||
stage: 'new_layer', msg: `进入第 ${layerId+1} 层：top=${v.top} bottom=${v.bottom} left=${v.left} right=${v.right}`,
|
||
visitedCount: idx, currentPos: null, direction: null,
|
||
top: v.top, bottom: v.bottom, left: v.left, right: v.right,
|
||
visitedSet: buildVisitedSet(idx)
|
||
});
|
||
}
|
||
|
||
const dirLabels = {top:'→ 向右', right:'↓ 向下', bottom:'← 向左', left:'↑ 向上'};
|
||
steps.push({
|
||
stage: v.dir, msg: `${dirLabels[v.dir]}：访问 matrix[${v.r}][${v.c}] = ${v.val}`,
|
||
visitedCount: idx + 1, currentPos: `${v.r},${v.c}`, direction: v.dir,
|
||
top: v.top, bottom: v.bottom, left: v.left, right: v.right,
|
||
visitedSet: buildVisitedSet(idx + 1)
|
||
});
|
||
}
|
||
|
||
steps.push({
|
||
stage: 'done', msg: `螺旋遍历完成！共访问 ${visitOrder.length} 个元素`,
|
||
visitedCount: visitOrder.length, currentPos: null, direction: null,
|
||
top: -1, bottom: -1, left: -1, right: -1,
|
||
visitedSet: buildVisitedSet(visitOrder.length)
|
||
});
|
||
}
|
||
|
||
function buildVisitedSet(count) {
|
||
const set = {};
|
||
for (let i = 0; i < count; i++) {
|
||
const v = visitOrder[i];
|
||
set[`${v.r},${v.c}`] = i + 1; // order number 1-based
|
||
}
|
||
return set;
|
||
}
|
||
|
||
function render(step) {
|
||
const s = steps[step];
|
||
const m = origMatrix.length, n = origMatrix[0].length;
|
||
|
||
function cellClass(val, r, c) {
|
||
const key = `${r},${c}`;
|
||
let cls = '';
|
||
if (s.currentPos === key) cls += ' spiral-current';
|
||
else if (s.visitedSet[key]) cls += ' spiral-visited';
|
||
// Boundary classes
|
||
if (s.top >= 0) {
|
||
if (r === s.top) cls += ' spiral-boundary-top';
|
||
if (r === s.bottom) cls += ' spiral-boundary-bottom';
|
||
if (c === s.left) cls += ' spiral-boundary-left';
|
||
if (c === s.right) cls += ' spiral-boundary-right';
|
||
}
|
||
return cls.trim();
|
||
}
|
||
|
||
function cellStyle(val, r, c) {
|
||
const key = `${r},${c}`;
|
||
if (s.visitedSet[key] && s.currentPos !== key) {
|
||
return 'position:relative;';
|
||
}
|
||
return '';
|
||
}
|
||
|
||
// Custom render with order number overlays
|
||
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:#dcfce7;border:1px solid #16a34a;"></span> 已访问</span>';
|
||
viz += '<span style="font-size:11px;color:#64748b;">边框粗线 = 当前层边界</span>';
|
||
viz += '</div>';
|
||
|
||
// Render grid
|
||
const grid = renderGrid(origMatrix, { cellClass, cellSize: 48, cellStyle });
|
||
viz += grid;
|
||
|
||
// Add order number overlays via JavaScript after rendering
|
||
// We'll do it by wrapping with IDs and post-processing
|
||
// Instead, let's render manually with overlays
|
||
|
||
// Re-render with custom cell rendering to include order numbers
|
||
let gridHtml = `<div class="grid-viz" style="grid-template-columns:repeat(${n}, 48px);">`;
|
||
for (let r = 0; r < m; r++) {
|
||
for (let c = 0; c < n; c++) {
|
||
const val = origMatrix[r][c];
|
||
const key = `${r},${c}`;
|
||
const cls = cellClass(val, r, c);
|
||
const style = cellStyle(val, r, c);
|
||
const orderNum = s.visitedSet[key];
|
||
let overlay = '';
|
||
if (orderNum && s.currentPos !== key) {
|
||
overlay = `<span class="order-overlay">${orderNum}</span>`;
|
||
}
|
||
gridHtml += `<div class="grid-cell ${cls}" style="width:48px;height:48px;${style}">${val}${overlay}</div>`;
|
||
}
|
||
}
|
||
gridHtml += '</div>';
|
||
viz = viz.replace(grid, gridHtml); // replace the renderGrid output
|
||
|
||
// Direction badge
|
||
if (s.direction) {
|
||
const dirMap = {top:'→ 向右', right:'↓ 向下', bottom:'← 向左', left:'↑ 向上'};
|
||
viz += `<div style="margin-top:10px;"><span class="direction-badge ${s.direction}">${dirMap[s.direction]}</span></div>`;
|
||
}
|
||
|
||
// Boundary info
|
||
if (s.top >= 0) {
|
||
viz += '<div class="boundary-info">';
|
||
viz += `<div class="boundary-item top-b">top = ${s.top}</div>`;
|
||
viz += `<div class="boundary-item bottom-b">bottom = ${s.bottom}</div>`;
|
||
viz += `<div class="boundary-item left-b">left = ${s.left}</div>`;
|
||
viz += `<div class="boundary-item right-b">right = ${s.right}</div>`;
|
||
viz += '</div>';
|
||
}
|
||
|
||
// Visited order sequence
|
||
const visitedVals = [];
|
||
for (let i = 0; i < s.visitedCount; i++) visitedVals.push(visitOrder[i].val);
|
||
if (visitedVals.length > 0) {
|
||
viz += '<div style="margin-top:12px;"><b>已访问序列：</b></div>';
|
||
viz += '<div style="display:flex;flex-wrap:wrap;gap:4px;margin-top:4px;">';
|
||
visitedVals.forEach((v, i) => {
|
||
viz += `<span class="chip green" style="min-width:30px;height:28px;font-size:12px;padding:2px 6px;">${v}</span>`;
|
||
});
|
||
viz += '</div>';
|
||
}
|
||
|
||
$('vizArea').innerHTML = viz;
|
||
|
||
// Detail
|
||
let detail = '<div class="calc-block">' + s.msg + '</div>';
|
||
if (s.currentPos) {
|
||
const [cr, cc] = s.currentPos.split(',').map(Number);
|
||
detail += `<div style="margin-top:6px;font-size:13px;">当前位置：matrix[${cr}][${cc}] = ${origMatrix[cr][cc]}</div>`;
|
||
}
|
||
detail += `<div style="margin-top:6px;font-size:13px;">已访问：${s.visitedCount} / ${visitOrder.length} 个元素</div>`;
|
||
$('detailContent').innerHTML = detail;
|
||
|
||
if (s.stage === 'done') {
|
||
$('resultContent').innerHTML = `<div class="final-answer">螺旋顺序：<b>[${visitOrder.map(v=>v.val)}]</b><div class="complexity">时间 O(mn) | 空间 O(1)（不含输出数组）</div></div>`;
|
||
}
|
||
|
||
$('hintText').textContent = s.msg;
|
||
const pipe = [['init','初始化'],['new_layer','新层'],['top','→ 向右'],['right','↓ 向下'],['bottom','← 向左'],['left','↑ 向上'],['done','完成']];
|
||
$('pipeline').innerHTML = pipe.map(([k,l]) =>
|
||
`<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 = JSON.stringify(examples[0].input);
|
||
|
||
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 mat = JSON.parse($('inputArea').value);
|
||
if (!Array.isArray(mat) || !Array.isArray(mat[0])) throw 0;
|
||
buildSteps(mat);
|
||
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 spiralOrder(matrix):
|
||
m, n = len(matrix), len(matrix[0])
|
||
top, bottom = 0, m - 1
|
||
left, right = 0, n - 1
|
||
result = []
|
||
while top <= bottom and left <= right:
|
||
# 向右 →
|
||
for j in range(left, right + 1):
|
||
result.append(matrix[top][j])
|
||
top += 1
|
||
# 向下 ↓
|
||
for i in range(top, bottom + 1):
|
||
result.append(matrix[i][right])
|
||
right -= 1
|
||
# 向左 ←
|
||
if top <= bottom:
|
||
for j in range(right, left - 1, -1):
|
||
result.append(matrix[bottom][j])
|
||
bottom -= 1
|
||
# 向上 ↑
|
||
if left <= right:
|
||
for i in range(bottom, top - 1, -1):
|
||
result.append(matrix[i][left])
|
||
left += 1
|
||
return result`, { lang: 'Python' });
|
||
})();
|
||
</script>
|
||
</body>
|
||
</html> |