Mind palace

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n = matrix.size();
        int lo = matrix[0][0], hi = matrix[n - 1][n - 1];
        while (lo < hi) {
            int m = lo + (hi - lo) / 2;
            int cnt = 0;
            for (const auto &v : matrix) { // 统计所有不大于m的数的个数
                cnt += (upper_bound(v.begin(), v.end(), m) - v.begin());
            }
            if (cnt < k) { // 如果不大于m（包括m）的数不到k个，说明m不是最终结果
                lo = m + 1;
            } else {
                hi = m;
            }
        }
        return lo;
    }
};

struct cmp {
    bool operator()(const pair<int, int> &lhs, const pair<int, int> &rhs) {
        return lhs.first < rhs.first;
    }
};

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        const int target = matrix.size() * matrix.size() - k;
        priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> heap;
        for (int row = 0; row < matrix.size(); ++row) {
            heap.push(make_pair(matrix[row].back(), row));
            matrix[row].pop_back();
        }
        for (int i = 0; i < target; ++i) {
            auto p = heap.top();
            heap.pop();
            if (!matrix[p.second].empty()) {
                heap.push(make_pair(matrix[p.second].back(), p.second));
                matrix[p.second].pop_back();
            }
        }
        return heap.top().first;
    }
};

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int size = matrix.size() * matrix.size() - k + 1;
        for (int i = 0; i < size; ++i) {
            int max_num = INT_MIN;
            int max_row = matrix.size() - 1;
            for (int row = matrix.size() - 1; row >= 0; --row) {
                if (!matrix[row].empty() && matrix[row].back() > max_num) {
                    max_num = matrix[row].back();
                    max_row = row;
                }
            }
            if (i == size - 1)
                return matrix[max_row].back();
            matrix[max_row].pop_back();
        }
        return 0;
    }
};

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * class NestedInteger {
 *   public:
 *     // Constructor initializes an empty nested list.
 *     NestedInteger();
 *
 *     // Constructor initializes a single integer.
 *     NestedInteger(int value);
 *
 *     // Return true if this NestedInteger holds a single integer, rather than a nested list.
 *     bool isInteger() const;
 *
 *     // Return the single integer that this NestedInteger holds, if it holds a single integer
 *     // The result is undefined if this NestedInteger holds a nested list
 *     int getInteger() const;
 *
 *     // Set this NestedInteger to hold a single integer.
 *     void setInteger(int value);
 *
 *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 *     void add(const NestedInteger &ni);
 *
 *     // Return the nested list that this NestedInteger holds, if it holds a nested list
 *     // The result is undefined if this NestedInteger holds a single integer
 *     const vector<NestedInteger> &getList() const;
 * };
 */
class Solution {
public:
    int depthSum(vector<NestedInteger>& nestedList) {
        int depth = 1, res = 0;
        while (!nestedList.empty()) {
            vector<NestedInteger> nextLevel;
            for (const auto &ni : nestedList) {
                if (ni.isInteger()) {
                    res += ni.getInteger() * depth;
                } else {
                    nextLevel.insert(end(nextLevel), begin(ni.getList()), end(ni.getList()));
                }
            }
            nestedList.swap(nextLevel);
            ++depth;
        }
        return res;
    }
};

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * class NestedInteger {
 *   public:
 *     // Constructor initializes an empty nested list.
 *     NestedInteger();
 *
 *     // Constructor initializes a single integer.
 *     NestedInteger(int value);
 *
 *     // Return true if this NestedInteger holds a single integer, rather than a nested list.
 *     bool isInteger() const;
 *
 *     // Return the single integer that this NestedInteger holds, if it holds a single integer
 *     // The result is undefined if this NestedInteger holds a nested list
 *     int getInteger() const;
 *
 *     // Set this NestedInteger to hold a single integer.
 *     void setInteger(int value);
 *
 *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 *     void add(const NestedInteger &ni);
 *
 *     // Return the nested list that this NestedInteger holds, if it holds a nested list
 *     // The result is undefined if this NestedInteger holds a single integer
 *     const vector<NestedInteger> &getList() const;
 * };
 */
