Massive Algorithms: LeetCode 818

LeetCode 818 - Race Car

Your car starts at position 0 and speed +1 on an infinite number line. (Your car can go into negative positions.)

Your car drives automatically according to a sequence of instructions A (accelerate) and R (reverse).

When you get an instruction "A", your car does the following: position += speed, speed *= 2.

When you get an instruction "R", your car does the following: if your speed is positive then speed = -1 , otherwise speed = 1. (Your position stays the same.)

For example, after commands "AAR", your car goes to positions 0->1->3->3, and your speed goes to 1->2->4->-1.

Now for some target position, say the length of the shortest sequence of instructions to get there.

Example 1:
Input: 
target = 3
Output: 2
Explanation: 
The shortest instruction sequence is "AA".
Your position goes from 0->1->3.

Example 2:
Input: 
target = 6
Output: 5
Explanation: 
The shortest instruction sequence is "AAARA".
Your position goes from 0->1->3->7->7->6

https://leetcode.com/problems/race-car/discuss/124326/Summary-of-the-BFS-and-DP-solutions-with-intuitive-explanation

DP solution works by noting that after each reverse, the car's speed returns to 1 (the sign can be interpreted as the direction of the speed). So we can redefine the problem in terms of the position of the car while leave out the speed: let T(i) be the length of the shortest instructions to move the car from position 0 to position i, with initail speed of 1 and its direction pointing towards position i. Then our original problem will be T(target), and the base case is T(0) = 0. Next we need to figure out the recurrence relations for T(i).

Note that to apply the definition of T(i) to subproblems, the car has to start with speed of 1, which implies we can only apply T(i) right after the reverse instruction. Also we need to make sure the direction of the initial speed when applying T(i) is pointing towards the final target position.

However, we don't really know how many accelerate instructions there should be before the reverse instruction, so theoretically we need to try all possible cases: zero A, one A, two A, three A, ... and so on. For each case, we can obtain the position of the car right before the reverse instruction, which will be denoted as j = 2^m - 1, with m the number of A's. Then depending on the relation between i and j, there will be three cases:

j < i: the reverse instruction is issued before the car reaches i. In this case, we cannot apply the definition of T(i) to the subproblems directly, because even though the speed of the car returns to 1, its direction is pointing away from the target position (in this case position i). So we have to wait until the second reverse instruction is issued. Again, we don't really know how many accelerate instructions there should be in between these two reverse instructions, so we will try each of the cases: zero A, one A, two A, three A, ..., etc. Assume the number of A is q, then the car will end up at position j - p right before the second reverse instruction, where p = 2^q - 1. Then after the second reverse instruction, our car will start from position j - p with speed of 1 and its direction pointing towards our target position i. Since we want the length of the total instruction sequence to be minimized, we certainly wish to use minimum number of instructions to move the car from j - p to i, which by definition will be given by T(i-(j-p)) (note that in the definition of T(i), we move the car from position 0 to position i. If the start position is not 0, we need to shift both the start and target positions so that the start position is aligned with 0). So in summary, for this case, the total length of the instruction will be given by: m + 1 + q + 1 + T(i-(j-p)), where m is the number of A before the first R, q is the number of A before the second R, the two 1's correspond to the two R's, and lastly T(i-(j-p)) is the length of instructions moving the car from position j - p to the target position i.
j == i: the target position is reached without any reverse instructions. For this case, the total length of the instruction will be given by m.
j > i: the reverse instruction is issued after the car goes beyond i. In this case, we don't need to wait for a second reverse instruction, because after the first reverse instruction, the car's speed returns to 1 and its direction will be pointing towards our target position i. So we can apply the definition of T(i) directly to the subproblem, which will be T(j-i). Note that not only do we need to shift the start and target positions, but also need to swap them as well as the directions. So for this case, the total length of the instructions will be given by m + 1 + T(j-i).

Our final answer for T(i) will be the minimum of the above three cases.

III -- Intuitive explanation of the optimizations

