818 Race Car

818. Race Car

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的距离还要远，则没必要对这个位置继续进行搜索

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)