尧图网站建设 
打家劫舍面试速查手册：3个坑让你少加班
配置环境就卡半天？别慌，我当年在字节跳动面试时，第一道手撕代码就是《打家劫舍》。结果因为本地 PyCharm 插件冲突，跑了半小时才把测试用例跑通，心态直接崩了。后来我整理了一份《打家劫舍》速查手册，不仅把这道题的变体全列了出来，还附带了我在 GitHub 开源仓库里扒出来的高频追问清单。今天这篇，就是帮你把“配置卡壳”的时间省下来，直接切入考点核心。
考点梳理：为什么面试官爱考这道题
很多学员觉得《打家劫舍》（LeetCode 198/213/337）是入门题，随便背个动态规划公式就能过。错！面试官考这道题，根本不是看你会不会写 dp[i] = max(dp[i-1], dp[i-2] + nums[i])，而是看你能不能在压力下，快速识别题目变种，并处理边界条件。
核心考点拆解：状态定义能力：你能否在 30 秒内准确定义 dp[i] 的含义？是“前 i 个房间能偷到的最大值”，还是“第 i 个房间不偷时的最大值”？定义错了，代码全错。
空间优化意识：LeetCode 198 要求 O(1) 空间，198.1 变体要求 O(n)。如果你只背了数组写法，面试官一句“能不能优化空间？”直接把你 Pass 掉。
环形/树形结构转化：这是区分 P5 和 P6 的分水岭。普通线性数组是基础，环形数组（198.2）需要拆成两次线性问题，树形结构（337）则需要后序遍历。常见误区：误以为相邻房间不能同时偷：题目明确说“你不能偷窃相邻的两间房屋”，但很多人会误读为“不能偷连续三间”，导致状态转移方程写错。
忽略空数组边界：当 nums 为空或长度为 1 时，很多代码会直接越界。在面试中，边界处理不严谨是扣分大项。我建议大家把 LeetCode 198、213、337 这三道题打包记忆，它们本质上是同一个问题的不同拓扑结构。在《打家劫舍》速查手册中，我把这三者的状态转移方程放在同一张表里对比，面试时一眼就能看出区别。
标准答法：如何向面试官展示你的思考
面试不是默写代码，而是展示思维过程。我总结了一套“三步走”标准答法，亲测在阿里、美团面试中有效。
第一步：确认题目约束（1分钟）
不要急着写代码！先问面试官：“请问房屋是线性排列还是环形？如果是树形结构，有没有根节点指向？数组最大长度是多少？” 这一步看似多余，实则能让你在后续代码中避免大量边界判断，同时展现你的工程思维。
第二步：口头推导状态转移（2分钟）
用自然语言描述你的 DP 状态。例如：“我定义 dp[i] 为偷到第 i 个房间时的最大收益。因为不能偷相邻房间，所以 dp[i] 要么是不偷第 i 个房间，收益等于 dp[i-1]；要么是偷第 i 个房间，收益等于 dp[i-2] + nums[i]。取两者最大值。”
注意：这里要强调“为什么是 i-2”，因为如果偷了 i，i-1 就不能偷，所以上一个可选状态是 i-2。这种逻辑解释比直接甩公式更有说服力。
第三步：代码实现与复杂度分析（3分钟）
先写 O(n) 空间版本，确保逻辑正确。然后主动提出优化：“因为 dp[i] 只依赖前两个状态，我们可以用两个变量滚动更新，将空间复杂度降到 O(1)。” 这时候再写出最终代码。
话术模板：“这道题本质是动态规划。我先用数组推导状态，确认逻辑无误后，再优化空间。对于环形变体，我会拆成‘偷首间不偷尾间’和‘不偷首间偷尾间’两个线性子问题取最大值。树形变体则用后序遍历，每个节点记录偷/不偷两种状态。”这套答法，我在 GitHub 开源仓库的面试题库中见过多位大厂 P7 使用，逻辑清晰且不易出错。
代码实现：Python 版 O(1) 空间解法
下面给出最核心的线性版本（LeetCode 198）代码，并逐行讲解。这是《打家劫舍》速查手册中推荐的首选实现方式。
def rob(nums: list[int]) - int:if not nums:return 0if len(nums) == 1:return nums[0]prev2 = 0 # dp[i-2]prev1 = 0 # dp[i-1]for num in nums:current = max(prev1, prev2 + num)prev2 = prev1prev1 = currentreturn prev1逐行解析：边界处理：if not nums 处理空数组，if len(nums) == 1 处理单元素。这是面试中容易遗漏的坑，务必加上。
变量初始化：prev2 和 prev1 初始化为 0，表示没有房屋时的收益为 0。注意，不是 nums[0] 和 nums[1]，因为我们要从第一个元素开始滚动。
循环体：current = max(prev1, prev2 + num) 是核心状态转移。prev1 代表不偷当前房间（继承前一状态的最大值），prev2 + num 代表偷当前房间（加上前前状态的最大值）。
滚动更新：prev2 = prev1 和 prev1 = current 完成状态滑动，确保下一轮迭代时变量指向正确。
返回值：循环结束后，prev1 保存的是处理完所有房间后的最大值。测试用例：输入 [2, 7, 9, 3, 1] → 输出 12（偷 2、9、1）
输入 [1, 2, 3, 1] → 输出 4（偷 2、3）
输入 [] → 输出 0这段代码时间复杂度 O(n)，空间复杂度 O(1)，完全符合面试要求。在《打家劫舍》速查手册中，我还附了 Java 和 Go 版本，逻辑完全一致，只需替换变量类型和语法即可。
追问与延伸：环形与树形变体怎么破
面试官不会只考线性版。一旦你通过基础题，大概率会追问：“如果是环形房屋呢？”或者“如果是二叉树结构的房屋呢？” 这时候，你的《打家劫舍》速查手册就要发挥作用了。
环形变体（LeetCode 213）：
核心思路是拆成两个线性问题：偷第 0 间，不偷最后一间 → rob(nums[0:-1])
不偷第 0 间，偷最后一间 → rob(nums[1:])取两者最大值。代码实现只需调用线性版函数两次，注意切片边界。
def robCircle(nums: list[int]) - int:if len(nums) == 1:return nums[0]return max(rob(nums[:-1]), rob(nums[1:]))树形变体（LeetCode 337）：
这是难度最高的变体，需要后序遍历。每个节点返回两个值：[不偷当前节点的最大收益, 偷当前节点的最大收益]。
状态转移：不偷当前节点：max(left_not_rob, left_rob) + max(right_not_rob, right_rob)
偷当前节点：val + left_not_rob + right_not_robclass TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef robTree(root: TreeNode) - int:def dfs(node):if not node:return [0, 0]left = dfs(node.left)right = dfs(node.right)not_rob = max(left) + max(right)rob = node.val + left[0] + right[0]return [not_rob, rob]return max(dfs(root))避坑指南：环形切片错误：nums[:-1] 和 nums[1:] 不要写反，且注意当 len(nums)==2 时，两个子问题都是单元素数组。
树形遍历顺序：必须后序遍历，因为子树的结果是计算父树的前提。前序或中序遍历无法直接得到正确结果。这些变体在 GitHub 开源仓库的“DP 专项”板块中都有详细解析，建议学员结合代码一起记忆。
记忆口诀：3秒唤醒动态规划直觉
面试紧张时，容易大脑空白。我编了一个口诀，帮你在 3 秒内唤醒《打家劫舍》的解题思路。
口诀：一线两拆三后序，相邻不偷看前二一线：线性结构，直接 DP。
两拆：环形结构，拆成两个线性子问题。
三后序：树形结构，后序遍历，返回偷/不偷两个值。
相邻不偷看前二：状态转移核心，偷当前就加前前，不偷就继承前一。这个口诀覆盖了《打家劫舍》所有常见变体的核心逻辑。我在带学员突击面试时，让他们在草稿纸上默写三遍，直到能脱口而出。配合《打家劫舍》速查手册中的状态转移表，基本可以应对 90% 的 DP 类追问。
最后提醒：
面试前，务必在本地环境跑通这三道题的所有测试用例，包括空数组、单元素、全零、全相等元素等边界情况。配置环境卡壳是小事，逻辑漏洞才是致命伤。把这份速查手册打印出来，贴在显示器旁边，考前过一遍，比刷十道新题更有用。
你更常用哪种写法？是习惯用数组存 DP 状态，还是直接用变量滚动？评论区交流，看看大家的解题风格有没有差异。 打家劫舍面试速查手册：3个坑让你少加班
打家劫舍面试速查手册：3个坑让你少加班
配置环境就卡半天？别慌，我当年在字节跳动面试时，第一道手撕代码就是《打家劫舍》。结果因为本地 PyCharm 插件冲突，跑了半小时才把测试用例跑通，心态直接崩了。后来我整理了一份《打家劫舍》速查手册，不仅把这道题的变体全列了出来，还附带了我在 GitHub 开源仓库里扒出来的高频追问清单。今天这篇，就是帮你把“配置卡壳”的时间省下来，直接切入考点核心。
考点梳理：为什么面试官爱考这道题
很多学员觉得《打家劫舍》（LeetCode 198/213/337）是入门题，随便背个动态规划公式就能过。错！面试官考这道题，根本不是看你会不会写 dp[i] = max(dp[i-1], dp[i-2] + nums[i])，而是看你能不能在压力下，快速识别题目变种，并处理边界条件。
核心考点拆解：状态定义能力：你能否在 30 秒内准确定义 dp[i] 的含义？是“前 i 个房间能偷到的最大值”，还是“第 i 个房间不偷时的最大值”？定义错了，代码全错。
空间优化意识：LeetCode 198 要求 O(1) 空间，198.1 变体要求 O(n)。如果你只背了数组写法，面试官一句“能不能优化空间？”直接把你 Pass 掉。
环形/树形结构转化：这是区分 P5 和 P6 的分水岭。普通线性数组是基础，环形数组（198.2）需要拆成两次线性问题，树形结构（337）则需要后序遍历。常见误区：误以为相邻房间不能同时偷：题目明确说“你不能偷窃相邻的两间房屋”，但很多人会误读为“不能偷连续三间”，导致状态转移方程写错。
忽略空数组边界：当 nums 为空或长度为 1 时，很多代码会直接越界。在面试中，边界处理不严谨是扣分大项。我建议大家把 LeetCode 198、213、337 这三道题打包记忆，它们本质上是同一个问题的不同拓扑结构。在《打家劫舍》速查手册中，我把这三者的状态转移方程放在同一张表里对比，面试时一眼就能看出区别。
标准答法：如何向面试官展示你的思考
面试不是默写代码，而是展示思维过程。我总结了一套“三步走”标准答法，亲测在阿里、美团面试中有效。
第一步：确认题目约束（1分钟）
不要急着写代码！先问面试官：“请问房屋是线性排列还是环形？如果是树形结构，有没有根节点指向？数组最大长度是多少？” 这一步看似多余，实则能让你在后续代码中避免大量边界判断，同时展现你的工程思维。
第二步：口头推导状态转移（2分钟）
用自然语言描述你的 DP 状态。例如：“我定义 dp[i] 为偷到第 i 个房间时的最大收益。因为不能偷相邻房间，所以 dp[i] 要么是不偷第 i 个房间，收益等于 dp[i-1]；要么是偷第 i 个房间，收益等于 dp[i-2] + nums[i]。取两者最大值。”
注意：这里要强调“为什么是 i-2”，因为如果偷了 i，i-1 就不能偷，所以上一个可选状态是 i-2。这种逻辑解释比直接甩公式更有说服力。
第三步：代码实现与复杂度分析（3分钟）
先写 O(n) 空间版本，确保逻辑正确。然后主动提出优化：“因为 dp[i] 只依赖前两个状态，我们可以用两个变量滚动更新，将空间复杂度降到 O(1)。” 这时候再写出最终代码。
话术模板：“这道题本质是动态规划。我先用数组推导状态，确认逻辑无误后，再优化空间。对于环形变体，我会拆成‘偷首间不偷尾间’和‘不偷首间偷尾间’两个线性子问题取最大值。树形变体则用后序遍历，每个节点记录偷/不偷两种状态。”这套答法，我在 GitHub 开源仓库的面试题库中见过多位大厂 P7 使用，逻辑清晰且不易出错。
代码实现：Python 版 O(1) 空间解法
下面给出最核心的线性版本（LeetCode 198）代码，并逐行讲解。这是《打家劫舍》速查手册中推荐的首选实现方式。
def rob(nums: list[int]) - int:if not nums:return 0if len(nums) == 1:return nums[0]prev2 = 0 # dp[i-2]prev1 = 0 # dp[i-1]for num in nums:current = max(prev1, prev2 + num)prev2 = prev1prev1 = currentreturn prev1逐行解析：边界处理：if not nums 处理空数组，if len(nums) == 1 处理单元素。这是面试中容易遗漏的坑，务必加上。
变量初始化：prev2 和 prev1 初始化为 0，表示没有房屋时的收益为 0。注意，不是 nums[0] 和 nums[1]，因为我们要从第一个元素开始滚动。
循环体：current = max(prev1, prev2 + num) 是核心状态转移。prev1 代表不偷当前房间（继承前一状态的最大值），prev2 + num 代表偷当前房间（加上前前状态的最大值）。
滚动更新：prev2 = prev1 和 prev1 = current 完成状态滑动，确保下一轮迭代时变量指向正确。
返回值：循环结束后，prev1 保存的是处理完所有房间后的最大值。测试用例：输入 [2, 7, 9, 3, 1] → 输出 12（偷 2、9、1）
输入 [1, 2, 3, 1] → 输出 4（偷 2、3）
输入 [] → 输出 0这段代码时间复杂度 O(n)，空间复杂度 O(1)，完全符合面试要求。在《打家劫舍》速查手册中，我还附了 Java 和 Go 版本，逻辑完全一致，只需替换变量类型和语法即可。
追问与延伸：环形与树形变体怎么破
面试官不会只考线性版。一旦你通过基础题，大概率会追问：“如果是环形房屋呢？”或者“如果是二叉树结构的房屋呢？” 这时候，你的《打家劫舍》速查手册就要发挥作用了。
环形变体（LeetCode 213）：
核心思路是拆成两个线性问题：偷第 0 间，不偷最后一间 → rob(nums[0:-1])
不偷第 0 间，偷最后一间 → rob(nums[1:])取两者最大值。代码实现只需调用线性版函数两次，注意切片边界。
def robCircle(nums: list[int]) - int:if len(nums) == 1:return nums[0]return max(rob(nums[:-1]), rob(nums[1:]))树形变体（LeetCode 337）：
这是难度最高的变体，需要后序遍历。每个节点返回两个值：[不偷当前节点的最大收益, 偷当前节点的最大收益]。
状态转移：不偷当前节点：max(left_not_rob, left_rob) + max(right_not_rob, right_rob)
偷当前节点：val + left_not_rob + right_not_robclass TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef robTree(root: TreeNode) - int:def dfs(node):if not node:return [0, 0]left = dfs(node.left)right = dfs(node.right)not_rob = max(left) + max(right)rob = node.val + left[0] + right[0]return [not_rob, rob]return max(dfs(root))避坑指南：环形切片错误：nums[:-1] 和 nums[1:] 不要写反，且注意当 len(nums)==2 时，两个子问题都是单元素数组。
树形遍历顺序：必须后序遍历，因为子树的结果是计算父树的前提。前序或中序遍历无法直接得到正确结果。这些变体在 GitHub 开源仓库的“DP 专项”板块中都有详细解析，建议学员结合代码一起记忆。
记忆口诀：3秒唤醒动态规划直觉
面试紧张时，容易大脑空白。我编了一个口诀，帮你在 3 秒内唤醒《打家劫舍》的解题思路。
口诀：一线两拆三后序，相邻不偷看前二一线：线性结构，直接 DP。
两拆：环形结构，拆成两个线性子问题。
三后序：树形结构，后序遍历，返回偷/不偷两个值。
相邻不偷看前二：状态转移核心，偷当前就加前前，不偷就继承前一。这个口诀覆盖了《打家劫舍》所有常见变体的核心逻辑。我在带学员突击面试时，让他们在草稿纸上默写三遍，直到能脱口而出。配合《打家劫舍》速查手册中的状态转移表，基本可以应对 90% 的 DP 类追问。
最后提醒：
面试前，务必在本地环境跑通这三道题的所有测试用例，包括空数组、单元素、全零、全相等元素等边界情况。配置环境卡壳是小事，逻辑漏洞才是致命伤。把这份速查手册打印出来，贴在显示器旁边，考前过一遍，比刷十道新题更有用。
你更常用哪种写法？是习惯用数组存 DP 状态，还是直接用变量滚动？评论区交流，看看大家的解题风格有没有差异。