Leetcode summary of 20200217-20200223

// 393. UTF-8 Validation
// https://leetcode.com/problems/utf-8-validation/
class Solution {
public:
    bool validUtf8(vector<int>& data) {
        if (data.empty()) return false;
        int size = data.size();
        function<bool(int, int)> valid = [&](int i, int n) {
            if ((size - i - 1) < n) return false;
            int j = i + 1;
            while (j <= i + n) {
                if (data[j] < 128 || data[j] > 191) return false;
                ++j;
            }
            return true;
        };
        for (int i = 0; i < size; ++i) {
            if (data[i] < 128) continue;
            else if (data[i] <= 247 && data[i] >= 240) {
                // three
                bool res = valid(i, 3);
                if (!res) return res;
                i = i + 3;
            } else if (data[i] >= 224 && data[i] <=239) {
                // two
                bool res = valid(i, 2);
                if (!res) return res;
                i = i + 2;
            } else if (data[i] >= 192 && data[i] <= 223) {
                // one
                bool res = valid(i, 1);
                if (!res) return res;
                i = i + 1;
            } else {
                return false;
            }
        }
        return true;
    }
};

// 200. Number of Islands
// https://leetcode.com/problems/number-of-islands/
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size();
        if (grid.empty()) return 0;
        int n = grid[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        function<int(int, int)> dfs = [&](int r, int c) {
            if (r >= m || r < 0) return 0;
            if (c >= n || c < 0) return 0 ;
            if (visited[r][c] || grid[r][c] == '0') return 0;
            visited[r][c] = true;
            r+1 < m ? dfs(r+1, c) : 0;
            r > 0 ? dfs(r-1, c) : 0;
            c+1 < n ? dfs(r, c+1): 0;
            c > 0 ? dfs(r, c-1): 0;
            return 0;

        };
        int cnt = 0;
        // cout << "---------" << endl;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                // cout << "visited[i][j]: " << visited[i][j] << endl;
                if (visited[i][j] || grid[i][j] == '0') continue;
                // cout << "i: " << i << " j: " << j << " grid[i][j]: " <<  grid[i][j] << endl;
                dfs(i, j);
                ++cnt;
            }
        }
        return cnt;
    }
};

// 138. Copy List with Random Pointer
// https://leetcode.com/problems/copy-list-with-random-pointer/
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (!head) return head;
        Node* h = head;
        while (head) {
            // cout << "valxx: " << head->val <<endl;
            auto next = head->next;
            Node* node = new Node(head->val);
            head->next = node;
            node->next = next;
            head = next;
        }
        // cout << "h->val: " << h->val <<endl;
        // p(h);
        // cout << "XXX" << endl;
        head = h;
        while (head) {
            auto next = head->next;
            if (head->random)
                next->random = head->random->next;
            head = head->next->next;
        }
        Node e(0), o(0);
        auto even = &e;
        auto odd = &o;
        head = h;
        while (head) {
            auto next = head->next;
            odd->next = head;
            head = next->next;
            odd = odd->next;
            odd->next = nullptr;
            even->next = next;
            even = even->next;
            even->next = nullptr;
        }
        even->next = nullptr;
        odd->next = nullptr;
        //vp(e.next);p(o.next);
        return e.next;
    }
    void p(Node* n) {
        cout << "val = ";
        while (n) {
            cout << n->val << ",";
            n = n->next;
        }
        cout << "。" << endl;
    }
};

// 148. Sort List
// https://leetcode.com/problems/sort-list/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        function<ListNode*(ListNode*, ListNode*)> merge = [](
            ListNode* l, ListNode* r
        ) {
            if (!l) return r;
            if (!r) return l;
            ListNode dummy(0); ListNode* head = &dummy;
            while (l || r) {
                if (!l) {
                    head->next = r;
                    r = r->next;
                } else if (!r) {
                    head->next = l;
                    l = l->next;
                } else {
                    if (l->val < r->val) {
                        head->next = l;
                        l = l->next;
                    } else {
                        head->next = r;
                        r = r->next;
                    }
                }
                head = head->next;
            }
            return dummy.next;
        };
        function<ListNode*(ListNode*)> mid = [](ListNode* node) {
            if (!node || !node->next) return node;
            auto slow = node;
            auto fast = node->next;
            while (fast && fast->next) {
                slow = slow->next;
                fast = fast->next->next;
            }
            return slow;
        };
        if (!head || !head->next) return head;
        auto m = mid(head);
        // cout << "mid: " << m->val << endl;
        ListNode* n = m->next;
        m->next = nullptr;
        // p(head); p(n);
        auto l = sortList(head);
        auto r = sortList(n);
        return merge(l, r);
    }
    void p(ListNode* n) {
        if (!n) cout << "shit" << endl;
        while (n) {
            cout << n->val << ",";
            n = n->next;
        }
        cout << endl;
    }
};

