给定一个数组,从下标为0开始,往右跳,下标对应的值表示其能跳的最远距离。求最少X步,能跳到最后一个元素?

简单思路

最近看SICP看的比较多,第一个想到的办法,就是递归。

  1. 对于数组\([a,a_1...a_n]\),找到能跳到最后的最小下标\(m\)
  2. 对于数组\([a,a_1...a_m]\),找到能跳到最后的最小下标\(l\)
  3. ……
  4. 当最后数组长度为1的时候,说明已经到头了
func jump(nums []int) int {
	return jumpIter(nums, 0)
}

func findMin(nums []int) int {
	for i := 0; i < len(nums); i++ {
		if i+nums[i] >= len(nums)-1 {
			return i
		}
	}
	return len(nums) - 1
}

func jumpIter(nums []int, count int) int {
	if len(nums) == 1 {
		return count
	}
	return jumpIter(nums[:findMin(nums)+1], count+1)
}

改进

在上面的算法中,从左到右,

  1. 很多位置(\(i\))能达到的最远距离(\(nums[i]+i\)),都被计算了多次。
  2. 就算是每个位置的最远距离缓存/保存起来,迭代次数并不会减少。

改进的思路,依然是从左往右遍历FindNext

func jump(nums []int) int {
	if len(nums) == 1 {
		return 0
	}
	var limit, next, steps int
	for i := 0; i <= limit; i++ { //从左到limit
		if i+nums[i] > next { //更新最大的next
			next = i + nums[i]
		}
		if i == limit { //如果已经移动到了limit
			steps++
			limit = next              //从0-limit之间选出最远的next
			if limit >= len(nums)-1 { //如果current-limit之间的最远距离已经达到目标
				break
			}
		}
	}
	return steps
}

整理一下

func jump(nums []int) int {
	var limit, try, steps int
	for i := 0; i < len(nums); i++ {
		if i > limit { //当前点 已经超过 之前最远下标
			steps++     //要移动1次
			limit = try //当前最大点 = 可到达最远下标
		}
		if try < i+nums[i] { //更新 可到达最远下标
			try = i + nums[i]
		}
	}
	return steps
}