网站开发规划书怎么写,wordpress前端会员中心,如何做转发文章赚钱的网站,外贸网站建设的败笔198. 打家劫舍
已解答 中等 相关标签 相关企业 你是一个专业的小偷#xff0c;计划偷窃沿街的房屋。每间房内都藏有一定的现金#xff0c;影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统#xff0c;如果两间相邻的房屋在同一晚上被小偷闯入#xff0c;系统…198. 打家劫舍
已解答 中等 相关标签 相关企业 你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组计算你 不触动警报装置的情况下 一夜之内能够偷窃到的最高金额。
示例 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 1000 nums[i] 400
代码
package __DPfunc rob(nums []int) int {n : len(nums)// 到达i盗窃最高金额dp[i]dp : make([]int, n)dp[0] nums[0]dp[1] rob_max(nums[0],nums[1])for i : 2; i n; i {dp[i] rob_max(dp[i-1], dp[i-2]nums[i])}return dp[n-1]
}func rob_max(i int, i2 int) int {if i i2 {return i}return i2
}213. 打家劫舍 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 1000 nums[i] 1000
代码
package __dpfunc rob_ii(nums []int) int {/*两次[0,n-1],[1,n]*/n : len(nums)if n 1 {return nums[0]} else if n 2 {return max(nums[0], nums[1])}dp, dp1 : make([]int, n-1), make([]int, n)dp[0] nums[0]dp[1] max(nums[0], nums[1])for i : 2; i n-1; i {dp[i] max(dp[i-2]nums[i], dp[i-1])}dp1[0] nums[1] // 修改此行dp1[1] max(nums[1], nums[2])for i : 2; i n-1; i {dp1[i] max(dp1[i-2]nums[i1], dp1[i-1]) // 修改此行}return max(dp[n-2], dp1[n-2]) // 修改此行
}337. 打家劫舍 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)
思路
与198.打家劫舍213.打家劫舍II一样关键是要讨论当前节点抢还是不抢。如果抢了当前节点两个孩子就不能动如果没抢当前节点就可以考虑抢左右孩子注意这里说的是“考虑”
