Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/818.html
818. Race Car
Level
Hard
Description
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.
Solution
Use dynamic programming. Create an array dp of length Math.max(target + 3, target * 2), where dp[i] represents the length of the shortest sequence of instructions to get to position i. Initialize dp[0] = 0, dp[1] = 1 and dp[2] = 4.
If i is 2^k - 1 for some k, then dp[i] = k. Otherwise, suppose 2^(k - 1) <= i < 2^k for some positive integer k, it is possible to reach 2^(k - 1) - 1 first and then use instructions with “R” to reach i, or reach 2^k - 1 first and then use instructions with “R” to reach i. Calculate the minimum length accordingly.
-
class Solution { public int racecar(int target) { int[] dp = new int[Math.max(target + 3, target * 2)]; Arrays.fill(dp, Integer.MAX_VALUE); dp[0] = 0; dp[1] = 1; dp[2] = 4; for (int i = 3; i <= target; i++) { int bits = (int) (Math.log(i) / Math.log(2)) + 1; if (i == (1 << bits) - 1) dp[i] = bits; else { for (int j = 0; j < bits - 1; j++) dp[i] = Math.min(dp[i], dp[i - (1 << (bits - 1)) + (1 << j)] + bits - 1 + j + 2); if ((1 << bits) - 1 - i < i) dp[i] = Math.min(dp[i], dp[(1 << bits) - 1 - i] + bits + 1); } } return dp[target]; } } -
// OJ: https://leetcode.com/problems/race-car/ // Time: O(?) // Space: O(?) // Ref: https://leetcode.com/problems/race-car/discuss/124312/Javascript-Python3-C%2B%2B-.-BFS-solutions class Solution { public: int racecar(int target) { queue<array<int, 2>> q; q.push({0, 1}); unordered_map<int, unordered_set<int>> seen; seen[0].insert(1); int step = 0; while (true) { int cnt = q.size(); while (cnt--) { auto [pos, speed] = q.front(); q.pop(); if (pos == target) return step; vector<array<int, 2>> cand; if (abs(target - (pos + speed)) < target) cand.push_back({ pos + speed, 2 * speed }); // Only continue moving in the current direction if doing so reduces the distance. cand.push_back({ pos, speed < 0 ? 1 : - 1 }); // reverse direction for (auto &[pos, speed] : cand) { if (seen[pos].count(speed)) continue; seen[pos].insert(speed); q.push({pos, speed}); } } ++step; } return -1; } }; -
class Solution: def racecar(self, target: int) -> int: dp = [0] * (target + 1) for i in range(1, target + 1): k = i.bit_length() if i == 2**k - 1: dp[i] = k continue dp[i] = dp[2**k - 1 - i] + k + 1 for j in range(k - 1): dp[i] = min(dp[i], dp[i - (2 ** (k - 1) - 2**j)] + k - 1 + j + 2) return dp[target] -
func racecar(target int) int { dp := make([]int, target+1) for i := 1; i <= target; i++ { k := bits.Len(uint(i)) if i == (1<<k)-1 { dp[i] = k continue } dp[i] = dp[(1<<k)-1-i] + k + 1 for j := 0; j < k; j++ { dp[i] = min(dp[i], dp[i-(1<<(k-1))+(1<<j)]+k-1+j+2) } } return dp[target] } func min(a, b int) int { if a < b { return a } return b }