image.png

要點(diǎn)：
(1)關(guān)鍵數(shù)據(jù)結(jié)構(gòu)：hash-unordered_map，堆-priority_queue
(2) string 排序
我們一個字符串str，和一個整數(shù)k，讓我們對字符串str重新排序，使得其中相同的字符之間的距離不小于k。哈希表，堆。
(1)一個哈希表來建立字符和其出現(xiàn)次數(shù)之間的映射:
unordered_map<char, int>
(2)然后需要一個堆來保存這每一堆映射，按照出現(xiàn)次數(shù)來排序:
priority_queue<pair<int, char>
(3) 然后如果堆不為空我們就開始循環(huán)，我們找出k和str長度之間的較小值，
(4) 然后從0遍歷到這個較小值，對于每個遍歷到的值，如果此時堆為空了，說明此位置沒法填入字符了，返回空字符串，否則我們從堆頂取出一對映射，
(5) 然后把字母加入結(jié)果res中，此時映射的個數(shù)減1，如果減1后的個數(shù)仍大于0，則我們將此映射加入臨時集合v中，同時str的個數(shù)len減1，遍歷完一次，我們把臨時集合中的映射對由加入堆中.
參見代碼如下：

class Solution {
public:
    string rearrangeString(string str, int k) {
        if (k == 0) return str;
        string res;
        int len = (int)str.size();
        unordered_map<char, int> m;
        priority_queue<pair<int, char>> q;
        for (auto a : str) ++m[a];
        for (auto it = m.begin(); it != m.end(); ++it) {
            q.push({it->second, it->first});
        }
        while (!q.empty()) {
            vector<pair<int, int>> v;
            int cnt = min(k, len);
            for (int i = 0; i < cnt; ++i) {
                if (q.empty()) return "";
                auto t = q.top(); q.pop();
                res.push_back(t.second);
                if (--t.first > 0) v.push_back(t);
                --len;
            }
            for (auto a : v) q.push(a);
        }
        return res;
    }
};

字符串排序sort(string)

image.png

根據(jù)題意進(jìn)行模擬，對每個字符串進(jìn)行排序作為 key，從而實(shí)現(xiàn)相同的「變位詞」對應(yīng)同一個 key，使用哈希表進(jìn)行統(tǒng)計(jì)即可。

要點(diǎn)：
關(guān)鍵數(shù)據(jù)結(jié)構(gòu)：string, map
關(guān)鍵操作：
（1）string 排序，可以用sort(string.begin(), string.end() );
（2）hash map操作：以排序后的string 作為key, 排序前的string添加到vector<string>的數(shù)組中value;
（3）for 遍歷map；

    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string,vector<string>> mp;
        for(auto i : strs)
        {
          string s=i;
          sort(s.begin(),s.end());
          mp[s].push_back(i);
        }
        vector<vector<string>> res;
        for(auto i:mp)
            res.push_back(i.second);
        return res;
    }