> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/oj-practices/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/oj-practices/chapter1/heap/818-race-car.md).

# 818     Race Car

## 818. [Race Car](https://leetcode.com/problems/race-car/description/)

## 1. Question

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.
```

**Note:**

* `1 <= target <= 10000`.

## 2. Implementation

**(1) BFS**

题目要求我们找出**最短**的instruction,使得car可以从0这个位置到target位置。已知instruction只有两种，A表示加速，R表示调头。由于题目给了我们初始状态，并要求我们利用最短的方式到达最终状态，很容易让我们想到用BFS。 BFS的思路比较直接，就是用queue存每个状态的两个变量: 当前位置和当前速度，然后对于每个状态都分别进行加速和掉头的操作，如果符合条件则放到queue中继续搜索。这里为了提高算法的效率，我们发现过程中可能会有重复的状态出现，所以我们需要用一个visited的set去重，另一可以优化的地方是，如果当前的位置nexPos离target的距离比初始位置离target的距离还要远，则没必要对这个位置继续进行搜索

```java
class Solution {
    public int racecar(int target) {
        Queue<int[]> queue = new LinkedList();
        queue.add(new int[] {0, 1});

        Set<String> visited = new HashSet();
        visited.add("0/1");

        int level = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                int[] curInfo = queue.remove();
                int curPos = curInfo[0];
                int curSpeed = curInfo[1];

                if (curPos == target) {
                    return level;
                }

                // Accelerate
                int nextPos = curPos + curSpeed;
                int nextSpeed = 2 * curSpeed;
                int[] nextInfo = new int[] {nextPos, nextSpeed};
                String key = nextPos + "/" + nextSpeed;

                // if the distance from target for nextPos is greater than the initial position (0), 
                // we don't consider nextPos
                if (!visited.contains(key) && Math.abs(nextPos - target) < target) {
                    visited.add(key);
                    queue.add(nextInfo);
                }

                // Reverse
                nextPos = curPos;
                nextSpeed = curSpeed > 0 ? -1 : 1;
                nextInfo = new int[] {nextPos, nextSpeed};
                key = nextPos + "/" + nextSpeed;

                // if the distance from target for nextPos is greater than the initial position (0), 
                // we don't consider nextPos
                if (!visited.contains(key) && Math.abs(nextPos - target) < target) {
                    visited.add(key);
                    queue.add(nextInfo);
                }
            }
            ++level;
        }
        return -1;
     }
}
```

## 3. Time & Space Complexity

时间复杂度O(2 ^ n), n为instruction的长度，因为在BFS过程中，我们对accelerate和reverse两种操作都进行了尝试, 所以总的时间复杂度是2^n, 空间复杂度O(2 ^ n)