Sword finger offer special assault edition day 11

The finger of the sword Offer II 033. Morpheme phrase

Sorting method

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;
    }
};

Counting writing method , The main optimization here is ： Theoretically unordered_map Just go , But the key should be an array of character occurrences , then vector It's getting longer ,unordered_map No, array Corresponding hash function , So you need to define .
The rest of the operation is similar to the sorting method .

class Solution {
    
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
    
        //  Customize to  array<int, 26>  Hash function of type 
        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;
    }
};

---

The finger of the sword Offer II 034. Whether alien languages are sorted

Because string comparison defaults to a-z That set , So we only need to map alien characters into a-z that will do

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;
    }
};

---

The finger of the sword Offer II 035. Minimum time difference

After sorting, the difference between a certain number and adjacent numbers is the smallest .
Be careful ： Because time is a ring , So finally, we should consider the difference between the beginning and the end .

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); //  The time difference between adjacent times 
            pre = t;
        }
        res = min(res, t0 + 1440 - pre); //  The time difference between the beginning and the end 
        return res;
    }
};