13-跳躍游戲 II

給定一個長度為?n?的?0 索引整數數組?nums。初始位置為?nums[0]。

每個元素?nums[i]?表示從索引?i?向后跳轉的最大長度。換句話說，如果你在?nums[i]?處，你可以跳轉到任意?nums[i + j]?處:

0 <= j <= nums[i]?
i + j < n

返回到達?nums[n - 1]?的最小跳躍次數。生成的測試用例可以到達?nums[n - 1]。

方法一：?貪心算法

這是一個典型的貪心算法問題，要求計算到達數組最后一個位置的最小跳躍次數。以下是使用 TypeScript 實現的代碼：

代碼實現

function jump(nums: number[]): number {const n = nums.length;if (n === 1) {return 0;}// 當前跳躍能到達的最遠位置let currentMaxReach = 0;// 下一步跳躍能到達的最遠位置let nextMaxReach = 0;// 跳躍次數let jumps = 0;for (let i = 0; i < n - 1; i++) {// 更新下一步跳躍能到達的最遠位置nextMaxReach = Math.max(nextMaxReach, i + nums[i]);// 如果當前位置到達了當前跳躍能到達的最遠位置if (i === currentMaxReach) {// 進行一次跳躍jumps++;// 更新當前跳躍能到達的最遠位置為下一步跳躍能到達的最遠位置currentMaxReach = nextMaxReach;// 如果當前跳躍能到達的最遠位置已經可以到達數組的最后一個位置，直接返回跳躍次數if (currentMaxReach >= n - 1) {break;}}}return jumps;
}// 示例調用
const nums = [2, 3, 1, 1, 4];
const minJumps = jump(nums);
console.log("到達數組最后一個位置的最小跳躍次數:", minJumps);

代碼解釋

邊界條件處理：如果數組長度為 1，說明已經在最后一個位置，不需要跳躍，直接返回 0。
初始化變量：
- currentMaxReach：表示當前跳躍能到達的最遠位置，初始化為 0。
- nextMaxReach：表示下一步跳躍能到達的最遠位置，初始化為 0。
- jumps：表示跳躍次數，初始化為 0。
遍歷數組：
- 在遍歷過程中，不斷更新?nextMaxReach，它是當前位置?i?加上該位置能跳躍的最大長度?nums[i]?與之前的?nextMaxReach?中的較大值。
- 當?i?等于?currentMaxReach?時，說明已經到達了當前跳躍能到達的最遠位置，此時需要進行一次跳躍，jumps?加 1。
- 同時更新?currentMaxReach?為?nextMaxReach，表示進入下一次跳躍的范圍。
- 如果?currentMaxReach?已經大于等于數組的最后一個位置的索引?n - 1，說明已經可以到達最后一個位置，直接跳出循環。
返回結果：遍歷結束后，jumps?即為到達數組最后一個位置的最小跳躍次數，將其返回。

復雜度分析

時間復雜度：O(n)，其中??是數組的長度。因為只需要對數組進行一次遍歷。
空間復雜度：O(1)，只使用了常數級的額外變量。

這種貪心算法的核心思想是在每一次跳躍中，盡可能地跳到最遠的位置，從而用最少的跳躍次數到達數組的最后一個位置。

方法二：?廣度優先搜索

除了前面介紹的貪心算法，還可以使用廣度優先搜索（BFS）的方法來解決這個問題。BFS 的核心思想是從起始位置開始，逐層擴展所有可能的跳躍位置，直到到達目標位置，每擴展一層就相當于進行了一次跳躍，記錄擴展的層數即為最小跳躍次數。

代碼實現

function jump(nums: number[]): number {const n = nums.length;if (n === 1) {return 0;}// 記錄已經訪問過的位置const visited = new Array(n).fill(false);// 初始化隊列，隊列中存儲 [當前位置, 跳躍次數]const queue: [number, number][] = [[0, 0]];visited[0] = true;while (queue.length > 0) {const [currentIndex, jumps] = queue.shift()!;// 遍歷當前位置能跳躍到的所有位置for (let j = 1; j <= nums[currentIndex] && currentIndex + j < n; j++) {const nextIndex = currentIndex + j;// 如果到達了最后一個位置，返回當前跳躍次數加 1if (nextIndex === n - 1) {return jumps + 1;}// 如果該位置未被訪問過if (!visited[nextIndex]) {// 標記為已訪問visited[nextIndex] = true;// 將該位置和跳躍次數加 1 加入隊列queue.push([nextIndex, jumps + 1]);}}}return -1; // 理論上不會執行到這里，因為題目保證可以到達最后一個位置
}// 示例調用
const nums = [2, 3, 1, 1, 4];
const minJumps = jump(nums);
console.log("到達數組最后一個位置的最小跳躍次數:", minJumps);

