Mind palace

class KthLargest {
public:
    KthLargest(int k, const vector<int>& nums) : k(k) {
        for (int x : nums) {
            q.push(x);
            if (q.size() > k) {
                q.pop();
            }
        }
    }

    int add(int val) {
        q.push(val);
        if (q.size() > k) {
            q.pop();
        }
        return q.top();
    }

    int k;
    priority_queue<int, vector<int>, greater<int>> q;
};

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest* obj = new KthLargest(k, nums);
 * int param_1 = obj->add(val);
 */

class Solution {
public:
    bool validWordAbbreviation(string word, string abbr) {
        word += " ", abbr += " "; // padding方便处理
        int m = word.length(), n = abbr.length(), i = 0, j = 0;
        for (int s = 0; i < m && j < n; i += s, ++j) {
            if (isdigit(abbr[j])) {
                if (abbr[j] == '0') return false; // 以0开头的数是非法的
                int x = 0; // 一次性把整个数取出来
                while (isdigit(abbr[j])) {
                    x = x * 10 + abbr[j] - '0';
                    ++j;
                }
                --j; // 注意下标要回退一个
                s = x;
            } else {
                if (word[i] != abbr[j]) return false;
                s = 1;
            }
        }
        return i == m && j == n; // 最后判断是否两个指针同时达到结尾
    }
};

class Solution {
public:
    bool validWordAbbreviation(string word, string abbr) {
        word += " ", abbr += " ";
        int m = word.length(), n = abbr.length(), s = 0, i = 0, j = 0;
        for (; i < m && j < n; ++j) {
            if (isdigit(abbr[j])) {
                if (s == 0 && abbr[j] == '0') return false;
                s = s * 10 + abbr[j] - '0';
            } else {
                i += s;
                s = 0;
                if (i < m && word[i] != abbr[j]) return false;
                ++i;
            }
        }
        return i == m && j == n;
    }
};

class Solution {
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        int n = words.size();
        unordered_map<string, int> m;
        for (int i = 0; i < n; ++i) {
            m[words[i]] = i;
        }
        vector<vector<int>> res;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j <= words[i].length(); ++j) { // 这里必须是<=，反例["a", ""]，否则答案会少一组，如果没有空串则不需要
                auto left = words[i].substr(0, j);
                auto right = words[i].substr(j);
                if (isValid(left)) {
                    string t(rbegin(right), rend(right));
                    if (m.count(t) && m[t] != i) {
                        res.push_back({m[t], i});
                    }
                }
                if (!right.empty() && isValid(right)) { // 这里要对right判空，因为之前left已经处理过完整字符串了，避免重复处理添加，反例["ab", "ba"]
                    string t(rbegin(left), rend(left));
                    if (m.count(t) && m[t] != i) {
                        res.push_back({i, m[t]});
                    }
                }
            }
        }
        return res;
    }

    bool isValid(const string &s) {
        int l = 0, r = s.length() - 1;
        while (l < r) {
            if (s[l++] != s[r--]) return false;
        }
        return true;
    }
};

