Skip to content

1. 从递归契约到分治 ​

分治把问题拆成更小的同类问题,递归求解,再合并结果。不是所有递归都叫分治,也不是所有问题简单二分就能解决;合并是否正确和拆分是否缩小都必须解释。

先看递归契约,再读排序中的归并:输入分两半,各自返回有序数组,然后合并。时间由每层线性成本和对数层数得到 O(n log n),具体实现计入辅助数组和调用栈。这里引用同一份已测试实现,不重复抄代码。

2. 表达式:枚举最后一次运算 ​

给表达式加括号,返回所有不同括号结构产生的结果,结果值相同也保留。例如 2*3-4*5 得到排序后的 [-34,-14,-10,-10,10]。

契约:输入必须是非空的十进制非负整数与二元 +、-、* 交替组成的字符串;没有空格、括号、一元负号或小数。数字和所有可能的中间结果须为安全整数。此教学枚举仅适合短表达式。

任意括号结构都有一个最后运算符。枚举这个位置,左右分别求出所有可能结果,再做笛卡尔积组合。没有运算符时就是一个数,递归终止。相同子串会被多次求解,使用共享记忆表避免重复。

js
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。解释为什么左右结果要两两组合,而不能只各取第一个。再比较归并:为什么归并每次固定分成两半,这题却要枚举所有分割位置?

评论

正在加载评论…