统计道路上的碰撞次数

难度: Medium

在一条无限长的公路上有 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'

Submission

运行时间: 35 ms

内存: 16.5 MB

class Solution:
    def countCollisions(self, directions: str) -> int:
        n = len(directions)
        i, j = 0, n-1
        while i <= j:
            if directions[i] == 'L':
                i += 1
            else:
                break
        while i <= j:
            if directions[j] == 'R':
                j -= 1
            else:
                break
        s = directions[i:j+1]
        return len(s)-s.count('S')

Explain

这个题解的核心思路是通过预处理字符串来简化碰撞计算的过程。首先，从字符串的左端开始，跳过所有向左移动的车辆（'L'），因为它们不会与任何车辆发生碰撞。接着，从字符串的右端开始，跳过所有向右移动的车辆（'R'），因为它们也不会与任何车辆发生碰撞。经过这样的处理后，剩余的中间部分包含了所有可能的碰撞。在这个子字符串中，只有向左移动的车辆（'L'）和静止的车辆（'S'）会保持原位，而向右移动的车辆（'R'）会与它们发生碰撞。然后，对于这个处理后的子字符串，碰撞次数等于子字符串的长度减去其中'S'的数量。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def countCollisions(self, directions: str) -> int:
        n = len(directions) # 获取字符串长度
        i, j = 0, n-1 # 初始化两个指针i和j分别指向字符串的开始和结束位置
        while i <= j: # 跳过所有向左移动的车辆
            if directions[i] == 'L':
                i += 1
            else:
                break
        while i <= j: # 跳过所有向右移动的车辆
            if directions[j] == 'R':
                j -= 1
            else:
                break
        s = directions[i:j+1] # 截取可能发生碰撞的子字符串
        return len(s)-s.count('S') # 计算碰撞次数：子字符串的长度减去其中'S'的数量

Explore

在原题解中，跳过所有初始位置在字符串左端的向左移动的车辆（'L'）和初始位置在字符串右端的向右移动的车辆（'R'）是合理的，因为这些车辆不会与其他车辆发生碰撞。对于在字符串中间的向左移动的车辆（'L'），如果它们位于处理后的子字符串中，它们仍然会被计算在内，因此不会错过与后面的停车（'S'）或向右移动的车辆（'R'）的碰撞。因此，题解的方法不会漏掉这类碰撞情况。

题解中的方法确实考虑了车辆的初始位置。通过跳过所有不会导致碰撞的车辆，处理后的子字符串包含了所有可能发生碰撞的车辆，这些车辆在原始字符串中是相邻的。因此，若两辆车在处理后的子字符串中相邻，则它们在原始字符串中也是紧密相邻的，能够发生碰撞。这表示题解逻辑确实反映了车辆的实际相对位置和碰撞的可能性。

题解中的碰撞计算方法可能会低估实际的碰撞次数。确实，当两辆相反方向移动的车辆（'R'和'L'）相遇时，每辆车都会因碰撞而改变方向，这可以被视为两次碰撞。然而，题解中的方法仅统计这种情况为一次碰撞。因此，这种计算方法虽然简洁，但不完全准确地反映了所有类型的碰撞，尤其是在处理相反方向移动的车辆相遇的情况时。