// 154. Find Minimum in Rotated Sorted Array II
// https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/
class Solution {
public:
    int findMin(vector<int>& nums) {
        int s = 0;
        int e = nums.size();
        if (e == 1) return nums[0];
        if (nums[0] < nums[e-1]) return nums[0];
        // cout << "____________________" << endl;
        // start + 1 = e, only one element,
        // start + 2 = e, mid = start + 1, min(start, start+1)
        while (s < e) {
            int mid = (e-s)/2 + s;
            // cout << "s: " << s << " e: " << e << " mid: " << mid << endl;
            if (mid > 0 && nums[mid] < nums[mid-1]) return nums[mid];
            if (mid + 1 < e && nums[mid] > nums[mid+1]) return nums[mid+1];
            if (nums[mid] < nums[e-1])
                e = mid;
            else if (nums[mid] > nums[e-1])
                s = mid+1;
            // else if (nums[mid] == nums[s]) ++s;
            else if (nums[mid] == nums[e-1]) --e;
            // cout << "s: " << s << " e: " << e << " mid: " << mid << endl;
        }
        // cout << "s: " << s << " e: " << e << endl;
        return s > 0 ?nums[s-1] : nums[s];
    }
};

// 153. Find Minimum in Rotated Sorted Array
// https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/
class Solution {
public:
    int findMin(vector<int>& nums) {
        int s = 0;
        int e = nums.size();
        if (e == 1) return nums[0];
        if (nums[0] < nums[e-1]) return nums[0];
        // cout << "____________________" << endl;
        // start + 1 = e, only one element,
        // start + 2 = e, mid = start + 1, min(start, start+1)
        while (s < e) {
            int mid = (e-s)/2 + s;
            // cout << "s: " << s << " e: " << e << " mid: " << mid << endl;
            if (mid > 0 && nums[mid] < nums[mid-1]) return nums[mid];
            if (mid + 1 < e && nums[mid] > nums[mid+1]) return nums[mid+1];
            if (nums[mid] < nums[e-1])
                e = mid;
            else if (nums[mid] > nums[s])
                s = mid+1;
            else
                --e;
            // cout << "s: " << s << " e: " << e << " mid: " << mid << endl;
        }
        // cout << "s: " << s << " e: " << e << endl;
        return -1;
    }
};

// 150. Evaluate Reverse Polish Notation
// https://leetcode.com/problems/evaluate-reverse-polish-notation/
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        if (tokens.empty()) return 0;
        if (tokens.size() == 1) return stoi(tokens[0]);
        stack<int> st;
        function<int(int, int, char)> calc = [](int l, int r, char c) {
            switch(c) {
                case '+': return l+r;
                case '-': return l-r;
                case '*': return l*r;
                case '/': return l/r;
                default:
                    return 0;
            }
        };
        function<bool(string&)> is_op = [](string& s) {
            return s.size()==1 &&(s[0]=='+' || s[0] == '-' || s[0] =='/' || s[0] =='*');
        };
        for (string& s : tokens) {
            if (is_op(s)) {
                auto r = st.top(); st.pop();
                auto l = st.top(); st.pop();
                st.push(calc(l, r, s[0]));
            } else {
                st.push(stoi(s));
            }
        }
        return st.top();
    }
};

