林业网站模板,黄岩建设局网站,做网站 怎么发布,调用wordpress栏目列表页LeetCode 55 跳跃游戏 给你一个非负整数数组 nums #xff0c;你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标#xff0c;如果可以#xff0c;返回 true #xff1b;否则#xff0c;返回 false 。 贪…LeetCode 55 跳跃游戏 给你一个非负整数数组 nums 你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标如果可以返回 true 否则返回 false 。 贪心
class Solution:def canJump(self, nums: List[int]) - bool:pos 0for idx, num in enumerate(nums):if idx pos or pos len(nums) - 1:breakpos max(pos, idx num)return pos len(nums) - 1虽然enumerate更加pythonic但是实际测试enrmerate相比range更加耗时不过差的很少大概10ms左右不影响AC
class Solution:def canJump(self, nums: List[int]) - bool:l len(nums)pos 0for idx in range(l):if idx pos or pos l - 1:breakpos max(pos, idx nums[idx])return pos l - 1动态规划
看了一眼评论区有人指出贪心实质上是动态规划动态规划的思路如下dp[n]为0~n位置能跳到的最远距离所以状态转移方程为dp[n] max(dp[n-1], dp[n-1] nums[n])初始值可以设置dp[0] nums[0]一维动态规划同时根据状态转移方程可知只涉及n和n-1可以进行滚动优化使用一个变量即可替代整个dp数组由此可得解法。实质上滚动优化后动态规划思路的代码和贪心思路的代码是一致的。 果然动态规划最难的是找状态。
