專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

一網友發文稱華為午餐一葷一素兩個菜就得20元，太貴了。我印象中只有學校里面的飯是最便宜的，一般的快餐店一葷一素20塊錢還好吧，不是太貴，但也不便宜。按照南方人的餐飲習俗，米飯還要另收2元，這樣算一葷一素加起來也就18塊錢。

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第45題：跳躍游戲 II。

問題描述

來源：LeetCode第45題

難度：中等

給定一個長度為 n 的 0 索引整數數組 nums。初始位置為 nums[0]。每個元素 nums[i] 表示從索引 i 向前跳轉的最大長度。換句話說，如果你在 nums[i] 處，你可以跳轉到任意 nums[i + j] 處:

1，0 <= j <= nums[i]

2，i + j < n

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

示例1：

輸入: nums = [2,3,1,1,4] 輸出: 2 解釋: 跳到最后一個位置的最小跳躍數是 2。 從下標為 0 跳到下標為 1 的位置，跳 1 步，然后跳 3 步到達數組的最后一個位置。

示例2：

輸入: nums = [2,3,0,1,4] 輸出: 2

• 1 <= nums.length <= 10^4

• 0 <= nums[i] <= 1000

• 題目保證可以到達 nums[n-1]

問題分析

這題讓計算的是跳到數組的最后需要跳躍的最小次數，第一次跳躍是站在下標為0的位置開始跳的。

我們可以用一個變量preRange表示上一次跳躍所能到達的范圍，然后在這個范圍內記錄跳躍所能達到的最遠距離curFarthest，計算的時候如果超過preRange這個范圍就表示需要再跳一次，然后更新preRange的值為curFarthest。

我們以示例一為例畫個圖來看下，第一次可以跳躍的范圍是[1,2]，這里指的是下標，實際上還可以跳到下標為0的位置，如果第一次還跳到下標為0就表示沒跳，我們不要記錄了。

第二次可以從下標為1或下標為2的位置開始跳，從下標為1的位置可以跳到[2,3,4]，從下標為2的位置可以跳到[3]，所以第二次就可以跳到數組的末尾了，只需要兩次即可。

JAVA：

public int jump(int[] nums) {     int jumps = 0;// 最小跳躍次數     int preRange = 0;// 上一次起跳的范圍     int curFarthest = 0;// 從上一次起跳范圍內所能跳的最遠距離。     for (int i = 0; i < nums.length - 1; i++) {         // 計算從當前位置跳躍所能到大的最遠距離，并更新curFarthest。         curFarthest = Math.max(curFarthest, i + nums[i]);         // 如果上一個跳遠范圍內都計算完了，就要重新開始跳了。         if (i == preRange) {             jumps++;             preRange = curFarthest;         }     }     return jumps; }

C++：

public:     int jump(vector

 & nums) {         int jumps = 0;// 最小跳躍次數         int preRange = 0;// 上一次起跳的范圍         int curFarthest = 0;// 從上一次起跳范圍內所能跳的最遠距離。         for (int i = 0; i < nums.size() - 1; i++) {             // 計算從當前位置跳躍所能到大的最遠距離，并更新curFarthest。             curFarthest = max(curFarthest, i + nums[i]);             // 如果上一個跳遠范圍內都計算完了，就要重新開始跳了。             if (i == preRange) {                 jumps++;                 preRange = curFarthest;             }         }         return jumps;     }

C：

int jump(int *nums, int numsSize) {     int jumps = 0;// 最小跳躍次數     int preRange = 0;// 上一次起跳的范圍     int curFarthest = 0;// 從上一次起跳范圍內所能跳的最遠距離。     for (int i = 0; i < numsSize - 1; i++) {         // 計算從當前位置跳躍所能到大的最遠距離，并更新curFarthest。         curFarthest = fmax(curFarthest, i + nums[i]);         // 如果上一個跳遠范圍內都計算完了，就要重新開始跳了。         if (i == preRange) {             jumps++;             preRange = curFarthest;         }     }     return jumps; }

Python：

def jump(self, nums: List[int]) -> int:     # 最小跳躍次數     # 上一次起跳的范圍     # 從上一次起跳范圍內所能跳的最遠距離。     jumps, preRange, curFarthest = 0, 0, 0     for i in range(len(nums) - 1):         # 計算從當前位置跳躍所能到大的最遠距離，并更新curFarthest。         curFarthest = max(curFarthest, i + nums[i])         # 如果上一個跳遠范圍內都計算完了，就要重新開始跳了。         if i == preRange:             jumps += 1             preRange = curFarthest     return jumps

筆者簡介

博哥，真名：王一博，畢業十多年， 作者，專注于 數據結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。