// 130. Surrounded Regions
// https://leetcode.com/problems/surrounded-regions/
class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int m = board.size();
        if (m == 0) return;
        int n = board[0].size();
        function<void(int, int)> color = [&](int row, int col) {
            if (row >= m || row < 0) return;
            if (col >= n || col < 0) return;
            if (board[row][col] != 'O') return;
            board[row][col] = 'Y';
            color(row+1, col);
            color(row-1, col);
            color(row, col+1);
            color(row, col-1);
        };
        for (int i = 0; i < n; ++i) {
            color(0, i);
            color(m-1, i);
        }
        for (int i = 0; i < m; ++i) {
            color(i, 0);
            color(i, n-1);
        }
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == 'Y') board[i][j] = 'O';
                else if (board[i][j] == 'O') board[i][j] = 'X';
            }
        }
    }
};

// 117. Populating Next Right Pointers in Each Node II
// https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/
/*
// 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_space(Node* root) {
        if (!root) return root;
        vector<Node*> cur;
        vector<Node*> next;
        cur.push_back(root);
        while (!cur.empty()) {
            auto b = begin(cur);
            auto e = end(cur);
            while (b != e) {
                auto c = b;
                ++b;
                if (b != e) {
                    (*c)->next = *b;
                }
                if ((*c)->left) next.push_back((*c)->left);
                if ((*c)->right) next.push_back((*c)->right);
            }
            cur.swap(next);
            next.clear();
        }
        return root;
    }
    Node* connect(Node* root) {
        function<int(Node*)> height = [&](Node* node) {
            if (!node) return 0;
            int left = node->left? height(node->left): 0;
            int right = node->right? height(node->right): 0;
            return 1 + max(left, right);
        };
        function<Node*(Node*, int, int, bool)> node_of_height = [&](Node* node, int height, int target, bool left) {
            if (height == target || !node) return node;
            if (left) {
                // leftmost
                auto l = node_of_height(node->left, height+1, target, left);
                return l? l : node_of_height(node->right, height+1, target, left);
            } else {
                // rightmost
                auto r = node_of_height(node->right, height+1, target, left);
                return r? r : node_of_height(node->left, height+1, target, left);
            }
        };
        function<void(Node*)> traverse = [&](Node* node) {
            if (!node) return;
            auto l = node->left;
            auto r = node->right;
            int target = min(height(l), height(r));
            int h = 1;
            while (h <= target) {
                auto ll = node_of_height(l, 1, h, false);
                auto rr = node_of_height(r, 1, h, true);
                ll->next = rr;
                ++h;
            }
            traverse(node->left);
            traverse(node->right);
        };
        traverse(root);
        return root;
    }
};

// 103. Binary Tree Zigzag Level Order Traversal
// https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/submissions/
/**
 * 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:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> res;
        vector<TreeNode*> dq;
        if (!root) return res;
        dq.push_back(root);
        bool reversed = false;
        function<void(vector<TreeNode*>&)> traverse = [&](
            vector<TreeNode*>& dq
        ) {
            vector<TreeNode*> next;
            vector<int> v;
            for_each(begin(dq), end(dq), [&] (TreeNode* node
            ) {
                v.push_back(node->val);
                if (node->left) next.push_back(node->left);
                if (node->right) next.push_back(node->right);
            });
            if (reversed) {
                reverse(begin(v), end(v));
            }
            res.push_back(v);
            reversed = !reversed;
            dq.swap(next);
        };
        while (!dq.empty()) {
            traverse(dq);
        }
        return res;
    }
};

// 116. Populating Next Right Pointers in Each Node
// https://leetcode.com/problems/populating-next-right-pointers-in-each-node/
/*
// 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_space(Node* root) {
        if (!root) return root;
        vector<Node*> cur;
        vector<Node*> next;
        cur.push_back(root);
        while (!cur.empty()) {
            auto b = begin(cur);
            auto e = end(cur);
            while (b != e) {
                auto c = b;
                ++b;
                if (b != e) {
                    (*c)->next = *b;
                }
                if ((*c)->left) next.push_back((*c)->left);
                if ((*c)->right) next.push_back((*c)->right);
            }
            cur.swap(next);
            next.clear();
        }
        return root;
    }
    Node* connect(Node* root) {
        function<void(Node*)> traverse = [&](Node*node) {
            if (!node) return;
            auto left = node->left;
            auto right = node->right;
            while (left && left->right && right->left) {
                auto l = left->right;
                auto r = right->left;
                l->next = r;
                left = l;right = r;
            }

            if (node->left) {
                node->left->next = node->right;
            }
            traverse(node->left);
            traverse(node->right);
        };
        traverse(root);
        return root;
    }
};

// 1352. Product of the Last K Numbers
// https://leetcode.com/problems/product-of-the-last-k-numbers/
class ProductOfNumbers {
    int prod;
    vector<int> bkp;
    vector<int> zeros;
public:
    ProductOfNumbers() {
        prod = 1;
        bkp.push_back(1);
    }

    void add(int num) {
        prod *= num;
        prod = max(1, prod);
        if (num == 0) {
            zeros.push_back(bkp.size());
        }
        bkp.push_back(prod);
    }
    // 2, 3, 0
    // {1} -> {1, 2} -> {1, 2, 6, 1}
    // {3}

    // {1, 3, 1, 2, 10, 40}
    // {2}
    // 2,3,4

    int getProduct(int k) {
        int size = bkp.size();
        int n = bkp[size - k - 1];
        auto ite = upper_bound(begin(zeros), end(zeros), size-k-1);
        /*
        cout << "k: " << k << " size: " << size << endl;
        cout << "size-k-1: " << size-k-1 << endl << "zeros: ";
        copy(zeros.begin(), zeros.end(), ostream_iterator<int>(cout, ","));
        cout << endl;
        cout << "ite == zeros.end(): " << (ite == zeros.end()) << endl;
        */
        if (ite != zeros.end()) return 0;
        else return bkp.back() / bkp[size-k-1];
    }
};

