面试难题：跳跃游戏

5 回答

• 16

  概述

  给定数组 a 和当前位置 i 的索引，重复以下操作直到到达最后一个元素 .

  考虑 a[i+1] 到 a[a[i] + i] 中的所有候选"jump-to elements" . 对于索引 e 处的每个此类元素，计算 v = a[e] e . 如果其中一个元素是最后一个元素，则跳转到最后一个元素 . 否则，跳转到具有最大 v 的元素 .

  更简单地说，触手可及的元素，寻找能让你在下一次跳跃中走得最远的元素 . 我们知道这个选择 x 是正确的，因为与你可以跳转到的每个其他元素 y 相比，从 y 可到达的元素是从 x 可到达的元素的子集（向后跳转的元素除外，这显然是坏的选择） .

  该算法在O（n）中运行，因为每个元素只需要考虑一次（可以跳过被认为是第二次的元素） .

  示例

  考虑值数组 a ，indicies， i 以及索引和值 v 的总和 .

  i ->  0   1   2   3   4   5   6   7   8   9  10  11  12
  a -> [4, 11,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1]
  v ->  4  12   3   4   5   6   7   8   9  10  11  12  13
  

  从索引0开始，考虑接下来的4个元素 . 找到最大 v 的那个 . 该元素位于索引1处，因此跳转到1.现在考虑接下来的11个元素 . 目标是触手可及的，所以跳到目标 .

  演示

  见here或here with code .

  回复于 2024-05-03T21:03:46+08:00
• 0

  动态编程 .

  想象一下，你有一个数组 B ，其中 B[i] 显示了在数组 A 中到达索引 i 所需的最小步数 . 您的回答当然是 B[n] ，因为 A 有 n 元素，索引从1开始 . 假设 C[i]=j 表示您从索引j跳转到索引i（这是为了恢复稍后采用的路径）

  所以，算法如下：

  set B[i] to infinity for all i
  B[1] = 0;                    <-- zero steps to reach B[1]
  for i = 1 to n-1             <-- Each step updates possible jumps from A[i]
      for j = 1 to A[i]        <-- Possible jump sizes are 1, 2, ..., A[i]
          if i+j > n           <-- Array boundary check
              break
          if B[i+j] > B[i]+1   <-- If this path to B[i+j] was shorter than previous
              B[i+j] = B[i]+1  <-- Keep the shortest path value
              C[i+j] = i       <-- Keep the path itself
  

  所需的跳转次数为 B[n] . 需要采取的路径是：

  1 -> C[1] -> C[C[1]] -> C[C[C[1]]] -> ... -> n
  

  哪个可以通过简单的循环恢复 .

  该算法具有 O(min(k,n)*n) 时间复杂度和 O(n) 空间复杂度 . n 是 A 中的元素数， k 是数组内的最大值 .

  注意

  我保留了这个答案，但是cheeken的贪婪算法是正确的，更有效率 .

  回复于 2024-05-03T21:03:46+08:00
• 5

  从数组构造有向图 . 例如：i-> j if | i-j | <= x [i]（基本上，如果你可以在一跳中从i移动到j，则i-> j作为图中的边缘） . 现在，找到从第一个节点到最后一个节点的最短路径 .

  FWIW，您可以使用Dijkstra的算法，以便找到最短的路线 . 复杂度为O（| E | | V | log | V |） . 自| E | <n ^ 2，这变为O（n ^ 2） .

  回复于 2024-05-03T21:03:46+08:00
• 6

  从左（结束）开始..和遍历直到数字与索引相同，使用这些数字的最大值 . 例如，如果列表是

  list:  2738|4|6927
     index: 0123|4|5678
  

  一旦你从这个数字重复上述步骤，直到你达到极右 .

  273846927
  000001234
  

  如果您没有找到与索引匹配的nething，请使用最远索引且值大于index的数字 . 在这种情况下7.（因为很快索引将大于数字，你可能只计算9个索引）

  回复于 2024-05-03T21:03:46+08:00
• 0

  基本理念：

  通过查找所有可以从中跳转到目标元素的数组元素（所有 i ，使得 A[i] >= target - i ），开始构建从结尾到开始的路径 .

  将每个这样的 i 视为新目标并找到它的路径（递归） .

  选择找到的最小长度路径，追加 target ，返回 .

  python中的简单示例：

  ls1 = [2,3,1,1,4]
  ls2 = [4,11,1,1,1,1,1,1,1,1,1,1,1]
  
  # finds the shortest path in ls to the target index tgti
  def find_path(ls,tgti):
  
      # if the target is the first element in the array, return it's index.
      if tgti<= 0:
          return [0]
  
      # for each 0 <= i < tgti, if it it possible to reach
      # tgti from i (ls[i] <= >= tgti-i) then find the path to i
  
      sub_paths = [find_path(ls,i) for i in range(tgti-1,-1,-1) if ls[i] >= tgti-i]
  
      # find the minimum length path in sub_paths
  
      min_res = sub_paths[0]
      for p in sub_paths:
          if len(p) < len(min_res):
              min_res = p
  
      # add current target to the chosen path
      min_res.append(tgti)
      return min_res
  
  print  find_path(ls1,len(ls1)-1)
  print  find_path(ls2,len(ls2)-1)
  
  >>>[0, 1, 4]
  >>>[0, 1, 12]
  

  回复于 2024-05-03T21:03:46+08:00