As I mentioned in section I, we need further optimizations for the BFS solution to work efficiently. This turns out also to be the case for the DP solution. To see why, recall that in the first case of the DP solution, we don't really impose any upper limit on the value of q (we do have limit for the value of m though: j = 2^m-1 < i), while in the third case, we don't really have any upper limit for the value of m. Apparently we cannot explore every possible values of m and q (there are infinitely many).

to be updated...

IV -- Solutions

Here is a list of solutions: one BFS, one top-down DP and one bottom-up DP.

The BFS runs at O(target * log(target)) in the worst case, with O(target * log(target)) space. The reasoning is as follows: in the worst case, all positions in the range [-target, target] will be visited and for each position there can be as many as 2 * log(target) different speeds.

Both the top-down DP and bottom-up DP run at O(target * (log(target))^2) with O(target) space. However, the top-down DP may be slightly more efficient as it may skip some of the intermediate cases that must be computed explicitly for the bottom-up DP. Though the nominal time complexity are the same, both DP solutions will be much more efficient in practice compared to the BFS solution, which has to deal with (position, speed) pairs and their keys for hashing, etc.

public int racecar(int target) {
    int[] dp = new int[target + 1];
    Arrays.fill(dp, 1, dp.length, -1);
    return racecar(target, dp);
}

private int racecar(int i, int[] dp) {
    if (dp[i] >= 0) {
        return dp[i];
    }
    
    dp[i] = Integer.MAX_VALUE;
    
    int m = 1, j = 1;
    
    for (; j < i; j = (1 << ++m) - 1) {
        for (int q = 0, p = 0; p < j; p = (1 << ++q) - 1) {
            dp[i] = Math.min(dp[i],  m + 1 + q + 1 + racecar(i - (j - p), dp));
        }
    }
    
    dp[i] = Math.min(dp[i], m + (i == j ? 0 : 1 + racecar(j - i, dp)));
    
    return dp[i];
}

public int racecar(int target) {
    int[] dp = new int[target + 1];
    
    for (int i = 1; i <= target; i++) {
        dp[i] = Integer.MAX_VALUE;
        
        int m = 1, j = 1;
        
        for (; j < i; j = (1 << ++m) - 1) {
            for (int q = 0, p = 0; p < j; p = (1 << ++q) - 1) {
                dp[i] = Math.min(dp[i], m + 1 + q + 1 + dp[i - (j - p)]);
            }
        }
        
        dp[i] = Math.min(dp[i], m + (i == j ? 0 : 1 + dp[j - i]));
    }
    
    return dp[target];
}

http://hehejun.blogspot.com/2018/04/leetcoderace-car.html

如果我们进一步考虑的话，如果x距离target还很遥远并且当前速度为v，我们还需要考虑把步长调整到小于v的情况吗？按道理也应该是不用的(很可惜我还是不会证明)，假设k满足条件2^(k - 1) - 1 <= target <= 2^k - 1那么我们搜索target的策略可以简化到如下情况：

一直走到达2^k - 1，然后Reverse，向左继续搜索，这样的话，就变成了从0开始搜索2^k - 1 - target的情况
一直走到2^(k - 1) - 1然后Reverse向左走到某点z，然后从z继续向右搜索。当前的步长为2^(k - 1)，我们向左走的距离不会超过这个步长，否则只是无意义地增加步数，遍历所有小于这个值的步长。假设我们向左走了m(m < k - 1)步到达z，也就是2^m - 1的距离，那么问题也就变成了，从0开始搜索target - (2^(k - 1) - 1 - 2^m - 1) = target - 2^(k - 1) + 2^m的问题

如果我们用dp[i]表示，从0开始搜索i需要的最小步数。假设n满足条件2^(n - 1) - 1 <= target <= 2^n - 1，我们根据上面可以推得递推公式：

dp[i] = n + 1 + dp[2^n - 1 - i]，对应第一种情况，连续n个A，之后一个R
dp[i] = n + m + 1 + dp[i - 2^(n - 1) + 2^m], where m < n - 1，第二种情况，n - 1个A，一个R，之后m个A，再一个R