/**
 * Your ProductOfNumbers object will be instantiated and called as such:
 * ProductOfNumbers* obj = new ProductOfNumbers();
 * obj->add(num);
 * int param_2 = obj->getProduct(k);
 */

// 1347. Minimum Number of Steps to Make Two Strings Anagram
// https://leetcode.com/problems/minimum-number-of-steps-to-make-two-strings-anagram/
class Solution {
public:
    int minStepsAlgo(string s, string t) {
        sort(s.begin(), s.end());
        sort(t.begin(), t.end());
        string r;
        set_difference(s.begin(), s.end(), t.begin(), t.end(), back_inserter(r));
        return r.size();
    }
    int minSteps(string s, string t) {
        array<int, 26> s1 = {0};
        array<int, 26> s2 = {0};
        int size = s.size();
        for (int i = 0; i < size; ++i) {
            ++s1[s[i]-'a'];
            ++s2[t[i]-'a'];
        }
        int res = 0;
        for (int i = 0; i < 26; ++i) {
            // cout << "i: " << i << " s1[i]: " << s1[i] << " s2[i]: " << s2[i] << endl;
            if (s1[i] > s2[i]) {
                res += (s1[i] - s2[i]);
            }
        }
        return res;
    }
};

// 93. Restore IP Addresses
// https://leetcode.com/problems/restore-ip-addresses/
class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        int size = s.size();
        vector<string> res;
        if (size < 4 || size > 12) return res;
        for (int i = 0; i < 3; ++i) {
            string s1 = s.substr(0, i+1);
            int n1 = stoi(s1);
            if (n1 > 255) break;
            if (s1.size() > 1 && s1[0] == '0') break;
            for (int j = i+1; j < min(i+4, size); ++j) {
                string s2 = s.substr(i+1, j-i);
                int n2 = stoi(s2);
                if (n2 > 255) break;
                if (s2.size() > 1 & s2[0] == '0') break;
                for (int k = j+1; k < min(j+4, size-1); ++k) {
                    string s3 = s.substr(j+1, k-j);
                    string s4 = s.substr(k+1);
                    if (s4.size() > 3) continue;
                    int n3 = stoi(s3);
                    int n4 = stoi(s4);
                    // cout << s1 << " " << s2 << " " << s3 << " " << s4 << endl;
                    if (n3 > 255) break;
                    if (s3.size() > 1 && s3[0] == '0') break;
                    if (n4 > 255 || (s4.size() > 1 && s4[0] == '0')) continue;
                    res.push_back(move(s1+"."+s2+"."+s3+"."+s4));
                }
            }
        }
        return res;
    }
};

