rust 解法, 执行用时: 0 ms, 内存消耗: 2.4 MB, 提交时间: 2025-01-27 08:53:08

impl Solution {
    pub fn jump(nums: Vec<i32>) -> i32 {
        let mut ans = 0;
        let mut cur_right = 0; // 已建造的桥的右端点
        let mut next_right = 0; // 下一座桥的右端点的最大值
        for i in 0..nums.len()-1 {
            next_right = next_right.max(i as i32 + nums[i]);
            if i as i32 == cur_right { // 到达已建造的桥的右端点
                cur_right = next_right; // 造一座桥
                ans += 1;
            }
        }
        ans
    }
}

javascript 解法, 执行用时: 1 ms, 内存消耗: 51.4 MB, 提交时间: 2025-01-27 08:52:57

/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function(nums) {
    let ans = 0;
    let curRight = 0; // 已建造的桥的右端点
    let nextRight = 0; // 下一座桥的右端点的最大值
    for (let i = 0; i < nums.length - 1; i++) {
        nextRight = Math.max(nextRight, i + nums[i]);
        if (i === curRight) { // 到达已建造的桥的右端点
            curRight = nextRight; // 造一座桥
            ans++;
        }
    }
    return ans;
};

cpp 解法, 执行用时: 0 ms, 内存消耗: 19.9 MB, 提交时间: 2025-01-27 08:52:45

class Solution {
public:
    int jump(vector<int>& nums) {
        int ans = 0;
        int cur_right = 0; // 已建造的桥的右端点
        int next_right = 0; // 下一座桥的右端点的最大值
        for (int i = 0; i + 1 < nums.size(); i++) {
            next_right = max(next_right, i + nums[i]);
            if (i == cur_right) { // 到达已建造的桥的右端点
                cur_right = next_right; // 造一座桥
                ans++;
            }
        }
        return ans;
    }
};

java 解法, 执行用时: 1 ms, 内存消耗: 44.5 MB, 提交时间: 2025-01-27 08:52:35

class Solution {
    public int jump(int[] nums) {
        int ans = 0;
        int curRight = 0; // 已建造的桥的右端点
        int nextRight = 0; // 下一座桥的右端点的最大值
        for (int i = 0; i < nums.length - 1; i++) {
            nextRight = Math.max(nextRight, i + nums[i]);
            if (i == curRight) { // 到达已建造的桥的右端点
                curRight = nextRight; // 造一座桥
                ans++;
            }
        }
        return ans;
    }
}

golang 解法, 执行用时: 8 ms, 内存消耗: 5.5 MB, 提交时间: 2021-07-19 09:56:02

func jump(nums []int) int {
    n := len(nums)
    // end是上次跳跃的最右点, maxPosition是目前能跳跃到的最远点
    end, maxPosition, steps := 0, 0, 0
    for i := 0; i < n - 1; i++ {
        maxPosition = max(maxPosition, i + nums[i])
        if i == end {
            end = maxPosition
            steps++
        }
    }
    return steps
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

golang 解法, 执行用时: 20 ms, 内存消耗: 5.6 MB, 提交时间: 2021-07-19 09:44:56

func jump(nums []int) int {
    position := len(nums) - 1
    steps := 0
    for position > 0 {
        for i := 0; i < position; i++ {
            if i + nums[i] >= position {
                position = i  // 每一步都是最佳选择
                steps++
                break
            }
        }
    }
    return steps
}

python3 解法, 执行用时: 52 ms, 内存消耗: 15.2 MB, 提交时间: 2020-11-30 17:43:42

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        maxPos, step, end = 0, 0, 0
        for i in range(n-1):
            if i <= maxPos:
                maxPos = max(maxPos, nums[i]+i)
                if end == i:
                    end = maxPos
                    step += 1
        return step

golang 解法, 执行用时: 344 ms, 内存消耗: 4.9 MB, 提交时间: 2020-11-30 16:56:02

func jump(nums []int) int {
    // position定义的是终点
    position, steps := len(nums) - 1, 0
    for position > 0 { // 直到退回到起点
        for i := 0; i < position; i++ {
            if i + nums[i] >= position { // 贪心算法, 每次都迈最大的步子
                position = i  // 回退一步, 终点左移
                steps++
                break
            }
        }
    }
    return steps
}