中文字幕人成人乱码亚洲电影,91打几把,国产69精品久久久久久久久久久久,大香蕉视频网站,99国产一区,亚洲无码视频在线观看高清,免费电影黄色视频,日你av

青蛙的故事

青蛙公主是遠(yuǎn)近聞名的大美蛙??，她一心想找一個聰明的老公，于是設(shè)下擂臺，比武招親：有連續(xù)的木板，因為材質(zhì)不同，每個木板能跳的最大距離有限，來應(yīng)招的青年才俊，需要判斷，是否能跳到最后一塊板子。

讓我們來看看輸入參數(shù)：一個非負(fù)整數(shù)數(shù)組，青蛙位于數(shù)組的第一個位置，數(shù)組中的每個元素代表你在該位置可以跳躍的最大長度。輸出就更簡單：能否跳到。

解題思路

按照一般的解題思維，DFS肯定可以做，但效率應(yīng)該不是最高。遞推的話，動態(tài)規(guī)劃可以考慮，同時看看有沒有使用貪心算法的可能性，如果能貪心，那可能就是最簡路徑。

很幸運，這道題無論是DFS，還是動態(tài)規(guī)劃，亦或是貪心算法都可以做，我比較喜歡這類題，從不同思路，開展不同做法，互相比較，歸納復(fù)盤，容易得到提高。話不多說，我們來逐個看看。

花式吊打

DFS深度優(yōu)先算法

最直接的解法，就是基于每種可能，即每塊板子可能的跳躍距離，進(jìn)行DFS遞歸搜索。這種算法思路比較無腦，缺點顯而易見：時間復(fù)雜度很高，大概率會超時。

換個角度：目標(biāo)是最后一個木板。那么往前找到所有能跳到目標(biāo)的木板，然后以這些木板為目標(biāo)，遞歸查找下去。這種算法速率也一般，算是優(yōu)化版的DFS。

果不其然，運行超時，蛙蛙流淚。

動態(tài)規(guī)劃

我們定義一個數(shù)組dp，dp[i]表示當(dāng)前可以覆蓋的最大范圍。當(dāng)前位置能否可達(dá)很簡單，判斷dp[i-1]是否小于i，如果小于就不可達(dá)。如果可達(dá)，更新dp[i] = Max(dp[i-1], i+nums[i])。

由上圖執(zhí)行結(jié)果可以看到，按照動態(tài)規(guī)劃執(zhí)行的數(shù)據(jù)，相比DFS是飛躍，耗時減少2/3，內(nèi)存消耗減少100%以上，時間復(fù)雜度應(yīng)該已經(jīng)是最優(yōu)，后面就看空間上是否可以優(yōu)化。

貪心算法

貪心算法，顧名思義，就是足夠貪心。如果當(dāng)前木板能跳到的距離比當(dāng)前能達(dá)的距離更遠(yuǎn)，就跳到當(dāng)前木板，否則就先停留在當(dāng)前木板。按照這樣的規(guī)則，一直跳到最后一塊板，其間永遠(yuǎn)站在能跳的最遠(yuǎn)的木板。如果中間有位置不可達(dá)了，那就是跳不到，因為在貪心的基礎(chǔ)上，當(dāng)前點已經(jīng)是覆蓋范圍最大的了，如果這樣都跳不到，其他方式也不行的。

我們能看到這樣寫代碼，簡潔優(yōu)雅，耗時滿足預(yù)期，寫完給自己點個贊??，青蛙王子也得感謝我！

但是仔細(xì)想想，上面的代碼其實可以更簡潔明了。因為在本題中跳點不是必要項，換句話說，我們可以從關(guān)注跳點，變成關(guān)注距離。優(yōu)化后的代碼如下，是不是更加清晰？

把簡單的事情做復(fù)雜不算什么。把復(fù)雜的事情越做越簡單，才是能力提升的關(guān)鍵！

逆推法

實不相瞞，這題做到這里，還做出感覺了。我就想，還有沒有其他解決方法？

換個角度思考一下，之前大多為正向推導(dǎo)，但是DFS是逆向行走，說明逆推是可行的，只是我們嫌棄DFS效率太低。

對于一個目標(biāo)位置，我們往前找能跳到該位置的最近的木板，將這個木板作為我們新的目標(biāo)。這樣持續(xù)倒推，如果最終推導(dǎo)到了第一塊木板，也就是我們的起點，那么就證明可以從起點跳到終點。

注意，我們來仔細(xì)思考下這種方式和DFS的不同，DFS是基于當(dāng)前位置，從后往前遞歸所有能跳到當(dāng)前木板的情況，會走完多條分支路徑；而這種逆推方式，只會隨遇而安地往前挪挪，是O(n)的復(fù)雜度。

蛙蛙復(fù)盤

橫看成嶺側(cè)成峰，條條大路通羅馬，一個簡單的跳板運動，居然有這么多思維方式。把一件事情做到極致，我們也一定會收獲多多。做算法題，不僅要嘗試beats 100%，更進(jìn)一步的追求是將各種方式都做透徹，每種方式可能有自己的優(yōu)缺點，很可能加一個限制條件，當(dāng)前最優(yōu)解就成死路了。

當(dāng)然，最重要的是，這樣的做題習(xí)慣訓(xùn)練了我們不同思維方式。無論是在學(xué)習(xí)還是工作中，一個問題，你能給出好幾種解決方案，還不能成為這條街上最靚的仔？

騰訊面試題：青蛙跳跳跳

DFS深度優(yōu)先算法

動態(tài)規(guī)劃

貪心算法

逆推法