class Solution {
public:
    int depthSum(vector<NestedInteger>& nestedList) {
        list<NestedInteger> q(begin(nestedList), end(nestedList));
        int depth = 1, res = 0;
        while (!q.empty()) {
            for (int i = q.size(); i > 0; --i) {
                auto x = q.front(); q.pop_front();
                if (x.isInteger()) {
                    res += x.getInteger() * depth;
                } else {
                    q.insert(end(q), begin(x.getList()), end(x.getList()));
                }
            }
            ++depth;
        }
        return res;
    }
};

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * class NestedInteger {
 *   public:
 *     // Constructor initializes an empty nested list.
 *     NestedInteger();
 *
 *     // Constructor initializes a single integer.
 *     NestedInteger(int value);
 *
 *     // Return true if this NestedInteger holds a single integer, rather than a nested list.
 *     bool isInteger() const;
 *
 *     // Return the single integer that this NestedInteger holds, if it holds a single integer
 *     // The result is undefined if this NestedInteger holds a nested list
 *     int getInteger() const;
 *
 *     // Set this NestedInteger to hold a single integer.
 *     void setInteger(int value);
 *
 *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 *     void add(const NestedInteger &ni);
 *
 *     // Return the nested list that this NestedInteger holds, if it holds a nested list
 *     // The result is undefined if this NestedInteger holds a single integer
 *     const vector<NestedInteger> &getList() const;
 * };
 */
class Solution {
public:
    int depthSum(vector<NestedInteger>& nestedList) {
        queue<NestedInteger> q;
        for (const auto &ni : nestedList) {
            q.push(ni);
        }
        int res = 0, depth = 1;
        while (!q.empty()) {
            for (int i = q.size(); i > 0; --i) {
                auto x = q.front(); q.pop();
                if (x.isInteger()) {
                    res += x.getInteger() * depth;
                } else {
                    for (const auto &ni : x.getList()) {
                        q.push(ni);
                    }
                }
            }
            ++depth;
        }
        return res;
    }
};

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * class NestedInteger {
 *   public:
 *     // Constructor initializes an empty nested list.
 *     NestedInteger();
 *
 *     // Constructor initializes a single integer.
 *     NestedInteger(int value);
 *
 *     // Return true if this NestedInteger holds a single integer, rather than a nested list.
 *     bool isInteger() const;
 *
 *     // Return the single integer that this NestedInteger holds, if it holds a single integer
 *     // The result is undefined if this NestedInteger holds a nested list
 *     int getInteger() const;
 *
 *     // Set this NestedInteger to hold a single integer.
 *     void setInteger(int value);
 *
 *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 *     void add(const NestedInteger &ni);
 *
 *     // Return the nested list that this NestedInteger holds, if it holds a nested list
 *     // The result is undefined if this NestedInteger holds a single integer
 *     const vector<NestedInteger> &getList() const;
 * };
 */
class Solution {
public:
    int depthSum(vector<NestedInteger>& nestedList) {
        return dfs(nestedList, 1);
    }

    int dfs(const vector<NestedInteger> &nestedList, int depth) {
        int res = 0;
        for (const auto &ni : nestedList) {
            if (ni.isInteger()) {
                res += ni.getInteger() * depth;
            } else {
                res += dfs(ni.getList(), depth + 1);
            }
        }
        return res;
    }
};

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        for (const auto &w : wordDict) {
            table.insert(string_view{w});
        }
        return dfs(string_view{s});
    }

    bool dfs(string_view sv) {
        if (sv.empty()) return true;
        if (m.count(sv)) return m[sv];
        for (int n = size(sv), i = 1; i <= n; ++i) {
            if (table.count(sv.substr(0, i)) && dfs(sv.substr(i))) return m[sv] = true;
        }
        return m[sv] = false;
    }

    unordered_set<string_view> table;
    unordered_map<string_view, bool> m;
};

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        ws = unordered_set<string>(wordDict.begin(), wordDict.end());
        return dfs(s);
    }

    bool dfs(const string &s) {
        if (s.empty()) return true;
        if (m.count(s)) return m[s];
        string prefix;
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            prefix += s[i];
            if (ws.count(prefix) && dfs(s.substr(i + 1))) return true;
        }
        return m[s] = false;
    }

    unordered_map<string, bool> m;
    unordered_set<string> ws;
};

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> dict(wordDict.begin(), wordDict.end()); // 用一个hashset存单词方便查找
        int n = s.length();
        vector<bool> f(n + 1, true); // 表示前n个字母是否符合要求，注意f[0]一定要为true
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (f[i] = f[j] && (dict.count(s.substr(j, i - j)) > 0)) break; // 注意及时break否则就白找了
            }
        }
        return f[n];
    }
};

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string_view> dict(begin(wordDict), end(wordDict));
        string_view sv{s};
        const int n = size(sv);
        vector<int> f(n + 1, true);
        for (int i = 1; i <= n; ++i) {
            for (int j = i - 1; j >= 0; --j) {
                if (f[i] = f[j] && (dict.count(sv.substr(j, i - j)) > 0)) break;
            }
        }
        return f[n];
    }
};

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.length();
        vector<bool> f(n + 1);
        f[0] = true;
        for (int i = 0; i < n; ++i) {
            for (const auto &w : wordDict) {
                if (f[i] && s.substr(i, min(n, w.length())) == w) {
                    f[i + w.length()] = true;
                }
            }
        }
        return f[n];
    }
};

