贪心、回溯、分治完全指南:算法三大范式与位运算技巧

"贪心、回溯、分治"是算法面试三大难点。它们不像 DP 那样有固定模板,需要"看见问题就想到用哪个"的直觉。这篇文章把这三种算法范式讲透,所有结论配题型识别和经典题。

贪心(Greedy)

核心思想:每一步都选当前看起来最好的,期望最终全局最优。

例题:活动选择

给一组活动 (start, end),选最多不重叠的活动。

function maxActivities(activities) {
    activities.sort((a, b) => a.end - b.end);   // 按结束时间排序
    let count = 0, lastEnd = -Infinity;
    for (const act of activities) {
        if (act.start >= lastEnd) {
            count++;
            lastEnd = act.end;
        }
    }
    return count;
}

贪心策略:"选结束最早的"。直觉对:结束早留出更多时间给后续。

例题:Huffman 编码

给字符频率,生成最优前缀编码。贪心:每次合并频率最小的两个。最终生成最优二叉树。压缩算法的基础。

例题:最少跳跃次数

function jump(nums) {
    let maxReach = 0, curEnd = 0, jumps = 0;
    for (let i = 0; i < nums.length - 1; i++) {
        maxReach = Math.max(maxReach, i + nums[i]);
        if (i === curEnd) {
            jumps++;
            curEnd = maxReach;
        }
    }
    return jumps;
}

贪心的陷阱

不是所有问题贪心都对!"局部最优 ≠ 全局最优"。例:

• 找零问题:用面值 [1, 5, 10],贪心(优先大面值)能给出最优。
• 找零问题:用面值 [1, 3, 4],凑 6 元 —— 贪心给 4+1+1=3 张,但 3+3=2 张更优!

必须证明贪心策略的"正确性"才能用,否则改用 DP。

回溯(Backtracking)

核心:系统枚举所有候选,失败时撤销选择回到上一步继续尝试。"带剪枝的暴力"。

模板

function backtrack(state, choices) {
    if (isFinished(state)) {
        recordSolution(state);
        return;
    }
    for (const choice of choices) {
        if (!isValid(state, choice)) continue;   // 剪枝
        applyChoice(state, choice);             // 做选择
        backtrack(state, getNextChoices(state)); // 递归
        undoChoice(state, choice);              // 撤销选择
    }
}

例题:全排列

function permute(nums) {
    const result = [];
    function bt(path, used) {
        if (path.length === nums.length) {
            result.push([...path]);
            return;
        }
        for (let i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            path.push(nums[i]); used[i] = true;
            bt(path, used);
            path.pop(); used[i] = false;
        }
    }
    bt([], new Array(nums.length).fill(false));
    return result;
}

例题:N 皇后

function solveNQueens(n) {
    const result = [];
    const cols = new Set(), diag1 = new Set(), diag2 = new Set();
    function bt(row, path) {
        if (row === n) { result.push([...path]); return; }
        for (let col = 0; col < n; col++) {
            if (cols.has(col) || diag1.has(row-col) || diag2.has(row+col)) continue;
            cols.add(col); diag1.add(row-col); diag2.add(row+col);
            path.push(col);
            bt(row + 1, path);
            cols.delete(col); diag1.delete(row-col); diag2.delete(row+col);
            path.pop();
        }
    }
    bt(0, []);
    return result;
}

例题:数独求解

同样套路:为每个空格尝试 1-9,违反规则就回溯。剪枝越强,速度越快(优先填可选最少的格)。

剪枝的艺术

朴素回溯指数级,加好剪枝能差几个数量级:

• 可行性剪枝:当前部分解已经违反约束,放弃。
• 最优性剪枝:当前解已经不可能比已知最优更好,放弃。
• 对称性剪枝:利用问题对称性,避免重复枚举(N 皇后第一行只搜前半部分,镜像即可)。

分治(Divide and Conquer)

核心:把大问题分成几个相同子问题,分别解决后合并。

归并排序

function mergeSort(arr) {
    if (arr.length <= 1) return arr;
    const mid = arr.length >> 1;
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));
    return merge(left, right);
}