// 79. Word Search
// https://leetcode.com/problems/word-search/
class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int m = board.size();
        int n = board[0].size();
        int word_size = word.size() - 1;
        vector<vector<bool>> flag(m, vector<bool>(n, false));
        function<bool(int, int, int)> search = [&](int row, int col, int index) {
            if (row >= m || row < 0) return false;
            if (col >= n || col < 0) return false;
            if (flag[row][col]) return false;
            if (board[row][col] != word[index]) return false;

            flag[row][col] = true;
            // cout << "index: " << index << " word_size: " << word_size << endl;
            // cout << "row: " << row << " col: "<< col<<endl;
            if (index == word_size) return true;
            bool res = search(row+1, col, index+1) || search(row-1, col, index+1) || search(row, col+1, index+1) || search(row, col-1, index+1);
            flag[row][col] = false;
            return res;
        };
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (search(i, j, 0)) return true;
            }
        }
        return false;
    }
};

// 80. Remove Duplicates from Sorted Array II
// https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/
class Solution {
public:
    int removeDuplicatesComplex(vector<int>& nums) {
        int size = nums.size();
        int count = 0;
        int prev = -1;
        int j = 0;
        for (int i = 0; i < size; ++i) {
            if (count == 0 || nums[i] != prev) {
                prev = nums[i];
                nums[j] = nums[i];
                ++j;
                count = 1;
            } else if (nums[i] == prev) {
                ++count;
                nums[j] = nums[i];
                ++j;
                if (count == 2) {
                    while (i < size && nums[i] == prev) ++i;
                    count = 0;
                    --i;
                }
            }
        }
        return j;
    }
    int removeDuplicates(vector<int>& nums) {
        int size = nums.size();
        if (size < 3) return size;
        int index = 2;
        for (int i = 2; i < size; ++i) {
            if (nums[i] != nums[index-2]) {
                nums[index++] = nums[i];
            }
        }
        return index;
    }
};

// 96. Unique Binary Search Trees
// https://leetcode.com/problems/unique-binary-search-trees/
class Solution {
public:
    int numTrees(int n) {
        // use dp with cache
        unordered_map<int, int> _c;
        _c[0] = 1;
        _c[1] = 1;
        _c[2] = 2;
        function<int(int)>  dp = [&](int n) {
            if (_c.find(n) != _c.end()) {
                return _c[n];
            }
            int sum = 0;
            for (int i = 1; i <= n; ++i) {
                sum += dp(i - 1) * dp(n - i);
            }
            _c[n] = sum;
            return sum;
        };
        return dp(n);
    }
};

// 109. Convert Sorted List to Binary Search Tree
// https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * 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 {
    // 1 2
    //
    // 1
    // 1 2 3
public:
    TreeNode* sortedListToBST(ListNode* head) {
        function<TreeNode*(ListNode*, ListNode*)> convert = [&](
            ListNode* start, ListNode* end
        ) ->TreeNode* {
            if (!start || !end) return nullptr;
            if (start->val > end->val) return nullptr;
            ListNode* slow = start;
            ListNode* fast = start->next;
            ListNode* prev = nullptr;
            while (fast && fast->val < end->val) {
                prev = slow;
                slow = slow->next;
                fast = fast->next;
                if (fast->val == end->val) break;
                fast = fast->next;
            }
            TreeNode* cur = new TreeNode(slow->val);
            cur->left = convert(start, prev);
            cur->right = convert(slow->next, end);
            return cur;
        };
        ListNode* node = head;
        ListNode* end = head;
        while (node) {
            end = node;
            node = node->next;
        }
        return convert(head, end);
    }
};

