跳跃游戏

题目要求

给定一个非负整数数组nums，其中每个元素表示从当前位置出发，能够跳跃的最大长度。你的任务是判断是否能够从数组的第一个元素开始，跳跃至数组的最后一个元素。如果能够到达数组的最后一个下标，则返回true；如果不能到达，则返回false。

解题思路

要解决这个问题，我们可以采用贪心算法的思想。具体的方法是：

初始化一个变量，比如命名为maxReach，用来记录在当前位置或之前的位置，我们能够到达的最远距离。初始时，maxReach等于第一个元素的值，因为我们最初位于数组的第一个下标。
遍历数组nums，对于每一个位置，我们更新maxReach。更新的方法是比较当前的maxReach和当前下标 + nums[当前下标]的值，取二者之间的较大值作为新的maxReach。
在遍历的过程中，如果某一时刻maxReach已经大于或等于数组的最后一个下标，那么说明我们可以到达数组的最后一个元素，返回true。
如果在遍历结束时，maxReach小于数组的最后一个下标，那么说明我们无法到达数组的最后一个元素，返回false。
特别注意的是，在遍历过程中，如果当前下标大于maxReach，说明当前位置已经不可达，直接返回false。

通过上述步骤，我们可以在遍历一次数组的过程中，得出是否能够到达数组的最后一个下标的结论。

Golang 版本

package main

import "fmt"

func canJump(nums []int) bool {
    maxReach := 0
    for i, num := range nums {
        if i > maxReach {
            return false
        }
        maxReach = max(maxReach, i+num)
        if maxReach >= len(nums)-1 {
            return true
        }
    }
    return false
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    nums := []int{2, 3, 1, 1, 4}
    fmt.Println(canJump(nums)) // 输出: true
}

C++版本

#include <iostream>
#include <vector>
using namespace std;

bool canJump(vector<int>& nums) {
    int maxReach = 0;
    for (int i = 0; i < nums.size(); ++i) {
        if (i > maxReach) {
            return false;
        }
        maxReach = max(maxReach, i + nums[i]);
        if (maxReach >= nums.size() - 1) {
            return true;
        }
    }
    return false;
}

int main() {
    vector<int> nums = {2, 3, 1, 1, 4};
    cout << (canJump(nums) ? "true" : "false") << endl; // 输出: true
    return 0;
}

Python 版本

def can_jump(nums):
    max_reach = 0
    for i, num in enumerate(nums):
        if i > max_reach:
            return False
        max_reach = max(max_reach, i + num)
        if max_reach >= len(nums) - 1:
            return True
    return False

# 示例
nums = [2, 3, 1, 1, 4]
print(can_jump(nums))  # 输出: True

Java 版本

public class Solution {
    public boolean canJump(int[] nums) {
        int maxReach = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > maxReach) {
                return false;
            }
            maxReach = Math.max(maxReach, i + nums[i]);
            if (maxReach >= nums.length - 1) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {2, 3, 1, 1, 4};
        System.out.println(solution.canJump(nums)); // 输出: true
    }
}

Rust 版本

fn can_jump(nums: Vec<i32>) -> bool {
    let mut max_reach = 0;
    for (i, &num) in nums.iter().enumerate() {
        if i > max_reach {
            return false;
        }
        max_reach = std::cmp::max(max_reach, i + num as usize);
        if max_reach >= nums.len() - 1 {
            return true;
        }
    }
    false
}

fn main() {
    let nums = vec![2, 3, 1, 1, 4];
    println!("{}", can_jump(nums)); // 输出: true
}

总结

上述问题的解法核心在于使用贪心算法。无论是在 Go、C++、Python、Java 还是 Rust 版本的代码中，核心思想都是相同的：

定义一个变量（例如maxReach），用于记录在遍历数组过程中，能够到达的最远位置。
遍历数组中的每个元素，对于每个位置，更新maxReach。更新规则是取当前maxReach和当前位置下标 + 当前位置的跳跃长度两者之间的较大值。
在遍历过程中，如果发现某个位置已经不可达（即当前位置的下标大于maxReach），则直接返回false。
如果在任意时刻maxReach已经大于或等于数组的最后一个下标，说明可以到达数组的末尾，返回true。
如果遍历结束后，没有返回true，则意味着无法到达数组的末尾，返回false。

这种方法的时间复杂度为 O(n)，因为它只需要遍历数组一次。空间复杂度为 O(1)，因为只使用了有限的几个变量。这种贪心算法的优势在于它的效率和简洁性，适用于各种编程语言实现。

hot-100