力扣2211.统计道路上的碰撞次数

力扣2211.统计道路上的碰撞次数

栈模拟

• 预处理右边剩余的车辆信息

  • 分类讨论

•   class Solution {
    public:
        int countCollisions(string directions) {
            unordered_map<char,int> cnt;
            for(char c:directions)
                cnt[c] ++;
            vector<char> st;
            int res=0;
            for(char c:directions)
            {
                cnt[c] --;
                if(c == 'R')
                    res += cnt['L'] > 0 || cnt['S'] > 0;
                else if(c == 'L')
                {
                    while(st.size() && st.back() == c)
                        st.pop_back();
                    if(st.size() && st.back() != c) res ++;
                }
                st.push_back(c);
            }
            return res;
        }
    };
  

贪心

• 去掉前缀L和后缀R

  • 剩余的非S的车必然使res++

•   class Solution {
    public:
        int countCollisions(string directions) {
            for(int i=0;i<directions.size();i++)
            {
                if(directions[i--] == 'L')
                    directions.erase(0,1);
                else break;
            }
            for(int i=directions.size() - 1;i>=0;i--)
            {
                if(directions[i] == 'R')
                    directions.erase(directions.size()-1,1);
                else break;
            }
            return directions.size() - count(directions.begin(),directions.end(),'S');
        }
    };