小落叶的个人知识库

外观

📖预计阅读时长：0 分钟字数：0

代码随想录 — 回溯与贪心 ​

对应 leetcode-master：回溯理论基础、77/216/17/39/40/131/93/78/90/491/46/47/332/51/37、贪心理论、455/376/53/122/55/45/134/135/406/452/435/763/56/738/968 等。

一、回溯算法理论基础 ​

  • 本质：一种搜索方式，常通过递归实现；回溯 = 递归的副产品，递归时「恢复状态」就是回溯。
  • 特点：穷举所有可能，再筛选答案；可加剪枝减少搜索，但本质仍是穷举。
  • 适用：组合（不强调顺序）、排列（强调顺序）、切割、子集、棋盘（N 皇后、数独）等。
  • 抽象：所有回溯问题都可抽象成树形结构：集合大小 = 树的宽度（for 选谁），递归深度 = 树的深度（选了几层）。

回溯模板（牢记） ​

text
void backtracking(参数) {
  if (终止条件) {
    存放结果;
    return;
  }
  for (选择：本层集合中的元素) {
    处理节点;
    backtracking(路径, 选择列表);  // 递归
    回溯，撤销处理;
  }
}
  • 横向：for 循环枚举本层可选元素。
  • 纵向：backtracking 递归到下一层。
  • 回溯：撤销本层对「路径」或「状态」的修改，才能正确尝试同层其它分支。

二、回溯 — 组合与切割 ​

题目思路要点
77 组合从 [1,n] 选 k 个数。递归参数：startIndex（本层从哪开始选）、path。终止：path.length === k。for 从 startIndex 到 n，选完递归 startIndex+1，回溯 pop。可剪枝：剩余元素不够 k-path.length 时不再枚举。
216 组合总和 III选 k 个数和为 n，只用 1～9，每个最多用一次。同 77，多一个「和为 n」的终止与剪枝（和已超 n 可剪）。
17 电话号码字母组合每个数字对应若干字母，求所有字母组合。层数 = 数字个数，每层选当前数字的一个字母，递归下一数字。
39 组合总和同一数组可重复选，和为 target。递归时从 startIndex 开始，选完仍从 startIndex 递归（可重复）；终止 target===0；剪枝：排序后若当前数已大于 target 可剪。
40 组合总和 II数组有重复，每个数只能用一次，组合不重复。排序 + 同层去重：for 里若 i>startIndex 且 nums[i]===nums[i-1] 则 continue。
131 分割回文串枚举切割点，保证每段是回文。递归参数 startIndex，for 枚举结束位置 i，若 s[startIndex,i] 是回文则加入 path 并递归 i+1，回溯 pop。
93 复原 IP类似切割，每段 0～255、无前导 0、共 4 段。注意单 0 合法，"01" 不合法。

三、回溯 — 子集与排列 ​

题目思路要点
78 子集所有子集。每个节点都是结果，先 push 当前 path 再 for；for 从 startIndex 开始，选完递归 i+1，回溯 pop。
90 子集 II数组有重复，子集不重复。同 40：排序 + 同层去重（i>startIndex && nums[i]===nums[i-1] continue）。
491 递增子序列不能排序（要保原顺序），同层去重用 Set：每层用 Set 记录本层已用过的值，重复则 continue。
46 全排列无重复数组，全排列。不用 startIndex，用 used 数组标记已选；for 遍历整个数组，未选的选上、递归、回溯。
47 全排列 II有重复。排序 + 同层去重：used[i-1]===false 且 nums[i]===nums[i-1] 时 continue（避免同一层重复选相同值）。
332 重新安排行程图上的回溯，求欧拉路径；需要建邻接表并排序（或按字典序选边），回溯时删边。
51 N 皇后每行放一个，列、两条对角线不能冲突。用数组记列、主对角、副对角是否占用；按行递归，每行 for 列，合法则放并递归下一行，回溯。
37 解数独每个空位试 1～9，行/列/九宫格不重复；找到一组解即返回，所以 backtracking 可返回 bool。

去重小结：组合/子集里「同一层不选相同值」→ 排序 + i>startIndex && nums[i]===nums[i-1]；排列里「同一层不选相同值」→ 排序 + !used[i-1] && nums[i]===nums[i-1]；不能排序时用 Set 记本层已用。

四、贪心算法理论基础 ​

  • 本质：每步选当前局部最优，希望得到全局最优。没有状态推导，和 DP 不同（DP 由前一状态推导）。
  • 何时用：没有固定套路；可先手动模拟，若「局部最优能推出全局最优」且举不出反例，可试贪心。
  • 验证：举反例最实用；面试中能说清「为什么这样选」、代码过用例即可，一般不要求严格证明。