class Solution {
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        Trie t;
        int n = words.size();
        for (int i = 0; i < n; ++i) {
            t.add(words, i);
        }
        vector<vector<int>> res;
        for (int i = 0; i < n; ++i) {
            for (auto idx : t.find(words[i])) {
                if (idx != i && isPalindrome(words[i] + words[idx])) { // 连接所有的可能单词并检查合法性
                    res.push_back({i, idx});
                }
            }
        }
        return res;
    }

    bool isPalindrome(const string &s) {
        int n = s.length();
        int i = 0, j = n - 1;
        for (; i < j && s[i] == s[j]; ++i, --j);
        return i >= j;
    }

    struct TrieNode {
        TrieNode() : idx(-1), children({nullptr}) {}
        TrieNode *children[26];
        int idx; // 如果单词到此结束，保存其下标
        vector<int> indices; // 保存所有长度大于等于 到此为止的单词 的单词的下标
    };

    struct Trie {
        Trie() : root(new TrieNode()) {}
        void add(const vector<string> &words, int idx) {
            auto node = root;
            for (auto rit = words[idx].rbegin(); rit != words[idx].rend(); ++rit) {
                if (!node->children[*rit - 'a']) {
                    node->children[*rit - 'a'] = new TrieNode();
                }
                node->indices.push_back(idx); // 如果当前单词不在此结束，当前节点保存该单词的下标
                node = node->children[*rit - 'a'];
            }
            node->idx = idx; // 当前单词结束于此，保存其下标
            node->indices.push_back(idx);
        }
        vector<int> find(const string &s) {
            auto node = root;
            vector<int> res;
            for (const auto &c : s) {
                if (!node->children[c - 'a']) {
                    res.insert(res.end(), node->indices.begin(), node->indices.end()); // 虽然当前查找的目标单词不在Trie上，但是仍然要把一路遇到的所有下标以及本来继续往下可能会遇到的所有下标全部返回
                    return res;
                } else {
                    if (node->idx != -1) {
                        res.push_back(node->idx); // 路过此节点，保存其代表的单词的下标
                    }
                    node = node->children[c - 'a'];
                }
            }
            res.insert(res.end(), node->indices.begin(), node->indices.end());
            return res;
        }
        TrieNode *root;
    };
};

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        map<int, int> m;
        for (const auto &t : trips) {
            m[t[1]] += t[0];
            m[t[2]] -= t[0];
        }
        int cnt = 0;
        for (const auto &[k, v] : m) {
            cnt += v;
            if (cnt > capacity) return false;
        }
        return true;
    }
};

// Forward declaration of the knows API.
bool knows(int a, int b);

class Solution {
public:
    int findCelebrity(int n) {
        int cand = 0;
        for (int i = 1; i < n; ++i) {
            // if (!knows(i, cand)) { // 理论上也可以
            if (knows(cand, i)) {
                cand = i;
            }
        }
        for (int i = 0; i < n; ++i) {
            if (i != cand && (knows(cand, i) || !knows(i, cand))) return -1;
        }
        return cand;
    }
};

class Solution {
public:
    string rearrangeString(string s, int k) {
        if (k == 0) return s;
        int f[26] = {0};
        for (char c : s) {
            ++f[c - 'a'];
        }
        auto cmp = [&f](int a, int b) { return f[a] == f[b] ? a > b : f[a] < f[b]; }; // 频数高的优先，相同频数的ASCII码小的优先
        priority_queue<int, vector<int>, decltype(cmp)> q(cmp);
        for (int i = 0; i < 26; ++i) {
            if (f[i] > 0) {
                q.push(i);
            }
        }
        int n = s.length();
        string res;
        while (!q.empty()) {
            vector<int> v; // 每次缓存k个字符
            int sz = min(k, n); // 这里由于要对n进行更新所以要提前判断还需要append几个字符
            for (int i = 0; i < sz; ++i) {
                if (q.empty()) return ""; // q为空，说明有字符过多，不满足相同字符间隔至少为k的要求
                int x = q.top(); q.pop();
                res += 'a' + x;
                if (--f[x] > 0) { // 如果放完当前字符还有剩余，则稍后放回堆
                    v.push_back(x);
                }
                --n; // 每append一个字符，更新需求n
            }
            for (int x : v) { // 最后统一从缓存加回最大堆
                q.push(x);
            }
        }
        return res;
    }
};

class Solution {
public:
    string rearrangeString(string s, int k) {
        if (k == 0) return s;
        int f[26] = {0};
        iota(f, f + 26, 0);
        for (char c : s) {
            f[c - 'a'] += 100;
        }
        priority_queue<int> q;
        for (int i = 0; i < 26; ++i) {
            if (f[i] > 99) {
                q.push(f[i]);
            }
        }
        int n = s.length();
        string res;
        while (!q.empty()) {
            vector<int> v; // 每次缓存k个字符
            int sz = min(k, n); // 这里由于要对n进行更新所以要提前判断还需要append几个字符
            for (int i = 0; i < sz; ++i) {
                if (q.empty()) return ""; // q为空，说明有字符过多，不满足相同字符间隔至少为k的要求
                int x = q.top(); q.pop();
                res += 'a' + x % 100;
                x -= 100;
                if (x > 99) { // 如果放完当前字符还有剩余，则稍后放回堆
                    v.push_back(x);
                }
                --n; // 每append一个字符，更新需求n
            }
            for (int x : v) { // 最后统一从缓存加回最大堆
                q.push(x);
            }
        }
        return res;
    }
};

