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.
代码
Approach #1 BFS Solution
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;
}
#2 BFS
class Solution {
class CarInfo{
int pos, speed;
public CarInfo(int p, int s) {
pos = p;
speed = s;
}
}
public int racecar(int target) {
Set<String> visited = new HashSet<>();
String begin = 0 + "/" + 1;
visited.add(begin);
Queue<CarInfo> queue = new LinkedList<>();
queue.add(new CarInfo(0,1));
int level = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for(int i = 0; i < size; i++) {
CarInfo cur = queue.poll();
if (cur.pos == target) return level;
String s1 = (cur.pos + cur.speed) + "/" + (cur.speed * 2);
String s2 = cur.pos + "/" + (cur.speed > 0 ? -1 : 1);
if (Math.abs(cur.pos + cur.speed - target) < target && !visited.contains(s1)) {
visited.add(s1);
queue.add(new CarInfo(cur.pos + cur.speed, cur.speed * 2));
}
if (Math.abs(cur.pos - target) < target && !visited.contains(s2)) {
visited.add(s2);
queue.add(new CarInfo(cur.pos, cur.speed > 0 ? -1 : 1));
}
}
level++;
}
return -1;
}
}
Approach #2 Dynamic Programming
Consider two general cases for number i with bit_length n.i==2^n-1, this case, n is the best way2^(n-1)-1<i<2^n-1, there are two ways to arrive at i: Use n A to arrive at 2^n-1 first, then use R to change the direction, by here there are n+1 operations (n A and one R), then the remaining is same as dp[2^n-1-i]Use n-1 A to arrive at 2^(n-1)-1 first, then R to change the direction, use m A to go backward, then use R to change the direction again to move forward, by here there are n-1+2+m=n+m+1 operations (n-1 A, two R, m A) , current position is 2^(n-1)-1-(2^m-1)=2^(n-1)-2^m, the remaining operations is same as dp[i-(2^(n-1)-1)+(2^m-1)]=dp[i-2^(n-1)+2^m)].`
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];
}
Top Down DP
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 target, int[] dp) {
if (dp[target] >= 0) {
return dp[target];
}
dp[target] = Integer.MAX_VALUE;
int m = 1, j = 1;
for (; j < target; j = (1 << ++m) - 1) {
for (int q = 0, p = 0; p < j; p = (1 << ++q) - 1) {
dp[target] = Math.min(dp[target], m + 1 + q + 1 + racecar(target - (j - p), dp));
}
}
dp[target] = Math.min(dp[target], m + (target == j ? 0 : 1 + racecar(j - target, dp)));
return dp[target];
}
Bottom-up DP
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];
}