golang刷leetcode 技巧（13）打家劫舍(I,II,III)
golang刷leetcode 技巧（13）打家劫舍(I,II,III)
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 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，这是一个典型的一维动态规划题
2，状态转移方程维f(n)=max(f(n-1),f(n-2)+num[n])
代码实现：
func rob(nums []int) int {
/*
l:=len(nums)
if l==0{
return 0
}
if l==1{
return nums[0]
}
if l==2{
if nums[0]>nums[1]{
return nums[0]
}
return nums[1]
}
s1:=rob(nums[:l-2])+nums[l-1]
s2:=rob(nums[:l-1])
if s1>s2{
return s1
}
return s2
*/
l:=len(nums)
if l==0{
return 0
}
sum:=make([]int,l)
sum[0]=nums[0]
if l>1 {
if nums[0]>nums[1]{
sum[1]=nums[0]
}else{
sum[1]=nums[1]
}
}
for i:=2;i<l;i++{
if sum[i-2]+nums[i]>sum[i-1]{
sum[i]=sum[i-2]+nums[i]
}else{
sum[i]=sum[i-1]
}
}
return sum[l-1]
}打家劫舍 II
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:
输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例 2:
输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。
解题思路：
1，这是一个环形数组，要求打劫第一个就不能打劫第二个
2，问题可以转化成两个子问题
A，打劫 nums[0:n-2]
B，打劫nums[1:n-1]
3,假设存在这样的最优解，打劫nums[1:n-1]的值sum2不包含 nums[1]和nums［n-1],最终结果有可能是 sum2+num[0];
4，由于sum2+num[0] 不包含num［n-1]，这个值一定在打劫 nums[0:n-2] 的结果sum1中
代码实现：
func rob(nums []int) int {
l:=len(nums)
if l==0{
return 0
}
if l==1{
return nums[0]
}
if l==2{
return max(nums[0],nums[1])
}
s1:=subRob(nums[:l-1])
s2:=subRob(nums[1:])
return max(s1,s2)
}
func subRob(nums []int)int{
l:=len(nums)
if l==0{
return 0
}
sum:=make([]int,l)
sum[0]=nums[0]
if l>1 {
if nums[0]>nums[1]{
sum[1]=nums[0]
}else{
sum[1]=nums[1]
}
}
for i:=2;i<l;i++{
if sum[i-2]+nums[i]>sum[i-1]{
sum[i]=sum[i-2]+nums[i]
}else{
sum[i]=sum[i-1]
}
}
return sum[l-1]
}
func max(a,b int)int{
if a>b{
return a
}
return b
}在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
示例 1:
输入: [3,2,3,null,3,null,1]
3
/ \
2 3
\ \
3 1
输出: 7
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
示例 2:
输入: [3,4,5,1,3,null,1]
3
/ \
4 5
/ \ \
1 3 1
输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.
解题思路：
1，这个问题类似
2，状态转移方程变成了，打劫父节点＋打劫孙子节点的最大值 与打劫左右孩子的最大值中较大者。
代码实现：
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func rob(root *TreeNode) int {
val:=0
if root==nil{
return val
}
if root.Left!=nil && root.Right!=nil{
ll:=rob(root.Left.Left)
lr:=rob(root.Left.Right)
rl:=rob(root.Right.Left)
rr:=rob(root.Right.Right)
l:=rob(root.Left)
r:=rob(root.Right)
if root.Val+ll+lr+rr+rl>l+r{
return root.Val+ll+lr+rr+rl
}
return l+r
}
if root.Left!=nil{
ll:=rob(root.Left.Left)
lr:=rob(root.Left.Right)
l:=rob(root.Left)
if root.Val+ll+lr>l{
return root.Val+ll+lr
}
return l
}
if root.Right!=nil{
rl:=rob(root.Right.Left)
rr:=rob(root.Right.Right)
r:=rob(root.Right)
if root.Val+rl+rr>r{
return root.Val+rl+rr
}
return r
}
return root.Val
}本文分享自 golang算法架构leetcode技术php 微信公众号，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ，欢迎热爱写作的你一起参与！
腾讯云开发者
