您的位置:首页 > 财经 > 金融 > 广告网络用语_100个简单的手工小玩具_西安百度网站快速优化_海南百度推广公司有哪些

广告网络用语_100个简单的手工小玩具_西安百度网站快速优化_海南百度推广公司有哪些

2024/12/23 14:14:56 来源:https://blog.csdn.net/m0_52238102/article/details/144597941  浏览:    关键词:广告网络用语_100个简单的手工小玩具_西安百度网站快速优化_海南百度推广公司有哪些
广告网络用语_100个简单的手工小玩具_西安百度网站快速优化_海南百度推广公司有哪些

一、题目描述

跳跃游戏II

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i + j] 处:

  • 0 <= j <= nums[i] 
  • i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置,跳 1步,然后跳3步到达数组的最后一个位置。

二、思路分析

从下标0开始,第一步只能由nums[0]决定,但不是当前跳的越远越好,nums[0]=2,但实际我们跳到位置1才能达到最小跳跃数。

那么究竟跳几格呢?那就看哪个位置下一步可以跳的更远了,这也就是贪心的思想。我们要不断确定下一步可以到达的最右端点,然后遍历完这一步的最右端点。

题目测试用例都确保可以跳到最后,根据上面的逻辑,走完一步,我们就要遍历这一步所涵盖的区域内,哪个位置能够跳的最远。知道这个最远的位置后,我们也遍历了当前步数可以到达最右端点,那么后面的位置是步数+1的区间,同理我们再遍历这个区间,然后确定下一步能够到的最远距离,直到最后可以遍历完。

例如下表:nums=[1,2,1,1,1] 那么第一步的区间是[0,1],第二步的区间是[2,3],第三步的区间是[4,4]。

在遍历第i步的区间我们要尽量确定第i+1步能到达的最远位置

第一步第二步第三步
12111

三、代码实现

1.dp数组存储

class Solution:def jump(self, nums: List[int]) -> int:length = len(nums)if length == 1:return 0right = 1dp = [0] * lengthfor i in range(length):# 需要更新的dp最右端点值temp = nums[i] + i + 1for j in range(right,min(temp,length)): # 将[right,temp]进行染色,也就是设置为下一步的区间dp[j] = dp[i] + 1right = max(temp,right)# 这一步已经可以到达终点   if right >= length:breakreturn dp[length-1]

2.双指针(更推荐)

效率更高,有更低的空间复杂度。

class Solution:def jump(self, nums: List[int]) -> int:n = len(nums)if n == 1:return 0border = 0  # 当前步数的最右端点值current_right = 0  # 下一步的最右端点值ans = 0for i in range(n):# 更新下一步可以到达的最远位置current_right = max(current_right, i + nums[i])# 下一步可以到达终点if current_right >= n - 1:return ans+1# 当前步数的区间遍历结束,要开始下一步if i == border:border = current_rightans += 1return ans

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com