Leetcode 2211 - Count Collisions on a Road

題目

Problem#

一條路上有 $n$ 台車，每台車可以有三種方向: S, L, R 分別是靜止、左、右。今天每台車都朝其方向駛去，當相撞時車子留在原地，問你給定一個 directions 序列，有幾台車會撞車。

想法#

可以觀察到 RS, SL, RL 這三種狀況一定會撞到，但如果序列是 RRL 則最一開始的 R 不會算到，所以必須要記錄 R 的數量，當遇到前面三種撞車的狀況時，就將目前算到 `R 的數量也加到答案中(那些 R 的車也會撞到)

• 時間複雜度: $\mathcal{O}(n)$
• 空間複雜度: $\mathcal{O}(1)$

AC Code#

Copy

/*
 * Leetcode Medium 2211. Count Collisions on a Road
 * author: roy4801
 * AC(C++)
 */
#include <bits/stdc++.h>
using namespace std;
#include "helper.h"
 
typedef pair<int, int> P;
typedef long long int LL;
#define PB push_back
#define MP make_pair
#define X first
#define Y second
 
class Solution
{
public:
    int countCollisions(string d)
    {
        int ans = 0, r = 0;
        
        for(int i = 1; i <= d.size()-1; i++)
        {
            // RS or SL
            if(d[i-1] == 'R' && d[i] == 'S' ||
               d[i-1] == 'S' && d[i] == 'L')
            {
                ans++;
                ans += r;
                r = 0;
                d[i-1] = d[i] = 'S';
            }
            // RL
            else if(d[i-1] == 'R' && d[i] == 'L')
            {
                ans += 2;
                ans += r;
                r = 0;
                d[i-1] = d[i] = 'S';
            }
            //  count R
            // e.g. RRL
            //      ^
            else if(d[i-1] == 'R')
                r++;
        }
        
        return ans;
    }
};
 
int main()
{
    // skip
}

view raw 2211.cpp delivered with ❤ by emgithub

賞析#

• 因為我們只在乎撞車的數量，所以只要找最左邊的 R 和最右邊的 L，在這之間的所有 L 和 R 最後都一定會相撞
  • https://leetcode.com/problems/count-collisions-on-a-road/discuss/1865669/Hold-my-beer-TC-%3A-O(N)-SC-O(1)

心得#

賽中沒想到要把撞到的車改成 S，然後計算沒相撞時 R 的數量，真的要多寫 greedy 的題目