function merge(a, b) {
    const result = [];
    let i = 0, j = 0;
    while (i < a.length && j < b.length) {
        if (a[i] <= b[j]) result.push(a[i++]);
        else result.push(b[j++]);
    }
    return [...result, ...a.slice(i), ...b.slice(j)];
}

分治三步:Divide(分)、Conquer(治)、Combine(合)。归并排序是典型。

快速排序

function quickSort(arr, lo = 0, hi = arr.length - 1) {
    if (lo >= hi) return;
    const p = partition(arr, lo, hi);
    quickSort(arr, lo, p - 1);
    quickSort(arr, p + 1, hi);
}

function partition(arr, lo, hi) {
    const pivot = arr[hi];
    let i = lo;
    for (let j = lo; j < hi; j++) {
        if (arr[j] < pivot) {
            [arr[i], arr[j]] = [arr[j], arr[i]];
            i++;
        }
    }
    [arr[i], arr[hi]] = [arr[hi], arr[i]];
    return i;
}

Top K 问题:快速选择

// 第 K 大元素,O(n) 平均
function kthLargest(nums, k) {
    function quickSelect(lo, hi, target) {
        const p = partition(nums, lo, hi);
        if (p === target) return nums[p];
        if (p < target) return quickSelect(p + 1, hi, target);
        return quickSelect(lo, p - 1, target);
    }
    return quickSelect(0, nums.length - 1, nums.length - k);
}

大数乘法:Karatsuba

朴素 O(n²),Karatsuba 分治算法 O(n^log2(3)) ≈ O(n^1.585)。BigInteger 类库底层用类似算法。

位运算技巧

不算独立范式,但是常用工具:

// 判奇偶:比 % 快
n & 1                  // 1 是奇数

// 乘除 2 的幂
n << k                  // n * 2^k
n >> k                  // n / 2^k(向下取整)

// 取最低位的 1
n & -n

// 消除最低位的 1
n & (n - 1)

// 判断是不是 2 的幂
n > 0 && (n & (n - 1)) === 0

// 统计 1 的个数(Brian Kernighan 算法)
function popcount(n) {
    let count = 0;
    while (n) { n &= n - 1; count++; }
    return count;
}

// 数组中唯一不重复的数(其他都出现两次)
function singleNumber(nums) {
    return nums.reduce((a, b) => a ^ b, 0);
}

// 位掩码状态压缩(用 32/64 位整数表示 N 个布尔值)
const FLAG_A = 1, FLAG_B = 2, FLAG_C = 4;
let flags = FLAG_A | FLAG_C;
if (flags & FLAG_A) { ... }

识别题型

• "最少 / 最多 + 当前选择不影响后续" → 贪心。
• "找出所有可能的" → 回溯。
• "可以分成相同子问题" → 分治。
• "最值 / 计数 + 子问题重叠" → DP。
• 位级别操作 / 状态压缩 → 位运算。

实战:Sudoku 求解器

function solveSudoku(board) {
    function isValid(row, col, num) {
        for (let i = 0; i < 9; i++) {
            if (board[row][i] === num) return false;
            if (board[i][col] === num) return false;
            const boxRow = 3 * Math.floor(row/3) + Math.floor(i/3);
            const boxCol = 3 * Math.floor(col/3) + i%3;
            if (board[boxRow][boxCol] === num) return false;
        }
        return true;
    }

    function bt() {
        for (let row = 0; row < 9; row++) {
            for (let col = 0; col < 9; col++) {
                if (board[row][col] === '.') {
                    for (let n = '1'; n <= '9'; n++) {
                        if (isValid(row, col, n)) {
                            board[row][col] = n;
                            if (bt()) return true;
                            board[row][col] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    bt();
}

写在最后

贪心 / 回溯 / 分治 是算法工具箱的三大基石。理解它们的核心思想后,面对新问题你能快速判断"哪类",再套对应模板。算法不是死记题目,是积累"问题特征 → 算法范式"的映射。这种映射熟练后,LeetCode 中等题大多能 15 分钟内解决。

—— 别看了 · 2026