Leetcode summary of 20200217-20200223

Posted by chunyang on February 24, 2020

Summary

Solved problems list

  • 393. UTF-8 Validation
  • 200. Number of Islands
  • 138. Copy List with Random Pointer
  • 148. Sort List
  • 154. Find Minimum in Rotated Sorted Array II
  • 153. Find Minimum in Rotated Sorted Array
  • 150. Evaluate Reverse Polish Notation
  • 130. Surrounded Regions
  • 117. Populating Next Right Pointers in Each Node II
  • 103. Binary Tree Zigzag Level Order Traversal
  • 116. Populating Next Right Pointers in Each Node
  • 1352. Product of the Last K Numbers
  • 1347. Minimum Number of Steps to Make Two Strings Anagram
  • 93. Restore IP Addresses
  • 79. Word Search
  • 80. Remove Duplicates from Sorted Array II
  • 96. Unique Binary Search Trees
  • 109. Convert Sorted List to Binary Search Tree
  • 98. Validate Binary Search Tree
  • 1025. Divisor Game
  • 1071. Greatest Common Divisor of Strings
  • 1114. Print in Order
  • 748. Shortest Completing Word
  • 733. Flood Fill
  • 836. Rectangle Overlap
  • 999. Available Captures for Rook
  • 1033. Moving Stones Until Consecutive
  • 1103. Distribute Candies to People
  • 942. DI String Match
  • 888. Fair Candy Swap
  • 806. Number of Lines To Write String
  • 690. Employee Importance
  • 884. Uncommon Words from Two Sentences
  • 976. Largest Perimeter Triangle
  • 1351. Count Negative Numbers in a Sorted Matrix

Highlight

DFS or BFS

Be careful about the visited status when using DFS or BFS. Otherwise, you may get stuck in a dead loop.

Implementation

  • Restore IP Address
    • 0 started string is not valid.
  • UTF-8 Validation
    • Sometimes manipulating numbers is more convenient than bits.

Rotated sorted array

There are two searching problems and two finding problems about rotated sorted arrays.

The key point is that: you need to know which one (the left or the right part) is an increasing sequence.

Finding the minimum element is a little tricky here. You havee to exit when you find targeting pattern, otherwise it is not easy to tell the result when you leave the loop.

Double check here

Code Section

The sequence of code is the same with the problem list.

// 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;
    }

};

Creative Commons License
This work is licensed under a CC A-S 4.0 International License.