class Solution {
public:
    Solution(vector<int> nums) : nums(move(nums)) {
        srand((unsigned)time(NULL));
    }

    int pick(int target) {
        int res = -1;
        for (int i = 0, count = 0; i < nums.size(); ++i) {
            if (nums[i] != target) continue; // 跳过所有的非目标，采样跟他们无关
            if (rand() % ++count == 0) { // 遇到目标时随机一次，这样采样数据源只包括所有的目标
                res = i;
            }
        }
        return res;
    }

    vector<int> nums;
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int param_1 = obj.pick(target);
 */

class Solution {
public:
    Solution(vector<int> &nums) : b(begin(nums)), e(end(nums)) {
        srand((unsigned)time(NULL));
    }

    int pick(int target) {
        int res = -1, count = 0;
        for (auto it = b; it != e; ++it) {
            if (*it != target) continue;
            if (rand() % ++count == 0) {
                res = distance(b, it);
            }
        }
        return res;
    }

    vector<int>::iterator b, e;
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int param_1 = obj.pick(target);
 */

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        dfs(root);
        return res;
    }

    int dfs(TreeNode *root) { // 返回以root为根的最长链有几个结点
        if (!root) return 0;
        int l = dfs(root->left), r = dfs(root->right);
        res = max(res, l + r); // 人家问的是边不是点，不要加1
        return max(l, r) + 1;
    }

    int res = 0;
};

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;

    Node() {}

    Node(int _val) {
        val = _val;
        next = NULL;
    }

    Node(int _val, Node* _next) {
        val = _val;
        next = _next;
    }
};
*/

class Solution {
public:
    Node* insert(Node* head, int insertVal) {
        if (!head) {
            auto res = new Node(insertVal);
            res->next = res;
            return res;
        }
        auto prev = head, curr = head->next;
        do { // 因为上来如果判断prev != head没法写循环，改成dowhile就可以了
            if (prev->val <= insertVal && insertVal <= curr->val) break;
            if (prev->val > curr->val && (prev->val <= insertVal || insertVal <= curr->val)) break;
            prev = curr;
            curr = prev->next;
        } while (prev != head);
        prev->next = new Node(insertVal, curr);
        return head;
    }
};

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;

    Node() {}

    Node(int _val, Node* _next) {
        val = _val;
        next = _next;
    }
};
*/
class Solution {
public:
    Node* insert(Node* head, int insertVal) {
        if (!head) { // 一定要注意空表！！！
            auto res = new Node(insertVal);
            res->next = res;
            return res;
        }
        auto prev = head, curr = prev->next;
        while (curr != head) { // curr == head说明已经找了一圈了都不符合要求，这是最后一个，只能这个了
            if (prev->val <= insertVal && insertVal <= curr->val) break; // 终止条件1：insertVal恰好在prev和curr之间
            if (prev->val > curr->val && (prev->val <= insertVal || insertVal <= curr->val)) break; // 终止条件2：升序序列，insertVal恰好比最大的数大或者比最小的数小，必须最大的严格大于最小的，否则可能插入错误
            prev = curr;
            curr = prev->next;
        } // 如果都不符合要求，则说明head之前就是应该插入的地方
        prev->next = new Node(insertVal, curr);
        return head;
    }
};

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;

    Node() {}

    Node(int _val, Node* _next) {
        val = _val;
        next = _next;
    }
};
*/
class Solution {
public:
    Node* insert(Node* head, int insertVal) {
        if (!head) {
            auto res = new Node(insertVal);
            res->next = res;
            return res;
        }
        auto curr = head;
        while (curr->next != head && curr->val <= curr->next->val) {
            curr = curr->next;
        }
        auto prev = curr, smallest = prev->next;
        curr = smallest;
        while (curr->val < insertVal) {
            prev = curr;
            curr = prev->next;
            if (curr == smallest) break;
        }
        prev->next = new Node(insertVal, curr);
        return head;
    }
};

