818.Race-Car

818. Race Car

题目地址

https://leetcode.com/problems/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.

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];
}