十七. 贪心

45. 跳跃游戏 II

推荐使用贪心，不推荐使用动态规划

class Solution:def jump(self, nums: List[int]) -> int:res = 0end = max_v = 0for i in range(len(nums)-1):max_v = max(max_v, i+nums[i])if i == end:end = max_vres += 1return res
# 1.维护几个变量：当前所能达到的最远位置 end，下一步所能跳到的最远位置 max_pos，最少跳跃次数 setps。
# 2.遍历数组 nums 的前 len(nums) - 1 个元素：
# 每次更新第 i 位置下一步所能跳到的最远位置 max_pos。
# 如果索引 i 到达了 end 边界，则：更新 end 为新的当前位置 max_pos，并令步数 setps 加 1。
# 3.最终返回跳跃次数 steps。# 时间复杂度：O(n)O(n)。一重循环遍历的时间复杂度是 O(n)O(n)，所以总体时间复杂度为 O(n)O(n)。
# 空间复杂度：O(1)O(1)。只用到了常数项的变量，所以总体空间复杂度为 O(1)O(1)。

55. 跳跃游戏

c

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！