LeetCode 2211. 统计道路上的碰撞次数

文章目录

• • 1. 题目
  • 2. 解题

1. 题目

在一条无限长的公路上有 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^5 directions[i] 的值为 'L'、'R' 或 'S'

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-collisions-on-a-road
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

• 首先找到左边不是 L 的边界，右边不是 R 的边界
• 然后计算这两个区间中间的 L 和 R 的数量，就是碰撞次数

class Solution { public:int countCollisions(string directions) {int ans = 0, n = directions.size();int i = 0, j = n-1;while(i < n && directions[i]=='L')i++;while(j>=0 && directions[j]=='R')j--;if(j <= i) return 0;for(int idx = i; idx <= j; ++idx)if(directions[idx] != 'S')ans++;return ans;} };

32 ms 16 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

总结

以上是生活随笔为你收集整理的LeetCode 2211. 统计道路上的碰撞次数的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。