leetcode45：跳跃游戏II

题目链接

leetcode

题目描述

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处满足：0 <= j <= nums[i], i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。

C++ 代码

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

/*
    常规思维就是暴力穷举，把所有可行的跳跃方案都穷举出来，计算步数最少的。
    穷举的过程会有重叠子问题，用备忘录消除一下，就成了自顶向下的动态规划。
    本题不需要穷举所有方案，只需要判断哪一个选择最好。
    贪心思想，比动态规划效率更高。

    时间复杂度：O(n)
        其中 n 是数组长度。
    空间复杂度：O(1)
        仅使用常数的额外空间。
*/
class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        int step = 0, end = 0, farthest = 0;
        for (int i = 0; i < n - 1; i ++) {
            farthest = max(farthest, i + nums[i]);
            if (i == end) {
                step ++;
                end = farthest;
            }
        }

        return step;
    }
};

/*
    动态规划，贪心优化

    状态定义：
        f[i] 表示到达 i 所需要的最少步数。
    状态计算：
        f[i] = f[last] + 1

    时间复杂度：O(n)
        数组中每个元素最多被遍历两次。
        最坏情况下，数组中每个元素都要被遍历一次。
    空间复杂度：O(n)
        数组需要的空间是 O(n)。
*/
class Solution_1 {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n);
        // base case
        f[0] = 0;

        int last = 0;
        // 依次求 f[i]
        for (int i = 1; i < n; i ++) {
            // 更新 last
            while (i > last + nums[last]) last ++;
            // 更新 f[i]
            f[i] = f[last] + 1;
        }

        return f[n - 1];
    }
};

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

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

    return 0;
}

Golang 代码

package main

import (
	"fmt"
)

/*
	贪心算法：
		使用三个变量：
		jumps：记录总的跳跃次数。
		currentEnd：记录当前能到达的最远位置。
		farthest：记录下一次能到达的最远位置。
		遍历数组，对于每个位置 i，更新 farthest 为 max(farthest, i + nums[i])。
		如果到达了 currentEnd，增加一次跳跃，并更新 currentEnd 为 farthest。
		如果 currentEnd 已经包括了最后一个位置，直接返回结果。
	边界条件：
		如果数组长度为 1 或更短，直接返回 0，因为不需要跳跃。

   时间复杂度：O(n)
       遍历一次数组，时间复杂度为 O(n)，其中 n 是数组的长度。
   空间复杂度：O(1)
       使用了常数级别的额外空间，空间复杂度为 O(1)。
*/
// jump 返回到达数组最后一个位置的最少跳跃次数
func jump(nums []int) int {
    n := len(nums)
    if n <= 1 {
		return 0
	}

	jumps := 0       // 跳跃次数
	currentEnd := 0  // 当前能到达的最远位置
	farthest := 0    // 下一次能到达的最远位置

	for i := 0; i < n - 1; i ++ {
		// 更新下一次能到达的最远位置
		farthest = max(farthest, i + nums[i])
		// 如果到达了当前能到达的最远位置
		if i == currentEnd {
			jumps ++               // 增加一次跳跃
			currentEnd = farthest  // 更新当前能到达的最远位置
			// 如果当前能到达的最远位置已经包括了最后一个位置，直接返回结果
			if currentEnd >= n - 1 {
				return jumps
			}
		}
	}
    
	return jumps
}

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

	for i, tc := range testCases {
		result := jump(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: %d, PASS\n", i+1, result)
		} else {
			fmt.Printf("Test Case %d, Output: %d, FAIL (Expected: %d)\n", i+1, result, tc.expected)
		}
	}
}