class Solution {
public:
    vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) {
        int m = A.size(), n = B.size();
        int i = 0, j = 0;
        vector<vector<int>> res;
        while (i < m && j < n) {
            int s = max(A[i][0], B[j][0]);
            int e = min(A[i][1], B[j][1]); // 找intersection
            if (s <= e) { // 如果有intersection
                res.push_back({s, e});
            }
            if (e == A[i][1]) { // 如果A[i]区间比较靠前则看下一个
                ++i;
            }
            if (e == B[j][1]) {
                ++j;
            }
        }
        return res;
    }
};

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> neighbors;

    Node() {}

    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/
class Solution {
public:
    Node* cloneGraph(Node* node) {
        if (!node) return node;
        if (nodes.count(node)) return nodes[node];
        auto res = new Node;
        nodes[node] = res; // 一定要先cache！！
        res->val = node->val;
        for (auto n : node->neighbors) {
            res->neighbors.push_back(cloneGraph(n));
        }
        return res;
    }

    unordered_map<Node *, Node *> nodes;
};

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> neighbors;

    Node() {}

    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/
class Solution {
public:
    Node* cloneGraph(Node* node) {
        if (!node) return node;
        unordered_map<Node *, Node *> nodes{{node, new Node(node->val, {})}};
        queue<Node *> q{{node}};
        while (!q.empty()) {
            auto x = q.front(); q.pop();
            for (auto n : x->neighbors) {
                if (!nodes.count(n)) {
                    nodes[n] = new Node(n->val, {});
                    q.push(n);
                }
                nodes[x]->neighbors.push_back(nodes[n]);
            }
        }
        return nodes[node];
    }
};

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        for (int i = m + n - 1, i1 = m - 1, i2 = n - 1; i2 >= 0; --i) {
            if (i1 >= 0) {
                nums1[i] = nums1[i1] > nums2[i2] ? nums1[i1--] : nums2[i2--];
            } else {
                nums1[i] = nums2[i2--];
            }
        }
    }
};

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        for (int i = m + n - 1, i1 = m - 1, i2 = n - 1; i >= 0; --i) {
            if (i1 >= 0 && i2 >= 0) {
                nums1[i] = nums1[i1] > nums2[i2] ? nums1[i1--] : nums2[i2--];
            } else if (i2 >= 0) { // i1到头了，只扫nums2即可
                nums1[i] = nums2[i2--];
            } else { // i2到头了，nums1保持不变，不用再扫了
                break;
            }
        }
    }
};

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        vector<int> res(m + n);
        for (int i = 0, j = 0; i < m || j < n;) {
            int a = i < m ? nums1[i] : INT_MAX;
            int b = j < n ? nums2[j] : INT_MAX;
            res[i + j] = min(a, b);
            if (res[i + j] == a) ++i;
            else ++j;
        }
        nums1 = res;
    }
};

class Solution {
public:
    bool isNumber(string s) {
        bool exp = false, dot = false, num = false, numAfterE = false;
        for (int i = s.find_first_not_of(' '); i <= s.find_last_not_of(' '); ++i) {
            char c = s[i];
            if (isdigit(c)) {
                num = numAfterE = true;
            } else if (c == 'e') {
                if (exp || !num) return false;
                exp = true;
                numAfterE = false;
            } else if (c == '.') {
                if (dot || exp) return false;
                dot = true;
            } else if (c == '+' || c == '-') {
                if (i > 0 && s[i - 1] != ' ' && s[i - 1] != 'e') return false;
            } else return false;
        }
        return num && numAfterE;
    }
};

class Solution {
public:
    bool isNumber(string s) {
        int n = s.length();
        bool num = false, numAfterE = false, dot = false, exp = false, sign = false;
        for (int i = 0; i < n; ++i) {
            char c = s[i];
            if (c == ' ') {
                if ((num || dot || exp || sign) && i + 1 < n && s[i + 1] != ' ') return false; // 空格不能出现在中间
            } else if (isdigit(c)) {
                num = numAfterE = true;
            } else if (c == '.') {
                if (dot || exp) return false; // 不能有多个.且指数部分不能有.
                dot = true;
            } else if (c == 'e') {
                if (exp || !num) return false; // 不能有多个e且e前必须得有数字出现
                exp = true;
                numAfterE = false; // 重置！！
            } else if (c == '+' || c == '-') {
                if (i > 0 && s[i - 1] != 'e' && s[i - 1] != ' ') return false; // 符号只能出现在最开始的空格之后或者e之后
                sign = true;
            } else return false;
        }
        return num && numAfterE; // 最后底数和指数都要检查
    }
};