// 98. Validate Binary Search Tree
// https://leetcode.com/problems/validate-binary-search-tree/
/**
 * 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 isValidBST(TreeNode* root) {
        if (!root) return true;
        function<bool(TreeNode*, long long, long long)> valid_tree = [&](
            TreeNode* node,
            long long l,
            long long r)
        {
            if (!node) return true;
            auto val = node->val;
            if (val <= l || val >= r) return false;
            return valid_tree(node->left, l, val) && valid_tree(node->right, val, r);
        };
        return valid_tree(root, LLONG_MIN, LLONG_MAX);
    }
};

// 1025. Divisor Game
// https://leetcode.com/problems/divisor-game/
class Solution {
public:
    bool divisorGame(int N) {
        return !(N%2);
    }
};

// 1071. Greatest Common Divisor of Strings
// https://leetcode.com/problems/greatest-common-divisor-of-strings/
class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        int s1 = str1.size();
        int s2 = str2.size();
        if (s1 > s2) {
            swap(s1, s2);
            str1.swap(str2);
        }
        // find all factors
        stack<int> fac;
        for (int i = 1; i <= s1; ++i) {
            if (s1 % i == 0) fac.push(i);
        }
        function<bool(string&, string&)> repeat = [](
            string& target,  string& rep
        ) {
            int size = rep.size();
            int s = target.size();
            if (s % size != 0) return false;
            string tmp;
            int time = s / size;
            while (time--) tmp += rep;
            return tmp == target;
        };
        while(!fac.empty()) {
            auto factor = fac.top(); fac.pop();
            string t = str1.substr(0, factor);
            bool l = repeat(str1, t);
            bool r = repeat(str2, t);
            if (l && r) return t;
        }
        return "";
    }
};

// 1114. Print in Order
// https://leetcode.com/problems/print-in-order/submissions/
class Foo {
public:
    Foo() {
        first_.lock();
        second_.lock();
    }

    void first(function<void()> printFirst) {

        // printFirst() outputs "first". Do not change or remove this line.
        printFirst();
        first_.unlock();
    }

    void second(function<void()> printSecond) {
        first_.lock();
        // printSecond() outputs "second". Do not change or remove this line.
        printSecond();
        second_.unlock();
    }

    void third(function<void()> printThird) {

        second_.lock();
        // printThird() outputs "third". Do not change or remove this line.
        printThird();
        second_.unlock();
    }
private:
    std::mutex first_;
    std::mutex second_;
};

// 748. Shortest Completing Word
// https://leetcode.com/problems/shortest-completing-word/
class Solution {
public:
    string shortestCompletingWord(string licensePlate, vector<string>& words) {
        vector<int> src(26, 0);
        for_each(
            begin(licensePlate),
            end(licensePlate),
            [&](char c) {
                c = tolower(c);
                if (c >= 'a' && c <= 'z') {
                    ++src[c-'a'];
                }
            }
        );
        string result;
        for (string& word: words) {
            vector<int> dst(26, 0);

            for_each(
                begin(word),
                end(word),
                [&](char c) {
                    ++dst[c-'a'];
                }
            );
            bool res = [&]() {
                for (int i = 0; i < 26; ++i) {
                    if (dst[i] < src[i])
                        return false;
                }
                return true;
            }();
            if (res && (result.empty() || word.size() < result.size())) {
                result = word;
            };
        }

        return result;

    }
};

// 733. Flood Fill
// https://leetcode.com/problems/flood-fill/
class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        // 1 1 1
        // 1 1 0
        // 1 0 1
        int m = image.size();
        int n = image[0].size();
        int srcColor = image[sr][sc];
        vector<vector<bool>> flag(m, vector<bool>(n, false));
        function<void(int, int)> dfs = [&](int sr, int sc) {
            if (sr < 0 || sr >= m) return;
            if (sc < 0 || sc >= n) return;
            if (image[sr][sc] != srcColor || flag[sr][sc]) return;
            flag[sr][sc] = true;
            image[sr][sc] = newColor;
            dfs(sr-1, sc);
            dfs(sr+1, sc);
            dfs(sr, sc-1);
            dfs(sr, sc+1);
        };
        dfs(sr, sc);
        return image;
    }
};

// 836. Rectangle Overlap
// https://leetcode.com/problems/rectangle-overlap/
class Solution {
public:
    bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) {
        if (rec1[0]>=rec2[2] || rec2[0]>=rec1[2]) return false;
        if (rec1[1]>=rec2[3] || rec2[1]>=rec1[3]) return false;
        return true;
    }
};

// 999. Available Captures for Rook
// https://leetcode.com/problems/available-captures-for-rook/
class Solution {
public:
    int numRookCaptures(vector<vector<char>>& board) {
        int cnt = 0;
        int mx, my;
        [&]() {
            for (mx = 0; mx < 8; ++mx) {
                for (my = 0; my < 8; ++my) {
                    if (board[mx][my] != 'R') continue;
                    else return;
                }
            }
        }();
        /*
        for (mx = 0; mx < 8; ++mx) {
            for (my = 0; my < 8; ++my) {
                if (board[mx][my] != 'R') continue;
                else goto SHIT;
            }
        }
        */
        // right
        int z = my;
        while (z < 8) {
            if (board[mx][z] == 'B') break;
            else if (board[mx][z] == 'p') { ++cnt; break;}
            ++z;
        }
        // left
        z = my;
        while (z >= 0) {
            if (board[mx][z] == 'B') break;
            else if (board[mx][z] == 'p') { ++cnt; break;}
            --z;
        }
        // down
        z = mx;
        while (z < 8) {
            if (board[z][my] == 'B') break;
            else if (board[z][my] == 'p') { ++cnt; break;}
            ++z;
        }
        // up
        z = mx;
        while (z >= 0) {
            if (board[z][my] == 'B') break;
            else if (board[z][my] == 'p') { ++cnt; break;}
            --z;
        }
        return cnt;
    }
};

