力扣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');
        }
    };
  

原文地址：https://blog.csdn.net/Pisasama/article/details/140385199

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！