浙江网站建设模板网站,wordpress重新安装,为什么输入网址打开的却是别的网站,网站建设营改增198.打家劫舍
力扣题目链接(opens new window)
你是一个专业的小偷#xff0c;计划偷窃沿街的房屋。每间房内都藏有一定的现金#xff0c;影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统#xff0c;如果两间相邻的房屋在同一晚上被小偷闯入#xff0c;系…198.打家劫舍
力扣题目链接(opens new window)
你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组计算你 不触动警报装置的情况下 一夜之内能够偷窃到的最高金额。
示例 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 。
提示
0 nums.length 1000 nums[i] 400 要解决这个问题我们可以创建一个数组来存储到每个房屋为止可以偷窃到的最大金额。对于数组中的每个元素 dp[i]有两个选择要么偷前一个房屋 dp[i-1]要么偷这个房屋加上前前一个房屋的金额 nums[i] dp[i-2]。我们取这两个选择中的最大值作为 dp[i] 的值。
状态转移方程可以写成这样
dp[i] max(dp[i-1], nums[i] dp[i-2])
初始条件是
dp[0] nums[0]只有一个房子则偷这个房子dp[1] max(nums[0], nums[1])两个房子则偷金额较大的那个
最终答案就是 dp[n-1]其中 n 是数组的长度。
class Solution:def rob(self, nums: List[int]) - int:if len(nums) 0: # 如果没有房屋返回0return 0if len(nums) 1: # 如果只有一个房屋返回其金额return nums[0]# 创建一个动态规划数组用于存储最大金额dp [0] * len(nums)dp[0] nums[0] # 将dp的第一个元素设置为第一个房屋的金额dp[1] max(nums[0], nums[1]) # 将dp的第二个元素设置为第一二个房屋中的金额较大者# 遍历剩余的房屋for i in range(2, len(nums)):# 对于每个房屋选择抢劫当前房屋和抢劫前一个房屋的最大金额dp[i] max(dp[i - 2] nums[i], dp[i - 1])return dp[-1] # 返回最后一个房屋中可抢劫的最大金额 213.打家劫舍II
力扣题目链接(opens new window)
你是一个专业的小偷计划偷窃沿街的房屋每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 这意味着第一个房屋和最后一个房屋是紧挨着的。同时相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组计算你 在不触动警报装置的情况下 能够偷窃到的最高金额。
示例 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 [0] 输出0
提示
1 nums.length 1000 nums[i] 1000
class Solution:def rob(self, nums: List[int]) - int:if len(nums) 0:return 0if len(nums) 1:return nums[0]result1 self.robRange(nums, 0, len(nums) - 2) # 情况二result2 self.robRange(nums, 1, len(nums) - 1) # 情况三return max(result1, result2)# 198.打家劫舍的逻辑def robRange(self, nums: List[int], start: int, end: int) - int:if end start:return nums[start]prev_max nums[start]curr_max max(nums[start], nums[start 1])for i in range(start 2, end 1):temp curr_maxcurr_max max(prev_max nums[i], curr_max)prev_max tempreturn curr_max
337.打家劫舍 III
力扣题目链接(opens new window)
在上次打劫完一条街道之后和一圈房屋后小偷又发现了一个新的可行窃的地区。这个地区只有一个入口我们称之为“根”。 除了“根”之外每栋房子有且只有一个“父“房子与之相连。一番侦察之后聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫房屋将自动报警。
计算在不触动警报的情况下小偷一晚能够盗取的最高金额。 解题关键在于考虑偷与不偷当前节点时的最大值需要计算两种情况
偷当前节点那么就不能偷它的子节点。不偷当前节点那么可以偷它的子节点。
对于二叉树上的每一个节点我们都保持它偷与不偷的最大值。在Python中这可以通过使用递归函数实现它返回一个包含两个元素的元组分别代表不偷当前节点时的最大值和偷当前节点时的最大值。
以下是Python代码示例这段代码解决了这个问题
class TreeNode:def __init__(self, val0, leftNone, rightNone):self.val valself.left leftself.right rightdef rob(root):def dfs(node):if not node:return (0, 0)left dfs(node.left)right dfs(node.right)# 不偷当前节点左右子节点可以偷或不偷取各自最大值rob_no max(left) max(right)# 偷当前节点左右子节点都不能偷rob_yes node.val left[0] right[0]return (rob_no, rob_yes)return max(dfs(root))# 假设有一棵树你可以这样调用函数
# root TreeNode(3)
# root.left TreeNode(2)
# root.right TreeNode(3)
# root.left.right TreeNode(3)
# root.right.right TreeNode(1)
# print(rob(root))在这段代码中dfs是一个递归函数它对二叉树进行深度优先搜索。它返回的元组的第一个元素表示不偷当前节点时从该节点开始的子树能偷到的最大金额第二个元素表示偷当前节点时从该节点开始的子树能偷到的最大金额。最终rob函数返回从根节点出发能偷到的最大金额。
