leetcode_213

Golang:

思路:这题我个人感觉要复杂一些,难度在于首尾相连,并且,你需要考虑的更全面一些。当然,这题做完的时间复杂度100%,空间47%,但我不太想优化了。简单来说,有房子[1...n],通过打家劫舍1得出的最大值,我们需要做出判断:如果我们没抢n,那么这个最大值没有问题,如果我们抢了n,那么就需要去看下我们抢没抢1,如果也没抢1,那么没问题,但如果抢1了,那么这个最大值就需要修改了,为max([2....n],[1...n-1])。

代码如下:

func rob(nums []int) int {
 if len(nums) == 0 {
 return 0
 }
 if len(nums) == 1 {
 return nums[0]
 }
 if len(nums) == 2 {
 if nums[0] > nums[1] {
 return nums[0]
 } else {
 return nums[1]
 }
 }
 res := make([]int, len(nums))
 res[0] = nums[0]
 if nums[0] > nums[1] {
 res[1] = nums[0]
 } else {
 res[1] = nums[1]
 }
 arr := make([]int, len(nums))
 arr[1]=nums[1]
 i := 2
 for i < len(res) {
 if nums[i]+res[i-2] > res[i-1] {
 res[i] = nums[i] + res[i-2]
 } else {
 res[i] = res[i-1]
 }
 if nums[i]+arr[i-2] > arr[i-1] {
 arr[i] = nums[i] + arr[i-2]
 } else{
 arr[i] = arr[i-1]
 }
 i++
 }
 if res[i-1]==res[i-2] {//最末尾的房子没动
 return res[i-1]
 }else{
 if res[i-1]==arr[i-1]{//最开始的房子没动
 return res[i-1]
 }else {
 if res[i-2]>arr[i-1] {
 return res[i-2]
 }else {
 return arr[i-1]
 }
 }
 }
}

本文来自:简书

感谢作者:淳属虚构

查看原文:leetcode_213

• 编辑
• 预览