网站建设计划书怎么写,十档行情免费软件,百度云虚拟主机做网站,新手做网站服务器用什么文章目录1 题目理解2 BFS3 dp3.1 基本情况3.2 递归方程分析3.2.1 先超过target再调头3.2.2 不超过target4 说明1 题目理解
先讲规则。一辆小汽车停在位置0#xff0c;并且方向朝向右侧#xff0c;并且速度为1。小汽车每次可以选择加速A#xff0c;那加速一次#xff0c;新…
文章目录1 题目理解2 BFS3 dp3.1 基本情况3.2 递归方程分析3.2.1 先超过target再调头3.2.2 不超过target4 说明1 题目理解
先讲规则。一辆小汽车停在位置0并且方向朝向右侧并且速度为1。小汽车每次可以选择加速A那加速一次新的位置原来位置速度并且新的速度速度*2。小汽车也可以选择掉头。掉头一次的话新的位置原来的位置并且新的速度如果原来速度0那就是-1否则的话是1。 输入int target。 输出小汽车到达位置target最少需要几次操作。 例子 Example 1: Input: target 3 Output: 2 Explanation: 最短的操作顺序 是 “AA”. 汽车位置变化为 0-1-3.
Example 2: Input: target 6 Output: 5 Explanation: 最短的操作顺序 是 “AAARA”. 汽车位置变化为 0-1-3-7-7-6.
题目分析思路来源于花花酱。
2 BFS
因为在每个位置上有两种操作。在每次操作后速度、位置会发生变化。一直变直到走到终点。所以可以按照BFS求解。遇到的第一个位置为target就是最短的操作。 这里有几个关键点。 关键点1如果相同的位置和速度已经加入过队列那就不需要再次计算。 关键点2如果在位置0小汽车朝向右侧一定比朝向左侧用的操作最少。这个可以用反证法证明。 关键点3小汽车向右走可以超过target但 不能超过2*target。否则操作数会更多。 当然这个方法是不能AC的。
class Solution {public int racecar(int target) {Queueint[] queue new LinkedListint[]();ListString filter new ArrayListString();queue.offer(new int[]{0,1});//pos speedfilter.add(0_1);filter.add(0_-1);int step 0;while(!queue.isEmpty()){int size queue.size();for(int i0;isize;i){int[] values queue.poll();int pos values[0];int speed values[1];//Aint newpos pos speed;if(newpos target){return step 1;}if(pos 2*target){queue.offer(new int[]{newpos,speed*2});filter.add(newpos_(speed*2));}//Rif(speed 0 ){speed -1;}else{speed 1;}String key pos_speed;if(!filter.contains(key)){queue.offer(new int[]{pos,speed});filter.add(key);}}step;}return -1;}
}通过这个方法我们知道在同一位置可能有两种状态速度向右、速度向左。这提示我们在做动态规划的时候可能需要维护二维数组。
3 dp
如果target7我们发现
操作位置速度起始01第1次A12第2次A34第3次A78
3.1 基本情况
如果target2n−1target 2^n-1target2n−1那么到达target的最少操作数是n。是dp中的基本情况。 3.2 递归方程分析
如果不是则可能要考虑两种情况。第一种情况是先走过5达到7因为7的最少操作数可以直接求解是基本情况。然后再调头需要走2个位置达到5。如果我们提前计算好了走距离2的最少操作数那就可以求解了。第二种情况是可能走到j1234然后再走剩下的距离。操作数之和就是达到5的操作数。两种情况求最小值就是答案。下面分别讨论。
令dp[i][0]表示从0达到位置i并且速度朝右的最小操作数。dp[i][1]表示从0达到位置i并且速度朝左的最小操作数。
3.2.1 先超过target再调头
例如上面到达7再返回达到5的时候可能速度方向朝左也可能朝右。 dp[7][0]3dp[7][1]4。 达到7调头这时候操作数是4。 继续走2个距离这时候的操作数是dp[2][0]这个时候的方向是朝左的。也就是说dp[5][1] 4 dp[2][0]。为什么是dp[2][0]而不是dp[2][1]呢dp[2][0]表示从0到达2并且方向向右又因为起始位置速度的方向也向右所以可以认为走过2个位置并且方向和起始方向相同的最少操作数是dp[2][0]。当到达7以后调头方向向左了走过2个距离并且速度方向一致那操作数就是dp[2][0]。 当然dp[5][1]也可能是通过dp[2][1]获得这个时候需要再加一个转向操作所以dp[5][1]4dp[2][1]1。两者取最小值。dp[5][1] 4 min(dp[2][0],dp[2][1]1)。 同理可以推出dpp[5][0] 4 min(dp[2][1],dp[2][0]1)。
推出一般情况就是 l2n−1−targetl2^n-1-targetl2n−1−target dp[target][0]n1min(dp[l][1],dp[l][0]1)dp[target][0] n 1 min(dp[l][1],dp[l][0]1)dp[target][0]n1min(dp[l][1],dp[l][0]1) dp[target][1]n1min(dp[l][0],dp[l][1]1)dp[target][1] n 1 min(dp[l][0],dp[l][1]1)dp[target][1]n1min(dp[l][0],dp[l][1]1)
3.2.2 不超过target
再参考上图target5如果不超过5。 那我们可以先走距离1到达1以后再走距离4。到达5。 我们也可以先走距离2到达2以后再走距离3。到达5。 … 我们也可以先走距离4到达4以后再走距离1。到达5。
我们先分析先走距离1到达1以后再走距离4。到达5的情况。达到1如果方向向右则需要先 调头再调头然后走距离4。那么dp[5][0] dp[1][0]2 dp[4][0]。达到1如果方向向左则需要先调头然后走距离4。那么dp[5][0] dp[1][1]1 dp[4][0]。最终dp[5][0] min(dp[1][1]1,dp[1][0]2) dp[4][0]。 同理dp[5][1] min(dp[1][1]1,dp[1][0]2) dp[4][1]。
最终代码
class Solution {public int racecar(int target) {int[][] dp new int[target1][2];dp[0][0] 0;dp[0][1] 1;for(int i1;itarget;i){int n (int)Math.ceil(Math.log(i1)/Math.log(2));if((1n) i1){dp[i][0] n;dp[i][1] n1;}else{int left ((1n)-1 - i);dp[i][0] n1Math.min(dp[left][1],dp[left][0]1);dp[i][1] n1Math.min(dp[left][0],dp[left][1]1);for(int j 1;ji;j){int min Math.min(dp[j][0]2,dp[j][1]1);dp[i][0] Math.min(dp[i][0], mindp[i-j][0]);dp[i][1] Math.min(dp[i][1], mindp[i-j][1]);}}}return Math.min(dp[target][0],dp[target][1]);}
}4 说明
看到题目还是应该拿着具体数值分析一下。在某一特定情况下是怎么到达目的地的。
