樣例 輸入: [2,3,1,1,4] 2 2 。從下標為 0 ?跳到下標為 1 ?的位置，跳?1 ?步，然后跳?3 ?步到達數(shù)組的最后一個位置。
解題 https://www.cnblogs.com/techflow/p/12596586.html 今天這題的題目蠻有意思，它是說給定我們一個非負整數(shù) 的數(shù)組。讓我們把這個數(shù)組想象成一個大富翁里的那種長條形的地圖。數(shù)組當中的數(shù)字表示這個位置向前最多能前進的距離?，F(xiàn)在我們從數(shù)組0號位置開始移動，請問至少需要移動多少步可以走到數(shù)組的結尾？ 搜索 我拿到題目的第一反應就是搜索，因為感覺貪心是不可以的。我們把數(shù)組當中每個位置的數(shù)字稱為前進能力，我們當下能達到的最遠的位置前進能力可能很差，所以貪心能夠達到最遠的位置并不可行，舉個例子： 如果我們從0開始的時候走到3的話，由于3的前進能力很小 ，所以我們需要3步才能走完數(shù)組。但是如果我們一開始不走滿3，而是走到2的話，我們只需要兩步就可以完成。所以貪心是有反例的，我們不能簡單地來貪心。而且這題的狀態(tài)轉移十分明顯，幾乎是裸的順推。那么我們只需要搜就完事了，由于這是一個求解最優(yōu)的問題 ，所以我們應該使用寬度優(yōu)先搜索。 class Solution :def jump (self, nums: List[int ]) -> int :import queuelen (nums)0 , 0 ))while not empty ():step = que.get ()if -1 :return step for in 1 )):step +1 ))但是顯然這么交上去是一定會gg的，想想也知道，我們遍歷轉移狀態(tài)的這個for-loop看起來就很恐怖，數(shù)組當中的狀態(tài)很有可能出現(xiàn)重復 ，那么必然會出現(xiàn)大量的冗余。所以我們需要加上一些剪枝 ，由于我們使用的是寬度優(yōu)先搜索，所以所有狀態(tài)第一次在隊列當中彈出的時候就是最優(yōu)解，不可能同樣的位置，我多走幾步會達到更優(yōu)的結果，所以我們可以放心地把之前出現(xiàn)過的位置全部標記起來，阻止重復遍歷： class Solution :def jump (self, nums: List[int ]) -> int :import queuelen (nums)0 , 0 ))set ()while not empty ():step = que.get ()if -1 :return step for in 1 )):# 如果已經(jīng)入過隊列了則跳過 if in continue step +1 ))很遺憾，雖然我們加上了優(yōu)化，但是還是會被卡掉 。所以還需要繼續(xù)優(yōu)化，我們來分析一下會超時的原因很簡單，雖然我們通過標記排除了重復進入隊列的情況。但是for循環(huán)本身的計算量可能就很大 ，尤其在數(shù)組當中存在大量前進能力很大的位置的時候。舉個例子，比如我們超時的樣例： [25000,24999,24998,24997,24996,24995,24994...] 可以看到，這個數(shù)組的前進能力都很大，我們會大量地重復遍歷 ，這個才是計算量的根源。所以我們要避免循環(huán)重復的部分，有辦法解決嗎？ 當然是有的，我們來分析一下問題，對于某一個位置x而言，它的前進能力是m。那么它可以達到的最遠距離是x + m，這是顯然的，但是很有可能從x到x+m的區(qū)間當中已經(jīng)有一部分被加入隊列了。所以當我們從x向x+m遍歷的時候，必然會重復遍歷一部分已經(jīng)在隊列當中的狀態(tài)。那怎么解決呢？ 其實很簡單，我們只需要把遍歷的順序倒過來 就好了。也就是說我們從x+m向x反向遍歷，當我們遇到一個狀態(tài)已經(jīng)在隊列當中的時候，就可以break了，沒必要繼續(xù)往下了。因為后面的狀態(tài)肯定已經(jīng)遍歷過了。 class Solution :def jump (self, nums: List[int ]) -> int :import queuelen (nums)0 , 0 ))set ()while not empty ():step = que.get ()if -1 :return step # 倒敘遍歷 for in -1 , pos+nums[pos]), pos, -1 ):# 當遇到已經(jīng)遍歷過的元素的時候直接break if in break step +1 ))除了上面的方法之外，我們還可以想到一種優(yōu)化，我們可以使用優(yōu)先隊列對隊列當中的元素進行排列 ，將潛力比較大的元素排在前面，而將潛力差的排在后面。但是你會發(fā)現(xiàn)如果我們把前進能力當做是潛力或者是所處的位置當做潛力都有反例，因為位置靠前的可能前進能力很差，但是前進能力比較好的，又可能位置靠后。有沒有兩全其美的辦法呢？ 當然是有的，方法也很簡單，我們把兩者相加，也就是位置加上它的前進能力當做這個位置的潛力 。也可以認為是最遠能夠移動到的位置當做是潛力，這樣我們每次都挑選出其中潛力最好的進行迭代，從而保證我們可以最快地找到答案。 class Solution :def jump (self, nums: List[int ]) -> int :import queuelen (nums)# 使用優(yōu)先隊列 0 , 0 , 0 ))set ()while not empty ():step = que.get ()if -1 :return step # 倒敘遍歷 for in -1 , pos+nums[pos]), pos, -1 ):if in break # 由于優(yōu)先隊列是默認元素小的排在前面，所以加上負號 step +1 ))貪心 不知道大家在寫完上面這串代碼之后有什么感覺，我最大的感覺不是成就感，而是覺得奇怪，就好像總覺得有哪里不太對勁 ，但是又不知道到底是哪里不對。 后來我想了很久，終于想明白了。不對的地方在于既然我們已經(jīng)想到了這么具體的策略來優(yōu)化搜索，我們?yōu)槭裁催€要用搜索呢？因為我們沒必要維護狀態(tài)了，直接貪心不行嗎？ 在正常的bfs搜索當中，我們是一層一層地遍歷狀態(tài)的，每次遍歷的都是搜索樹上同樣深度的節(jié)點 。只有某一個深度的節(jié)點都遍歷結束了，我們才會遍歷下一個深度的節(jié)點。但是現(xiàn)在使用了優(yōu)先隊列之后，我們打破了這個限制 ，也就是說我們拿到的狀態(tài)根本不知道是來源于哪一個深度的。而從這個題目的題意來看，潛力大的排在前面，會使得一開始潛力小的狀態(tài)一直得不到迭代，沉積在隊列的底部。 既然如此，我們?yōu)槭裁催€要用隊列來存儲呢，直接維護最大的潛力值不就可以了？ 解釋一下上面這段話的意思，在當前問題當中，由于我們可以走的距離是連續(xù)的。我們可以維護一個當前步數(shù)能夠移動的范圍 ，舉個例子，比如nums[0]=10，也就是說從0開始，一直到10的區(qū)間都是我們可以移動的。對于這個區(qū)間里的每一個x來說，它可以移動的范圍就是[x, x+nums[x]]。所以我們可以得到x+nums[x]的集合，這里面最大的那個，就是下一步我們能夠移動的范圍 。也就是說第二步的移動范圍就是[11, max(x+nums[x])]。我們不停地迭代，當能夠達到的最遠位置大于或等于數(shù)組長度的時候，就表示遍歷結束了。 rangeI表示第一步能夠移動到的范圍，顯然由于我們起始位置是0，所以這個范圍就是[0, nums[0]]。等于rangeI當中的每一個位置都有一個潛力值，其實就是它能達到的最遠的距離。對于rangeI當中的每一個位置的潛力值而言，它們顯然有一個最大值，我們假設最大值的下標是x，它的潛力值就是x+nums[x] 。那么我們就可以得到rangeII的范圍是[nums[0]+1, x+nums[x]]。我們只需要在遍歷rangeI的時候記錄下這個x 就可以得到rangeII的范圍，我們重復以上過程迭代就行了。 class Solution :def jump (self, nums: List[int ]) -> int :len (nums)end = 0 , nums[0 ]step = 1 if 1 :return 0 while end < n-1 :0 , 0 # 維護下一個區(qū)間 for in end +1 ):if # 下一個區(qū)間的起始范圍 end = end +1 , maxistep += 1 return step 只有短短十來行，我們就解出了一個LeetCode當中的難題。一般來說都是我們先試著用貪心，然后發(fā)現(xiàn)不行，再換算法用搜索，而這道題剛好相反，我們是先想到搜索的解法，然后一點一點推導出了貪心 。我想如果你能把上面思路推導的過程全部理解清楚，一定可以對這兩種算法都有更深的感悟。當然，也有些大神是可以直接想到最優(yōu)解的，如果做不到也沒什么好遺憾的，只要我們勤于思考，多多理解，遲早有一天，這些問題對我們來說也不會是難事。 好了，今天的文章就到這里，如果覺得有所收獲，請順手點個在看 或者轉發(fā)吧，你們的支持是我最大的動力。 
