算法leetcode|45. 跳跃游戏 II(rust重拳出击)

这篇具有很好参考价值的文章主要介绍了算法leetcode|45. 跳跃游戏 II(rust重拳出击)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。



45. 跳跃游戏 II:

给定一个长度为 n0 索引整数数组 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 步到达数组的最后一个位置。

样例 2:

输入: 

	nums = [2,3,0,1,4]
	
输出: 

	2

提示:

  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 1000
  • 题目保证可以到达 nums[n-1]

分析:

  • 面对这道算法题目,二当家的再次陷入了沉思。
  • 看到提示说保证有解,就想到逆向查找出发位置,由终点回起点,但是很慢。
  • 看题目是让找最优解,又想到用动态规划,但是效率依然不够好。
  • 再看题目说每个数字表示的是跳跃的最大长度,而不是固定长度,这时候就想到了使用贪心,先在当前能到达的范围内选能跳到最远的位置作为下一跳,这样就保证了下一步的可选位置最多,但下一步我不一定非得跳固定长度,完全可以跳的近,它包含了跳的近的位置,依次再从中选能挑到最远的位置,走一步说一步,局部选最优,贪心,太贪心了。
  • 在循环遍历时,由于到达最后一个位置之后不需要再次跳跃,所以应该比通常的遍历要少一次循环,最后一个位置的数字是没有用处的,能到就可以了,而不需要再跳跃。

算法leetcode|45. 跳跃游戏 II(rust重拳出击)


题解:

rust

impl Solution {
    pub fn jump(nums: Vec<i32>) -> i32 {
        let (mut maxPos, mut end, mut steps) = (0, 0, 0);
        (0..nums.len() - 1).for_each(|i| {
            maxPos = maxPos.max(i + nums[i] as usize);
            if i == end {
                end = maxPos;
                steps += 1;
            }
        });
        return steps;
    }
}

go

func jump(nums []int) int {
    l := len(nums)
	maxPos, end, steps := 0, 0, 0
	for i := 0; i < l-1; i++ {
		if maxPos < i+nums[i] {
			maxPos = i + nums[i]
		}
		if i == end {
			end = maxPos
			steps++
		}

	}
	return steps
}

c++

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size(), maxPos = 0, end = 0, step = 0;
        for (int i = 0; i < n - 1; ++i) {
            maxPos = max(maxPos, i + nums[i]);
            if (i == end) {
                end = maxPos;
                ++step;
            }
        }
        return step;
    }
};

c

int jump(int* nums, int numsSize){
    int maxPos = 0, end = 0, step = 0;
    for (int i = 0; i < numsSize - 1; ++i) {
        maxPos = fmax(maxPos, i + nums[i]);
        if (i == end) {
            end = maxPos;
            ++step;
        }
    }
    return step;
}

python

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        max_pos, end, step = 0, 0, 0
        for i in range(n - 1):
            max_pos = max(max_pos, i + nums[i])
            if i == end:
                end = max_pos
                step += 1
        return step


java

class Solution {
    public int jump(int[] nums) {
        int maxPos = 0, end = 0, steps = 0;
        for (int i = 0; i < nums.length - 1; ++i) {
            maxPos = Math.max(maxPos, i + nums[i]);
            if (i == end) {
                end = maxPos;
                ++steps;
            }
        }
        return steps;
    }
}

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】~
放弃不难,但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子:https://le-yi.blog.csdn.net/ 博客原创~文章来源地址https://www.toymoban.com/news/detail-413649.html


到了这里,关于算法leetcode|45. 跳跃游戏 II(rust重拳出击)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法leetcode|63. 不同路径 II(rust重拳出击)

    一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish”)。 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径? 网格中的障碍

    2024年02月16日
    浏览(48)
  • 算法leetcode|92. 反转链表 II(rust重拳出击)

    给你单链表的头指针 head 和两个整数 left 和 right ,其中 left = right 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。 链表中节点数目为 n 1 = n = 500 -500 = Node.val = 500 1 = left = right = n 你可以使用一趟扫描完成反转吗? 将链表分成3部分,即前面不需要反转的部

    2024年02月05日
    浏览(47)
  • 算法leetcode|81. 搜索旋转排序数组 II(rust重拳出击)

    已知存在一个按非降序排列的整数数组 nums ,数组中的值不必互不相同。 在传递给函数之前, nums 在预先未知的某个下标 k ( 0 = k nums.length )上进行了 旋转 ,使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (下标 从 0 开始 计数)。例如, [0,1,2,4,4,4,5,6,

    2024年02月07日
    浏览(44)
  • 算法leetcode|80. 删除有序数组中的重复项 II(rust重拳出击)

    给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使得出现次数超过两次的元素只出现两次 ,返回删除后数组的新长度。 不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。 说明 : 为什么返回数值是整数,但输出的答案是

    2024年02月09日
    浏览(50)
  • 算法leetcode|82. 删除排序链表中的重复元素 II(rust重拳出击)

    给定一个已排序的链表的头 head , 删除原始链表中所有重复数字的节点,只留下不同的数字 。返回 已排序的链表 。 链表中节点数目在范围 [0, 300] 内 -100 = Node.val = 100 题目数据保证链表已经按升序 排列 面对这道算法题目,二当家的再次陷入了沉思。 这道题目和 83. 删除排序

    2024年02月08日
    浏览(36)
  • leetcode 45. 跳跃游戏 II

             本题为 跳跃游戏I 的升级版,保证可以到达终点的情况下,要求出最短的跳跃次数。         还是仿照 跳跃游戏I 的思路,定义一个cover用于记录最大覆盖范围,终止条件是:        cover = nums.size()-1   ,还要定义一个变量 largest 用于记录当前最远覆盖范围的下

    2024年02月14日
    浏览(38)
  • 算法leetcode|66. 加一(rust重拳出击)

    给定一个由 整数 组成的 非空 数组所表示的非负整数,在该数的基础上加一。 最高位数字存放在数组的首位, 数组中每个元素只存储 单个 数字。 你可以假设除了整数 0 之外,这个整数不会以零开头。 1 = digits.length = 100 0 = digits[i] = 9 面对这道算法题目,二当家的再次陷入了

    2024年02月14日
    浏览(38)
  • 算法leetcode|72. 编辑距离(rust重拳出击)

    给你两个单词 word1 和 word2 , 请返回将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作: 插入一个字符 删除一个字符 替换一个字符 0 = word1.length, word2.length = 500 word1 和 word2 由小写英文字母组成 面对这道算法题目,二当家的再次陷入了沉思。 编

    2024年02月12日
    浏览(41)
  • 算法leetcode|48. 旋转图像(rust重拳出击)

    给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。 你必须在 原地 旋转图像,这意味着你需要直接修改输入的二维矩阵。 请不要 使用另一个矩阵来旋转图像。 n == matrix.length == matrix[i].length 1 = n = 20 -1000 = matrix[i][j] = 1000 面对这道算法题目,二当家

    2024年02月01日
    浏览(88)
  • 算法leetcode|89. 格雷编码(rust重拳出击)

    n 位格雷码序列 是一个由 2 n 个整数组成的序列,其中: 每个整数都在范围 [0, 2 n - 1] 内(含 0 和 2 n - 1) 第一个整数是 0 一个整数在序列中出现 不超过一次 每对 相邻 整数的二进制表示 恰好一位不同 ,且 第一个 和 最后一个 整数的二进制表示 恰好一位不同 给你一个整数

    2024年02月04日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包