Mind palace

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;
        int n = matrix.size();
        int m = matrix[0].size();
        vector<int> height(m + 1); // 这里一定要多一个！！方便后边算最大面积
        int res = 0;
        for (int row = 0; row < n; ++row) {
            for (int col = 0; col < m; ++col) {
                height[col] = matrix[row][col] == '0' ? 0 : height[col] + 1;
            }
            res = max(res, helper(height));
        }
        return res;
    }

    int helper(const vector<int> &height) {
        int n = height.size();
        stack<int> s{{-1}};
        int res = 0;
        for (int i = 0; i < n; ++i) {
            while (s.top() != -1 && height[i] < height[s.top()]) {
                int h = height[s.top()];
                s.pop();
                res = max(res, h * (i - s.top() - 1));
            }
            s.push(i);
        }
        return res;
    }
};

class Solution {
public:
    bool canAttendMeetings(vector<vector<int>>& intervals) {
        sort(begin(intervals), end(intervals));
        for (int i = 1; i < size(intervals); ++i) {
            if (intervals[i - 1][1] > intervals[i][0]) return false;
        }
        return true;
    }
};

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    bool canAttendMeetings(vector<Interval>& intervals) {
        auto cmp = [](const Interval &a, const Interval &b) {return a.start < b.start;};
        sort(begin(intervals), end(intervals), cmp);
        for (int i = 1; i < intervals.size(); ++i) {
            if (intervals[i - 1].end > intervals[i].start) return false;
        }
        return true;
    }
};

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    bool canAttendMeetings(vector<Interval>& intervals) {
        auto cmp = [](const Interval &a, const Interval &b) {return a.start < b.start;};
        sort(begin(intervals), end(intervals), cmp);
        int end = -1;
        for (const auto &i : intervals) {
            if (i.start < end) return false;
            end = i.end;
        }
        return true;
    }
};

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    bool canAttendMeetings(vector<Interval>& intervals) {
        map<int, int> m;
        for (const auto &i : intervals) {
            ++m[i.start];
            --m[i.end];
        }
        int cnt = 0;
        for (auto &&p : m) {
            cnt += p.second;
            if (cnt > 1) return false;
        }
        return true;
    }
};

class Solution {
public:
    vector<string> subdomainVisits(vector<string>& cpdomains) {
        unordered_map<string, int> m;
        int cnt = 0;
        string d;
        for (const auto &s : cpdomains) {
            istringstream input(s);
            input >> cnt >> d;
            m[d] += cnt;
            int n = d.length();
            for (int i = 0; i < n; ++i) {
                if (d[i] == '.') {
                    m[d.substr(i + 1)] += cnt;
                }
            }
        }
        vector<string> res;
        for (const auto &p : m) {
            res.push_back(to_string(p.second) + " " + p.first);
        }
        return res;
    }
};

class Solution {
public:
    int calculate(string s) {
        int i = 0;
        s += "+";
        return calc(s, i);
    }

    int calc(const string &s, int &i) {
        char op = '+';
        long n = s.size(), num = 0, res = 0;
        for (; i < n; ++i) {
            char c = s[i];
            if (isdigit(c)) {
                num = num * 10 + c - '0';
            } else if (c == '(') {
                num = calc(s, ++i);
            } else if (c != ' ') {
                res += (44 - op) * num; // 因为没有*/所以不需要curRes来进行局部运算，直接用res累加即可
                op = c;
                num = 0;
                if (c == ')') break;
            }
        }
        return res;
    }
};

class Solution {
public:
    int calculate(string s) {
        int i = 0;
        s += "+";
        return calc(s, i);
    }

    int calc(const string &s, int &i) {
        char op = '+';
        long n = s.size(), num = 0, res = 0;
        for (; i < n && op != ')'; ++i) {
            char c = s[i];
            if (isdigit(c)) {
                num = num * 10 + c - '0';
            } else if (c == '(') {
                num = calc(s, ++i);
                --i; // 因为最后循环终止条件是op != ')'所以当op为')'时i已经指向下一个符号，所以需要回退一个
            } else if (c != ' ') {
                res += (44 - op) * num; // 因为没有*/所以不需要curRes来进行局部运算，直接用res累加即可
                op = c;
                num = 0;
            }
        }
        return res;
    }
};

class Solution {
public:
    int calculate(string s) {
        s += ' '; // padding
        stack<int> operands, operators;
        long sign(1), res(0), num(0);
        for (auto &&c : s) {
            if (isdigit(c)) {
                num = num * 10 + c - '0'; // 用long防止溢出
            } else {
                res += sign * num;
                num = 0;
                switch (c) {
                    case '+': sign = 1; break;
                    case '-': sign = -1; break;
                    case '(': {
                        operands.push(res);
                        operators.push(sign);
                        res = 0; // 开始括号内的新计算所以reset两个变量res和sign
                        sign = 1;
                    }
                    break;
                    case ')': {
                        res = operands.top() + operators.top() * res;
                        operands.pop();
                        operators.pop();
                    }
                    break;
                    default: break;
                }
            }
        }
        return res;
    }
};

