既股票買賣系列之后的第二組貪心算法題目：跳躍游戲系列。這一篇介紹的兩個(gè)問(wèn)題，其輸入均為一個(gè)數(shù)組，每個(gè)元素表示在該位置可以跳躍的最大長(zhǎng)度。

55. Jump Game

You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 1:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

問(wèn)題描述

給定一個(gè)非負(fù)整數(shù)數(shù)組，每個(gè)元素表示在該位置可以跳躍的最大長(zhǎng)度。判斷是否能夠到達(dá)最后一個(gè)下標(biāo)。

貪心策略

• 維護(hù)一個(gè)最遠(yuǎn)可到達(dá)的位置 max_reach。
• 遍歷數(shù)組，更新 max_reach。
• 如果 max_reach 超過(guò)最后一個(gè)下標(biāo)，則返回 True。

解題思路

這是一個(gè)典型的貪心算法問(wèn)題。我們可以通過(guò)維護(hù)一個(gè)變量 max_reach 來(lái)記錄當(dāng)前能夠到達(dá)的最遠(yuǎn)位置。遍歷數(shù)組時(shí)，更新 max_reach，并檢查是否能夠到達(dá)或超過(guò)最后一個(gè)下標(biāo)。

步驟

• 初始化 max_reach = 0，表示當(dāng)前能夠到達(dá)的最遠(yuǎn)位置。
• 遍歷數(shù)組 nums：
  • 如果當(dāng)前位置 i 超過(guò)了 max_reach，說(shuō)明無(wú)法到達(dá)當(dāng)前位置，返回 false。
  • 更新 max_reach 為 max(max_reach, i + nums[i])。
  • 如果 max_reach 已經(jīng)大于或等于最后一個(gè)下標(biāo)，返回 true。
• 遍歷結(jié)束后，如果 max_reach 大于或等于最后一個(gè)下標(biāo)，返回 true，否則返回 false。

bool canJump(vector<int>& nums) {int max_reach = 0;for (int i = 0; i < nums.size(); i++) {if (max_reach < i) {return false;}max_reach = max(max_reach, i + nums[i]);if (max_reach >= nums.size() - 1) {return true;}}if (max_reach >= nums.size() - 1) {return true;}else {return false;}
}

復(fù)雜度分析

• 時(shí)間復(fù)雜度：只需要遍歷數(shù)組一次，時(shí)間復(fù)雜度為 $O(n)$，其中 $n$ 是數(shù)組的長(zhǎng)度。
• 空間復(fù)雜度：只使用了常數(shù)級(jí)別的額外空間，空間復(fù)雜度為 $O(1)$。

45. Jump Game II

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

• 0 <= j <= nums[i] and
• i + j < n

Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

Example 1:

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [2,3,0,1,4]
Output: 2

解題思路

這是一個(gè)典型的貪心算法問(wèn)題。我們需要找到到達(dá)最后一個(gè)下標(biāo)的最小跳躍次數(shù)。可以通過(guò)維護(hù)兩個(gè)變量來(lái)解決：

• 當(dāng)前跳躍范圍：[start, end]，表示當(dāng)前跳躍可以到達(dá)的范圍。
• 最遠(yuǎn)可到達(dá)位置：max_reach，表示在當(dāng)前跳躍范圍內(nèi)，能夠到達(dá)的最遠(yuǎn)位置。

步驟

• 初始化：
  • jumps = 0：記錄跳躍次數(shù)。
  • end = 0：當(dāng)前跳躍范圍的結(jié)束位置。
  • max_reach = 0：當(dāng)前跳躍范圍內(nèi)能夠到達(dá)的最遠(yuǎn)位置。
• 遍歷數(shù)組 nums：
  • 更新 max_reach 為 max(max_reach, i + nums[i])。
  • 如果當(dāng)前位置 i 到達(dá)了當(dāng)前跳躍范圍的結(jié)束位置 end：
    • 增加跳躍次數(shù) jumps++。
    • 更新 end 為 max_reach，表示進(jìn)入下一個(gè)跳躍范圍。
• 返回 jumps。

int jump(vector<int>& nums) {int jumps = 0;      // 記錄跳躍次數(shù)int end = 0;        // 當(dāng)前跳躍范圍的結(jié)束位置int max_reach = 0;  // 當(dāng)前跳躍范圍內(nèi)能夠到達(dá)的最遠(yuǎn)位置for (int i = 0; i < nums.size() - 1; i++) {max_reach = max(max_reach, i + nums[i]);// 如果當(dāng)前位置到達(dá)了當(dāng)前跳躍范圍的結(jié)束位置if (i == end) {jumps++;       // 增加跳躍次數(shù)end = max_reach; // 更新跳躍范圍}}return jumps;
}

復(fù)雜度分析

• 時(shí)間復(fù)雜度：只需要遍歷數(shù)組一次，時(shí)間復(fù)雜度為 $O(n)$，其中 $n$ 是數(shù)組的長(zhǎng)度。
• 空間復(fù)雜度：只使用了常數(shù)級(jí)別的額外空間，空間復(fù)雜度為 $O(1)$。