55. 跳跃游戏-2

每天一道Rust-LeetCode(2020-02-03)

坚持每天一道题,刷题学习Rust.

题目描述

给定一个非负整数数组,你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例 1:

输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步,从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
示例 2:

输入: [3,2,1,0,4]
输出: false
解释: 无论怎样,你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 , 所以你永远不可能到达最后一个位置。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/jump-game
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

倒着走
1.将终点下标设置为l

  1. 那么找到一个能达到l的下标,将l更新为当前值,继续从1开始
    因为如果还有能达到l其他下标,他一定能达到更新后的l
    复杂度O(N)

解题过程

struct Solution {}
impl Solution {
        pub fn can_jump(nums: Vec<i32>) -> bool {
        if nums.len() <= 1 {
            return true;
        }
        let mut l = nums.len() - 1;
        for i in (0..l).rev() {
            if nums[i] >= (l - i) as i32 {
                l = i;
                if i == 0 {
                    return true;
                }
            }
        }
        false
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test() {
        assert_eq!(true, Solution::can_jump(vec![2, 3, 1, 1, 4]));
        assert_eq!(false, Solution::can_jump(vec![3, 2, 1, 0, 4]));
        let v = vec![
            2, 0, 6, 9, 8, 4, 5, 0, 8, 9, 1, 2, 9, 6, 8, 8, 0, 6, 3, 1, 2, 2, 1, 2, 6, 5, 3, 1, 2,
            2, 6, 4, 2, 4, 3, 0, 0, 0, 3, 8, 2, 4, 0, 1, 2, 0, 1, 4, 6, 5, 8, 0, 7, 9, 3, 4, 6, 6,
            5, 8, 9, 3, 4, 3, 7, 0, 4, 9, 0, 9, 8, 4, 3, 0, 7, 7, 1, 9, 1, 9, 4, 9, 0, 1, 9, 5, 7,
            7, 1, 5, 8, 2, 8, 2, 6, 8, 2, 2, 7, 5, 1, 7, 9, 6,
        ];
        assert_eq!(false, Solution::can_jump(v));
    }
}

一点感悟

其他

欢迎关注我的github,本项目文章所有代码都可以找到.