44. Jump Game II

题目

给定一个非负数组 nums，你一开始在数组的第一个索引。
数组中的每个元素表示你在该位置可以跳的最大距离。
你的目标是以最少的跳跃次数，到达最后一个索引。
你可以认为你总能到达最后一个索引。

解析

这个问题看起来就像是一个动态规划的问题。
f(n) = canjump(n-i) + f(n-i)

1. 假设跳转的目标索引是 target
2. 在 target 之后找到一个数字 jump
3. 如果这个数字能跳转到 jump，那么到达 target 所需的次数是后边的数到达 jump 的次数 + 1。
4. 如果这个数字不能到达 target，放弃这次循环。

伪代码

jump(nums []int, target, j)

if nums[j] < target-i 
    return MAX
for i:=len(num)-1;i--
  if nums[i] >= target-i
    min = f(num[:i]) + 1
    if min < rst
      rst = min
return min

上边的代码效率会太慢，因为会重复计算位置，考虑循环解决这个问题。

1. 计算 f(0) 得到 f(0) = 0
2. 计算 f(1),f(1) = f(0) + 1 条件：num[0] 一定大于 0
3. 计算 f(2),f(2)= min(f(0) + 1 f(1) + 1)
4. 计算 f(3), f(3) =min(f(0)+1, f(1)+1, f(2)+1)

f map[int]int
for target := 1; target<len(nums);target++
  min = MAX
  for i:=0;i<target;i++
    if nums[i] > target-i
        min = min(min, f[i]+1)
  f[target]=min

代码

func jump(nums []int) int {
    f := map[int]int{0:0}
    for target:=1; target<len(nums); target++ {
        rst := 1<<31-1
        for i:=0;i<target;i++{
            if nums[i] >= target-i {
                rst = min(rst, f[i]+1)
            }
        }
        f[target]=rst
    }
    return f[len(nums)-1]
}

func min(a,b int) int {
    if a < b {
        return a
    }
    return b
}

image.png

将 map 改为 slice。内存利用率和查询速度都有所提升。

image.png

算法改进。

1. 问题在于，第二次迭代的时候，每次都是从 0 到 n 比较计算。其实这个时候，已经有一些元素无法再到达这个地址了。对于这些元素，我们要将其抛弃掉。不再计算和比较。
2. 我们需要一个map结构，因为 map 结构，有界，可删除。 map[address][]index，key 表示目标地址，值是可以到达这些目标地址的索引。
3. 当我们走到一个 address 地址时，我们在 map 中删除 address-1，然后遍历 map，得到索引值，比较并计算。

f map[int]int
addr map[int][]int
f[0] = 0
addr[nums[0]] = []int{0}
for target := 1; target<len(nums);target++
  delete(addr, target-1)
  min = MAX
  for _, v := range addr
    for _,i = range v
        min = min(min, f[i]+1)
  f[target]=min
  addr[nums[target]] = []int{target}

代码

func jump(nums []int) int {
    f := make([]int,len(nums))
    addr := map[int][]int{}
    f[0] = 0
    addr[nums[0]] = append(addr[nums[0]], 0)
    for target:=1; target<len(nums); target++ {
        delete(addr, target-1)
        rst := 1<<63-1
        for _,idxs := range addr {
            for _, idx := range idxs {
                rst = min(rst, f[idx]+1)
            }
        }
        f[target]=rst
        addr[nums[target]+target] = append(addr[nums[target]+target], target)
    }
    return f[len(nums)-1]
}

func min(a,b int) int {
    if a < b {
        return a
    }
    return b
}

image.png

并没有预期的效率提升？