180 lines
8.1 KiB
HTML
180 lines
8.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>080. 划分字母区间 – 图解</title>
|
||
<link rel="stylesheet" href="../shared/style.css">
|
||
<style>.vis-area { min-height: 120px; padding: 16px 0; } .code-section { margin-top: 16px; }
|
||
.seg-bar{display:flex;height:36px;border-radius:8px;overflow:hidden;margin-top:8px;}
|
||
.seg-item{display:flex;align-items:center;justify-content:center;font-weight:700;color:white;font-size:13px;transition:all .25s;}
|
||
</style>
|
||
</head>
|
||
<body><div class="container">
|
||
<h1>🟡 080. 划分字母区间 <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="ababcbacadefegdehijhklij">
|
||
<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:"ababcbacadefegdehijhklij", label:'示例1: ababcbacadefegdehijhklij'},
|
||
{input:"eccbbbbdec", label:'示例2: eccbbbbdec'},
|
||
{input:"abc", label:'示例3: abc'},
|
||
];
|
||
const COLORS = ['#3b82f6','#8b5cf6','#f59e0b','#ef4444','#10b981','#06b6d4','#ec4899','#14b8a6'];
|
||
let s, steps, stepCtrl;
|
||
|
||
function buildSteps(str) {
|
||
s = str; steps = [];
|
||
// find last occurrence
|
||
const last = {};
|
||
for (let i = 0; i < str.length; i++) last[str[i]] = i;
|
||
steps.push({stage:'scan', msg:`扫描记录每个字母的最后出现位置`, str, last:{...last}, i:-1, start:0, end:0, segs:[], done:false});
|
||
|
||
let start = 0, end = 0;
|
||
const segs = [];
|
||
for (let i = 0; i < str.length; i++) {
|
||
end = Math.max(end, last[str[i]]);
|
||
steps.push({stage:'extend', msg:`i=${i} "${str[i]}"，最后出现位置=${last[str[i]]}，当前区间end=${end}`, str, last:{...last}, i, start, end, segs:JSON.parse(JSON.stringify(segs)), done:false});
|
||
if (i === end) {
|
||
segs.push({start, end, color:COLORS[segs.length%COLORS.length]});
|
||
steps.push({stage:'cut', msg:`i=${i} 达到当前end，切割区间 [${start},${end}]，长度=${end-start+1}`, str, last:{...last}, i, start, end, segs:JSON.parse(JSON.stringify(segs)), done:false});
|
||
start = i + 1;
|
||
end = i + 1;
|
||
}
|
||
}
|
||
const lengths = segs.map(sg => sg.end - sg.start + 1);
|
||
steps.push({stage:'done', msg:`划分完成，共 ${segs.length} 个区间`, str, last:{...last}, i:-1, start, end, segs, done:true, lengths});
|
||
}
|
||
|
||
function render(step) {
|
||
const st = steps[step];
|
||
// string visualization with segments
|
||
let viz = '<div style="margin-bottom:8px;"><b>字符串：</b></div>';
|
||
viz += '<div class="nums-line">';
|
||
for (let i = 0; i < st.str.length; i++) {
|
||
const seg = st.segs.find(sg => i >= sg.start && i <= sg.end);
|
||
let cls = 'default';
|
||
let style = '';
|
||
if (seg) { style = `background:${seg.color}22;border:2px solid ${seg.color};color:${seg.color};font-weight:800;`; }
|
||
if (st.i === i) { cls = 'active'; style = ''; }
|
||
viz += `<span class="chip ${cls}" style="min-width:28px;font-size:13px;${style}">${st.str[i]}</span>`;
|
||
}
|
||
viz += '</div>';
|
||
|
||
// last occurrence table
|
||
viz += '<div style="margin-top:12px;"><b>字母最后位置：</b></div>';
|
||
viz += '<div style="display:flex;flex-wrap:wrap;gap:4px;margin-top:4px;">';
|
||
const sortedKeys = Object.keys(st.last).sort();
|
||
sortedKeys.forEach(ch => {
|
||
const isCurrent = st.i >= 0 && st.str[st.i] === ch;
|
||
viz += `<code style="padding:2px 6px;${isCurrent?'background:#fef3c7;border:1px solid #f59e0b;':''}">${ch}→${st.last[ch]}</code>`;
|
||
});
|
||
viz += '</div>';
|
||
|
||
// segment bar
|
||
if (st.segs.length > 0) {
|
||
viz += '<div class="seg-bar">';
|
||
st.segs.forEach((sg,idx) => {
|
||
const pct = (sg.end - sg.start + 1) / st.str.length * 100;
|
||
viz += `<div class="seg-item" style="width:${pct}%;background:${sg.color};">${sg.end-sg.start+1}</div>`;
|
||
});
|
||
const covered = st.segs.reduce((a,s)=>a+s.end-s.start+1,0);
|
||
if (covered < st.str.length) {
|
||
viz += `<div class="seg-item" style="width:${(st.str.length-covered)/st.str.length*100}%;background:#e2e8f0;color:#94a3b8;">...</div>`;
|
||
}
|
||
viz += '</div>';
|
||
}
|
||
|
||
if (st.i >= 0) {
|
||
viz += `<div style="margin-top:6px;font-size:13px;color:#475569;">当前区间: [${st.start}, ${st.end}]</div>`;
|
||
}
|
||
$('vizArea').innerHTML = viz;
|
||
|
||
$('detailContent').innerHTML = '<div class="calc-block">' + st.msg + '</div>';
|
||
if (st.segs.length > 0) {
|
||
let segInfo = '<div style="margin-top:8px;"><b>已划分区间：</b></div>';
|
||
st.segs.forEach((sg,idx) => {
|
||
segInfo += `<div style="color:${sg.color};font-weight:600;">区间${idx+1}: [${sg.start},${sg.end}] 长度=${sg.end-sg.start+1}</div>`;
|
||
});
|
||
$('detailContent').innerHTML += segInfo;
|
||
}
|
||
|
||
if (st.done) {
|
||
$('resultContent').innerHTML = `<div class="final-answer">
|
||
划分结果: <b>[${st.lengths.join(', ')}]</b><br>
|
||
共 ${st.segs.length} 个区间
|
||
</div>
|
||
<div class="complexity">时间复杂度 O(n)，空间复杂度 O(1)</div>`;
|
||
}
|
||
$('hintText').textContent = st.msg;
|
||
const stages = ['scan→扫描','extend→扩展','cut→切割','done→完成'];
|
||
$('pipeline').innerHTML = stages.map(st2 => {
|
||
const [k,l] = st2.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>`);
|
||
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[+$('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 partitionLabels(s):
|
||
last = {c: i for i, c in enumerate(s)}
|
||
start = end = 0
|
||
result = []
|
||
for i, c in enumerate(s):
|
||
end = max(end, last[c])
|
||
if i == end:
|
||
result.append(end - start + 1)
|
||
start = i + 1
|
||
return result`, {lang:'Python'});
|
||
})();
|
||
</script>
|
||
</body></html>
|