題目描述
給定一個(gè)非負(fù)整數(shù)數(shù)組，你最初位于數(shù)組的第一個(gè)位置。
數(shù)組中的每個(gè)元素代表你在該位置可以跳躍的最大長度。
你的目標(biāo)是使用最少的跳躍次數(shù)到達(dá)數(shù)組的最后一個(gè)位置。
示例:
輸入: [2,3,1,1,4]
輸出: 2
解釋: 跳到最后一個(gè)位置的最小跳躍數(shù)是 2。
從下標(biāo)為 0 跳到下標(biāo)為 1 的位置，跳 1 步，然后跳 3 步到達(dá)數(shù)組的最后一個(gè)位置。
說明:
假設(shè)你總是可以到達(dá)數(shù)組的最后一個(gè)位置。
解題思路：
從左到右，依次查找到能一次跳到目的地的位置des最后位置k，然后將目的地位置des更新為k，遞歸循環(huán)到k=0，每地遞歸一次步數(shù)+1，最后返回步數(shù)。另外如果全部出現(xiàn)全部為1的情況，添加標(biāo)簽flag，表示到達(dá)目的地的位置之前的元素是否全為1，如果全為1，且最后一步k = des - 1，直接返回des-1 +jumps（之前的步數(shù)）。 代碼如下：
var jumps = 0
func jump(_ nums: [Int]) -> Int {
if nums.count < 2 {
return 0
}
return jumpTo(nums.count - 1, nums: nums)
}
func jumpTo(_ des:Int,nums:[Int]) -> Int {
var k = 0
jumps += 1
var isnoOne = true ///不是所有的元素都為1
while k < des && nums[k] + k < des {///查找到目的地des的最后一跳的位置
if nums[k] != 1{///過程中是否存在全為1的元素
isnoOne = false
}
k += 1
}
if k == 0 {
return jumps;
}else if k == des - 1 && isnoOne{///des之前的元素都為1，且最后一步的位置在des - 1
return des + jumps - 1
}else{
return jumpTo(k, nums: nums)///更新目的地為找到的最后一跳的位置
}
}
