55. Jump Game Medium

1/**
2 * [55] Jump Game
3 *
4 * Given an array of non-negative integers nums, you are initially positioned at the first index of the array.
5 * Each element in the array represents your maximum jump length at that position.
6 * Determine if you are able to reach the last index.
7 * 
8 * Example 1:
9 * 
10 * Input: nums = [2,3,1,1,4]
11 * Output: true
12 * Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
13 * 
14 * Example 2:
15 * 
16 * Input: nums = [3,2,1,0,4]
17 * Output: false
18 * Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.
19 * 
20 *  
21 * Constraints:
22 * 
23 *  1 <= nums.length <= 10^4
24 *  0 <= nums[i] <= 10^5
25 *  
26 */
27pub struct Solution {}
28
29// problem: https://leetcode.com/problems/jump-game/
30// discuss: https://leetcode.com/problems/jump-game/discuss/?currentPage=1&orderBy=most_votes&query=
31
32// submission codes start here
33
34impl Solution {
35    pub fn can_jump(nums: Vec<i32>) -> bool {
36        let mut max = 0;
37        let l = nums.len();
38        for i in 0..nums.len() {
39            if i > max {
40                return false
41            }
42            let x = i + nums[i] as usize;
43            max = if max > x { max } else { x };
44
45            if max > l { return true }
46        }
47        true
48    }
49}
50
51// submission codes end
52
53#[cfg(test)]
54mod tests {
55    use super::*;
56
57    #[test]
58    fn test_55_1() {
59        println!("Got {}", Solution::can_jump([3,2,1,0,4].to_vec()))
60    }
61
62    #[test]
63    fn test_55_2() {
64        println!("Got {}", Solution::can_jump([2,3,1,1,4].to_vec()))
65    }
66}
67