JAVA程序设计：赛车（LeetCode：818）

你的赛车起始停留在位置 0&＃xff0c;速度为 &＃43;1&＃xff0c;正行驶在一个无限长的数轴上。&＃xff08;车也可以向负数方向行驶。&＃xff09;

你的车会根据一系列由 A&＃xff08;加速&＃xff09;和 R&＃xff08;倒车&＃xff09;组成的指令进行自动驾驶 。

当车得到指令 "A" 时, 将会做出以下操作&＃xff1a; position &＃43;&＃61; speed, speed *&＃61; 2。

当车得到指令 "R" 时, 将会做出以下操作&＃xff1a;如果当前速度是正数&＃xff0c;则将车速调整为 speed &＃61; -1 &＃xff1b;否则将车速调整为 speed &＃61; 1。  (当前所处位置不变。)

例如&＃xff0c;当得到一系列指令 "AAR" 后, 你的车将会走过位置 0->1->3->3&＃xff0c;并且速度变化为 1->2->4->-1。

现在给定一个目标位置&＃xff0c;请给出能够到达目标位置的最短指令列表的长度。

示例 1:
输入: 
target &＃61; 3
输出: 2
解释: 
最短指令列表为 "AA"
位置变化为 0->1->3
示例 2:
输入: 
target &＃61; 6
输出: 5
解释: 
最短指令列表为 "AAARA"
位置变化为 0->1->3->7->7->6
说明:

1 <&＃61; target&＃xff08;目标位置&＃xff09; <&＃61; 10000。

官方题解中的方法二和我的方法类似&＃xff0c;这里放出另一种方法&＃xff08;最短路&＃xff09;的代码。

class Solution {class node{int step,target;public node(int step,int target) {this.step&＃61;step;this.target&＃61;target;}}public int racecar(int target) {int K&＃61;33-Integer.numberOfLeadingZeros(target-1);int barrier&＃61;1< q&＃61;new PriorityQueue((a,b)->a.step-b.step);q.add(new node(0,target));while(!q.isEmpty()) {node now&＃61;q.poll();int steps&＃61;now.step;int tar1&＃61;now.target;if(dis[Math.floorMod(tar1, dis.length)]>steps)continue;for(int k&＃61;0;k<&＃61;K;k&＃43;&＃43;) {int walk&＃61;(1<}

方法二&＃xff1a;动态规划

class Solution {public int racecar(int target) {int[] dp&＃61;new int[target&＃43;3];Arrays.fill(dp, Integer.MAX_VALUE);dp[0]&＃61;0; dp[1]&＃61;1; dp[2]&＃61;4;for(int t&＃61;3;t<&＃61;target;t&＃43;&＃43;) {//从最高位不为0的位算起&＃xff0c;二进制表示的位数int k&＃61;32-Integer.numberOfLeadingZeros(t);if(t&＃61;&＃61;(1<}