剑指offer专项突击版第11天

剑指 Offer II 033. 变位词组

排序做法

class Solution {
    
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
    
        unordered_map<string, vector<string>> mp;
        for (string& str: strs) {
    
            string key = str;
            sort(key.begin(), key.end());
            mp[key].emplace_back(str);
        }
        vector<vector<string>> ans;
        for (auto it = mp.begin(); it != mp.end(); ++it) {
    
            ans.emplace_back(it->second);
        }
        return ans;
    }
};

计数写法，这里主要优化是：理论上unordered_map就行，但是键应该是字符出现次数的数组，然后vector是变长的，unordered_map没有array对应的哈希函数，所以需要自己定义。
剩下的操作就跟排序做法大同小异了。

class Solution {
    
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
    
        // 自定义对 array<int, 26> 类型的哈希函数
        auto arrayHash = [fn = hash<int>{
    }] (const array<int, 26>& arr) -> size_t {
    
            return accumulate(arr.begin(), arr.end(), 0u, [&](size_t acc, int num) {
    
                return (acc << 1) ^ fn(num);
            });
        };

        unordered_map<array<int, 26>, vector<string>, decltype(arrayHash)> mp(0, arrayHash);
        for (string& str: strs) {
    
            array<int, 26> counts{
    };
            int length = str.length();
            for (int i = 0; i < length; ++i) {
    
                counts[str[i] - 'a'] ++;
            }
            mp[counts].emplace_back(str);
        }
        vector<vector<string>> ans;
        for (auto it = mp.begin(); it != mp.end(); ++it) {
    
            ans.emplace_back(it->second);
        }
        return ans;
    }
};

---

剑指 Offer II 034. 外星语言是否排序

因为字符串比较默认的是a-z那一套，所以我们只需要把外星字符根据优先级映射成a-z即可

class Solution {
    
public:
    bool isAlienSorted(vector<string>& words, string order) {
    
        unordered_map<char,char> um;
        for(int i = 0; i < order.size(); i++) {
    
            um[order[i]] = 'a' + i; 
        }
        string tmp;
        for(auto word: words) {
    
            for(int i = 0; i < word.size(); i++){
    
                word[i] = um[word[i]];
            }
            if(word < tmp) return false;
            tmp = word;
        }
        return true;
    }
};

---

剑指 Offer II 035. 最小时间差

排序后某个数与相邻数之间相差最小。
注意：因为时间是个环，所以最后要考虑首尾差值。

class Solution {
    
    int get_min(string &t) {
    
        return (int(t[0] - '0') * 10 + int(t[1] - '0')) * 60 + int(t[3] - '0') * 10 + int(t[4] - '0');
    }

public:
    int findMinDifference(vector<string> &timePoints) {
    
        int n = timePoints.size();
        if (n > 1440) {
    
            return 0;
        }
        sort(timePoints.begin(), timePoints.end());
        int res = 0x3f3f3f3f;
        int t0 = get_min(timePoints[0]);
        int pre = t0;
        for (int i = 1; i < n; ++i) {
    
            int t = get_min(timePoints[i]);
            res = min(res, t - pre); // 相邻时间的时间差
            pre = t;
        }
        res = min(res, t0 + 1440 - pre); // 首尾时间的时间差
        return res;
    }
};