代码随想录算法训练营第四十八天| 198.打家劫舍、213.打家劫舍II、337.打家劫舍III

本文主要是介绍代码随想录算法训练营第四十八天| 198.打家劫舍、213.打家劫舍II、337.打家劫舍III，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

代码随想录算法训练营第四十八天| 198.打家劫舍、213.打家劫舍II、337.打家劫舍III

题目

198.打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

class Solution:def rob(self, nums: List[int]) -> int:if not nums:return 0if len(nums) == 1:return nums[0]dp = [0] * len(nums)dp[0] = nums[0]dp[1] = max(nums[0], nums[1])for i in range(2, len(nums)):# 旁边的最大值和如果偷当前，两个判断dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])return dp[-1]

题目

213.打家劫舍II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

class Solution:def rob(self, nums: List[int]) -> int:if len(nums) < 3:return max(nums)# 本质上还是第一版，但是第二版抢劫只有四种可能# 抢第一家，不抢最后一家# 不抢第一家，抢最后一家# 不抢第一家，不抢最后一家# 抢第一家，抢最后一家（这种情况明显不符合题意）# 因此只需要分开求不抢某一家的最大值，返回最大值就可以了no_first = self.rob_circle(nums[1:])no_end = self.rob_circle(nums[:-1])return max(no_first, no_end)def rob_circle(self, nums):        dp = [0] * len(nums)dp[0] = nums[0]dp[1] = max(nums[0], nums[1])flag = 0if nums[0] < nums[1]:flag = 1for i in range(2, len(nums)):if i == len(nums) - 1 and flag == 1:dp[i] = dp[i - 2] + nums[i]dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])return dp[-1]

题目

337.打家劫舍III

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额。

# Definition for a binary tree node.
# 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: Optional[TreeNode]) -> int:res = self.traversal(root)return max(res)def traversal(self, node):if not node:return (0, 0)# 左代表已经被偷，不可以偷当前结点# 右代表还没被偷，可以偷当前结点left = self.traversal(node.left)right = self.traversal(node.right)rob_val = max(left[0], left[1]) + max(right[0], right[1]) # 子结点已经被偷，当前结点不能偷了no_rob_val = node.val + left[1] + right[1] # 子结点没被偷过，这个结点可以偷了return (no_rob_val, rob_val)