【数据结构-邻项消除】力扣2211. 统计道路上的碰撞次数

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

贪心思想

class Solution {
public:
    int countCollisions(string s) {
        int l = 0, r = s.size() - 1;
        while(l <= r && s[l] == 'L') ++l;
        while(l <= r && s[r] == 'R') --r;
        int res = 0; 
        for(int i = l; i <= r; ++i) if(s[i] == 'L' || s[i] == 'R') ++res;
        return res;
    }
};

我们采用贪心的思想，实际上R和L相撞，也就是两个车停下，碰撞+2，R或L和S相撞，也就是一个车停下，碰撞+1。所以也就是，除了开头为L和结尾为R的不会影响结果的车，其他L和R的车的数量一定会碰撞并且停下，那么碰撞数量就是这些L和R的车的总和。我们在代码开头，用两个while将指针跳过不影响结果的元素，然后统计L和R的数量，最终结果就是碰撞数。