Mind palace

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        auto n1 = headA, n2 = headB;
        while (n1 != n2) {
            n1 = n1 ? n1->next : headB; // 注意要判断n1是不是为空，最后有可能根本没有交点，则两个指针都落在nullptr上
            n2 = n2 ? n2->next : headA;
        }
        return n1;
    }
};

struct Node {
    Node(int x) : val(x) {}
    Node *next = nullptr;
};

Node *getCycle(Node *head) {
    auto fast = head, slow = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) break;
    }
    if (!fast || !fast->next) return nullptr;
    slow = head;
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}

bool f(Node *headA, Node *headB) {
    auto a = getCycle(headA), b = getCycle(headB);
    if (a && b) return a == b;
    if (!a && !b) {
        while (headA != headB) {
            headA = headA ? headA->next : headB;
            headB = headB ? headB->next : headA;
        }
        return headA;
    }
    return false;
}

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

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        Node dummy, *p = &dummy, *res = root;
        while (root) {
            if (root->left) {
                p->next = root->left;
                p = p->next;
            }
            if (root->right) {
                p->next = root->right;
                p = p->next;
            }
            root = root->next; // 假设上一层已经连完了
            if (!root) { // 到头了
                root = dummy.next; // 设成下一层起始
                dummy.next = nullptr; // 重置dummy和p
                p = &dummy;
            }
        }
        return res;
    }
};

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

    Node() {}

    Node(int _val, Node* _left, Node* _right, Node* _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/
class Solution {
public:
    Node* connect(Node* root) {
        if (!root) return root;
        Node dummy_head(0, nullptr, nullptr, nullptr), *tail = &dummy_head;
        for (auto p = root; p; p = p->next) {
            if (p->left) {
                tail->next = p->left;
                tail = tail->next;
            }
            if (tail->next) break; // 已经连上的没必要再连一遍
            if (p->right) {
                tail->next = p->right;
                tail = tail->next;
            }
            if (tail->next) break;
        }
        connect(root->right);
        connect(root->left);
        return root;
    }
};

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> m;
        for (int n : nums1) {
            ++m[n];
        }
        vector<int> res;
        for (int n : nums2) {
            if (m[n] > 0) {
                --m[n];
                res.push_back(n);
            }
        }
        return res;
    }
};

