LeetCode 818. Race Car

原题链接在这里：https://leetcode.com/problems/race-car/

题目：

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.

题解：

Use BFS to find out shortest sequence.

Each step, there are 2 possibilities, either A or R. Maintain a set to store visited state.

If current position is alrady beyond 2 * target, it can't make shortest path.

Time Complexity: O(nlogn). n = target. totoally there are 2*n positions, each position could be visited 2*logn times at most. Since the speed could not be beyond logn.

Space: O(n).

AC Java:

 class Solution {

     public int racecar(int target) {

         if(target == 0){

             return 0;

         }

         int step = 0;

         LinkedList<int []> que = new LinkedList<>();

         que.add(new int[]{0, 1});

         int curCount = 1;

         int nextCount = 0;

         HashSet<String> visited = new HashSet<>();

         visited.add(0 + "," + 1);

         while(!que.isEmpty()){

             int [] cur = que.poll();

             curCount--;

             if(cur[0] == target){

                 return step;

             }

             int [] next1 = new int[]{cur[0]+cur[1], 2*cur[1]};

             int [] next2 = new int[]{cur[0], cur[1] > 0 ? -1 : 1};

             if(0<next1[0] && next1[0]<=target*2 && !visited.contains(next1[0] + "," + next1[1])){

                 que.add(next1);

                 visited.add(next1[0] + "," + next1[1]);

                 nextCount++;

             }

             if(!visited.contains(next2[0] + "," + next2[1])){

                 que.add(next2);

                 visited.add(next2[0] + "," + next2[1]);

                 nextCount++;

             }

             if(curCount == 0){

                 curCount = nextCount;

                 nextCount = 0;

                 step++;

             }

         }

         return -1;

     }

 }

巴特西

LeetCode 818. Race Car

最新文章

热门文章