class Solution {
public:
    string reorganizeString(string S) {
        int n = S.length();
        int f[26] = {0}; // 很牛逼的编码方式，f[i] = freq * 100 + i，避免使用pair的麻烦
        iota(f, f + 26, 0);
        for (char c : S) {
            f[c - 'a'] += 100;
        }
        sort(f, f + 26, greater<>());
        if (f[0] / 100 > (n + 1) / 2) return ""; // 如果某个字符过多，直接返回空串
        string s;
        for (int i = 0; i < 26; ++i) {
            s.append(f[i] / 100, 'a' + f[i] % 100); // 按频数由大到小重组字符串
        }
        string res;
        for (int i = 0; i < (n + 1) / 2; ++i) {
            res += s[i];
            int j = i + (n + 1) / 2;
            if (j < n) {
                res += s[j];
            }
        }
        return res;
    }
};

class Solution {
public:
    string reorganizeString(string S) {
        int n = S.length();
        int f[26] = {0};
        for (char c : S) {
            f[c - 'a'] += 100;
        }
        priority_queue<int, vector<int>> q;
        for (int i = 0; i < 26; ++i) {
            if (f[i] / 100 > (n + 1) / 2) return "";
            if (f[i]) {
                q.push(f[i] + i);
            }
        }
        string res;
        while (q.size() > 1) {
            int f1 = q.top(); q.pop();
            int f2 = q.top(); q.pop();
            res += ('a' + f1 % 100); f1 -= 100;
            res += ('a' + f2 % 100); f2 -= 100;
            if (f1 >= 100) {
                q.push(f1);
            }
            if (f2 >= 100) {
                q.push(f2);
            }
        }
        if (!q.empty()) {
            res += ('a' + q.top() % 100);
        }
        return res;
    }
};

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int n = nums.size();
        int l = 0, r = n - 1;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (nums[m] == nums[m + 1]) {
                if (m & 1) {
                    r = m - 1;
                } else {
                    l = m + 2;
                }
            } else {
                if (m & 1) {
                    l = m + 1;
                } else {
                    r = m;
                }
            }
        }
        return nums[l];
    }
};

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int n = nums.size();
        int l = 0, r = n - 1;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (nums[m] == nums[m ^ 1]) { // 任一数m异或1得到其相邻的数，偶数则是相邻较大的奇数，奇数则是相邻较小的偶数
                l = m + 1; // 如果相邻两数相等，则所求的数肯定在右侧，因为两个数左边是偶数个数右边是奇数个数
            } else { // 如果相邻两数不等，则所求的数要不是nums[m]要不在左侧
                r = m;
            }
        }
        return nums[l];
    }
};

class Solution {
public:
    double angleClock(int hour, int minutes) {
        double diff = fabs(minutes * 5.5 - hour * 30);
        return min(diff, 360 - diff);
    }
};

class Solution {
public:
    double angleClock(int hour, int minutes) {
        double diff = fabs(minutes * 5.5 - hour * 30);
        return diff <= 180 ? diff : 360 - diff;
    }
};

class Solution {
public:
    vector<vector<int>> spiralMatrixIII(int R, int C, int r0, int c0) {
        vector<vector<int>> res = {{r0, c0}};
        int dr[] = {0, 1, 0, -1}, dc[] = {1, 0, -1, 0};
        int sz = 1, dir = 0, r = r0, c = c0;
        while (res.size() < R * C) {
            for (int i = 0; i < sz; ++i) {
                r += dr[dir];
                c += dc[dir];
                if (0 <= r && r < R && 0 <= c && c < C) {
                    res.push_back({r, c});
                }
            }
            dir = (dir + 1) % 4; // 方向每次转一下
            sz += !(dir & 1); // 在每个方向上走的步数，每两个方向加一，即dir模2为0时加一
        }
        return res;
    }
};