题解

题面描述

给定一个非负整数数组 $nums$，数组中每个元素表示当前位置可以跳跃的最大步数。初始时你位于数组的第一个下标，判断是否能够跳跃到最后一个下标。如果可以，返回 $true$；否则返回 $false$。

思路

我们可以使用贪心算法：

• 定义变量 $max\_reach$ 表示当前能跳跃到的最远下标。
• 遍历数组，对于每个下标 $i$：
  • 若 $i > max\_reach$，说明下标 $i$ 不可达，直接返回 $false$；
  • 否则更新 $max\_reach = max(max\_reach, i + nums[i])$；
• 如果最终 $max\_reach$ 大于或等于数组的最后一个下标，则返回 $true$，否则返回 $false$。

这种方法的时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。

代码分析

• 变量定义：$max\_reach$ 用来记录目前可以到达的最远位置。
• 更新过程：对于每个下标 $i$，如果 $i$ 在 $max\_reach$ 之内，则更新 $max\_reach$ 为 $max(max\_reach, i + nums[i])$。
• 终止条件：如果在遍历过程中发现 $i > max\_reach$，则意味着当前位置不可达，直接返回 $false$。遍历结束后，如果 $max\_reach$ 大于等于最后一个下标，说明可达最后一个位置。

问题本质分析

该问题的本质是贪心策略，通过每一步的最优选择（即更新能到达的最远位置）来判断整个数组是否可以遍历到末尾。关键在于：

• 能否在遍历过程中保持连续的可达区间。
• 及时更新能跳跃的最远位置，避免陷入无法前进的状态。

C++

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

class Solution {
public:
    // 判断是否可以跳到最后一个下标
    bool canJump(vector<int>& nums) {
        int max_reach = 0; // 当前可跳跃的最远下标
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            // 如果当前位置不可达，则返回 false
            if (i > max_reach) return false;
            // 更新最远可以到达的下标
            max_reach = max(max_reach, i + nums[i]);
            // 如果已经可以到达最后一个下标，则直接返回 true
            if (max_reach >= n - 1) return true;
        }
        return false;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string line;
    // 读取一整行输入
    getline(cin, line);
    istringstream iss(line);
    vector<int> nums;
    int num;
    // 分割字符串获得每个数字
    while (iss >> num) {
        nums.push_back(num);
    }
    Solution sol;
    // 根据判断结果输出 true 或 false
    cout << (sol.canJump(nums) ? "true" : "false") << "\n";
    return 0;
}

Python

# 定义 Solution 类
class Solution:
    def canJump(self, nums: list) -> bool:
        max_reach = 0  # 当前可以跳跃到的最远下标
        n = len(nums)
        for i in range(n):
            # 如果当前位置不可达，则返回 False
            if i > max_reach:
                return False
            # 更新最远可以到达的下标
            max_reach = max(max_reach, i + nums[i])
            # 如果可以到达最后一个下标，直接返回 True
            if max_reach >= n - 1:
                return True
        return False

if __name__ == '__main__':
    import sys
    # 读取标准输入中的一行数据
    line = sys.stdin.readline().strip()
    # 将输入字符串分割为整数列表
    nums = list(map(int, line.split()))
    sol = Solution()
    # 输出判断结果
    print("true" if sol.canJump(nums) else "false")

Java

import java.util.Scanner;

public class Main {
    // 定义 Solution 类
    static class Solution {
        public boolean canJump(int[] nums) {
            int maxReach = 0; // 当前可以跳跃到的最远下标
            int n = nums.length;
            for (int i = 0; i < n; i++) {
                // 如果当前位置不可达，则返回 false
                if (i > maxReach) return false;
                // 更新最远可以到达的下标
                maxReach = Math.max(maxReach, i + nums[i]);
                // 如果可以到达最后一个下标，直接返回 true
                if (maxReach >= n - 1) return true;
            }
            return false;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 读取整行输入
        String line = sc.nextLine();
        String[] parts = line.split(" ");
        int n = parts.length;
        int[] nums = new int[n];
        // 将字符串数组转换为整数数组
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(parts[i]);
        }
        Solution sol = new Solution();
        // 根据判断结果输出 "true" 或 "false"
        System.out.println(sol.canJump(nums) ? "true" : "false");
        sc.close();
    }
}

Leetcode 78.跳跃游戏-原题链接

题目内容

给你一个非负整数数组 $nums$ ，你最初位于数组的第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 $true$ ；否则，返回 $false$ 。

输入描述

输出描述

样例1

输入

2 3 1 1 4

输出

true

说明

可以先跳 $1$ 步，从下标 $0$ 到达下标 $1$, 然后再从下标$1$ 跳 $3$步到达最后一个下标。

样例2

输入

3 2 1 0 4 

输出

flase

说明

无论怎样，总会到达下标为 $3$的位置。但该下标的最大跳跃长度是 $0$ ， 所以永远不可能到达最后一个下标。

提示

• $1 <= nums.length <= 10^4$
• $0 <= nums[i] <= 10^5$