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 #1, BFS 暴解,内存不不够 case: 330
O(2^n)
class Solution { public int racecar(int target) { Queue<Node> que = new LinkedList<>(); Node root = new Node(0, 1, 0); que.add(root); while (!que.isEmpty()) { Node node = que.poll(); if (node.pos == target) return node.len; que.add(new Node(node.pos + node.speed, node.speed * 2, node.len + 1)); que.add(new Node(node.pos, node.speed > 0 ? -1 : 1, node.len + 1)); } return 0; } class Node{ public int pos; public int speed; public int len; public Node(int pos, int speed, int len) { this.pos = pos; this.speed = speed; this.len = len; } } }
Solution #2, 加了优化 关键在于剪枝:Math.abs(nextPos - target) <= target. 因为起点跟target的距离就是target,如果比这个还远的话,那最终的步数肯定会超过,没有意义,所以要略掉O (n * log n), n为target的⼤小。速度只有log n种可能,因为速度永远是2的幂次⽅ O(n * log n) 空间,最坏情况是把所有pos和speed的组合都放在queue⾥
class Solution { public int racecar(int target) { Queue<Node> que = new LinkedList<>(); Node root = new Node(0, 1, 0); que.add(root); Set<String> visited = new HashSet<>(); visited.add("0#1"); visited.add("0#-1"); while (!que.isEmpty()) { Node node = que.poll(); if (node.pos == target) return node.len; int nextPos = node.pos + node.speed; String key1 = nextPos + "#" + node.speed *2; if (!visited.contains(key1) && Math.abs(nextPos - target) <= target) { que.add(new Node(nextPos, node.speed * 2, node.len + 1)); visited.add(key1); } String key2 = node.pos + "#" + (node.speed > 0 ? -1 : 1); if (!visited.contains(key2)) { que.add(new Node(node.pos, node.speed > 0 ? -1 : 1, node.len + 1)); visited.add(key2); } } return 0; } class Node{ public int pos; public int speed; public int len; public Node(int pos, int speed, int len) { this.pos = pos; this.speed = speed; this.len = len; } } }
Solution #3 rec + memoiz1tion 暴力枚举。 分3种情况:
- 刚好⾛到,target == pos,target刚好是2的幂次⽅
- 走过头一步,target < pos (两步就没有必要了,看Solution#2的剪枝)
- ⾛i步回头, 再⾛j步回头, i 属于[0, target], j 属于 [0, target - pos]. 注意变量的取值
ref: https://leetcode.com/problems/r1ce-c1r/discuss/124326/Summ1ry-of-the-BFS-1nd-DP-solutions-with-intuitive-expl1n1tion
class Solution { public int racecar(int target) { int[] dp = new int[target + 1]; Arrays.fill(dp, - 1); dp[0] = 0; return dfs(target, dp); } private int dfs(int target, int[] dp) { if (dp[target] >= 0) return dp[target]; dp[target] = Integer.MAX_VALUE; int speed = 1, pos = 0, times = 0; for (; pos < target; pos += speed, speed <<= 1, times++) { for (int revPos = 0, revSpeed = 1, revTimes = 0; revPos < pos; revPos += revSpeed, revSpeed <<= 1, revTimes++) { dp[target] = Math.min(dp[target], times + 2 + revTimes + dfs(revPos + target - pos, dp)); } } if (target == pos) { dp[target] = Math.min(dp[target], times); }else { dp[target] = Math.min(dp[target], times + 1 + dfs(pos - target, dp)); } return dp[target]; } }
Solution #4 iterative的⽅法,ToDo
No comments:
Post a Comment