2211. Count Collisions on a Road

發表於 | 分類於

problem

solution

option 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    int countCollisions(string directions) {
        int count = 0;
        int n = directions.size();
        // 撞到後會停在原地，後續有車子經過又會被撞
        // 將 RL SL 狀況下的L 改成 S狀態
        // 將 RL RS 狀態下的R 改成 S狀態
        for(int i=1;i<n;++i){
            char c = directions[i];
            if(c=='L'){
                if(directions[i-1] == 'R'){
                    // RL
                    count+=2;
                    directions[i] = 'S';
                    directions[i-1] = 'S';
                }
                else if(directions[i-1] =='S'){
                    // SL
                    count++;
                    directions[i] = 'S';
                }
            }
            else if(c=='S'){
                if(directions[i-1] == 'R'){
                    // RS
                    count++;
                    directions[i-1] = 'S';
                }
            }
        }
        
        // 在計算 有多少R 會撞到S
        int j=n-1;
        while(j>-1 && directions[j]=='R') j--;
        for(int i=0;i<=j;++i) count+=(directions[i] == 'R');
        
        return count;
    }
};

option 2

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int countCollisions(string directions) {
        int n = directions.size(), l = 0, r = n-1, count = 0;
        while(l<n && directions[l] == 'L') l++;
        while(r>-1 && directions[r] == 'R') r--;
        for(int i=l;i<=r;++i) count+=(directions[i]!='S')?1:0;
        return count;
    }
};

analysis

  • time complexity O(n)
  • space complexity O(1)