// 1033. Moving Stones Until Consecutive
// https://leetcode.com/problems/moving-stones-until-consecutive/
class Solution {
public:
    vector<int> numMovesStones(int a, int b, int c) {
        vector<int> v{a, b, c};
        sort(begin(v), end(v));
        int diff1 = v[1] - v[0];
        int diff2 = v[2] - v[1];
        if (diff1 > diff2) swap(diff1, diff2);
        int m = 0;
        if (diff1 == 1 && diff2 == 1) m = 0;
        else if (diff1 == 1 || diff2 == 1) m = 1;
        else if (diff1 == 2 || diff2 == 2) m = 1;
        else m = 2;
        return {m, diff1 + diff2 - 2};
    }
};

// 1103. Distribute Candies to People
// https://leetcode.com/problems/distribute-candies-to-people/
class Solution {
public:
    vector<int> distributeCandies(int candies, int num_people) {
        // 1 2 ... n = 0*n^2 + prev
        // n+1 n+2 ... 2*n = 1*n^2 + prev
        // 2*n+1 2*n+2 ... 2*n+n = 2*n^2 + prev
        // n*n (0 + k)*k/2 + k * n(n+1)/2 = candies line K
        int sq = num_people * num_people;
        int k = 0;
        while ( k * (k+1) * sq / 2 + (sq+num_people)/2 * (k+1) <= candies) {
            ++k;
        }
        k =  max(k-1, 0);
        vector<int> res(num_people, 0);
        int candies1 = candies;
        for (int i = 0; i < num_people; ++i) {
            res[i] = (k+1) * (i+1) + (0 + k) * (k+1) / 2 * num_people;
            res[i] = min(candies1, res[i]);
            candies1 -= res[i];
            if (candies1 < 0) break;
        }
        int remain = candies - k * (k+1) * sq / 2 - (sq+num_people)/2 * (k+1);
        // if (remain < 0) { res.back() += remain; return res;}
        // cout << "k: " << k << " remain: " << remain << " sq:" << sq << endl;
        ++k;
        // cout << "res[0] = " << res[0] << endl;
        for (int i = 0; remain > 0; ++i) {
            int diff = min(remain, k * num_people + i + 1);
            res[i] += diff;
            remain -= diff;
        }
        return res;
    }
};

// 942. DI String Match
// https://leetcode.com/problems/di-string-match/
class Solution {
public:
    vector<int> diStringMatch(string S) {
        S += 'I';
        int N = S.size() - 1;
        int M = 0;
        vector<int> res; res.reserve(N+1);
        for (char c : S) {
            if (c == 'I') {
                res.push_back(M++);
            } else {
                res.push_back(N--);
            }
        }
        return res;
    }
};

