网站建设电话销售话术实例,上海最出名的编程培训,百度下载文章转wordpress,wordpress博客主题制作Problem: 45. 跳跃游戏 II 文章目录 题目思路复杂度Code 题目
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说#xff0c;如果你在 nums[i] 处#xff0c;你可以跳转到任意 nums[i j] 处:
… Problem: 45. 跳跃游戏 II 文章目录 题目思路复杂度Code 题目
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说如果你在 nums[i] 处你可以跳转到任意 nums[i j] 处:
$0 j nums[i] $ i j n i j n ijn 返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
示例 1: 输入: nums [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置跳 1 步然后跳 3 步到达数组的最后一个位置。 示例 2: 输入: nums [2,3,0,1,4] 输出: 2 思路
我们思考一种朴素的解法就是从后往前遍历遍历所有点x在这层循环中再从左往右遍历所有点看看哪个点最先能到达x,这个点就是我们的下一个要达到的点然后我们再从左往右寻找能到达这个点的点就ok
class Solution {public int jump(int[] nums) {int position nums.length - 1;int steps 0;while (position 0) {for (int i 0; i position; i) {if (i nums[i] position) {position i;steps;break;}}}return steps;}
}我们观察下每次跳跃的规律就拿 [ 2 , 3 , 1 , 2 , 4 , 2 , 3 ] [2,3,1,2,4,2,3] [2,3,1,2,4,2,3] 来说
对于位置0而言他可以跳到位置12上对于位置1而言他可以跳到234这些位置上对于位置2而言他可以跳到位置4上 此时我们发现一件事当我们遍历数组到位置2即 [1] 的时候此时跳跃者肯定会从 [31] 这个子数组中跳跃到更远的地方我们记录这个更远的地方为end当我们遍历到end的时候跳跃者肯定会从 [ 上一次跳跃的位置 e n d ] [上一次跳跃的位置end] [上一次跳跃的位置end] 中一个地方往前跳哪个点跳的远就从哪个点跳
不难发现我们每次到达end点其实之前或者此刻都跳了一次我们记录这次跳跃。
在程序一开始的时候只遍历的第一个点所以只能从第一个点开始跳
当遍历结束的时候如果我们遍历第n个点而此刻end又恰好是第n个点因为end是上一次跳跃更新的所以上一次跳跃我们就到达了n点所以我们不遍历n点以免多计算一次
复杂度
时间复杂度: O ( n ) O(n) O(n) 空间复杂度: O ( 1 ) O(1) O(1) Code
class Solution:def jump(self, nums: List[int]) - int:right 0end 0n len(nums)cnt 0for i in range(n-1):if right inums[i]:right inums[i]if end i:cnt 1end rightreturn cnt
