关于leetcode个人解题总结:golangleetcode初级最大子序和打家劫舍

32次阅读

共计 704 个字符,预计需要花费 2 分钟才能阅读完成。

什么是动静布局

https://zhuanlan.zhihu.com/p/…

第一题 最大子序和

题目信息

解题思路



一开始在思考的时候走错了方向

直到看到这条评论失去了启发

错误代码如下

正确代码如下

func maxSubArray(nums []int) int {max := nums[0]
    for i := 1; i < len(nums); i++ {if nums[i] + nums[i-1] > nums[i] {nums[i] += nums[i-1]
        }
        if nums[i] > max {max = nums[i]
        }
    }
    return max
}

第二题 打家劫舍

题目信息

解题思路

同样为多决策问题,动静布局能够疾速的解决

代码

func rob(nums []int) int {if len(nums) == 0 {return 0}
    if len(nums) == 1 {return nums[0]
    }
    dp := make([]int, len(nums))
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    for i := 2; i < len(nums); i++ {dp[i] = max(dp[i-2] + nums[i], dp[i-1])
    }
    return dp[len(nums)-1]
}

func max(x, y int) int {
    if x > y {return x}
    return y
}

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/house-robber/solution/da-jia-jie-she-by-leetcode-solution/
起源:力扣(LeetCode)著作权归作者所有。商业转载请分割作者取得受权,非商业转载请注明出处。

正文完
 0