首页 > 其他分享 >【Golang】LeetCode面试经典150题:45. 跳跃游戏 II

【Golang】LeetCode面试经典150题:45. 跳跃游戏 II

时间:2024-09-07 21:24:09浏览次数:12  
标签:150 currentEnd farthest nums 复杂度 45 Golang 索引 跳跃

题干:

给定一个长度为 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是55.跳跃游戏,可以点链接对照看看:55题是问是否能跳到最后;45题是跳到最后的步数最少是多少,都是贪心算法

解法:贪心算法

func jump(nums []int) int {
	n := len(nums)
	if n <= 1 {
		return 0
	}

	jumps := 0       // 跳跃次数
	currentEnd := 0  // 当前跳跃的结束位置
	farthest := 0    // 下一跳的最远位置

	for i := 0; i < n-1; i++ {
		// 更新下一跳的最远位置
		farthest = max(farthest, i+nums[i])

		// 如果到达当前跳跃的结束位置,增加跳跃次数
		if i == currentEnd {
			jumps++
			currentEnd = farthest // 更新当前跳跃的结束位置
		}
	}

	return jumps
}

// 辅助函数,返回两个整数中的较大值
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

解析:

贪心策略

  1. 跳跃范围

    • 在每一步中,我们需要确定从当前位置可以跳到的最远位置。这个最远位置是通过当前索引 i 和 nums[i] 计算得出的,即 farthest = max(farthest, i + nums[i])
    • farthest 变量记录了在当前跳跃范围内(从 currentEnd 到 farthest)可以到达的最远位置。
  2. 跳跃计数

    • 当我们遍历到当前跳跃的结束位置 currentEnd 时,意味着我们需要进行一次跳跃来继续前进。此时,我们增加跳跃次数 jumps,并将 currentEnd 更新为 farthest,以便在下一次跳跃中使用。
    • 这意味着我们在每次到达当前跳跃范围的末尾时,都会进行一次跳跃,并更新我们的跳跃范围。
  3. 终止条件

    • 当我们遍历到倒数第二个元素(n-1),我们不需要再进行跳跃,因为我们已经可以到达最后一个元素。

具体示例:

考虑数组 nums = [2, 3, 1, 1, 4]

  • 从索引 0 开始,nums[0] = 2,我们可以跳到索引 1 或 2。此时 farthest = 2
  • 当我们到达索引 1nums[1] = 3,我们可以跳到索引 23 或 4。此时 farthest = 4
  • 由于我们已经到达了当前跳跃的结束位置(currentEnd = 2),我们增加跳跃次数,更新 currentEnd 为 farthest(即 4)。
  • 继续遍历,发现我们已经可以到达最后一个元素,因此跳跃次数为 2

复杂度分析:

时间复杂度:

  • 该算法的时间复杂度为 O(n),其中 n 是数组的长度,因为我们只遍历了一次数组。

空间复杂度:

  • 空间复杂度为 O(1),只使用了常数级别的额外空间。

标签:150,currentEnd,farthest,nums,复杂度,45,Golang,索引,跳跃
From: https://blog.csdn.net/weixin_46506407/article/details/142004108

相关文章

  • Paladin® HD系列: 245-8214-11V、245-8216-11V、245-8218-11V、245-8219-11V、245-82
    优化的密度和性能Paladin®HD互连系统具有高密度,支持112GB/s的数据速率,提供高带宽,在1U空间内支持多达144个正交差分对。PaladinHD采用平衡对结构;采用单独组装和分立屏蔽差分对,配备颠覆性的混合板固定机构,可实现高密度传输。配接接口旨在优化空间并避免传统的正交"扭曲"。Paladin......
  • 202409071506,开始写代码,从0开始 验证基本架子
    由于视频教程里面用的VS2105所以照抄。 开发环境是VS2015,WIN10.  VS2015在今天看来是一个很古老的开发环境了,估计都很难找到安装包。(各种安装包:https://www.cnblogs.com/zjoch/p/5694013.html)用:vs2015.ent_chs.iso(3.88GB(4,172,560,384字节))这个安装包,安装过程出......
  • AP3215 8-150V 外围简单 宽输入 电压降压BUCK 恒压恒流驱动器 POE、电动车、扭扭车、
    产品描述AP3215是一系列外围电路简洁的宽输入电压降压BUCK恒压恒流驱动器,适用于8-150V输入电压范围的DC-DC降压应用。AP3215输出电压通过FB管脚设置,输出电流通过CS电阻设置,外围简洁,具备高效率,低功耗,低纹波,优异的线性调整率和负载调整率等优点。支持输出线......
  • CF1945F Kirill and Mushrooms
    题意营地里的人一睡着,基里尔就偷偷溜出帐篷,去智者橡树那里采蘑菇。众所周知,橡树下生长着\(n\)种蘑菇,每种蘑菇都有\(v_i\)的魔力。基里尔非常想用这些蘑菇制作一种魔力最大的灵药。灵药的强度等于其中蘑菇的数量与这些蘑菇中最小魔力的乘积。为了配制灵药,基里尔将依次采摘......
  • 20240906_150054 python 内容对齐方式 format
    format左右中对齐让数据左对齐"{:!<30}".format(数据)让数据右对齐"{:!>30}".format(数据)让数据居中对齐"{:!^30}".format(数据)......
  • 20240906_150844 python 槽的进制转换
    十进制转二进制b是bit的意思比特十进制转八进制十进制转16进制记忆b,二进制o,八进制x,十六进制......
  • Leetcode面试经典150题-210.课程表II
    这个题是图的问题,因为图的拓扑排序在实际应用中有非常多的用途图,所以最近考的越来越多解法都在代码里,不懂就留言或者私信看这个题之前一定要好好看看207题我写的题解,也许207看懂了的话,210只是一个coding问题了Leetcode面试经典150题-207.课程表-CSDN博客一定要看!一定要看!......
  • JSP酒店管理系统456ho(程序+源码+数据库+调试部署+开发环境)
    本系统(程序+源码+数据库+调试部署+开发环境)带论文文档1万字以上,文末可获取,系统界面在最后面。系统程序文件列表开题报告内容一、项目背景随着旅游业的持续繁荣和酒店业的快速发展,传统酒店管理模式面临效率低下、服务体验不佳等挑战。为了提升酒店运营管理水平,增强客户满意......
  • golang实现ip地址扫描
    Golang实现IP地址扫描原创 GoOfficialBlog GoOfficialBlog  2024年09月05日18:13 中国香港 听全文你是否想过哪些设备连接到了家里的Wi-Fi网络?无论是出于安全目的还是单纯的好奇心,我们都可以去了解一下家庭网络中的设备情况。在本文中,我们将介绍如何使用......
  • POJ - 3150
    题解题意:题面很臭很长。大意是,有一个大小为N的环,给出M,K,D,以及N个数。我们进行K次操作,每次操作把距离当前点不超过D的累加到当前点,结果模M。思路:因为要进行K次,每次的原则是一样的,我们可以想到用矩阵来优化,如果i能到达j,把么base[i][j]=1;则结果ans=A(base^K)。但是需要优化,时间复杂......