根据递推公式实现即可，时间复杂度O(n * log n)

https://www.cnblogs.com/grandyang/p/10360655.html

首先来定义dp数组吧，就用一个一维的dp数组，长度为target+1，其中dp[i]表示到达位置i，所需要的最少的指令个数。接下来就是推导最难的状态转移方程了，这里我们不能像BFS解法一样对每个状态都无脑尝试加速和反向操作，因为状态转移方程是要跟之前的状态建立联系的。根据之前的分析，对于某个位置i，我们有两种操作，一种是在到达该位置之前，回头两次，另一种是超过该位置后再回头，我们就要模拟这两种情况。

首先来模拟位置i之前回头两次的情况，那么这里我们就有正向加速，和反向加速两种可能。我们假设正向加速能到达的位置为j，正向加速次数为cnt1，反向加速能到达的位置为k，反向加速的次数为cnt2。那么正向加速位置j从1开始遍历，不能超过i，且根据之前的规律，j每次的更新应该是 2^cnt1 - 1，然后对于每个j位置，我们都要反向跑一次，此时反向加速位置k从0开始遍历，不能超过j，k每次更新应该是 2^cnt2 - 1，那么到达此时的位置时，我们正向走了j，反向走了k，即可表示为正向走了(j - k)，此时的指令数为 cnt1 + 1 + cnt2 + 1，加的2个‘1’分贝是反向操作的两次计数，当我们第二次反向后，此时的方向就是朝着i的方向了，此时跟i之间的距离可以直接用差值在dp数组中取，为dp[i - (j - k)]，以此来更新dp[i]。

接下来模拟超过i位置后才回头的情况，此时cnt1是刚好能超过或到达i位置的加速次数，我们可以直接使用，此时我们比较i和j，若相等，则直接用cnt1来更新dp[i]，否则就反向操作一次，然后距离差为j-i，从dp数组中直接调用 dp[j-i]，然后加上反向操作1次，用来更新dp[i]，最终返回 dp[target] 即为所求

采用动态规划的思路，定义dp[target]表示行驶长度为target的距离所需要的最小指示个数。可以证明有如下两种可能性：

1）如果target刚好是可以由“AAA...AR”（一共n步）达到，也就是说前面一路加速，最后再减速到-1，那么这种走法就是最优选择；

2）如果不满足条件1），那么最优解就有多种可能性了：a）第一次冲过target的时候进行‘R’操作，然后反向再接近target。此时我们已经走了n+1步，并且和target的距离已经减少到了(1 << n) - 1 - target，所以我们可以递归地调用rececar函数；b）前面先走m步（可以通过递归调用racecar函数得到最优值），然后再采用1）的策略。最终的答案就是a）和b）的各种可能性的最小值。

为了达到最优的运行效率，我们采用dp + memorization的策略：每当需要计算一个子问题时，首先查表看看该子问题是否已经被计算过了；如果是，则直接返回结果；否则我们再进行计算，并且将结果保存下来，以备后面的计算再次使用

        int[] dp = new int[target + 3];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0; dp[1] = 1; dp[2] = 4;

        for (int t = 3; t <= target; ++t) {
            int k = 32 - Integer.numberOfLeadingZeros(t);
            // 如果 t = 2^k - 1,那么 k 步就是最短的步数(一直加速到达 t 位置即可 'AAA...')
            if (t == (1 << k) - 1) {
                dp[t] = k;
                continue;
            }

            for (int j = 0; j < k - 1; ++j) {
                dp[t] = Math.min(dp[t], dp[t - (1 << (k - 1)) + (1 << j)] + k - 1 + j + 2);
            }
            if ((1 << k) - 1 - t < t) {
                dp[t] = Math.min(dp[t], dp[(1 << k) - 1 - t] + k + 1);
            }
        }

        return dp[target];
    }

X. https://leetcode.com/problems/race-car/discuss/123834/C%2B%2BJavaPython-DP-solution

