力扣818.赛车 BFS

 818. 赛车

你的赛车可以从位置 ​

​0​

​​ 开始，并且速度为 ​

​+1​

​​ ，在一条无限长的数轴上行驶。赛车也可以向负方向行驶。赛车可以按照由加速指令 ​

​'A'​

​​ 和倒车指令 ​

​'R'​

​ 组成的指令序列自动行驶。

• 当收到指令​

  ​'A'​

  ​ 时，赛车这样行驶：

• ​

  ​position += speed​

  ​
• ​

  ​speed *= 2​

  ​

• 当收到指令​

  ​'R'​

  ​ 时，赛车这样行驶：

• 如果速度为正数，那么​

  ​speed = -1​

  ​
• 否则​

  ​speed = 1​

  ​

例如，在执行指令 ​

​"AAR"​

​​ 后，赛车位置变化为 ​

​0 --> 1 --> 3 --> 3​

​​ ，速度变化为 ​

​1 --> 2 --> 4 --> -1​

​ 。

给你一个目标位置 ​

​target​

​ ，返回能到达目标位置的最短指令序列的长度。

示例 1：

输入：target = 3

输出：2

解释：

最短指令序列是 "AA" 。

位置变化 0 --> 1 --> 3 。

示例 2：

输入：target = 6

输出：5

解释：

最短指令序列是 "AAARA" 。

位置变化 0 --> 1 --> 3 --> 7 --> 7 --> 6 。

提示：

• ​

  ​1 <= target <= 10^4​

  ​

来源：力扣（LeetCode）

链接：https://leetcode.cn/problems/race-car

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

做题结果

成功，最短步数 BFS 

疑惑点

为什么进入负数区域不会有更优解？

因为指令具有一定的对称性。比如：

位置：0->0->-1->-3->-3->-2->0

速度：1->-1->-2->-4->1->2->4

所以进入负数区再回来正数区等于没走，不能减少步数

启发来自下面这篇题解，这个作者写的非常专业：​​力扣

https://leetcode.cn/problems/race-car/solution/onfu-za-du-de-dfsyi-ji-yi-xie-xing-zhi-z-1i47/​​

 为什么超过 pow(2,k+1) 再回头走不会有更优解呢？（k代表以2为底target的对数）

1. 对于所有落在 2^t-1 位置来说，已经有了一个最短步数解。因为它一直加速已经是最快速度跑到此位置了，没有回头。

2. 有回头的情况。走了一定的步数后，落在某个位置，此时回头，假设回头的某一步，刚好踩到目标位置target。那么假设这个超出原位置 target 的距离是 S, 那么回头走到该位置最少需要 log(S) 步。对于位置A,B,B在A的后面，A=target+AS B=target+BS,那么这两者回头需要的步数分别为 log(AS)和log(BS)，由于 B>A,且 target=target,所以 BS>AS,取整数 log(BS)>=log(AS)，所以从后面的位置回头不会有更优解了，后面回头必然耗费更多步数。

反向走log步的结论，来自这篇：

【Leetcode】818. Race Car 818. 赛车_MYSDB的博客

方法：BFS

基本思路是保持每个位置的速度不重复

class Solution {
    public int racecar(int target) {
        Map<Integer,Set<Integer>> posStep = new HashMap<>();//位置，速度
        posStep.put(0,new HashSet<>());
        posStep.get(0).add(1);
        Queue<int[]> queue = new LinkedList<>();//位置，速度
        int time = (int)(Math.log(target)/Math.log(2));
        int max = (int)Math.pow(2,time+1);
        int step = 0;
        queue.offer(new int[]{0,1});
        while (!queue.isEmpty()){
            ++step;
            int size = queue.size();
            for(int a = 0; a < size; a++){
                int[] curr = queue.poll();
                //加速
                if(curr[0]+curr[1]<=max && (!posStep.containsKey(curr[0]+curr[1]) || !posStep.get(curr[0]+curr[1]).contains(curr[1]*2))){     
                      if(curr[0]+curr[1]==target)
                         return step;
                    queue.offer(new int[]{curr[0]+curr[1],curr[1]*2});
                    posStep.putIfAbsent(curr[0]+curr[1],new HashSet<>());
                    posStep.get(curr[0]+curr[1]).add(curr[1]*2);
                }
                //变向-反向
                if(curr[1]>0){
                    if(!posStep.containsKey(curr[0]) || !posStep.get(curr[0]).contains(-1)){
                        queue.offer(new int[]{curr[0],-1});
                        posStep.putIfAbsent(curr[0],new HashSet<>());
                        posStep.get(curr[0]).add(-1);
                    }

                }else{
                //变向-正向
                    if(!posStep.containsKey(curr[0]) || !posStep.get(curr[0]).contains(1)){
                        queue.offer(new int[]{curr[0],1});
                        posStep.putIfAbsent(curr[0],new HashSet<>());
                        posStep.get(curr[0]).add(1);
                    }

                }
            }

        }
        return -1;
    }
}