代碼解釋

邊界條件處理：如果數組長度為 1，說明已經在最后一個位置，不需要跳躍，直接返回 0。
初始化變量：
- visited：一個布爾類型的數組，用于記錄每個位置是否已經被訪問過，初始時所有位置都標記為未訪問。
- queue：一個隊列，用于存儲待擴展的位置和對應的跳躍次數，初始時將起始位置?0?和跳躍次數?0?加入隊列，并將起始位置標記為已訪問。
BFS 過程：
- 當隊列不為空時，從隊列中取出一個元素，包含當前位置?currentIndex?和跳躍次數?jumps。
- 遍歷當前位置能跳躍到的所有位置?nextIndex（范圍是從?currentIndex + 1?到?currentIndex + nums[currentIndex]?且不超過數組長度）。
- 如果?nextIndex?是最后一個位置，說明已經到達目標，返回當前跳躍次數加 1。
- 如果?nextIndex?未被訪問過，將其標記為已訪問，并將?[nextIndex, jumps + 1]?加入隊列。
返回結果：如果一切正常，在 BFS 過程中會找到到達最后一個位置的最小跳躍次數并返回；理論上不會執行到返回?-1?的情況，因為題目保證可以到達最后一個位置。

復雜度分析

時間復雜度：O(n)，其中??是數組的長度。每個位置最多被訪問一次，因此時間復雜度為線性。
空間復雜度：O(n)，主要用于存儲?visited?數組和隊列，隊列在最壞情況下可能存儲所有位置。

與貪心算法相比，BFS 方法的代碼實現相對復雜一些，但它的思路更加直觀，適合用于解決一些需要搜索所有可能路徑的問題。不過，在這個特定問題中，貪心算法的時間和空間復雜度雖然與 BFS 相同，但在實際運行中可能會更快，因為貪心算法不需要維護隊列和訪問標記數組。

方法三：?動態規劃

動態規劃的核心思想是將原問題分解為子問題，通過求解子問題的最優解來得到原問題的最優解。

思路分析

定義狀態：設?dp[i]?表示到達數組中第?i?個位置所需的最小跳躍次數。
初始化狀態：dp[0] = 0，因為初始位置就在?nums[0]，不需要跳躍。對于其他位置?i，初始化為一個較大的值（比如?Infinity），表示暫時無法到達。
狀態轉移方程：對于每個位置?i，遍歷其前面的所有位置?j（0 <= j < i），如果從位置?j?能夠跳到位置?i（即?j + nums[j] >= i），則更新?dp[i]?為?dp[j] + 1?和?dp[i]?中的較小值。
最終結果：dp[n - 1]?即為到達數組最后一個位置所需的最小跳躍次數。

代碼實現

function jump(nums: number[]): number {const n = nums.length;// 初始化 dp 數組，dp[i] 表示到達第 i 個位置所需的最小跳躍次數const dp: number[] = new Array(n).fill(Infinity);// 初始位置不需要跳躍dp[0] = 0;// 遍歷數組中的每個位置for (let i = 1; i < n; i++) {// 遍歷 i 之前的所有位置for (let j = 0; j < i; j++) {// 如果從位置 j 能夠跳到位置 iif (j + nums[j] >= i) {// 更新 dp[i] 為 dp[j] + 1 和 dp[i] 中的較小值dp[i] = Math.min(dp[i], dp[j] + 1);}}}return dp[n - 1];
}// 示例調用
const nums = [2, 3, 1, 1, 4];
const minJumps = jump(nums);
console.log("到達數組最后一個位置的最小跳躍次數:", minJumps);

復雜度分析

時間復雜度：O(n^2)，其中??是數組的長度。因為需要使用兩層嵌套循環來填充?dp?數組。
空間復雜度：O(n)，主要用于存儲?dp?數組。

代碼解釋

初始化?dp?數組：創建一個長度為?n?的數組?dp，并將所有元素初始化為?Infinity，表示暫時無法到達。將?dp[0]?設為 0，因為初始位置不需要跳躍。
填充?dp?數組：使用兩層嵌套循環，外層循環遍歷從 1 到?n - 1?的每個位置?i，內層循環遍歷從 0 到?i - 1?的每個位置?j。對于每個位置?j，如果從位置?j?能夠跳到位置?i（即?j + nums[j] >= i），則更新?dp[i]?為?dp[j] + 1?和?dp[i]?中的較小值。
返回結果：最終返回?dp[n - 1]，即到達數組最后一個位置所需的最小跳躍次數。