Rust）

2022年3月20日 12:10

去掉前缀向左开、后缀向右开的车，剩下非停止（$\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)$。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

阅读视图

复杂度分析

分类题单