How do I approach the Count Collisions on a Road problem?

Start by simulating car movements using a stack-based approach. Track the cars' directions and handle collisions efficiently by considering each car's interaction with others.

What is the pattern used in Count Collisions on a Road?

The problem uses stack-based state management to track car movements and calculate collisions. It involves simulating car interactions based on their directions.

Can a car stay stationary and still cause a collision?

Yes, a stationary car can collide with a moving car that passes by. The stationary car itself does not move, but the moving cars affect the collision count.

How should I handle edge cases like all cars moving in the same direction?

If all cars are moving in the same direction, no collisions will occur. You should check for this case early and return 0 as the result.

How does GhostInterview help me solve this problem?

GhostInterview helps you break down the problem into manageable parts, ensuring you understand how to simulate the car movements and handle collisions using a stack-based approach.

#2211

Medium

auto_awesome栈·状态

LeetCode 题解工作台

统计道路上的碰撞次数

在一条无限长的公路上有 n 辆汽车正在行驶。汽车按从左到右的顺序按从 0 到 n - 1 编号，每辆车都在一个独特的位置。给你一个下标从 0 开始的字符串 directions ，长度为 n 。 directions[i] 可以是 'L' 、 'R' 或 'S' 分别表示第 i 辆车是向左 …

字符串栈模拟

题目描述

在一条无限长的公路上有 n 辆汽车正在行驶。汽车按从左到右的顺序按从 0 到 n - 1 编号，每辆车都在一个 独特的 位置。

给你一个下标从 0 开始的字符串 directions ，长度为 n 。directions[i] 可以是 'L'、'R' 或 'S' 分别表示第 i 辆车是向左、向右或者停留在当前位置。每辆车移动时 速度相同 。

碰撞次数可以按下述方式计算：

当两辆移动方向相反的车相撞时，碰撞次数加 2 。
当一辆移动的车和一辆静止的车相撞时，碰撞次数加 1 。

碰撞发生后，涉及的车辆将无法继续移动并停留在碰撞位置。除此之外，汽车不能改变它们的状态或移动方向。

返回在这条道路上发生的 碰撞总次数 。

示例 1：

输入：directions = "RLRSLL"
输出：5
解释：
将会在道路上发生的碰撞列出如下：
- 车 0 和车 1 会互相碰撞。由于它们按相反方向移动，碰撞数量变为 0 + 2 = 2 。
- 车 2 和车 3 会互相碰撞。由于 3 是静止的，碰撞数量变为 2 + 1 = 3 。
- 车 3 和车 4 会互相碰撞。由于 3 是静止的，碰撞数量变为 3 + 1 = 4 。
- 车 4 和车 5 会互相碰撞。在车 4 和车 3 碰撞之后，车 4 会待在碰撞位置，接着和车 5 碰撞。碰撞数量变为 4 + 1 = 5 。
因此，将会在道路上发生的碰撞总次数是 5 。

示例 2：

输入：directions = "LLRR"
输出：0
解释：
不存在会发生碰撞的车辆。因此，将会在道路上发生的碰撞总次数是 0 。

提示：

1 <= directions.length <= 10⁵
directions[i] 的值为 'L'、'R' 或 'S'

lightbulb

解题思路

方法一：脑筋急转弯

根据题意，当两辆移动方向相反的车相撞时，碰撞次数加 $2$ ，即两辆车被撞停，答案加 $2$ ；当一辆移动的车和一辆静止的车相撞时，碰撞次数加 $1$ ，即一辆车被撞停，答案加 $1$ 。

而显然前缀的 $\textit{L}$ 和后缀的 $\textit{R}$ 是不会发生碰撞的，所以我们只需要统计中间不等于 $\textit{S}$ 的字符个数即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 或 $O(1)$ 。其中 $n$ 是字符串 $\textit{directions}$ 的长度。

1

2

3

4

5

class Solution:
    def countCollisions(self, directions: str) -> int:
        s = directions.lstrip("L").rstrip("R")
        return len(s) - s.count("S")

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Tests understanding of stack-based state management in simulating real-world interactions.
question_mark
Evaluates the candidate's ability to manage multiple car states (moving left, right, stationary).
question_mark
Assesses the candidate's approach to handling edge cases, such as all cars moving in the same direction or all cars stationary.

warning

常见陷阱

外企场景

error
Misunderstanding when collisions happen—confusing collisions between stationary cars and moving cars.
error
Overcomplicating the simulation without efficiently managing the cars' states with a stack.
error
Not accounting for edge cases like cars moving in the same direction or all cars being stationary.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider a scenario where no cars are moving; how does this affect the collision count?
arrow_right_alt
What happens when all cars move in the same direction? How would you adjust the algorithm?
arrow_right_alt
Extend the problem to track additional states, such as car speeds or varying collision impacts.

help

常见问题

外企场景

继续练习

#2296 设计一个文本编辑器 #2390 从字符串中移除星号 #1910 删除一个字符串中所有出现的给定子字符串