去掉前缀向左开、后缀向右开的车，剩下非停止（$\ne \texttt{S}$）的车必然会碰撞。
class Solution:
def countCollisions(self, s: str) -> int:
s = s.lstrip('L') # 前缀向左的车不会发生碰撞
s = s.rstrip('R') # 后缀向右的车不会发生碰撞
return len(s) - s.count('S') # 剩下非停止的车必然会碰撞
class Solution {
public int countCollisions(String s) {
int n = s.length();
// 前缀向左的车不会发生碰撞
int l = 0;
while (l < n && s.charAt(l) == 'L') {
l++;
}
// 后缀向右的车不会发生碰撞
int r = n;
while (r > l && s.charAt(r - 1) == 'R') {
r--;
}
// 剩下非停止的车必然会碰撞
int cnt = 0;
for (int i = l; i < r; i++) {
if (s.charAt(i) != 'S') {
cnt++;
}
}
return cnt;
}
}
class Solution {
public int countCollisions(String s) {
s = s.replaceAll("^L+", ""); // 前缀向左的车不会发生碰撞
s = new StringBuilder(s).reverse().toString().replaceAll("^R+", ""); // 后缀向右的车不会发生碰撞
return (int) s.chars().filter(c -> c != 'S').count(); // 剩下非停止的车必然会碰撞
}
}
class Solution {
public:
int countCollisions(string s) {
int n = s.size();
// 前缀向左的车不会发生碰撞
int l = 0;
while (l < n && s[l] == 'L') {
l++;
}
// 后缀向右的车不会发生碰撞
int r = n;
while (r > l && s[r - 1] == 'R') {
r--;
}
// 剩下非停止的车必然会碰撞
int cnt = 0;
for (int i = l; i < r; i++) {
cnt += s[i] != 'S';
}
return cnt;
}
};
class Solution {
public:
int countCollisions(string s) {
s.erase(s.begin(), ranges::find_if(s, [](auto c) { return c != 'L'; })); // 前缀向左的车不会发生碰撞
s.erase(find_if(s.rbegin(), s.rend(), [](auto c) { return c != 'R'; }).base(), s.end()); // 后缀向右的车不会发生碰撞
return s.length() - ranges::count(s, 'S'); // 剩下非停止的车必然会碰撞
}
};
int countCollisions(char* s) {
// 前缀向左的车不会发生碰撞
int l = 0;
while (s[l] == 'L') {
l++;
}
// 后缀向右的车不会发生碰撞
int r = strlen(s);
while (r > l && s[r - 1] == 'R') {
r--;
}
// 剩下非停止的车必然会碰撞
int cnt = 0;
for (int i = l; i < r; i++) {
cnt += s[i] != 'S';
}
return cnt;
}
func countCollisions(s string) int {
s = strings.TrimLeft(s, "L") // 前缀向左的车不会发生碰撞
s = strings.TrimRight(s, "R") // 后缀向右的车不会发生碰撞
return len(s) - strings.Count(s, "S") // 剩下非停止的车必然会碰撞
}
var countCollisions = function(s) {
const n = s.length;
// 前缀向左的车不会发生碰撞
let l = 0;
while (l < n && s[l] === 'L') {
l++;
}
// 后缀向右的车不会发生碰撞
let r = n;
while (r > l && s[r - 1] === 'R') {
r--;
}
// 剩下非停止的车必然会碰撞
let cnt = 0;
for (let i = l; i < r; i++) {
if (s[i] !== 'S') {
cnt++;
}
}
return cnt;
};
impl Solution {
pub fn count_collisions(s: String) -> i32 {
let s = s.as_bytes();
let n = s.len();
// 前缀向左的车不会发生碰撞
let mut l = 0;
while l < n && s[l] == b'L' {
l += 1;
}
// 后缀向右的车不会发生碰撞
let mut r = n;
while r > l && s[r - 1] == b'R' {
r -= 1;
}
// 剩下非停止的车必然会碰撞
s[l..r].iter().filter(|&&c| c != b'S').count() as _
}
}
复杂度分析
- 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $s$ 的长度。
- 空间复杂度：$\mathcal{O}(n)$ 或 $\mathcal{O}(1)$。
分类题单
如何科学刷题？
- 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
- 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
- 单调栈（基础/矩形面积/贡献法/最小字典序）
- 网格图（DFS/BFS/综合应用）
- 位运算（基础/性质/拆位/试填/恒等式/思维）
- 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
- 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
- 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
- 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
- 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
- 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
- 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）
我的题解精选（已分类）
欢迎关注 B站@灵茶山艾府
登录
