解题思路

这是一个判断能否跳到数组末尾的问题，可以通过贪心算法来解决：

  1. 维护一个变量 ，表示当前能够到达的最远位置
  2. 遍历数组，对于每个位置 ：
    • 如果 超过了 ，说明无法到达该位置，返回
    • 更新
  3. 如果能遍历完整个数组，说明可以到达末尾

代码

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

bool canJump(vector<int>& nums) {
    int n = nums.size();
    int maxReach = 0;  // 当前能到达的最远位置
    
    for (int i = 0; i <= maxReach; i++) {
        // 如果已经可以到达最后一个位置
        if (maxReach >= n - 1) return true;
        
        // 更新最远可达位置
        maxReach = max(maxReach, i + nums[i]);
    }
    
    return false;
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    
    cout << (canJump(nums) ? "true" : "false") << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static boolean canJump(int[] nums) {
        int n = nums.length;
        int maxReach = 0;
        
        for (int i = 0; i <= maxReach; i++) {
            if (maxReach >= n - 1) return true;
            maxReach = Math.max(maxReach, i + nums[i]);
        }
        
        return false;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        
        System.out.println(canJump(nums) ? "true" : "false");
    }
}

def canJump(nums):
    n = len(nums)
    max_reach = 0  # 当前能到达的最远位置
    
    for i in range(n):
        # 如果当前位置已经超过了能到达的最远位置
        if i > max_reach:
            return False
            
        # 更新最远可达位置
        max_reach = max(max_reach, i + nums[i])
        
        # 如果已经可以到达最后一个位置
        if max_reach >= n - 1:
            return True
            
    return True

n = int(input())
nums = list(map(int, input().split()))
print("true" if canJump(nums) else "false")

算法及复杂度

  • 算法：贪心算法
  • 时间复杂度： - 只需要遍历一次数组
  • 空间复杂度： - 只需要常数额外空间

这道题的关键在于理解贪心的思想：我们只需要关心在当前位置能跳到的最远距离。对于每个位置，我们都更新能到达的最远位置，如果在遍历过程中发现当前位置已经超过了能到达的最远位置，就说明无法到达终点。

几个重要的点：

  1. 表示当前能到达的最远位置，初始为
  2. 遍历时需要判断当前位置 是否可达（）
  3. 对于每个可达位置，更新
  4. 如果在遍历过程中 ，说明可以到达终点

这种贪心的方法比动态规划更高效，因为我们只需要遍历一次数组，并且只需要维护一个变量。