Hello, 剛剛結束完一天的工作,忙着把算法題寫完.那麼今天繼續講解算法題第55題, 也是一道經典的面試題目,那我們來一起看一看吧.
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
「Example1」Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.
來簡單描述一下這道題目的意思, 大緻上就是給定一個數組, 數組中的元素代表你可以往後跳的一個步數,比方nums[0]=2 代表它可以選擇跳到nums[1] 和 nums[2] 這兩步
我們來畫個圖，舉個例子給大家看看
我用四種不同的顔色代表每個元素可以跳躍的步數, 這下子是不是就很清楚了
接着我們來回顧一下
「遞歸」和
「動态規劃」的思想
- 「建立一個數組 存儲動态規劃的過程」
- 「尋找遞歸結束的條件(可以先畫個樹圖出來幫助了解)」
我們先來看一下 動态規劃我們要準備什麼？ 其實我們就是要儲存, 每個點是否能跳躍到終點的記錄
我們用-1,0,1來代表3種狀态,分别是
「不能到達」,
「初始化」,
「可以到達」三個階段
我們先初始化dp的數組, 并且将終點設定為1, 因為終點肯定能到終點 接下來,我們來思考一下
「遞歸的結束條件應該是什麼？」我們先把遞歸圖畫出來
從這道例子中, 我們遞歸樹應該是這樣子
我們的遞歸順序,就是從左邊的1開始，往右邊數,最後才做2自己本身, 在這個例子中你會發現, 你無論選那一條路 你都能到終點對吧, 那我們就換一題來講
我們對着下面這個題目, 畫一下動态規劃表
是以, 我們的動态規劃表應該是上圖那樣的結果. 1代表可到達的路徑, -1代表不可到達
是以說, 我們遞歸結束的條件 應該是
「dp[i]==-1」或
「dp[i]==1」為結束條件
如果
「dp[i]==0」說明該節點尚未被計算,需要再次把這個節點進行遞歸 如果遞歸到了死胡同了, 我們就把該點标記成為-1退出則可
讓我們來看一下遞歸代碼
func recurrentJump(position int,nums []int, dp *[]int) bool{
if (*dp)[position] == 1{
return true
}else if (*dp)[position] == -1{
return false
}
maxJump := min(position + nums[position], len(nums)-1)
for i:= position + 1; i<=maxJump; i++{
result:=recurrentJump(i, nums, dp)
if result {
(*dp)[position] = 1
return true
}
}
(*dp)[position] = -1
return false
}
func min(x int, y int) int{
if (x < y){
return x
}
return y
}
遞歸的主函數就在上面, 和我們描述的一緻, 如果說
「dp[i]==-1」或
「dp[i]==1」直接可以傳回否則說明該節點尚未被計算
我們來看一下節點未被計算的時候需要做的循環
maxJump := min(position + nums[position], len(nums)-1)
for i:= position + 1; i<=maxJump; i++{
result:=recurrentJump(i, nums, dp)
if result {
(*dp)[position] = 1
return true
}
}
首先 求最小的跳躍 次數 這裡的
「position + nums[i]」與
「nums長度」比較,取小的一位代表着該節點，最大能跳到哪裡 然後我們再循環遞歸, 把該節點能跳的位置, 全部再遞歸一次
如果說傳回值等于
「true」則代表本節點可以跳躍到終點, 記錄本節點為
「dp[position]=1」然後傳回
「true」告訴上一層的節點, 你也可以通過我到達終點, 如下圖所示
然後我們在看一下主函數
func canJump(nums []int) bool {
var dp = make([]int, len(nums))
for i:=0; i<len(nums); i++ {
dp[i] = 0
}
dp[len(nums)-1] = 1
ans:= recurrentJump(0, nums, &dp)
return ans
}
這裡, 沒什麼好講的 就是初始化DP數組, 然後從下标0開始遞歸,
遞歸以及動态規劃的例子, 那麼很明顯的問題就是...效率極低 那麼我們也沒有什麼思路可以讓效率更高一些呢?
順便附帶上GitHub的代碼位址:LeetCode代碼集合-持續更新中
那麼就來講解另外2種思路
「1. 動态規劃」 「2. 優化版動态規劃(優化的是空間複雜度)」那我們就順着這個思路往下走, 先來了解一下動态規劃的算法去取代掉遞歸的算法
動态規劃版
大家應該忘記,我們動态規劃是需要一個表來存儲以往的記錄的吧,在這個算法裡, 我們照樣需要使用到這個數組
那麼這個做法就是不使用遞歸, 用for循環做, 我們繼續看代碼
func nonRecurrentJump(nums[] int, dp *[]int) bool{
for i:= len(nums)-2;i>=0;i-- {
maxJump := min(i+nums[i], len(nums)-1) //擷取跳躍的步數
for j := i + 1; j<=maxJump; j++{
if (*dp)[j] == 1{
(*dp)[i] = 1
break
}
}
}
if (*dp)[0] == 1{
return true
}
return false
}
在這個算法中, 跟遞歸的很像,唯一的差别就是在于在第二個For的循環中,我們不在是進入遞歸了, 而是直接檢視
「dp[j]==1」是否成立, 而這段代碼中我們的思路其實轉變了, 遞歸的思想是從頭開始找, 而這段代碼是從後往前
我們把問題簡化一下, 從需要到達
「dp[len(nums)-1]」變成
「dp[len(nums)-i]」個
因為隻要我們能到達
「2」這個元素,說明我們可以達到終點, 那麼從2往前的元素,隻需要知道自己能不能到達2
這就是這個算法的核心所在, 如果可以到達 則把
「dp[i]=1」并且跳出内層循環,直到最後的結果應該是這樣
最後, 我們判斷
「dp[0]==1」是否成立,如果成立代表從第0個出發,可以到達終點, 很明顯我們比起遞歸而言要快将近
「5倍」的時間
優化動态規劃
我們在想深一層次, 我們真的需要這個數組嗎?
其實不需要對吧, 為什麼? 因為我們一直都是在與
「最新」的一個元素做對比, 那我們為什麼還需要一個數組去存儲呢?
也就是說,我們可以去掉數組,将代碼簡化成這樣...
func optimizeNonRecurrentJump(nums[] int) bool{
aim := len(nums)-1 //終點
for i:= len(nums)-2;i>=0;i-- {
maxJump := min(i+nums[i], len(nums)-1)
for j := i + 1; j<=maxJump; j++{
if j == aim{
aim = i //更新最近的終點
}
}
}
if aim == 0{
return true
}
return false
}
建立 一個變量叫aim 永遠拿它指向最後一個終點, 如果有比它更前的元素接近終點, 則更新它
最後我們判斷
「aim==0」是否成立,就知道我們第一個元素是否可以到達終點拉
這個方案比之前的省下了
「0.2MB」的空間 又一次的進步。
創作不易, 希望留下你們的小贊贊,是最大的鼓勵