五、贪心 — 经典题思路 ​

题目思路要点
455 分发饼干胃口和饼干都排序，小饼干先满足小胃口；双指针或贪心匹配。
376 摆动序列保留「峰」和「谷」，中间单调的删；可记录当前趋势（升/降），只在趋势变化时计数。
53 最大子序和当前和 <0 就舍弃（从当前重开），否则累加；过程中更新最大和。
122 买卖股票 II可多次买卖。贪心：相邻两天能赚就累加（等价于所有上升段都吃）。
55 跳跃游戏能否到终点。维护「当前能到的最远距离」maxReach，若 i>maxReach 则 false，否则 maxReach = max(maxReach, i+nums[i])。
45 跳跃游戏 II最少跳数。可维护「当前步能到的范围」与「下一步能到的最大范围」，出范围则步数+1 并更新范围。
1005 K 次取反负数优先取反（从小到大），若 k 有剩且为奇则对最小正数取反一次。
134 加油站若总油量≥总耗则必有解。从 0 开始，累加 rest[i]，若当前和 <0 则起点移到 i+1、和清零；最后起点即答案。
135 分发糖果左右各扫一遍：左扫保证「比左大则多 1」，右扫保证「比右大则多 1」，取两者较大。
860 柠檬水找零优先用 10 找 20（保留 5）；5 和 10 的个数维护好即可。
406 根据身高重建队列按身高降序、同高按 k 升序；然后按 k 作为「前面有几个≥自己身高」插入到结果数组的 k 位置（贪心：矮的插到前面不影响高的 k）。
452 用最少数量的箭按右端点排序，每支箭射在区间右端点；若下一区间左端点超过当前右端点则新箭。
435 无重叠区间按右端点排序，选不重叠的最多区间（与 452 类似）；总数 - 最多不重叠数 = 最少删除数。
763 划分字母区间先记录每个字母最后出现位置；遍历时更新「当前段最远」，当 i 等于当前段最远时切一刀。
56 合并区间按左端点排序，若当前与上一段重叠则合并（更新右端点为 max），否则新开一段。
738 单调递增的数字从高到低找第一个「前一位>当前位」的位置，该位减 1、后面全变 9；注意 0 和借位。
968 监控二叉树后序：节点状态 0 未覆盖/1 摄像头/2 已覆盖；叶子尽量不放摄像头，由父覆盖；根若未覆盖则多放一个。

六、回溯与贪心总结 ​

  • 回溯：树形枚举 + 递归 + 回溯撤销；组合用 startIndex，排列用 used；去重分清「树层」与「树枝」。
  • 贪心：局部最优推全局；区间题常按一端排序；证不了就模拟 + 举反例。

附：核心代码模板 ​

回溯模板 — 组合（77） ​

javascript
// JavaScript — 从 [1,n] 选 k 个数的所有组合
function combine(n, k) {
  const res = [], path = [];
  function backtrack(start) {
    if (path.length === k) { res.push([...path]); return; }
    // 剪枝：剩余元素不够时提前终止
    for (let i = start; i <= n - (k - path.length) + 1; i++) {
      path.push(i);
      backtrack(i + 1);
      path.pop(); // 回溯
    }
  }
  backtrack(1);
  return res;
}

回溯模板 — 全排列（46） ​

javascript
// JavaScript — 无重复数组全排列
function permute(nums) {
  const res = [], path = [], used = new Array(nums.length).fill(false);
  function backtrack() {
    if (path.length === nums.length) { res.push([...path]); return; }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      used[i] = true;
      path.push(nums[i]);
      backtrack();
      path.pop();
      used[i] = false; // 回溯
    }
  }
  backtrack();
  return res;
}
python
# Python — 全排列
def permute(nums):
    res, path = [], []
    used = [False] * len(nums)
    def backtrack():
        if len(path) == len(nums):
            res.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            backtrack()
            path.pop()
            used[i] = False
    backtrack()
    return res

贪心 — 跳跃游戏（55） ​

javascript
// JavaScript — 时间 O(n)
function canJump(nums) {
  let maxReach = 0;
  for (let i = 0; i <= maxReach && i < nums.length; i++) {
    maxReach = Math.max(maxReach, i + nums[i]);
  }
  return maxReach >= nums.length - 1;
}

贪心 — 合并区间（56） ​

javascript
// JavaScript — 时间 O(n log n)
function merge(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  const res = [intervals[0]];
  for (let i = 1; i < intervals.length; i++) {
    const last = res[res.length - 1];
    if (intervals[i][0] <= last[1]) {
      last[1] = Math.max(last[1], intervals[i][1]);
    } else {
      res.push(intervals[i]);
    }
  }
  return res;
}

Copyright@ 2024 Luoye Zero