For the input 5, we can reach with only 7 steps: AARARAA. Because we can step back.

Let's say n is the length of target in binary and we have 2 ^ (n - 1) <= target < 2 ^ n
We have 2 strategies here:
1. Go pass our target , stop and turn back
We take n instructions of A.
1 + 2 + 4 + ... + 2 ^ (n-1) = 2 ^ n - 1
Then we turn back by one R instruction.
In the end, we get closer by n + 1 instructions.

2. Go as far as possible before pass target, stop and turn back
We take N - 1 instruction of A and one R.
Then we take m instructions of A, where m < n

    int[] dp = new int[10001];
    public int racecar(int t) {
        if (dp[t] > 0) return dp[t];
        int n = (int)(Math.log(t) / Math.log(2)) + 1;
        if (1 << n == t + 1) dp[t] = n;
        else {
            dp[t] = racecar((1 << n) - 1 - t) + n + 1;
            for (int m = 0; m < n - 1; ++m)
                dp[t] = Math.min(dp[t], racecar(t - (1 << (n - 1)) + (1 << m)) + n + m + 1);
        }
        return dp[t];
    }

X.
https://www.cnblogs.com/grandyang/p/10360655.html

以下讲解主要参考了fun4LeetCode大神的帖子。说是起始时有个小车在位置0，速度为1，有个目标位置target，是小车要到达的地方。而小车只有两种操作，第一种是加速操作，首先当前位置加上小车速度，然后小车速度乘以2。第二种是反向操作，小车位置不变，小车速度重置为单位长度，并且反向。问我们最少需要多少个操作才能到达target。我们首先来看下若小车一直加速的话，都能经过哪些位置，从起点开始，若小车连加五次速，位置的变化为：

0 -> 1 -> 3 -> 7 -> 15 -> 31

有没有发现这些数字很眼熟，没有的话，就每个数字都加上个1，那么就应该眼熟了吧，对于信仰1024的程序猿来说，不眼熟不行啊，这就变成了2的指数数列啊，那么我们得出了结论，当小车从0开始连加n个速的话，其将会到达位置 2^n - 1。我们可以看出，小车越往后，位置跨度越大，那么当target不在这些位置上，很有可能一脚油门就开过了，比如，target = 6 的话，小车在3的位置上，一脚油门，就到7了，这时候就要回头，回头后，速度变为-1，此时正好就到达6了，那么小车的操作如下：

Initial: pos -> 0, speed -> 1

A: 　　pos -> 1, speed -> 2

A: 　　pos -> 3, speed -> 4

A: 　　pos -> 7, speed -> 8

R: 　　pos -> 7, speed -> -1

A: 　　pos -> 6, speed -> -2

所以，我们只需要5步就可以了。但是还有个问题，假如回头了以后，一脚油门之后，又过站了怎么办？比如 target = 5 的时候，之前小车回头之后到达了6的位置，此时速度已经是-2了，再加个速，就直接干到了位置4，就得再回头，那么这种方式小车的操作如下：

Initial: pos -> 0, speed -> 1

A: 　　pos -> 1, speed -> 2

A: 　　pos -> 3, speed -> 4

A: 　　pos -> 7, speed -> 8

R: 　　pos -> 7, speed -> -1

A: 　　pos -> 6, speed -> -2

A: 　　pos -> 4, speed -> -4

R: 　　pos -> 4, speed -> 1

A: 　　pos -> 5, speed -> 2

那么此时我们就用了8步，但这是最优的方法么，我们一定要在过了目标才回头么，不撞南墙不回头么？其实不必，我们可以在到达target之前提前调头，然后往回走走，再调回来，使得之后能恰好到达target，比如下面这种走法：

Initial: pos -> 0, speed -> 1

A: 　　pos -> 1, speed -> 2

A: 　　pos -> 3, speed -> 4

R: 　　pos -> 3, speed -> -1

A: 　　pos -> 2, speed -> -2

R: 　　pos -> 2, speed -> 1

