763. 划分字母区间(滑动窗口,贪心)

763. 划分字母区间(滑动窗口,贪心)

 分析:运用滑动窗口的思想,开needs哈希表和窗口哈希表,由于要划分尽可能多的片段,那么只要当前窗口中全部元素都满足了needs的数量(同一字母只在一个片段中),就立即断开,保证尽可能多的数量

class Solution {
public:
    vector<int> partitionLabels(string s) {
       unordered_map<char,int> needs;//需求
       unordered_map<char,int> mp;  //窗口
       int valid=0; //满足条件的数量
       int j=0,i=0;
       for(char c:s)
        needs[c]++;
        vector<int> q;
        //j表示片段左端点,i表示片段右端点
        for(int i=0,j=0;i<s.size();i++)
        {
            char c=s[i];
            mp[c]++;
            if(mp[c]==needs[c]) //同一字母在一个片段
                valid++;
            if(valid==mp.size())//窗口中所有元素都满足同一字母再一个片段
            {
                q.push_back(i-j+1);
                valid=0;    //清空
                mp.clear();
                j=i+1;        
            }
        }
    return q;
    }
};

上一篇:unordered_map赋值以及常用成员函数


下一篇:C++刷leetcode几点注意事项