/**
 * 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:
    bool hasPathSum(TreeNode* root, int sum) {
        if (!root) return false;
        if (root->val == sum && !root->left && !root->right) return true;
        return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
    }
};

/**
 * 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:
    bool hasPathSum(TreeNode* root, int sum) {
        if (!root) return false;
        if (!root->left && !root->right) return root->val == sum;
        return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
    }
};

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        dfs(1, k, n);
        return res;
    }

    void dfs(int b, int k, int n) {
        if (v.size() == k) {
            res.push_back(v);
            return;
        }
        for (int i = b; i <= n && v.size() + n - i + 1 >= k; ++i) { // 第二个终止条件是一个优化 表示剩余的数加到v里也不够k个则不再往下做了 可有可无 （当前是i之前已经查看了i -1个数放了v.size()个数 所以是v.size() + n - (i - 1)要至少为k）
            v.push_back(i);
            dfs(i + 1, k, n);
            v.pop_back();
        }
    }

    vector<int> v;
    vector<vector<int>> res;
};

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        if (n <= 0 || k <= 0) return {};
        vector<vector<int>> res;
        for (int i = 1; i <= n; ++i) {
            res.push_back({i});
        }
        for (int i = 2; i <= k; ++i) {
            vector<vector<int>> t;
            for (int j = 1; j <= n; ++j) {
                for (const auto &v : res) {
                    if (v.back() >= j) break;
                    t.push_back(v);
                    t.back().push_back(j);
                }
            }
            t.swap(res);
        }
        return res;
    }
};

class Solution {
public:
    int compress(vector<char>& chars) {
        int n = chars.size(), res = 0;
        for (int i = 0, j = 1; i < n; i = j) { // 一次循环过后chars[j]已经跟chars[i]不一样，把i设成新的j
            while (j < n && chars[j] == chars[i]) { // j从i开始往后找第一个跟chars[i]不一样的chars[j]
                ++j;
            }
            chars[res++] = chars[i]; // 写chars[i]
            if (i + 1 == j) continue; // 如果chars[i]只有一个字母，则不需要写个数
            for (char c : to_string(j - i)) { // 写字母个数
                chars[res++] = c;
            }
        }
        return res;
    }
};

/**
 * 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:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for (int i = 0; i < inorder.size(); ++i) {
            m[inorder[i]] = i;
        }
        return helper(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
    }

    TreeNode *helper(const vector<int> &preorder, int pl, int pr, const vector<int> &inorder, int il, int ir) {
        if (pl > pr) return nullptr;
        auto res = new TreeNode(preorder[pl]);
        int lpl = pl + 1;
        int lir = m[preorder[pl]] - 1;
        int lil = il;
        int lpr = lpl + lir - lil;
        res->left = helper(preorder, lpl, lpr, inorder, lil, lir);
        int rpl = lpr + 1;
        int rpr = pr;
        int ril = lir + 2;
        int rir = ir;
        res->right = helper(preorder, rpl, rpr, inorder, ril, rir);
        return res;
    }

    unordered_map<int, int> m;
};

/**
 * 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:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for (auto it = begin(inorder); it != end(inorder); ++it) {
            m[*it] = it;
        }
        return helper(begin(preorder), end(preorder), begin(inorder), end(inorder));
    }

    using It = vector<int>::iterator;
    TreeNode *helper(It pb, It pe, It ib, It ie) {
        if (pb == pe) return nullptr;
        auto res = new TreeNode(*pb);
        auto it = m[*pb];
        int d = distance(ib, it);
        res->left = helper(pb + 1, pb + d + 1, ib, it);
        res->right = helper(pb + d + 1, pe, it + 1, ie);
        return res;
    }

    unordered_map<int, It> m;
};

/**
 * 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:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return helper(preorder.begin(), preorder.end(), inorder.begin(), inorder.end());
    }

    using Iter = vector<int>::iterator;

    TreeNode *helper(Iter pb, Iter pe, Iter ib, Iter ie) {
        if (pb >= pe || ib >= ie) return nullptr;
        int v = *pb;
        TreeNode *root = new TreeNode(v);
        auto it = find(ib, ie, v);
        int dist = distance(ib, it);
        root->left = helper(pb + 1, pb + dist + 1, ib, it);
        root->right = helper(pb + dist + 1, pe, it + 1, ie);
        return 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:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int pn = preorder.size(), in = inorder.size();
        return helper(preorder, 0, pn - 1, inorder, 0, in - 1);
    }

    TreeNode *helper(const vector<int> &p, int pl, int pr, const vector<int> &i, int il, int ir) {
        if (pl > pr || il > ir) return nullptr;
        int v = p[pl];
        TreeNode *root = new TreeNode(v);
        int ri = il;
        for (int j = il; j <= ir; ++j) {
            if (i[j] == v) {
                ri = j;
                break;
            }
        }
        root->left = helper(p, pl + 1, pl + ri - il, i, il, ri - 1);
        root->right = helper(p, pr + ri - ir + 1, pr, i, ri + 1, ir);
        return root;
    }
};

class MyHashMap {
public:
    /** Initialize your data structure here. */
    MyHashMap() {
        m.resize(n);
    }

    /** value will always be non-negative. */
    void put(int key, int value) {
        auto it = find(key);
        if (it != end(m[key % n])) {
            it->second = value;
        } else {
            m[key % n].emplace_back(key, value);
        }
    }

    /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
    int get(int key) {
        auto it = find(key);
        return it != end(m[key % n]) ? it->second : -1;
    }

    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    void remove(int key) {
        auto it = find(key);
        if (it != end(m[key % n])) {
            m[key % n].erase(it);
        }
    }

    list<pair<int, int>>::iterator find(int key) {
        auto& lst = m[key % n];
        auto pred = [key](const auto &p) { return key == p.first; };
        return find_if(begin(lst), end(lst), pred);
    }

    int n = 1001;
    vector<list<pair<int, int>>> m;
};

/**
 * Your MyHashMap object will be instantiated and called as such:
 * MyHashMap* obj = new MyHashMap();
 * obj->put(key,value);
 * int param_2 = obj->get(key);
 * obj->remove(key);
 */

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int total = 0, n = gas.size(), res = 0;
        for (int i = 0, sum = 0; i < n; ++i) {
            total += gas[i] - cost[i];
            sum += gas[i] - cost[i];
            if (sum < 0) {
                res = i + 1;
                sum = 0;
            }
        }
        return total < 0 ? -1 : res;
    }
};

class NumArray {
public:
    NumArray(vector<int>& nums) {
        int n = nums.size();
        presum.resize(n + 1);
        for (int i = 0; i < n; ++i) {
            presum[i + 1] = presum[i] + nums[i];
        }
    }

    int sumRange(int i, int j) {
        return presum[j + 1] - presum[i];
    }

    vector<int> presum;
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * int param_1 = obj->sumRange(i,j);
 */