class Solution {
public:
    int minMoves(vector<int>& nums, int limit) {
        vector<int> f(limit * 2 + 2);
        int n = size(nums);
        for (int i = 0; i * 2 < n; ++i) {
            int a = nums[i], b = nums[n - 1 - i];
            f[2] += 2;
            --f[min(a, b) + 1];
            --f[a + b];
            ++f[a + b + 1];
            ++f[max(a, b) + limit + 1];
        }
        int res = n, cnt = 0;
        for (int i = 2; i <= limit * 2; ++i) {
            res = min(res, cnt += f[i]);
        }
        return res;
    }
};

class Solution {
public:
    bool arrayStringsAreEqual(vector<string>& word1, vector<string>& word2) {
        int i1 = 0, i2 = 0, m = size(word1), n = size(word2);
        for (int j1 = 0, j2 = 0; i1 < m && i2 < n;) {
            if (word1[i1][j1] != word2[i2][j2]) return false;
            if (++j1 == size(word1[i1])) {
                ++i1;
                j1 = 0;
            }
            if (++j2 == size(word2[i2])) {
                ++i2;
                j2 = 0;
            }
        }
        return i1 == m && i2 == n;
    }
};

#include <iostream>

using namespace std;

class A {
    virtual void a() = 0;
};

class B : public A {
    virtual void b() = 0;
};

class C : public A {
    virtual void c() = 0;
};

class D : public B, public C {
public:
    void a() { cout << "a\n"; }
    void b() {}
    void c() {}
};

int main() {
    D d;
    d.a();
    return 0;
}

class NumMatrix {
public:
    NumMatrix(vector<vector<int>> matrix) {
        if (matrix.empty() || matrix[0].empty()) return;
        int n = matrix.size(), m = matrix[0].size();
        mtx.resize(n + 1, vector<int>(m + 1));
        for (int r = 1; r <= n; ++r) {
            for (int c = 1; c <= m; ++c) {
                mtx[r][c] = matrix[r - 1][c - 1] + mtx[r - 1][c] + mtx[r][c - 1] - mtx[r - 1][c - 1];
            }
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        return mtx[row2 + 1][col2 + 1] - mtx[row1][col2 + 1] - mtx[row2 + 1][col1] + mtx[row1][col1];
    }

    vector<vector<int>> mtx;
};

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */

class Solution {
public:
    vector<string> findStrobogrammatic(int n) {
        string s(n, '0');
        v = {"16896891", "018810", "0168968910"};
        dfs(s, 0, n - 1);
        return res;
    }

    void dfs(string &s, int l, int r) {
        if (l > r) {
            res.push_back(s);
            return;
        }
        int k = 0;
        if (l == r) {
            k = 1;
        } else if (l > 0) {
            k = 2;
        }
        for (int n = size(v[k]), i = 0, j = n - 1; i < j; ++i, --j) {
            s[l] = v[k][i];
            s[r] = v[k][j];
            dfs(s, l + 1, r - 1);
        }
    }

    vector<string> res, v;
};

class Solution {
public:
    vector<string> findStrobogrammatic(int n) {
        string s(n, '0');
        vector<string> res;
        find(s, 0, n - 1, res);
        return res;
    }

    void find(string &s, int l, int r, vector<string> &res) {
        if (r < l) { // 如果指针交错，添加结果
            res.push_back(s);
            return;
        }
        string chars;
        if (l == r) { // 如果指针相遇，只有可能是180，包括n为1的情况
            chars = "180081";
        } else if (l == 0) { // 如果指针在两头，则不可能是0
            chars = "18696981";
        } else { // 如果指针在其他位置，则都有可能
            chars = "1869006981";
        }
        for (int i = 0, j = chars.length() - 1; i < j; ++i, --j) {
            s[l] = chars[i];
            s[r] = chars[j];
            find(s, l + 1, r - 1, res);
        }
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int largestBSTSubtree(TreeNode* root) {
        return get<0>(dfs(root));
    }

    tuple<int, int, int> dfs(TreeNode *p) { // {以root为根的这棵树的最大BST子树的结点数，最小值，最大值}
        if (!p) return {0, INT_MAX, INT_MIN};
        auto [ln, lmn, lmx] = dfs(p->left);
        auto [rn, rmn, rmx] = dfs(p->right);
        if (lmx >= p->val || rmn <= p->val) return {max(ln, rn), INT_MIN, INT_MAX}; // 如果这棵树不是BST，左右子可能有一个是BST，不是的话也会把那棵子树上最大的BST的结点数返回给上一层
        return {ln + 1 + rn, min(lmn, p->val), max(rmx, p->val)}; // 这里最小值和最大值都要把root考虑进去
    }
};

/**
 * 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 largestBSTSubtree(TreeNode* root) {
        auto ret = dfs(root);
        return ret[2];
    }

    vector<int> dfs(TreeNode *root) {
        if (!root) return {INT_MAX, INT_MIN, 0}; // {最小值，最大值，以root为根的这棵树的最大BST子树的结点数}
        auto l = dfs(root->left);
        auto r = dfs(root->right);
        if (l[1] < root->val && root->val < r[0]) return {min(l[0], root->val), max(root->val, r[1]), l[2] + r[2] + 1}; // 这里最小值和最大值都要把root考虑进去
        return {INT_MIN, INT_MAX, max(l[2], r[2])}; // 如果这棵树不是BST，左右子可能有一个是BST，不是的话也会把那棵子树上最大的BST的结点数返回给上一层
    }
};