1. 从递归契约到分治
分治把问题拆成更小的同类问题,递归求解,再合并结果。不是所有递归都叫分治,也不是所有问题简单二分就能解决;合并是否正确和拆分是否缩小都必须解释。
先看递归契约,再读排序中的归并:输入分两半,各自返回有序数组,然后合并。时间由每层线性成本和对数层数得到 O(n log n),具体实现计入辅助数组和调用栈。这里引用同一份已测试实现,不重复抄代码。
2. 表达式:枚举最后一次运算
给表达式加括号,返回所有不同括号结构产生的结果,结果值相同也保留。例如 2*3-4*5 得到排序后的 [-34,-14,-10,-10,10]。
契约:输入必须是非空的十进制非负整数与二元 +、-、* 交替组成的字符串;没有空格、括号、一元负号或小数。数字和所有可能的中间结果须为安全整数。此教学枚举仅适合短表达式。
任意括号结构都有一个最后运算符。枚举这个位置,左右分别求出所有可能结果,再做笛卡尔积组合。没有运算符时就是一个数,递归终止。相同子串会被多次求解,使用共享记忆表避免重复。
function diffWaysToCompute(expression) {
if (!/^[0-9]+(?:[+*-][0-9]+)*$/.test(expression)) {
throw new SyntaxError('Expected unsigned integers separated by +, - or *');
}
const memo = new Map();
function solve(text) {
if (memo.has(text)) return memo.get(text);
const result = [];
for (let i = 0; i < text.length; i++) {
const op = text[i];
if (!'+-*'.includes(op)) continue;
const left = solve(text.slice(0, i));
const right = solve(text.slice(i + 1));
for (const a of left) {
for (const b of right) {
result.push(op === '+' ? a + b : op === '-' ? a - b : a * b);
}
}
}
if (result.length === 0) result.push(Number(text));
memo.set(text, result);
return result;
}
return solve(expression);
}解析前检查语法,避免把非法输入经 parseInt 悄悄接受。不要去重结果:-10 出现两次对应两种结构。函数不使用 eval,也不按通常乘法优先级计算,因为题目要求枚举括号。
3. 输出规模不能藏起来
有 k 个运算符时,完整括号结构数量是第 k 个卡特兰数 Cₖ,它呈指数增长;仅返回结果就需要 Ω(Cₖ) 时间和空间。缓存并不能将所有答案的枚举变成多项式。
若表达式长度为 L,一个保守总时间上界为 O(L³ + L²Cₖ),缓存结果与字符串的空间上界为 O(L³ + L²Cₖ),调用深度为 O(k)。它们是宽松上界,不是紧确复杂度;字符串切片和所有子表达式结果都已计入。长表达式应限制规模或改成求一个目标性质,不适合强行枚举全部结构。
4. 验证与迁移
运行 node --test tests/algorithm-strategies-examples.test.mjs,测试单数字、多位数、重复结果和非法语法。
闭卷练习:对 2-1-1 画出两种最后运算位置,得到 0 与 2。解释为什么左右结果要两两组合,而不能只各取第一个。再比较归并:为什么归并每次固定分成两半,这题却要枚举所有分割位置?
评论
正在加载评论…