文章目錄

• • 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. 统计道路上的碰撞次数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。