Steven's BlogAppearance
每天一道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 2. 那么找到一个能达到l的下标,将l更新为当前值,继续从1开始 因为如果还有能达到l其他下标,他一定能达到更新后的l 复杂度O(N)
解题过程
rust
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,本项目文章所有代码都可以找到.