字节面经 | 面试题 | 跳动的“字节”

题目描述

“字节”在数轴 0 点出发，向左或向右跳动（左右横跳），第一次跳 1 个单位，第二次 2 个单位，以此类推。给定系列目标 [x1, x2, ..., xn]，“字节”依次跳动到给定目标，并在到达后重置跳跃步长，继续按 1, 2,... 步长跳往下一目标。求“字节”跳动到 [x1, x2, ..., xn] 的最小步数 [s1, s2, ..., sn]

示例一

1. 输入： nums = [2, 1]
2. 输出：3, 4
3. 解释：

• 从 0 跳动到节点 2 的最小路径是 0 -> 1 -> -1 -> 2，步数为 3
• 从 2 跳动到节点 1 的最短路劲是 2 -> 1，步数为 3 + 1

示例二

1. 输入： nums = [1, 2, 2]
2. 输出：1, 2, 2
3. 解释：

• 从 0 跳动到节点 1 的最小路径是 0 -> 1，步数为 1
• 从 1 跳动到节点 2 的最小路径是 1 -> 2，步数为 1 + 1
• 从 1 跳动到节点 2 的最小路径是 2，步数为 2

数据范围

1. 1<=n<=100
2. -10^7 <= xi <= 10^7

以下是个人思路

预处理

从位置 x 跳到 y，新增步数只与间距 |x-y| 有关，问题转化为：给定间距 gap，求从 0 跳到 gap 的最小步数。用差分提取数据间距

gaps = [abs(nums[i+1]-nums[i]) for i in range(len(nums))]
gaps.insert(0, abs(nums[0])) # 补首元素

假设 0 跳动到 n 的最小步数为 jump_to(n)，累和得总步数 res

totalstep, res = 0, []
for gap in gaps:
      totalstep += jump_to(gap)
      res.append(totalstep)

问题难点计算 jump_to(n)，由于数据范围为 -10^7 <= xi <= 10^7，计算复杂度至多是线性的。

代码

def jump_to(gap):
    n = int((2 * gap) ** .5)
    if n*(n + 1) < 2 * gap: # 定位上界
        n += 1
    if gap & 1: # 奇数情形
        if n % 4 in (1, 2): return n
        return n + (1 if n % 4 == 0 else 2)
    if n % 4 in (0, 3): return n
    return n + (1 if (n % 4) == 2 else 2)

def min_jump(nums):
    gaps = [abs(nums[i+1] - nums[i]) for i in range(len(nums)-1)]
    gaps.insert(0, abs(nums[0]))
    totalstep, res = 0, []
    for gap in gaps:
        totalstep += jump_to(gap)
        res.append(totalstep)
    return res

复杂度分析：

• 设间距为 G，jump_to 的复杂度为 O(1)
• 设数据总数为 N，min_jump 时间复杂度为 O(N)，空间复杂度优化后为 O(1)

  def min_jump(nums):
      pre, totalstep, res = 0, 0, []
      for num in nums:
          totalstep += jump_to(abs(num - pre))
          res.append(totalstep)
          pre = num
      return res

解题思路

分析一：若 gap > 1+2+...+n，跳动到 gap 至少要 n+1 步
分析二：若 n 步到达 gap，则 gap = ± 1 ± 2 ± ... ± n，往左跳为负，往右为正

1. 观察跳跃 6 次到达的位置：21, 19, 17，从 21 开始每次退 2，退到 15，步长减一
   

2. 类似地，跳跃 5 次到达的位置：15, 13, 11, 9, 7, 5，从 15 开始退2， 退到 3，步长减一
   

3. 注意后退不改变奇偶性，gap 的奇偶情形要分开处理

4. 最后考虑累和序列 1, 1+2, 1+2+3,1+2+3+4,...,n*(n+1) 的奇偶性： 奇,奇,偶,偶,奇,奇,偶,偶...，即

   • n % 4 == 1, 2 序列值为奇数
   • n % 4 == 0, 3 序列值为偶数

5. 算法思路：

   • 定位最小上界 n 使得 n*(n+1) >= 2*gap
   • 如果位置 n 的奇偶性符合，返回 n
   • 如果位置 n 的奇偶性不符合，返回最近的正确位置

6. 举两个例子：

具体地：

• 8 = -1 + 2 + 3 + 4
• 14 = 1 + 2 + 3 + 4 + 5 + 6 - 7