// 888. Fair Candy Swap
// https://leetcode.com/problems/fair-candy-swap/
class Solution {
public:
    vector<int> fairCandySwap(vector<int>& A, vector<int>& B) {
        A.swap(B);
        int s_a = accumulate(begin(A), end(A), 0);
        int s_b = 0;
        unordered_set<int> num;
        for_each(
            begin(B),
            end(B),
            [&](int n) {
                s_b += n;
                num.insert(n);
            }
        );
        int avg = (s_a + s_b) / 2;
        int diff = avg - s_a;
        int size = A.size();
        for (int i = 0; i < size; ++i) {
            if (num.find(A[i] + diff) != num.end()) {
                return {A[i]+diff, A[i]};
            }
        }
        return {0, 0};
    }
};

// 806. Number of Lines To Write String
// https://leetcode.com/problems/number-of-lines-to-write-string/
class Solution {
public:
    vector<int> numberOfLines(vector<int>& widths, string S) {
        int cur_sum = 0;
        int lines = 1;
        const int L = 100;
        for (char c : S) {
            int len = widths[c - 'a'];
            if (cur_sum + len <= L) {
                cur_sum += len;
            } else {
                ++lines;
                cur_sum = len;
            }
        }
        return {lines, cur_sum};
    }
};

// 690. Employee Importance
// https://leetcode.com/problems/employee-importance/
/*
// Employee info
class Employee {
public:
    // It's the unique ID of each node.
    // unique id of this employee
    int id;
    // the importance value of this employee
    int importance;
    // the id of direct subordinates
    vector<int> subordinates;
};
*/
class Solution {
public:
    int getImportance(vector<Employee*> employees, int id) {
        unordered_map<int, Employee*> m;
        for_each(
            begin(employees),
            end(employees),
            [&](Employee* e) {
                m[e->id] = e;
            }
        );
        vector<int> st; st.push_back(id);
        int sum = 0;
        while (!st.empty()) {
            vector<int> next;
            while (!st.empty()) {
                auto e = m[st.back()];
                sum += e->importance;
                copy(e->subordinates.begin(), e->subordinates.end(), back_inserter(next));
                st.pop_back();
            }
            st.swap(next);
        }
        return sum;
    }
};

// 884. Uncommon Words from Two Sentences
// https://leetcode.com/problems/uncommon-words-from-two-sentences/
class Solution {
public:
    vector<string> uncommonFromSentences(string A, string B) {
        istringstream iss1(A), iss2(B);
        unordered_map<string, int>m;
        for_each(
            istream_iterator<string>(iss1),
            istream_iterator<string>(),
            [&](const string& s) { ++m[s];}
        );
        for_each(
            istream_iterator<string>(iss2),
            istream_iterator<string>(),
            [&](const string& s) { ++m[s];}
        );
        vector<string> result;

        for_each(
            begin(m),
            end(m),
            [&](auto& v) {
                if (v.second == 1)
                    result.push_back(v.first);
            }
        );


        return result;

    }
};

// 976. Largest Perimeter Triangle
// https://leetcode.com/problems/largest-perimeter-triangle/
class Solution {
public:
    int largestPerimeter(vector<int>& A) {
        sort(A.begin(), A.end(), [](int a, int b) {return a > b;});
        function<bool(int, int, int)> valid = [](int a, int b, int c) {
            return (a+b) > c;
        };
        int size = A.size();
        int m = 0;
        int K = size;
        for (int i = 0; i < size - 2; ++i) {
            if (valid(A[i+1], A[i+2], A[i])) {
                return A[i] + A[i+1] + A[i+2];
            }
        }
        return m;
    }
};

// 1351. Count Negative Numbers in a Sorted Matrix
// https://leetcode.com/problems/count-negative-numbers-in-a-sorted-matrix/
class Solution {
public:
    int countNegativesNaive(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int cnt = 0;
        for_each(begin(grid), end(grid),
                [&](const vector<int>& v) {
                    for_each(begin(v), end(v),
                            [&](int vv) { cnt += vv < 0;});
                });
        return cnt;
    }
    int countNegatives(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int cnt = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] < 0) {
                    cnt += (n - j) * (m - i);
                    n = j;
                    break;
                }
            }
        }
        return cnt;
    }

};