A: 　　pos -> 3, speed -> 2

A: 　　pos -> 5, speed -> 4

我们在未到达target的位置3时就直接掉头了，往后退到2，再调回来，往前走，到达5，此时总共只用了7步，是最优解。那么我们怎么知道啥时候要掉头？问得好，答案是不知道，我们得遍历每种情况。但是为了避免计算一些无用的情况，比如小车反向过了起点，或者是超过target好远都不回头，我们需要限定一些边界，比如小车不能去小于0的位置，以及小车在超过了target时，就必须回头了，不能继续往前开了。还有就是小车当前的位置不能超过target*2，不过这个限制条件博主还没有想出合理的解释，各位看官大神们知道的话可以给博主讲讲～

对于求极值的题目，根据博主多年与LeetCode抗争的经验，就是BFS，带剪枝的DFS解法，贪婪算法，或者动态规划Dynamic Programming这几种解法（带记忆数组的DFS解法也可以归到DP一类中去）。一般来说，贪婪算法比较naive，大概率会跪。BFS有时候可以，带剪枝的DFS解法中的剪枝比较难想，而DP绝对是神器，基本没有解决不了的问题，但是代价就是得抓破头皮想状态转移方程，并且一般DP只能用来求极值，而想求极值对应的具体情况（比如这道题如果让求最少个数的指令是什么），有时候可能还得用带剪枝的DFS解法。不过这道题BFS也可以，那么我们就先用BFS来解吧。

这里的BFS解法，跟迷宫遍历中的找最短路径很类似，可以想像成水波，一圈一圈的往外扩散，当碰到target时候，当前的半径就是最短距离。用队列queue来辅助遍历，里面放的是位置和速度的pair对儿，将初始状态位置0速度1先放进queue，然后需要一个HashSet来记录处理过的状态，为了节省空间和加快速度，我们将位置和速度变为字符串，并在中间加逗号隔开，这样HashSet中只要保存字符串即可。之后开始while循环，此时采用的是层序遍历的写法，当前queue中所有元素遍历完了之后，结果res才自增1。在for循环中，首先取出队首pair对儿的位置和速度，如果位置和target相等，直接返回结果res。否则就要去新的地方了，首先尝试的是加速操作，此时新的位置newPos为之前的位置加速度，新的速度newSpeed为之前速度的2倍，然后将newPos和newSpeed加码成字符串，若新的状态没有处理过，且新位置大于0，小于target*2的话，则将新状态加入visited，并排入队列中。接下来就是转向的情况，newPos和原位置保持不变，newSpeed根据之前speed的正负变成-1或1，然后将newPos和newSpeed加码成字符串，若新的状态没有处理过，且新位置大于0，小于target*2的话，则将新状态加入visited，并排入队列中。for循环结束后，结果res自增1即可

I -- BFS solution

Well, the BFS solution is straightforward: we can keep track of all the possible positions of the racecar after n instructions (n = 0, 1, 2, 3, 4, ...) and return the smallest n such that the target position is reached. Naive BFS will run at O(2^n) since for each position we have two choices: either accelerate or reverse. Further observations reveal that there may be overlapping among intermediate states so we need to memorize visited states (each state is characterized by two integers: car position and car speed). However, the total number of unique states still blows up for large target positions (because the position and speed can grow unbounded), so we need further pruning of the search space.

public int racecar(int target) {
    Deque<int[]> queue = new LinkedList<>();
    queue.offerLast(new int[] {0, 1}); // starts from position 0 with speed 1
    
    Set<String> visited = new HashSet<>();
    visited.add(0 + " " + 1);
    
    for (int level = 0; !queue.isEmpty(); level++) {
        for(int k = queue.size(); k > 0; k--) {
            int[] cur = queue.pollFirst();  // cur[0] is position; cur[1] is speed
            
            if (cur[0] == target) {
                return level;
            }
            
            int[] nxt = new int[] {cur[0] + cur[1], cur[1] << 1};  // accelerate instruction
            String key = (nxt[0] + " " + nxt[1]);
            
            if (!visited.contains(key) && 0 < nxt[0] && nxt[0] < (target << 1)) {
                queue.offerLast(nxt);
                visited.add(key);
            }
            
            nxt = new int[] {cur[0], cur[1] > 0 ? -1 : 1};  // reverse instruction
            key = (nxt[0] + " " + nxt[1]);
            
            if (!visited.contains(key) && 0 < nxt[0] && nxt[0] < (target << 1)) {
                queue.offerLast(nxt);
                visited.add(key);
            }
        }
    }
    
    return -1;
}

