Hot100

哈希

49.字母异位表（Group Anagrams）

灵神这个题解的意思是使用std::range::sort来处理，结果相同的字符串表明由相同的字母构成，因此自然就分在同一组里面了.

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {

        unordered_map<string, vector<string>> mapping;

        for (string& s: strs){
            string sorted_s = s;
            ranges::sort(sorted_s);
            mapping[sorted_s].push_back(s);
        }

        vector<vector<string>> ans;
        ans.reserve(mapping.size());

        for (auto& [_, value] : mapping){
            ans.push_back(value);
        }
        return ans;
    }
};

---

动态规划

70.爬楼梯

考虑矩阵快速幂来降低时间复杂度：

vector<vector<long long>> multiply(vector<vector<long long>> &a, vector<vector<long long>> &b) {
        vector<vector<long long>> c(2, vector<long long>(2));
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
            }
        }
        return c;
    }

    vector<vector<long long>> matrixPow(vector<vector<long long>> a, int n) {
        vector<vector<long long>> ret = {{1, 0}, {0, 1}};
        while (n > 0) {
            if ((n & 1) == 1) {
                ret = multiply(ret, a);
            }
            n >>= 1;
            a = multiply(a, a);
        }
        return ret;
    }

    int climbStairs(int n) {
        vector<vector<long long>> ret = {{1, 1}, {1, 0}};
        vector<vector<long long>> res = matrixPow(ret, n);
        return res[0][0];
    }

---