leetcode 对应题号： 198、213、337、2560
1. 打家劫舍 I House Robber i
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
提示：
1 <= nums.length <= 100
0 <= nums[i] <= 400
代码：
class Solution: def rob1(self, nums): if not nums: return 0 n = len(nums) if n == 1: return nums[0] dp = [0] * n dp[0] = nums[0] dp[1] = max(nums[0], nums[1]) for i in range(2, n): dp[i] = max(dp[i-2]+nums[i], dp[i-1]) return dp[n-1] def rob2(self, nums): if not nums: return 0 n = len(nums) if n == 1: return nums[0] prepre, pre = nums[0], max(nums[0], nums[1]) for i in range(2, n): cur = max(prepre+nums[i], pre) prepre, pre = pre, cur return pre def rob3(self, nums): mem = [-1] * len(nums) return helper(nums, mem, len(nums)-1) def helper(nums, mem, i): if i < 0: return 0 if mem[i] >= 0: return mem[i] res = max(helper(nums, mem, i-2)+nums[i], helper(nums, mem, i-1)) mem[i] = res return res if __name__ == '__main__': solution = Solution() nums = [1, 2, 3, 1] print(solution.rob1(nums)) print(solution.rob2(nums)) print(solution.rob3(nums)) nums = [2, 7, 9, 3, 1] print(solution.rob1(nums)) print(solution.rob2(nums)) print(solution.rob3(nums))
输出：
4
4
4
12
12
12
2. 打家劫舍 II House Robber ii
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
示例 1：
输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例 2：
输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 3：
输入：nums = [1,2,3]
输出：3
提示：
1 <= nums.length <= 100
0 <= nums[i] <= 1000
代码：
def robII(nums): if not nums: return 0 n = len(nums) if n == 1: return nums[0] return max(rob_range(nums, 0, n-2), rob_range(nums, 1, n-1)) def rob_range(nums, start, end): dp = [0] * (end-start+1) dp[0] = nums[start] dp[1] = max(nums[start], nums[start+1]) for i in range(2, end-start+1): dp[i] = max(dp[i-2]+nums[start+i], dp[i-1]) return dp[-1] if __name__ == '__main__': nums = [2,3,2] print(robII(nums)) nums = [1,2,3,1] print(robII(nums)) nums = [1,2,3] print(robII(nums))
3
4
3
3. 打家劫舍 III House Robber iii
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
示例 1:
输入: root = [3,2,3,null,3,null,1]
输出: 7
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7
示例 2:
输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9
提示：
- 树的节点数在
[1, 10^4]范围内 0 <= Node.val <= 10^4
代码：
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class Solution: def rob(self, root: TreeNode) -> int: def _rob(node): if not node: return (0, 0) left = _rob(node.left) right = _rob(node.right) rob = node.val + left[1] + right[1] not_rob = max(left) + max(right) return (rob, not_rob) return max(_rob(root)) def listToTree(lst: list) -> TreeNode: if not lst: return None root = TreeNode(lst[0]) queue = [root] i = 1 while i < len(lst): node = queue.pop(0) if lst[i] is not None: node.left = TreeNode(lst[i]) queue.append(node.left) i += 1 if i < len(lst) and lst[i] is not None: node.right = TreeNode(lst[i]) queue.append(node.right) i += 1 return root if __name__ == '__main__': solution = Solution() null = None root = listToTree([3,2,3,null,3,null,1]) print(solution.rob(root)) root = listToTree([3,4,5,1,3,null,1]) print(solution.rob(root))
输出：
7
9
4. 打家劫舍 IV House Robber iv
沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。
由于相邻的房屋装有相互连通的防盗系统，所以小偷 不会窃取相邻的房屋 。
小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额 。
给你一个整数数组 nums 表示每间房屋存放的现金金额。形式上，从左起第 i 间房屋中放有 nums[i] 美元。
另给你一个整数 k ，表示窃贼将会窃取的 最少 房屋数。小偷总能窃取至少 k 间房屋。
返回小偷的 最小 窃取能力。
示例 1：
输入：nums = [2,3,5,9], k = 2
输出：5
解释：
小偷窃取至少 2 间房屋，共有 3 种方式：
- 窃取下标 0 和 2 处的房屋，窃取能力为 max(nums[0], nums[2]) = 5 。
- 窃取下标 0 和 3 处的房屋，窃取能力为 max(nums[0], nums[3]) = 9 。
- 窃取下标 1 和 3 处的房屋，窃取能力为 max(nums[1], nums[3]) = 9 。
因此，返回 min(5, 9, 9) = 5 。
示例 2：
输入：nums = [2,7,9,3,1], k = 2
输出：2
解释：共有 7 种窃取方式。窃取能力最小的情况所对应的方式是窃取下标 0 和 4 处的房屋。返回 max(nums[0], nums[4]) = 2 。
提示：
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
1 <= k <= (nums.length + 1)/2
代码：
from typing import List class Solution: def minCapability(self, nums: List[int], k: int) -> int: left = min(nums) right = max(nums) dp = [0] * (len(nums) + 2) while left <= right: mid = left + (right - left) // 2 for i in range(len(nums)): dp[i + 2] = dp[i + 1] if nums[i] <= mid: dp[i + 2] = max(dp[i + 2], dp[i] + 1) if dp[len(nums) + 1] >= k: right = mid - 1 else: left = mid + 1 return left if __name__ == '__main__': s = Solution() nums = [2, 3, 5, 9] print(s.minCapability(nums, 2)) nums = [2, 7, 9, 3, 1] print(s.minCapability(nums, 2))
输出：
5
2