http://guoyc.com/post/leetcode_weekly_contest_80/#818-race-car

Simple BFS, use a trick to prevent Memory Limit Exceed, only remember (position, speed) pair in visited when speed==1 or speed ==-1 (After R operation).


def racecar(self, target):

if target==0:

return 0

q = [(0, 1)]

visited = set((0, 1))

cnt = 0

while q:

new_q = []

cnt += 1

for pos, sp in q:

p1, s1 = pos+sp, sp*2

if p1==target:

return cnt

p2, s2 = pos, -1 if sp>0 else 1



# If we remember every position and speed pair, we get Memory Limit Exceed

# The most annoying part is continuous R, so only remember situations with speed 1 and -1

if (p1, s1) not in visited:

if s1==1 or s1==-1:

visited.add((p1, s1))

new_q.append((p1, s1))

if (p2, s2) not in visited:

visited.add((p2, s2))

if s1==1 or s1==-1:

visited.add((p1, s1))

new_q.append((p2, s2))

q = new_q

return -1

https://github.com/cherryljr/LeetCode/blob/master/Race%20Car.java

 * 对于 1 中的方法，虽然能够但是多少心里还是不舒坦，既然都贪了，为什么不贪到底呢？
 * 因为我们为了记录状态而使用了 String 类型，但是我们知道在 Java 中对于 String 的操作是线性的，
 * 因此代价还是挺高的。所以我们想能不能将它转换成 Integer 类型来表示呢？
 * 但是 Accelerate 操作带来的 2*speed 影响我们不好记录，因此我们想要不干脆就不记录它了吧。
 * 我们只在 Reverse 操作的时候记录状态信息，即变成了我只在 方向翻转 的时候记录状态，
 * 从而避免在 状态翻转 点的扩展，这样还是能够省去很多时间的。
 * 并且因为 反转点 的速度只有 -1 和 1 两种，为了处理方便，我们对其进行了 +1 操作将其转成了 [0, 2]
 * 这样我们只需要 两位 就能够记录它们的状态了（00, 10）。
 * 因此我们以最低的两位来记录翻转点的速度信息，高位记录位置信息。根据题目的数据范围，32位的数据是完全足够的。
 * 所以这里就将 String 转换成了 Integer 来记录数据，省去了对字符串的操作以及 HashSet 对于字符串的查找，
 * 这会使得我们的速度提升非常多。最后验证运行时间为 90ms.
 *
 * 当然这种极端的做法比较 hack,正常情况下并不推荐这么做，也会给代码的阅读上带来困难
 */
class Solution {
    public int racecar(int target) {
        if (target == 0) {
            return 0;
        }

        Queue<int[]> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        queue.offer(new int[]{0, 1});
        // 利用 Integer 来替代 String 表示 位置 和 速度 信息
        // 将 speed + 1 转换成 [0, 2] 以便被低位的两位表示
        visited.add(0);
        visited.add(2);
        int step = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] curr = queue.poll();

                // Accelerate
                int pos1 = curr[0] + curr[1];
                int speed1 = curr[1] << 1;
                if (pos1 == target) {
                    return step + 1;
                }
                // 剪枝优化
                if (pos1 > 0 && pos1 < target << 1) {
                    queue.offer(new int[]{pos1, speed1});
                }

