赛车

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.

Given a target position target, return 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.

 

Constraints:

• 1 <= target <= 104

这个题解使用BFS（广度优先搜索）的方法来解决问题。具体思路如下： 1. 使用队列 queue 存储当前位置、当前速度以及下一步是否执行 'A' 操作的状态。 2. 使用 visited 集合记录已访问过的状态，避免重复访问。 3. 从初始状态 (0, 1, True) 开始进行BFS搜索。 4. 在每一轮搜索中，取出队列中的所有状态，并对每个状态进行以下操作： - 如果当前状态已经访问过，则跳过。 - 如果当前位置等于目标位置 target，则返回当前的搜索步数 k。 - 如果下一步是 'A' 操作，则更新当前位置和速度。 - 如果下一步是 'R' 操作，则根据当前速度的正负来更新速度。 - 根据更新后的速度和位置，判断是否会超过目标位置： - 如果不会超过，则将新状态加入队列，并标记下一步为 'A'。 - 如果会超过，则将两个新状态都加入队列，分别标记下一步为 'A' 和 'R'。 5. 搜索步数 k 不断递增，直到找到目标位置或队列为空。 6. 返回最终的搜索步数 k。

O(target)

O(target)