赛车

标签: 动态规划

难度: Hard

你的赛车可以从位置 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 <= 104

Submission

运行时间: 77 ms

内存: 0.0 MB

class Solution:
    def racecar(self, target: int) -> int:
        queue = collections.deque([(0, 1, True)])
        visited = set()
        k = 0
        
        while queue:
            size = len(queue)
            
            for _ in range(size):
                curr_pos, curr_spead, if_A = queue.popleft()
                # old_speed = curr_speed 
                # old_pos = curr_pos
                if (curr_pos, curr_spead, if_A) in visited:
                    continue
                
                visited.add((curr_pos, curr_spead, if_A))
                if curr_pos == target:
                    return k
                
                if if_A:
                    curr_pos += curr_spead
                    curr_spead *= 2
                else:
                    if curr_spead > 0:
                        curr_spead = -1
                    else:
                        curr_spead = 1
                
                if ((curr_spead > 0 and curr_pos + curr_spead < target)
                   or (curr_spead < 0 and curr_pos + curr_spead > target)):
                    queue.append((curr_pos, curr_spead, True))
                else:
                    queue.append((curr_pos, curr_spead, True))
                    queue.append((curr_pos, curr_spead, False))
            
            k += 1
        
        return k

Explain

这个题解使用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)

class Solution:
    def racecar(self, target: int) -> int:
        queue = collections.deque([(0, 1, True)])  # 初始状态为位置0，速度1，下一步操作为 'A'
        visited = set()  # 记录已访问过的状态
        k = 0  # 搜索步数
        
        while queue:
            size = len(queue)
            
            for _ in range(size):
                curr_pos, curr_spead, if_A = queue.popleft()
                if (curr_pos, curr_spead, if_A) in visited:  # 如果当前状态已访问过，则跳过
                    continue
                
                visited.add((curr_pos, curr_spead, if_A))  # 将当前状态标记为已访问
                if curr_pos == target:  # 如果到达目标位置，则返回搜索步数
                    return k
                
                if if_A:  # 如果下一步操作为 'A'
                    curr_pos += curr_spead  # 更新位置
                    curr_spead *= 2  # 更新速度
                else:  # 如果下一步操作为 'R'
                    if curr_spead > 0:  # 如果当前速度为正，则变为-1
                        curr_spead = -1
                    else:  # 如果当前速度为负，则变为1
                        curr_spead = 1
                
                if ((curr_spead > 0 and curr_pos + curr_spead < target)  # 如果速度为正且下一步不会超过目标位置
                   or (curr_spead < 0 and curr_pos + curr_spead > target)):  # 或速度为负且下一步不会超过目标位置
                    queue.append((curr_pos, curr_spead, True))  # 将新状态加入队列，下一步操作为 'A'
                else:
                    queue.append((curr_pos, curr_spead, True))  # 将新状态加入队列，下一步操作为 'A'
                    queue.append((curr_pos, curr_spead, False))  # 将新状态加入队列，下一步操作为 'R'
            
            k += 1  # 搜索步数加1
        
        return k

Explore

在赛车问题中，执行操作 'R'（反向）的目的是改变赛车的方向，准备下一次加速或减速。根据题目的规则，每次执行 'R' 操作只影响速度的方向，而不直接影响位置。这种设计模拟了真实世界中汽车在改变方向时，虽然方向改变了但位置仍保持不变，只有在随后的加速或减速操作中，位置才会改变。因此，在模拟这个过程时，执行 'R' 操作后只更新速度，不更新位置，以符合题目的逻辑和现实的行为模式。

在使用BFS处理赛车问题时，确实存在位置和速度快速增长的问题，这可能导致内存使用量增加。为了控制资源使用和提高算法的效率，主要可以采用以下策略：1. 使用 visited 集合来存储已经访问过的状态（位置和速度），避免重复搜索相同状态。2. 限制搜索范围，例如，在状态转移时检查新状态是否有意义（如位置和目标距离过远或速度过大时可剪枝）。3. 在某些情况下，可以通过设置适当的阈值来限制速度或位置的最大值，避免无效的搜索。这些方法可以帮助减少不必要的内存消耗和提升搜索效率。

使用 visited 集合来记录已访问状态是防止赛车问题中发生重复搜索的常用方法。然而，这种方法主要防止同一状态的精确重复访问。在某些复杂的情况下，尽管不同的搜索路径可能达到相同的状态，但可能存在由于不同操作序列而产生的细微变化，这些变化可能未能通过简单的 visited 检查被识别出来。因此，虽然 visited 集合在大多数情况下能有效减少重复搜索，但它不能完全排除所有重复搜索的可能性，特别是在存在多路径到达同一状态的情况下。为了进一步优化，可以考虑使用更复杂的状态管理策略，如记录到达每个状态的最小步数，进行更细致的状态比较。