文章目錄

• • 1. 題目來源
  • 2. 題目說明
  • 3. 題目解析
  • • • • 方法一：哈希表、記憶化搜索、遞歸解法
        • 方法二：迭代解法
        • 方法三：回溯法+貪心策略+剪枝

1. 題目來源

鏈接：青蛙過河
來源：LeetCode

2. 題目說明

一只青蛙想要過河。 假定河流被等分為 x 個單元格，并且在每一個單元格內(nèi)都有可能放有一石子（也有可能沒有）。 青蛙可以跳上石頭，但是不可以跳入水中。

給定石子的位置列表（用單元格序號升序表示）， 請判定青蛙能否成功過河（即能否在最后一步跳至最后一個石子上）。 開始時， 青蛙默認已站在第一個石子上，并可以假定它第一步只能跳躍一個單位（即只能從單元格1跳至單元格2）。

如果青蛙上一步跳躍了 k 個單位，那么它接下來的跳躍距離只能選擇為 k - 1、k 或 k + 1個單位。 另請注意，青蛙只能向前方（終點的方向）跳躍。

請注意：

石子的數(shù)量 ≥ 2 且 < 1100；
每一個石子的位置序號都是一個非負整數(shù)，且其 < $2^{31}$；
第一個石子的位置永遠是0。

示例1：

[0,1,3,5,6,8,12,17]
總共有8個石子。
第一個石子處于序號為0的單元格的位置, 第二個石子處于序號為1的單元格的位置,
第三個石子在序號為3的單元格的位置， 以此定義整個數(shù)組…
最后一個石子處于序號為17的單元格的位置。
返回 true。即青蛙可以成功過河，按照如下方案跳躍：
跳1個單位到第2塊石子, 然后跳2個單位到第3塊石子, 接著
跳2個單位到第4塊石子, 然后跳3個單位到第6塊石子,
跳4個單位到第7塊石子, 最后，跳5個單位到第8個石子（即最后一塊石子）。

示例2：

[0,1,2,3,4,8,9,11]
返回 false。青蛙沒有辦法過河。
這是因為第5和第6個石子之間的間距太大，沒有可選的方案供青蛙跳躍過去。

3. 題目解析

方法一：哈希表、記憶化搜索、遞歸解法

首先要理解青蛙跳到某個石頭上可能有多種跳法，由于這道題只是讓判斷青蛙是否能跳到最后一個石頭上，并沒有讓我們返回所有的路徑，這樣就降低了一些難度。下面為遞歸做法思路：

• 使用記憶化搜索，維護一個哈希表，建立青蛙在 pos 位置和擁有 jump 跳躍能力時是否能跳到對岸
• 為了能用一個變量同時表示 pos 和 jump，可以將 jump 左移很多位并或上 pos，由于題目中對于位置大小有限制，所以不會產(chǎn)生沖突
• 首先判斷 pos 是否已經(jīng)到最后一個石頭了，是的話直接返回 true
• 然后查看當(dāng)前這種情況是否已經(jīng)出現(xiàn)在哈希表中，是的話直接從哈希表中取結(jié)果
• 如果沒有，就遍歷余下的所有石頭，對于遍歷到的石頭，計算到當(dāng)前石頭的距離 dist
• 如果 dist 小于 jump - 1，接著遍歷下一塊石頭
• 如果 dist 大于 jump + 1，說明無法跳到下一塊石頭，m[key] 賦值為 false，并返回 false
• 如果在青蛙能跳到的范圍中，調(diào)用遞歸函數(shù)，以新位置 i 為 pos，距離 dist 為 jump，如果返回 true 了，即給 m[key] 賦值為 true，并返回 true
• 如果結(jié)束遍歷給 m[key] 賦值為 false，并返回 false

參見代碼如下：

// 執(zhí)行用時 :40 ms, 在所有 C++ 提交中擊敗了94.12%的用戶 // 內(nèi)存消耗 :13.9 MB, 在所有 C++ 提交中擊敗了81.25%的用戶class Solution { public:bool canCross(vector<int>& stones) {unordered_map<int, bool> m;return help(stones, 0, 0, m);}bool help(vector<int>& stones, int pos, int jump, unordered_map<int, bool>& m) {int n = stones.size(), key = pos | jump << 11;if (pos >= n - 1) return true;if (m.count(key)) return m[key];for (int i = pos + 1; i < n; ++i) {int dist = stones[i] - stones[pos];if (dist < jump - 1) continue;if (dist > jump + 1) return m[key] = false;if (help(stones, i, dist, m)) return m[key] = true;}return m[key] = false;} };

方法二：迭代解法

也可以用迭代的方法來解，思路如下：

• 用一個哈希表來建立每個石頭和在該位置上能跳的距離之間的映射
• 建立一個一維 dp 數(shù)組，其中 dp[i] 表示在位置為 i 的石頭青蛙的彈跳力(只有青蛙能跳到該石頭上，dp[i]才大于0)
• 由于題目中規(guī)定了第一個石頭上青蛙跳的距離必須是 1，為了跟后面的統(tǒng)一，對青蛙在第一塊石頭上的彈跳力初始化為 0 (雖然為 0，但是由于題目上說青蛙最遠能到其彈跳力 +1 的距離，所以仍然可以到達第二塊石頭)。
• 用變量 k 表示當(dāng)前石頭，然后開始遍歷剩余的石頭
• 對于遍歷到的石頭 i，來找到剛好能跳到 i 上的石頭 k，如果 i 和 k 的距離大于青蛙在 k 上的彈跳力 +1，則說明青蛙在 k 上到不了 i，則 k 自增 1
• 從 k 遍歷到 i，如果青蛙能從中間某個石頭上跳到 i 上，則更新石頭 i 上的彈跳力和最大彈跳力
• 這樣當(dāng)循環(huán)完成后，只要檢查最后一個石頭上青蛙的最大彈跳力是否大于0即可

