0818：赛车（2391 分）

Ian

2017-03-28 约 797 字预计阅读 2 分钟次阅读

力扣第 818 题

题目

你的赛车可以从位置 0 开始，并且速度为 +1 ，在一条无限长的数轴上行驶。赛车也可以向负方向行驶。赛车可以按照由加速指令 ‘A’ 和倒车指令 ‘R’ 组成的指令序列自动行驶。

当收到指令 'A' 时，赛车这样行驶：
- position += speed
- speed *= 2
当收到指令 'R' 时，赛车这样行驶：
- 如果速度为正数，那么speed = -1
- 否则 speed = 1
当前所处位置不变。

例如，在执行指令 "AAR" 后，赛车位置变化为 0 --> 1 --> 3 --> 3 ，速度变化为 1 --> 2 --> 4 --> -1 。

给你一个目标位置 target ，返回能到达目标位置的最短指令序列的长度。

示例 1：

输入：target = 3
输出：2
解释：
最短指令序列是 "AA" 。
位置变化 0 --> 1 --> 3 。

示例 2：

输入：target = 6
输出：5
解释：
最短指令序列是 "AAARA" 。
位置变化 0 --> 1 --> 3 --> 7 --> 7 --> 6 。

提示：

1 <= target <= 10⁴

分析

#1

用A^k表示连续使用k次A指令，那么最优指令必然可以表示为 $A^{k1}RA^{k2}R⋯A^{kn},ki≥0$
- 假如某个指令列表是 $RA^{k1}RA^{k2}R⋯A^{kn}$，可以将 $RA^{k1}R$ 放到结尾变成 $RA^{k1}$ 或 $RRA^{k1}$，长度相等或更短
- 还可以将 ki 排序，使得 k1 最大，长度不变
先求 target 的二进制位数 m，则 2^(m-1)<=target<2^m
- 若 target=2^m-1，k1 取 m，直接到达终点
- 否则 k1 要么取 m，要么取 m-1：
  - k1 取 m，那么用了指令 $RA^{k1}R$ 后，转为递归子问题，求 t=2^m-1-target 的最短长度
  - k1 取 m-1，那么枚举 0<=k2<k1，用了指令 $RA^{k1}RA^{k2}R$ 后，转为递归子问题，求 t=target-2^(m-1)+2^(k2) 的最短长度
k1、k2 取值限制的证明见 O(n^0.695)复杂度的dfs，以及一些性质证明

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution(object):
    def racecar(self, target):
        @cache
        def dfs(t):
            k = t.bit_length()
            base = 1<<(k-1)
            if t==base*2-1:
                return k
            res = dfs(base*2-1-t)+k+1
            for j in range(k-1):
                res = min(res,dfs(t-base+(1<<j))+k+j+1)
            return res
        return dfs(target)

7 ms

#2

还可以写成最短路的形式，用 dijkstra

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


class Solution(object):
    def racecar(self, target):
        pq = [(0,target)]
        d = defaultdict(lambda:inf)
        d[target] = 0
        while pq:
            w,u = heapq.heappop(pq)
            if u==0:
                return w
            if w>d[u]:
                continue
            k = u.bit_length()
            base = 1<<(k-1)
            if u==base*2-1:
                heappush(pq,(w+k,0))
                continue
            v,w2 = base*2-1-u,w+k+1
            if w2<d[v]:
                d[v] = w2
                heappush(pq,(w2,v))
            for j in range(k-1):
                v,w2 = u-base+(1<<j),w+k+j+1
                if w2<d[v]:
                    d[v] = w2
                    heappush(pq,(w2,v))

0 ms

目录

0818：赛车（2391 分）

题目

分析

#1

#2

解答