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)
Last updated
Was this helpful?