參見代碼如下：

// 執(zhí)行用時 :140 ms, 在所有 C++ 提交中擊敗了66.29%的用戶 // 內(nèi)存消耗 :35.5 MB, 在所有 C++ 提交中擊敗了36.81%的用戶class Solution { public:bool canCross(vector<int>& stones) {unordered_map<int, unordered_set<int>> m;vector<int> dp(stones.size(), 0);m[0].insert(0);int k = 0;for (int i = 1; i < stones.size(); ++i) {while (dp[k] + 1 < stones[i] - stones[k]) ++k;for (int j = k; j < i; ++j) {int t = stones[i] - stones[j];if (m[j].count(t - 1) || m[j].count(t) || m[j].count(t + 1)) {m[i].insert(t);dp[i] = max(dp[i], t);}}}return dp.back() > 0;} };

方法三：回溯法+貪心策略+剪枝

和上述幾種方法大致思路一樣：由于當(dāng)前可跳的步長取決于上一次調(diào)到次石頭上的步長，所以將上一次可達此石頭的步長保存，然后根據(jù)上一次的到達此石頭的步長集合選擇當(dāng)前可跳的步長。

// 執(zhí)行用時 :616 ms, 在所有 C++ 提交中擊敗了15.61%的用戶 // 內(nèi)存消耗 :38.9 MB, 在所有 C++ 提交中擊敗了14.94%的用戶 class Solution { public:bool canCross(vector<int>& stones) {//第一步只能跳一個不長if (stones[1] != stones[0] + 1) {return false;}int endStone = *(--stones.end());//尾端石頭set<int> stonesSet(++stones.begin(), stones.end());//將vector容器轉(zhuǎn)換為set容器map<int, set<int> > myMap;//myMap[i]標(biāo)記i可跳的不長myMap[*stonesSet.begin()].insert(1);//初始只能跳一步到第二個位置//順序訪問所有石頭for (auto stone : stonesSet) {//根據(jù)上一次到達此地的步長集合，計算下一步可跳的步長for (auto nextStone : myMap[stone]) {//步長nextStone - 1if (nextStone > 1 && stonesSet.find(stone + nextStone - 1) != stonesSet.end()) {//如果跳nextStone - 1后到達的石頭在stonesSet中，說明stone + nextStone - 1這塊石頭可由不長nextStone - 1到達myMap[stone + nextStone - 1].insert(nextStone - 1);}//步長nextStoneif (stonesSet.find(stone + nextStone) != stonesSet.end()) {//如果跳nextStone 后到達的石頭在stonesSet中，說明stone + nextStone這塊石頭可由不長nextStone到達myMap[stone + nextStone].insert(nextStone);}//步長nextStone + 1if (stonesSet.find(stone + nextStone + 1) != stonesSet.end()) {//如果跳nextStone + 1后到達的石頭在stonesSet中，說明stone + nextStone + 1這塊石頭可由不長nextStone + 1到達myMap[stone + nextStone + 1].insert(nextStone + 1);}//如果已經(jīng)達到了endStoneif (myMap.count(endStone) > 0) {return true;}}}return false;} };

剪枝：

// 執(zhí)行用時 :24 ms, 在所有 C++ 提交中擊敗了96.83%的用戶 // 內(nèi)存消耗 :12.3 MB, 在所有 C++ 提交中擊敗了86.81%的用戶 class Solution { private:set<int> stonesSet; public://從nowStone開始搜索能否到達last，beforeStep為到達nowStone的步長bool jump(int nowStone, int beforeStep, int last) {//如果已經(jīng)達到了終點if ((nowStone + beforeStep + 1) == last || (nowStone + beforeStep) == last || (nowStone + beforeStep - 1) == last){return true;}//采取貪心策略，每次都先選擇beforeStep + 1步長if (stonesSet.find(nowStone + beforeStep + 1) != stonesSet.end() && jump(nowStone + beforeStep + 1, beforeStep + 1, last)) {return true;}//再beforeStep步長if (stonesSet.find(nowStone + beforeStep) != stonesSet.end()&& jump(nowStone + beforeStep, beforeStep, last)) {return true;}//最后beforeStep - 1步長if (beforeStep > 1 && stonesSet.find(nowStone + beforeStep - 1) != stonesSet.end()&& jump(nowStone + beforeStep - 1, beforeStep - 1, last)) {return true;}return false;}bool canCross(vector<int>& stones) {if (stones[1] != 1) return false;int last = stones.back();for (int i = 1; i < stones.size(); ++i) {if (i > 3 && stones[i - 1] * 2 < stones[i]){//剪枝算法，stones[i - 1]最多是有步長stones[i - 1]到達//stones[i - 1] * 2 < stones[i],說明無論如何stones[i]都不可達return false;}stonesSet.insert(stones[i]);}return jump(1, 1, last);} };

總結(jié)

以上是生活随笔為你收集整理的[每日一题] 128. 青蛙过河(数组、记忆化搜索、递归、剪枝）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。