leetcode55：跳跃游戏

题目链接

leetcode

题目描述

一个非负整数数组 nums，最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true；否则，返回 false 。

C++ 代码

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

/*
    贪心选择性质：每一步都做出一个局部最优的选择，最终的结果就是全局最优。
    注意，这是一种特殊性质，只有一部分问题拥有这个性质。

	贪心算法可以理解为一种特殊的动态规划问题，有一些特殊的性质，进一步降低了算法的时间复杂度。
    例如：一个算法问题使用暴力解法需要指数级时间，
    若使用动态规划消除重叠子问题，则可以降到多项式级别的时间；
    若满足贪心选择性质，则可以进一步降低时间复杂度，达到线性级别。

	这道题表面上不是求最值，但是可以改为：
		根据题目中的跳跃规则，求出能够跳到的最远距离。
		若能跳到最后一格，返回 true；否则，返回 false。

    时间复杂度：O(n)
        其中 n 为数组的大小。
        遍历数组一次，计算每一步的最远距离，最多遍历 n 次。
    空间复杂度：O(1)
        仅使用常数的额外空间。
*/
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        int farthest = 0;
        for (int i = 0; i < n - 1; i ++) {
            // 计算当前可以跳到的最远距离
            farthest = max(farthest, i + nums[i]);
            // cout << "i: " << i << ", farthest: " << farthest << endl;
            // 可能碰到了 0，卡住跳不动
            if (farthest <= i) return false;
        }

        return farthest >= n - 1;
    }
};

/*
    思路同上
*/
class Solution_1 {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        int farthest = 0;
        for (int i = 0; i < n; i ++) {
            // 卡住跳不动
            if (i > farthest) return false;
            // 计算当前可以跳到的最远距离
            farthest = max(farthest, i + nums[i]);
            // 越界
            if (farthest >= n - 1) return true;
        }

        return false;
    }
};

int main() {
    Solution solution;
    vector<vector<int>> test_cases = {
        {2, 3, 1, 1, 4},
        {3, 2, 1, 0, 4}
    };

    for (auto& nums : test_cases) {
        cout << "Input: ";
        for (int num : nums) {
            cout << num << " ";
        }
        cout << endl;
        cout << "Output: " << (solution.canJump(nums) ? "true" : "false") << endl;
    }

    return 0;
}

Golang 代码

package main

import (
	"fmt"
)

/*
   贪心算法：
       使用一个变量 maxReach 来记录当前能到达的最远位置。
       遍历数组，对于每个位置 i，更新 maxReach 为 max(maxReach, i + nums[i])。
       如果在某个位置 i，i 已经超过了 maxReach，说明无法继续前进，直接返回 false。
       如果 maxReach 超过了或等于数组的最后一个位置，返回 true。
   边界条件：
       如果数组长度为 1 或更短，直接返回 true，因为不需要跳跃。

   时间复杂度：O(n)
       遍历一次数组，时间复杂度为 O(n)，其中 n 是数组的长度。
   空间复杂度：O(1)
       使用了常数级别的额外空间，空间复杂度为 O(1)。
*/
// canJump 判断是否能够到达数组的最后一个位置
func canJump(nums []int) bool {
	n := len(nums)
	if n <= 1 {
		return true
	}

	maxReach := 0 // 当前能到达的最远位置
    for i := 0; i < n; i ++ {
        if i > maxReach {
            // 如果当前位置已经超过了能到达的最远位置，说明无法继续前进
            return false
        }
        // 更新能到达的最远位置
        maxReach = max(maxReach, i + nums[i])
        if maxReach >= n - 1 {
            // 如果能到达的最远位置已经包括了最后一个位置，直接返回 true
            return true
        }
    }
    return true
}

func main() {
	// 测试用例
	testCases := []struct {
		nums    []int
		expected bool
	}{
		{
			nums:    []int{2, 3, 1, 1, 4},
			expected: true,
		},
		{
			nums:    []int{3, 2, 1, 0, 4},
			expected: false,
		},
		{
			nums:    []int{0},
			expected: true,
		},
	}

	for i, tc := range testCases {
		result := canJump(tc.nums)
		fmt.Printf("Test Case %d, Input: nums = %v\n", i+1, tc.nums)
		if result == tc.expected {
			fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, result)
		} else {
			fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, result, tc.expected)
		}
	}
}