                // Reverse
                int speed2 = curr[1] > 0 ? -1 : 1;
                // 位置信息左移两位腾出空间用来存储速度信息
                int key = curr[0] << 2 | (speed2 + 1);
                if (!visited.contains(key)) {
                    visited.add(key);
                    queue.offer(new int[]{curr[0], speed2});
                }
            }
            step++;
        }

        return -1;
    }

https://leetcode.com/problems/race-car/discuss/123884/Accepted-Java-solution-with-BFS

X. Approach #1: Dijkstra's [Accepted]
https://leetcode.com/articles/race-car/
http://hehejun.blogspot.com/2018/04/leetcoderace-car.html

With some target, we have different moves we can perform (such as

k_1 = 0, 1, 2, \cdots

, using the notation from our Approach Framework), with different costs.

This is an ideal setup for Dijkstra's algorithm, which can help us find the shortest cost path in a weighted graph.

Dijkstra's algorithm uses a priority queue to continually searches the path with the lowest cost to destination, so that when we reach the target, we know it must have been through the lowest cost path. Refer to this link for more detail.

Back to the problem, as described above, we have some barrier where we are guaranteed to never cross. We will also handle negative targets; in total we will have 2 * barrier + 1 nodes.

After, we could move walk = 2**k - 1 steps for a cost of k + 1 (the 1 is to reverse). If we reach our destination exactly, we don't need the R, so it is just k steps.

Time Complexity: $O(T \log T)$ . There are $O(T)$ nodes, we process each one using $O(\log T)$ work (both popping from the heap and adding the edges).
Space Complexity: $O(T)$ .

public int racecar(int target) {

int K = 33 - Integer.numberOfLeadingZeros(target - 1);

int barrier = 1 << K;

int[] dist = new int[2 * barrier + 1];

Arrays.fill(dist, Integer.MAX_VALUE);

dist[target] = 0;

PriorityQueue<Node> pq = new PriorityQueue<Node>((a, b) -> a.steps - b.steps);

pq.offer(new Node(0, target));

while (!pq.isEmpty()) {

Node node = pq.poll();

int steps = node.steps, targ1 = node.target;

if (dist[Math.floorMod(targ1, dist.length)] > steps)

continue;

for (int k = 0; k <= K; ++k) {

int walk = (1 << k) - 1;

int targ2 = walk - targ1;

int steps2 = steps + k + (targ2 != 0 ? 1 : 0);

if (Math.abs(targ2) <= barrier && steps2 < dist[Math.floorMod(targ2, dist.length)]) {

pq.offer(new Node(steps2, targ2));

dist[Math.floorMod(targ2, dist.length)] = steps2;

}

return dist[0];

}

class Node {

int steps, target;

Node(int s, int t) {

steps = s;

target = t;

}

https://www.acwing.com/solution/LeetCode/content/927/

你的赛车起始停留在位置 0，速度为 +1，正行驶在一个无限长的数轴上。（车也可以向负数方向行驶。）

你的车会根据一系列由 A（加速）和 R（倒车）组成的指令进行自动驾驶。

当车得到指令 “A” 时, 将会做出以下操作：position += speed, speed *= 2。

当车得到指令 “R” 时, 将会做出以下操作：如果当前速度是正数，则将车速调整为 speed = -1；否则将车速调整为 speed = 1。 (当前所处位置不变。)

例如，当得到一系列指令 “AAR” 后, 你的车将会走过位置 0->1->3->3，并且速度变化为 1->2->4->-1。

现在给定一个目标位置，请给出能够到达目标位置的最短指令列表的长度。

样例

示例 1:
输入: 
target = 3
输出: 2
解释: 
最短指令列表为 "AA"
位置变化为 0->1->3

输入: 
target = 6
输出: 5
解释: 
最短指令列表为 "AAARA"
位置变化为 0->1->3->7->7->6

X. Videos

花花酱 LeetCode 818. Race Car (上) - 刷题找工作 EP182
花花酱 LeetCode 818. Race Car (下） - 刷题找工作 EP184

LeetCode 818 - Race Car

样例

Labels

Popular Posts