leetcode 的刷题之旅

之前已经刷过剑指offer和newcoder上的leetcode140题。如果感兴趣可以去看看那些文章。这篇博客主要是为了记录自己刷leetcode的过程，希望可以刷到300题左右（ps：我自己也不知道什么时候会太监）
话不多说，开始。

class Solution {
public:
    /*
    1. Two Sum: unsorted array, find index
    sumbission: Runtime: 4 ms, faster than 99.70% of C++ online submissions for Two Sum.
    */
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> res;
        map<int, int> mp;
        for (int i = 0; i < nums.size(); i++) {
            int remaining = target - nums[i];
            if (mp.find(remaining) != mp.end()) {
                res.push_back(mp[remaining]);
                res.push_back(i);
                return res;
            }
            else {
                mp[nums[i]] = i;
            }
        }
        return res;
    }
};

class Solution {
public:
    /*
    2. Add two numbers
    Runtime: 16 ms, faster than 97.55% of C++ online submissions for Add Two Numbers.
    */
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* header = new ListNode(0);
        ListNode* node = header;
        int carrier = 0;
        while (l1 || l2) {
            int val = carrier;
            if (l1) val += l1->val;
            if (l2) val += l2->val;
            carrier = val / 10;
            val %= 10;
            ListNode* tmp = new ListNode(val);
            node->next = tmp;
            node = tmp;
            if (l1) l1 = l1->next;
            if (l2) l2 = l2->next;
        }
        if (carrier != 0) {
            ListNode* tmp = new ListNode(carrier);
            node->next = tmp;
            node = tmp;
        }
        return header->next;
    }
};

class Solution {
public:
    /*
    3. Longest Substring Without Repeating Characters
    algorithm is quit easy. the thing need to be remembered is that always assign value to right pointer
    */
    int lengthOfLongestSubstring(string s) {
        char mp[256];
        memset(mp, 0, sizeof(mp));
        int left = 0;
        int right = left;
        int res = 0;
        for (int i = 0; i < s.size(); i++) {
            if (mp[s[i]] == 0) {
                mp[s[i]] ++;
                right = i + 1;
                if (right - left > res) res = right - left; 
            }
            else {
                for (; left < right; left++) {
                    mp[s[left]]--;
                    if (s[left] == s[i]) {
                        mp[s[left]]++;
                        break;
                    }
                }
                left++;
                right = i + 1;
            }
        }
        res = max(res, right - left);
        return res;
    }
};

class Solution {
public:
    /*
    5. Longest Palindromic Substring
    */
    // method 1: dynamic programming. O(n^2)
    // Runtime: 68 ms, faster than 45.51% of C++ online submissions for Longest Palindromic Substring.
    // Memory Usage: 9.8 MB, less than 56.55% of C++ online submissions for Longest Palindromic Substring.
    string longestPalindrome2(string s) {
        int size = s.size();
        if (size == 0) return s;
        bool table[size][size];
        memset(table, 0, sizeof(table));
        table[size-1][size-1] = true;
        int start = 0;
        int len = 0;
        for (int i = size-1; i >= 0; i--) {
            for (int j = size-1; j >= i; j--) {
                if (s[i] == s[j]) {
                    if (j - i <= 1) table[i][j] = true;
                    else if (table[i+1][j-1]) table[i][j] = true;
                    if (j - i >= len && table[i][j]) {
                        start = i;
                        len = j - i;
                    }
                }
            }
        }
        return s.substr(start, len + 1);
    }
    string longestPalindrome(string s) {
        int left = 0, right = 0;
        int len = 0, start = 0;
        for (int i = 0; i < s.size(); i++) {
            // case 1: s[i] is the middle of palidrome
            left = i;
            right = i;
            while (left >= 0 && right <= s.size()-1 && s[left] == s[right]) {
                left--;
                right++;
            }
            if (len < right-left-1) {
                len = right-left-1;
                start = left+1;
            }
            // case 2: s[i] is the middle left of palidrome
            if (i < s.size()-1 && s[i] == s[i+1]) {
                left = i;
                right = i+1;
                while (left >= 0 && right <= s.size()-1 && s[left] == s[right]) {
                    left--;
                    right++;
                }
                if (len < right-left-1) {
                    len = right-left-1;
                    start = left+1;
                }
            }
        }
        return s.substr(start, len);
    }
};

class Solution {
public:
    /*
    6. ZigZag Conversion
    Runtime: 8 ms, faster than 93.37% of C++ online submissions for ZigZag Conversion.
    Memory Usage: 12.7 MB, less than 46.29% of C++ online submissions for ZigZag Conversion.
    */
    string convert(string s, int numRows) {
        if (numRows == 1) return s;
        vector<string> vecstr(numRows, "");
        int ptr = 0;
        int flag = 0;
        int down = true;
        while (ptr < s.size()) {
            vecstr[flag] += s[ptr++];
            if (down) flag++;
            else flag--;
            if (flag >= numRows) {
                down = false;
                flag -= 2;
            }
            if (flag < 0) {
                down = true;
                flag += 2;
            }
        }
        string res;
        for (auto ss : vecstr) {
            res += ss;
        }
        return res;
    }
};

class Solution {
public:
    /*
    7. Reverse Integer
    Runtime: 4 ms, faster than 68.24% of C++ online submissions for Reverse Integer.
    Memory Usage: 8 MB, less than 100.00% of C++ online submissions for Reverse Integer.
    */
    int reverse(int x) {
        long long res = 0;
        while (x) {
            int digit = x % 10;
            x /= 10;
            res *= 10;
            res += digit;
            if (res > INT_MAX || res < INT_MIN) return 0;
        }
        return res;
    }
};

class Solution {
public:
    /*
    8. String to Integer (atoi)
    Runtime: 8 ms, faster than 40.51% of C++ online submissions for String to Integer (atoi).
    Memory Usage: 8.3 MB, less than 100.00% of C++ online submissions for String to Integer       (atoi).
    */
    int myAtoi(string str) {
        if (str.size() == 0) return 0;
        int flag = 1;
        int ptr = 0;
        // move back until first unblank
        for (; ptr < str.size() && str[ptr] == ' '; ptr++);
        // sign of integer
        if (str[ptr] == '-') {
            flag = -1;
            ptr++;
        }
        else if (str[ptr] == '+') {
            flag = 1;
            ptr++;
        }
        long long res = 0;
        for (; ptr < str.size(); ptr++) {
            if (str[ptr] < '0' || str[ptr] > '9') break;
            res *= 10;
            res += str[ptr] - '0';
            if (res * flag > INT_MAX) return INT_MAX;
            if (res * flag < INT_MIN) return INT_MIN;
        }
        return res * flag;
    }
};

class Solution {
public:
    /*
    9. Palindrome Number
    Runtime: 12 ms, faster than 72.81% of C++ online submissions for Palindrome Number.
    Memory Usage: 11.6 MB, less than 12.73% of C++ online submissions for Palindrome Number.
    */
    bool isPalindrome(int x) {
        if (x < 0) return false;
        vector<int> v;
        if (x == 0) v.push_back(0);
        while (x) {
            int digit = x % 10;
            x /= 10;
            v.push_back(digit);
        }
        int half = v.size() / 2;
        for (int i = 0; i <= half; i++) {
            if (v[i] != v[v.size()-i-1]) return false;
        }
        return true;
    }
};

这一题其实蛮有趣的，可以和maxhistogram混合着看。这个要比柱状图简单。但是感觉柱状图更具有逻辑性。

class Solution {
public:
    /*
    11. Container With Most Water
    Runtime: 20 ms, faster than 65.76% of C++ online submissions for Container With Most        Water.
    Memory Usage: 9.8 MB, less than 69.07% of C++ online submissions for Container With Most Water.
    */
    // method 1: brute force search: O(n^2)
    int maxArea2(vector<int>& height) {
        int size = height.size();
        int area = 0;
        for (int i = 0; i < size; i++) {
            for (int j = i; j < size; j++) {
                area = max(area, min(height[i], height[j]) * (j-i));
            }
        }
        return area;
    }
    // method 2: for any two choices, drop the one that is impossible
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size()-1;
        int area = 0;
        while (left < right) {
            area = max(area, min(height[left], height[right]) * (right-left));
            if (height[left] < height[right]) {
                left++;
            }
            else right--;
        }
        return area;
    }
};

class Solution {
public:
    /*
    12. Integer to Roman
    Runtime: 8 ms, faster than 74.82% of C++ online submissions for Integer to Roman.
    Memory Usage: 8.3 MB, less than 100.00% of C++ online submissions for Integer to Roman.
    */
    string intToRoman(int num) {
        string res;
        int numOfM = num / 1000;
        res += string(numOfM, 'M');
        num -= numOfM * 1000;
        if (num >= 900) {
            res += "CM";
            num -= 900;
        }
        int numOfD = num / 500;
        res += string(numOfD, 'D');
        num -= numOfD * 500;
        if (num >= 400) {
            res += "CD";
            num -= 400;
        }
        int numOfC = num / 100;
        res += string(numOfC, 'C');
        num -= numOfC * 100;
        if (num >= 90) {
            res += "XC";
            num -= 90;
        }
        int numOfL = num / 50;
        res += string(numOfL, 'L');
        num -= numOfL * 50;
        if (num >= 40) {
            res += "XL";
            num -= 40;
        }
        int numOfX = num / 10;
        res += string(numOfX, 'X');
        num -= numOfX * 10;
        if (num >= 9) {
            res += "IX";
            num -= 9;
        }
        int numOfV = num / 5;
        res += string(numOfV, 'V');
        num -= numOfV * 5;
        if (num >= 4) {
            res += "IV";
            num -= 4;
        }
        int numOfI = num / 1;
        res += string(numOfI, 'I');
        num -= numOfI * 1;
        return res;
        
    }
};

class Solution {
public:
    /*
    13. Roman to Integer
    Runtime: 8 ms
    Memory Usage: 8.3 MB
    */
    int romanToInt(string s) {
        int mp[256];
        memset(mp, 0, sizeof(mp));
        mp['I'] = 1;
        mp['V'] = 5;
        mp['X'] = 10;
        mp['L'] = 50;
        mp['C'] = 100;
        mp['D'] = 500;
        mp['M'] = 1000;
        int res = 0;
        int pre = 0;
        for (int i = s.size()-1; i >= 0; i--) {
            int addition = mp[s[i]];
            if (pre <= addition) res += addition;
            else res -= addition;
            pre = addition;
        }
        return res;
    }
};

class Solution {
public:
    /*
    14. Longest Common Prefix
    Runtime: 4 ms, faster than 94.86% of C++ online submissions for Longest Common Prefix.
    Memory Usage: 8.9 MB, less than 62.90% of C++ online submissions for Longest Common Prefix.
    */
    // method 1: brute force
    string longestCommonPrefix2(vector<string>& strs) {
        if (strs.size() == 0) return "";
        int ptr = 0;
        for (; ptr < strs[0].size(); ptr++) {
            bool flag = true;
            for (int i = 1; i < strs.size(); i++) {
                if (strs[i].size() > ptr && strs[i][ptr] == strs[0][ptr]) continue;
                else {
                    flag = false; 
                    break;
                }
            }
            if (!flag) break;
        }
        return strs[0].substr(0, ptr);
    }
    // method 2: sort and only neet to compare first and last
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.size() == 0) return "";
        if (strs.size() == 1) return strs[0];
        sort(strs.begin(), strs.end());
        int ptr = 0;
        int size = strs.size() - 1;
        int minlen = min(strs[0].size(), strs[size].size());
        for (; ptr < minlen; ptr++) {
            if (strs[0][ptr] == strs[size][ptr]) continue;
            else break;
        }
        return strs[0].substr(0, ptr);
    }     
};

class Solution {
public:
    /*
    15. 3Sum
    Runtime: 96 ms, faster than 82.78% of C++ online submissions for 3Sum.
    Memory Usage: 15.9 MB, less than 44.71% of C++ online submissions for 3Sum.
    */
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int> > res;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); i++) {
            if (i != 0 && nums[i] == nums[i-1]) continue;
            int left = i + 1, right = nums.size() - 1;
            int remaining = 0 - nums[i];
            while (left < right) {
                if (i == left) {
                    left++;
                    continue;
                };
                if (i == right) {
                    right--;
                    continue;
                }
                int s = nums[left] + nums[right];
                if (s < remaining) {
                    left++;
                }
                else if (s > remaining) {
                    right--;
                }
                else {
                    vector<int> tmp = {nums[i], nums[left], nums[right]};
                    res.push_back(tmp);
                    for (; left < right && nums[left+1] == nums[left]; left++);
                    for (; left < right && nums[right-1] == nums[right]; right--);
                    left ++;
                    right --;
                }
            }
        }
        return res;
    }
};

class Solution {
public:
    /*
    16. 3Sum Closest
    */
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int res = INT_MAX;
        int solution = 0;
        for (int i = 0; i < nums.size(); i++) {
            int left = i + 1;
            int right = nums.size() - 1;
            int remaining = target - nums[i];
            while (left < right) {
                int s = nums[right] + nums[left];
                if (res > abs(remaining - s)) {
                    res = abs(remaining - s);
                    solution = nums[i] + s;
                }
                if (s < remaining) left++;
                else if (s > remaining) right--;
                else return target;
            }
        }
        return solution;
    }
};

class Solution {
public:
    /*
    17. Letter Combinations of a Phone Number
    Runtime: 0 ms, faster than 100.00% of C++ online submissions for Letter Combinations of a Phone Number.
    Memory Usage: 8.5 MB, less than 91.43% of C++ online submissions for Letter Combinations of a Phone
    */
    vector<string> letterCombinations(string digits) {
        if (digits.size() == 0) return res;
        mp.push_back("");
        mp.push_back("");
        mp.push_back("abc");
        mp.push_back("def");
        mp.push_back("ghi");
        mp.push_back("jkl");
        mp.push_back("mno");
        mp.push_back("pqrs");
        mp.push_back("tuv");
        mp.push_back("wxyz");
        
        dfs(digits, 0);
        return res;
    }
    void dfs(string& digits, int pos) {
        if (pos == digits.size()) {
            string s;
            for (auto c : tmp) {
                s += c;
            }
            res.push_back(s);
        }
        else {
            string tem = mp[digits[pos]-'0'];
            for (int i = 0; i < tem.size(); i++) {
                tmp.push_back(tem[i]);
                dfs(digits, pos+1);
                tmp.pop_back();
            }
        }
    }
private:
    vector<string> mp;
    vector<string> res;
    vector<char> tmp;
};

class Solution {
public:
    /*
    18. 4Sum
    Runtime: 12 ms, faster than 89.69% of C++ online submissions for 4Sum.
    Memory Usage: 9 MB, less than 100.00% of C++ online submissions for 4Sum.
    There are some tricks to reduce the calculation.
    1. skip the checking if following sum is greater than target
    2. skip the checking if the max possibility is smaller than target
    */
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int> > res;
        if (nums.size() < 4) return res;
        int n = nums.size();
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size()-3; i++) {
            if (i != 0 && nums[i] == nums[i-1]) continue;
            if (nums[i]+nums[i+1]+nums[i+2]+nums[i+3] > target) break;
            if (i >= 3 && nums[i]+nums[n-1]+nums[n-2]+nums[n-3] < target) continue;
            for (int j = i+1; j < nums.size()-2; j++) {
                if (j != i+1 && nums[j] == nums[j-1]) continue;
                if (nums[i]+nums[j]+nums[j+1]+nums[j+2] > target) break;
                if (nums[i]+nums[j]+nums[n-1]+nums[n-2] < target) continue;
                int left = j+1, right = nums.size()-1;
                int rem = target - nums[i] - nums[j];
                while (left < right) {
                    int s = nums[left] + nums[right];
                    if (rem > s) {
                        do {
                            left++;
                        } 
                        while (left < right && nums[left] == nums[left-1]);
                    }
                    else if (rem < s) {
                        do {
                            right--;
                        }
                        while (left < right && nums[right] == nums[right+1]);
                    }
                    else {
                        vector<int> tmp = {nums[i], nums[j], nums[left], nums[right]};
                        res.push_back(tmp);
                        do left++; while (left < right && nums[left] == nums[left-1]);
                        do right--; while (left < right && nums[right] == nums[right+1]);
                    }
                }
            }
        }
        return res;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    /*
    19. Remove Nth Node From End of List
    Runtime: 4 ms, faster than 85.71% of C++ online submissions for Remove Nth Node From End of List.
    Memory Usage: 8.6 MB, less than 73.68% of C++ online submissions for Remove Nth Node From End of List.
    */
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* hd = new ListNode(0);
        hd->next = head;
        ListNode* parent = hd;
        ListNode* ptr1 = head;
        ListNode* ptr2 = head;
        while (ptr1 != NULL && n > 1) {
            ptr1 = ptr1->next;
            n--;
        }
        while (ptr1->next != NULL) {
            ptr1 = ptr1->next;
            parent = ptr2;
            ptr2 = ptr2->next;
        }
        parent->next = ptr2->next;
        delete ptr2;
        return hd->next;
    }
};

class Solution {
public:
    /*
    20. Valid Parentheses
    Runtime: 0 ms, faster than 100.00% of C++ online submissions for Valid Parentheses.
    Memory Usage: 8.6 MB, less than 70.54% of C++ online submissions for Valid Parentheses.
    */
    bool isValid(string s) {
        if (s.size() <= 0) return true;
        stack<char> st;
        int ptr = 0;
        if (s[0] == '(' || s[0] == '[' || s[0] == '{') st.push(s[0]);
        else return false;
        ptr++;
        while (ptr < s.size()) {
            if (s[ptr] == '(' || s[ptr] == '{' || s[ptr] == '[') st.push(s[ptr]);
            else if (!st.empty()) {
                if (s[ptr] == ')' && st.top() == '(') st.pop();
                else if (s[ptr] == ']' && st.top() == '[') st.pop();
                else if (s[ptr] == '}' && st.top() == '{') st.pop();
                else return false;
            }
            else return false;
            ptr++;
        }
        return st.empty();
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    /*
    Runtime: 8 ms, faster than 76.89% of C++ online submissions for Merge Two Sorted Lists.
    Memory Usage: 8.8 MB, less than 95.08% of C++ online submissions for Merge Two Sorted Lists.
    */
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == NULL) return l2;
        if (l2 == NULL) return l1;
        ListNode* node;
        if (l1->val < l2->val) {
            node = l1;
            l1 = l1->next;
        }
        else {
            node = l2;
            l2 = l2->next;
        }
        ListNode* head = node;
        while (l1 != NULL && l2 != NULL) {
            if (l1->val < l2->val) {
                node->next = l1;
                l1 = l1->next;
            }
            else {
                node->next = l2;
                l2 = l2->next;
            }
            node = node->next;
        }
        while (l1 != NULL) {
            node->next = l1;
            l1 = l1->next;
            node = node->next;
        }
        while (l2 != NULL) {
            node->next = l2;
            l2 = l2->next;
            node = node->next;
        }
        return head;
    }
};

class Solution {
public:
    /*
    22. Generate Parentheses
    Runtime: 0 ms, faster than 100.00% of C++ online submissions for Generate Parentheses.
    Memory Usage: 17.1 MB, less than 76.03% of C++ online submissions for Generate Parentheses.
    */
    vector<string> generateParenthesis(int n) {
        if (n == 0) return res;
        dfs("", n, n);
        return res;
    }
    void dfs(string str, int left, int right) {
        if (left == 0 && right == 0) res.push_back(str);
        if (left > 0) dfs(str+'(', left-1, right);
        if (right > left) dfs(str+')', left, right-1);
    }
private:
    vector<string> res;
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    /*
    23. Merge k Sorted Lists
    */
    /*
    Approach 3: merge 2 list iteratively
    Runtime: 20 ms, faster than 98.78% of C++ online submissions for Merge k Sorted Lists.
    Memory Usage: 10.8 MB, less than 91.67% of C++ online submissions for Merge k Sorted Lists.
    */
    ListNode* merge2Lists(ListNode* l1, ListNode* l2) {
        ListNode head(0);
        ListNode* node = &head;
        while (l1 != NULL && l2 != NULL) {
            if (l1->val < l2->val) {
                node->next = l1;
                l1 = l1->next;
            }
            else {
                node->next = l2;
                l2 = l2->next;
            }
            node = node->next;
        }
        while (l1 != NULL) {
            node->next = l1;
            l1 = l1->next;
            node = node->next;
        }
        while (l2 != NULL) {
            node->next = l2;
            l2 = l2->next;
            node = node->next;
        }
        return head.next;
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.size() <= 0) return NULL;
        int left = 0, right = lists.size() - 1;
        while (right > 0) {
            while (left < right) {
                lists[left] = merge2Lists(lists[left], lists[right]);
                left++;
                right--;
            }
            left = 0;
        }
        return lists[0];
    }
    /*
    Approach 2: using heap to reduce the sort time. O(nlogk)
    Runtime: 28 ms, faster than 67.66% of C++ online submissions for Merge k Sorted Lists.
    Memory Usage: 11.1 MB, less than 69.05% of C++ online submissions for Merge k Sorted Lists.
    */
    static bool cmp(ListNode* l1, ListNode* l2) {
        return l1->val > l2->val;
    }
    ListNode* mergeKLists3(vector<ListNode*>& lists) {
        vector<ListNode*> heap;
        for (auto l : lists) {
            if (l) heap.push_back(l);
        }
        ListNode* head = new ListNode(0);
        ListNode* node = head;
        make_heap(heap.begin(), heap.end(), cmp);
        while (heap.size() > 0) {
            ListNode* tmp = heap[0];
            pop_heap(heap.begin(), heap.end(), cmp);
            node->next = tmp;
            node = node->next;
            heap.back() = heap.back()->next;
            if (!heap.back()) heap.pop_back();
            else {
                push_heap(heap.begin(), heap.end(), cmp);
            }
        }
        return head->next;
    }
    /*
    Intuitive approach: search for a smallest node; O(k*N);
    Runtime: 608 ms, faster than 5.16% of C++ online submissions for Merge k Sorted Lists.
    Memory Usage: 11.4 MB, less than 41.67% of C++ online submissions for Merge k Sorted Lists.
    */
    ListNode* mergeKLists2(vector<ListNode*>& lists) {
        vector<ListNode*> headlist;
        for (int i = 0; i < lists.size(); i++) {
            ListNode* hd = new ListNode(0);
            hd->next = lists[i];
            headlist.push_back(hd);
        }
        ListNode* head = new ListNode(0);
        ListNode* node = head;
        while (true) {
            int tmp = -1;
            bool has = false;
            for (int i = 0; i < headlist.size(); i++) {
                if (headlist[i]->next == NULL) continue;
                if (tmp == -1 || headlist[tmp]->next->val > headlist[i]->next->val) {
                    has = true;
                    tmp = i;
                }
            }
            if (!has) break;
            node->next = headlist[tmp]->next;
            headlist[tmp]->next = headlist[tmp]->next->next;
            node = node->next;
        }
        return head->next;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    
    /*
    24. Swap Nodes in Pairs
    Approach 2: recursive approach
    Runtime: 4 ms, faster than 68.94% of C++ online submissions for Swap Nodes in Pairs.
    Memory Usage: 8.7 MB, less than 75.00% of C++ online submissions for Swap Nodes in Pairs.
    */
    ListNode* swapPairs(ListNode* head) {
        if (head == NULL || head->next == NULL) return head;
        ListNode* child = head->next;
        ListNode* grandChild = child->next;
        child->next = head;
        
        head->next = swapPairs(grandChild);
        return child;
    }
    /*
    Approach 1: iterative approach
    Runtime: 4 ms, faster than 68.94% of C++ online submissions for Swap Nodes in Pairs.
    Memory Usage: 8.5 MB, less than 100.00% of C++ online submissions for Swap Nodes in Pairs.
    */
    ListNode* swapPairs2(ListNode* head) {
        if (head == NULL) return NULL;
        if (head->next == NULL) return head;
        ListNode hd(0);
        ListNode* parent = &hd;
        parent->next = head;
        ListNode* nextParent = head->next->next;
        ListNode* node = head;
        while (node != NULL && node->next != NULL) {
            ListNode* child = node->next;
            parent->next = child;
            child->next = node;
            node->next = nextParent;
            
            parent = node;
            if (nextParent == NULL) break;
            if (nextParent->next == NULL) break;
            nextParent = nextParent->next->next;
            node = node->next;
        }
        return hd.next;
    }
};

class Solution {
public:
    /*
    26. Remove Duplicates from Sorted Array
    Runtime: 20 ms, faster than 93.12% of C++ online submissions for Remove Duplicates from Sorted Array.
    Memory Usage: 9.9 MB, less than 96.25% of C++ online submissions for Remove Duplicates from Sorted Array.
    */
    int removeDuplicates(vector<int>& nums) {
        int ptr = -1;
        for (int i = 0; i < nums.size(); i++) {
            if (ptr == -1 || nums[ptr] != nums[i]) nums[++ptr] = nums[i];
        }
        return ptr+1;
    }
};

class Solution {
public:
    /*
    27. Remove Element
    Runtime: 0 ms, faster than 100.00% of C++ online submissions for Remove Element.
    Memory Usage: 8.4 MB, less than 100.00% of C++ online submissions for Remove Element.
    */
    int removeElement(vector<int>& nums, int val) {
        int ptr = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == val) continue;
            else nums[ptr++] = nums[i];
        }
        return ptr;
    }
};

重新总结一下KMP算法。KMP是为了匹配字段而产生的O(n+m)的一种算法。
首先，要计算移动table(DICT)。DICT表示对于pattern每一位和str不匹配时需要到达的ptr。用通俗的话来讲，把pattern写成如下形式，
pattern[prestr, …, poststr, …]，prestr和poststr相同，每一位表示自己之前可以写成prestr…poststr的形式，而dict每一位表示prestr的长度。
如AAAABAA，DICT=[0, 1, 2, 3, 0, 0, 1]。以最后一位A来讲，前面是AAAABAA，prestr=AA，poststr=AA。所以最后一位应当指向第二个A。
生成DICT可以用如下算法：
case1, dict[i]=dict[len]
case2, dict[i]!=dict[len] && len != 0
case3, dict[i]!=dict[len] && len == 0
其中，len是指前后缀的长度。
具体匹配时，用如下算法：
case1，str[i]=pattern[ptr] -> i++, ptr++
case2, str[i]!=pattern[ptr] && dict[i] != 0 -> ptr = dict[i-1]
case3, str[i]!=pattern[ptr] && dict[i] == 0 -> i++
生成DICT需要m到2m的比较（最坏情况aaaaaaab）
匹配需要n到2n的比较（最坏情况以m为周期循环，即aaabaaabaaab，aaaa，比较次数为n/m*m+n=2n）

class Solution {
public:
    /*
    28. Implement strStr()
    Runtime: 0 ms, faster than 100.00% of C++ online submissions for Implement strStr().
    Memory Usage: 9.5 MB, less than 10.00% of C++ online submissions for Implement strStr().
    */
    /*
    Approach 2: KMP
    */
    vector<int> generateDict(string needle) {
        vector<int> dict(needle.size(), 0);
        dict[0] = 0;
        int i = 1;
        int len = 0;
        while (i < needle.size()) {
            // character match
            if (needle[i] == needle[len]) {
                len++;
                dict[i] = len;
                i++;
            }
            else {
                if (len != 0) {
                    len = dict[len-1];
                }
                else {
                    dict[i] = 0;
                    i++;
                }
            }
        }
        return dict;
    }
    int strStr(string haystack, string needle) {
        if (needle.size() == 0) return 0;
        int str1ptr = 0, str2ptr = 0;
        vector<int> dict = generateDict(needle);
        while (str1ptr < haystack.size()) {
            if (str2ptr == needle.size()) return str1ptr - str2ptr;
            if (haystack[str1ptr] == needle[str2ptr]) {
                str1ptr++;
                str2ptr++;
            }
            else {
                if (str2ptr == 0) str1ptr++;
                else str2ptr = dict[str2ptr-1];
            }
        }
        if (str2ptr == needle.size()) return str1ptr - str2ptr;
        return -1;
    }
    /*
    Approach 1: brute force search. O(n^2)
    */
    int strStr2(string haystack, string needle) {
        if (needle.size() == 0) return 0;
        for (int i = 0; i < haystack.size(); i++) {
            int j = 0;
            for (j = 0; j < needle.size() && j+i < haystack.size(); j++) {
                if (needle[j] == haystack[i+j]) continue;
                else break;
            }
            if (j == needle.size()) return i;
        }
        return -1;
    }
};

class Solution {
public:
    /*
    29. Divide Two Integers
    Runtime: 4 ms, faster than 77.46% of C++ online submissions for Divide Two Integers.
    Memory Usage: 8.1 MB, less than 90.00% of C++ online submissions for Divide Two Integers.
    */
    int divide(int dividend, int divisor) {
        long long caldividend = dividend;
        long long caldivisor = divisor;
        caldividend = abs(caldividend);
        caldivisor = abs(caldivisor);
        if (caldividend < caldivisor) return 0;
        long long i = 0;
        while (caldividend >= caldivisor) {
            long long base = caldivisor;
            long long dou = 1;
            while (base + base <= caldividend) {
                base += base;
                dou += dou;
            }
            i += dou;
            caldividend -= base;
            if ((dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0)) {
                if (i - INT_MAX > 1) return INT_MAX;
            }
            else {
                if (i > INT_MAX) return INT_MAX;
            }
        }
        
        if ((dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0)) return -i;
        return i;
    }
};

class Solution {
public:
    /*
    31. Next Permutation
    Runtime: 4 ms, faster than 98.76% of C++ online submissions for Next Permutation.
    Memory Usage: 8.6 MB, less than 92.47% of C++ online submissions for Next Permutation.
    */
    void nextPermutation(vector<int>& nums) {
        if (nums.size() <= 1) return;
        int idx = nums.size()-1;
        for (; idx >= 0; idx--) {
            if (idx < nums.size()-1 && nums[idx] < nums[idx+1]) {
                break;
            }
        }
        if (idx >= 0) {
            int idxx = nums.size()-1;
            for (; idxx > idx; idxx--) {
                if (nums[idxx] > nums[idx]) break;
            }
            swap(nums[idx], nums[idxx]);
        }
        sort(nums.begin()+idx+1, nums.end());
    }
};

class Solution {
public:
    /*
    34. Find First and Last Position of Element in Sorted Array
    Approach 2: using 3 binary search to determin left and right boundary
    Runtime: 8 ms, faster than 84.59% of C++ online submissions for Find First and Last Position of Element in Sorted Array.
    Memory Usage: 10.1 MB, less than 100.00% of C++ online submissions for Find First and Last Position of Element in Sorted Array.
    */
    vector<int> searchRange2(vector<int>& nums, int target) {
        // binary search
        int left = 0, right = nums.size()-1;
        int mid = left + (right - left) / 2;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left++;
            }
            else if (nums[mid] > target) {
                right--;
            }
            else {
                break;
            }
        }
        if (mid < nums.size() && nums[mid] == target) {
            left = searchLeft(nums, 0, mid, target);
            right = searchRight(nums, mid, nums.size()-1, target);
            vector<int> res = {left, right};
            return res;
        }
        else {
            vector<int> res = {-1, -1};
            return res;
        }
    }
    int searchLeft(vector<int>& nums, int left, int right, int target) {
        int mid;
        while (left < right) {
            mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            }
            else if (mid > left && nums[mid] == nums[mid - 1]) {
                right = mid - 1;
            }
            else {
                return mid;
            }
        }
        return right;
    }
    int searchRight(vector<int>& nums, int left, int right, int target) {
        int mid;
        while (left < right) {
            mid = left + (right - left) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
            }
            else if (mid < right && nums[mid] == nums[mid + 1]) {
                left = mid + 1;
            }
            else {
                return mid;
            }
        }
        return left;
    }
    
    /*
    Approach 1: binary search + linear scan. worst case O(n)
    Runtime: 12 ms, faster than 30.55% of C++ online submissions for Find First and Last    Position of Element in Sorted Array.
    Memory Usage: 10.3 MB, less than 93.41% of C++ online submissions for Find First and Last Position of Element in Sorted Array.
    */
    vector<int> searchRange(vector<int>& nums, int target) {
        // binary search
        int left = 0, right = nums.size()-1;
        int mid = left + (right - left) / 2;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            }
            else if (nums[mid] > target) {
                right = mid - 1;
            }
            else {
                break;
            }
        }
        if (mid < nums.size() && nums[mid] == target) {
            left = mid;
            right = mid;
            while (left >= 0 && nums[left] == target) left--;
            while (right <= nums.size()-1 && nums[right] == target) right++;
            vector<int> res = {left+1, right-1};
            return res;
        }
        else {
            vector<int> res = {-1, -1};
            return res;
        }
    }
};

class Solution {
public:
    /*
    35. Search Insert Position
    Runtime: 4 ms, faster than 98.49% of C++ online submissions for Search Insert Position.
    Memory Usage: 8.7 MB, less than 100.00% of C++ online submissions for Search Insert Position.
    */
    int searchInsert(vector<int>& nums, int target) {
        int left = 0, right = nums.size()-1;
        int mid = 0;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            else if (nums[mid] < target) {
                if (mid + 1 <= right && nums[mid + 1] > target) return mid + 1;
                left = mid + 1;
            }
            else {
                if (mid - 1 >= left && nums[mid - 1] < target) return mid;
                right = mid - 1;
            }
        }
        if (mid >= 0 && nums[mid] < target) return mid + 1;
        else if (mid >= 0 && nums[mid] > target) return mid;
        else return mid;
    }
};

class Solution {
public:
    /*
    33. Search in Rotated Sorted Array
    Runtime: 4 ms, faster than 79.30% of C++ online submissions for Search in Rotated Sorted Array.
    Memory Usage: 8.6 MB, less than 100.00% of C++ online submissions for Search in Rotated Sorted Array.
    */
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size()-1;
        int mid;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) {
                // case 1: left hand size is in order
                if (nums[left] <= nums[mid]) {
                    left = mid + 1;
                }
                // case 2: left hand size is not in order
                else {
                    if (target < nums[left]) left = mid + 1;
                    else if (target == nums[left]) return left;
                    else right = mid - 1;
                }
            }
            else {
                // nums[mid] > target
                if (nums[mid] <= nums[right]) {
                    right = mid - 1;
                }
                else {
                    if (target > nums[right]) right = mid - 1;
                    else if (target == nums[right]) return right;
                    else left = mid + 1;
                }
            }
        }
        return -1;
    }
};

class Solution {
public:
    /*
    36. Valid Sudoku
    Runtime: 12 ms, faster than 89.91% of C++ online submissions for Valid Sudoku.
    Memory Usage: 9.4 MB, less than 97.44% of C++ online submissions for Valid Sudoku.
    */
    bool isValidSudoku(vector<vector<char>>& board) {
        bool table[10];
        // check each box
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                memset(table, 0, sizeof(table));
                for (int k = 0; k < 3; k++) {
                    for (int t = 0; t < 3; t++) {
                        if (board[i*3+k][j*3+t] == '.') continue;
                        if (!table[board[i*3+k][j*3+t]-'0']) {
                            table[board[i*3+k][j*3+t]-'0'] = true;
                        }
                        else return false;
                    }
                }
            }
        }
        
        for (int i = 0; i < 9; i++) {
            memset(table, 0, sizeof(table));
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') continue;
                if (!table[board[i][j]-'0']) table[board[i][j]-'0'] = true;
                else return false;
            }
        }
        for (int j = 0; j < 9; j++) {
            memset(table, 0, sizeof(table));
            for (int i = 0; i < 9; i++) {
                if (board[i][j] == '.') continue;
                if (!table[board[i][j]-'0']) table[board[i][j]-'0'] = true;
                else return false;
            }
        }
        return true;
    }
};

class Solution {
public:
    /*
    38. Count and Say
    Runtime: 4 ms, faster than 77.08% of C++ online submissions for Count and Say.
    Memory Usage: 8.8 MB, less than 84.72% of C++ online submissions for Count and Say.
    */
    string countAndSay(int n) {
        if (n == 1) return "1";
        if (n == 2) return "11";
        if (n == 3) return "21";
        if (n == 4) return "1211";
        if (n == 5) return "111221";
        string curr = "111221";
        for (int i = 5; i < n; i++) {
            // count curr
            int pre = 0;
            int count = 0;
            string tmp;
            for (int j = 0; j < curr.size(); j++) {
                if (curr[j] - '0' != pre) {
                    if (count != 0) {
                        tmp += to_string(count);
                        tmp += to_string(pre);
                    }
                    count = 1;
                    pre = curr[j] - '0';
                }
                else {
                    count++;
                }
            }
            if (count != 0) {
                tmp += to_string(count);
                tmp += to_string(pre);
            }
            curr = tmp;
        }
        return curr;
    }
};

class Solution {
public:
    /*
    39. Combination Sum
    Runtime: 8 ms, faster than 98.25% of C++ online submissions for Combination Sum.
    Memory Usage: 9.8 MB, less than 58.33% of C++ online submissions for Combination Sum.
    */
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        dfs(candidates, 0, target);
        return res;
    }
    void dfs(vector<int>& cand, int pos, int target) {
        if (target == 0) {
            res.push_back(tmp);
        }
        else {
            for (int i = pos; i < cand.size(); i++) {
                if (cand[i] <= target) {
                    tmp.push_back(cand[i]);
                    dfs(cand, i, target-cand[i]);
                    tmp.pop_back();
                }
            }
        }
    }
private:
    vector<vector<int> > res;
    vector<int> tmp;
};

class Solution {
public:
    /*
    40. Combination Sum II
    Runtime: 8 ms, faster than 83.16% of C++ online submissions for Combination Sum II.
    Memory Usage: 9.2 MB, less than 50.00% of C++ online submissions for Combination Sum II.
    */
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        dfs(candidates, 0, target);
        return res;
    }
    void dfs(vector<int>& cand, int pos, int target) {
        if (target == 0) {
            res.push_back(tmp);
        }
        else {
            for (int i = pos; i < cand.size(); i++) {
                if (target >= cand[i]) {
                    if (i > pos && cand[i] == cand[i-1]) continue;
                    tmp.push_back(cand[i]);
                    dfs(cand, i+1, target-cand[i]);
                    tmp.pop_back();
                }
            }
        }
    }
private:
    vector<vector<int> > res;
    vector<int> tmp;
};

这题还是挺有趣的，如果要找到第一个未出现的正整数，可以使用类似于bucket sort的思想。
原理：要找到第一个未出现的正整数，则只需要保留最大size个数，其他都是没有用的。那么，将数字放在他的位置，然后再次线性扫描即可。

class Solution {
public:
    /*
    41. First Missing Positive
    Runtime: 4 ms, faster than 62.62% of C++ online submissions for First Missing Positive.
    Memory Usage: 8.5 MB, less than 100.00% of C++ online submissions for First Missing Positive.
    */
    int firstMissingPositive(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] <= 0) continue;
            else {
                // put nums at index nums
                if (nums[i] <= nums.size()) {
                    if (nums[nums[i]-1] != nums[i]) {
                        swap(nums[nums[i]-1], nums[i]);
                        i--;
                    }
                }
            }
        }
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != i+1) {
                return i+1;
            }
        }
        return nums.size()+1;
    }
};

class Solution {
public:
    /*
    Approach 2: dynamic programming.
    Runtime: 8 ms, faster than 58.47% of C++ online submissions for Trapping Rain Water.
    Memory Usage: 9.1 MB, less than 91.14% of C++ online submissions for Trapping Rain Water.
    */
    int trap2(vector<int>& height) {
        vector<int> left(height.size(), 0);
        vector<int> right(height.size(), 0);
        int mleft = 0;
        for (int i = 0; i < height.size(); i++) {
            mleft = max(mleft, height[i]);
            left[i] = mleft;
        }
        int mright = 0;
        for (int i = height.size()-1; i >= 0; i--) {
            mright = max(mright, height[i]);
            right[i] = mright;
        }
        int res = 0;
        for (int i = 0; i < height.size(); i++) {
            res += min(left[i], right[i]) - height[i];
        }
        return res;
    }
    /*
    Approach 1: using stack. from left to right, if height greater than s.top, water can be put. O(n^2).
    Runtime: 8 ms, faster than 58.47% of C++ online submissions for Trapping Rain Water.
    Memory Usage: 10 MB, less than 5.06% of C++ online submissions for Trapping Rain Water.
    */
    int trap(vector<int>& height) {
        stack<int> s;
        int res = 0;
        for (int i = 0; i < height.size(); i++) {
            if (s.empty() && height[i] == 0) continue;
            if (s.empty() || height[s.top()] >= height[i]) {
                s.push(i);
            }
            else {
                while (!s.empty() && height[s.top()] < height[i]) {
                    int h = s.top();
                    s.pop();
                    if (s.empty()) break;
                    int boundary = min(height[s.top()], height[i]) - height[h];
                    res += boundary * (i - s.top() - 1);
                }
                s.push(i);
            }
        }
        return res;
    }
};

class Solution {
public:
    /*
    43. Multiply Strings
    Runtime: 16 ms, faster than 27.18% of C++ online submissions for Multiply Strings.
    Memory Usage: 11.8 MB, less than 12.82% of C++ online submissions for Multiply Strings.
    */
    string multiply(string num1, string num2) {
        int ptr1 = num1.size()-1;
        int ptr2 = num2.size()-1;
        int carrier = 0;
        string res;
        for (int i = num1.size()-1; i >= 0; i--) {
            carrier = 0;
            string tmp;
            for (int j = num2.size()-1; j >= 0; j--) {
                int digit = (num1[i] - '0') * (num2[j] - '0') + carrier;
                carrier = digit / 10;
                tmp += '0' + digit % 10;
            }
            if (carrier > 0) tmp += '0' + carrier;
            reverse(tmp.begin(), tmp.end());
            // add res and tmp
            carrier = 0;
            string up(num1.size()-1-i, '0');
            tmp += up;
            int ptr1 = res.size()-1, ptr2 = tmp.size()-1;
            while (ptr1 >= 0 && ptr2 >= 0) {
                int digit = res[ptr1] - '0' + tmp[ptr2--] - '0' + carrier;
                carrier = digit / 10;
                digit %= 10;
                res[ptr1--] = '0' + digit;
            }
            while (ptr1 >= 0) {
                int digit = res[ptr1] - '0' + carrier;
                carrier = digit / 10;
                digit %= 10;
                res[ptr1--] = '0' + digit;
            }
            while (ptr2 >= 0) {
                int digit = tmp[ptr2--] - '0' + carrier;
                carrier = digit / 10;
                digit %= 10;
                string dig;
                dig += '0' + digit;
                res = dig + res;
            }
            if (carrier > 0) {
                string dig;
                dig += '0' + carrier;
                res = dig + res;
            }
        }
        int ptr = 0;
        for (; res[ptr] == '0' && ptr < res.size()-1; ptr++);
        return res.substr(ptr, res.size()-ptr);

    }
};

class Solution {
public:
    /*
    46. Permutations
    Runtime: 12 ms, faster than 66.46% of C++ online submissions for Permutations.
    Memory Usage: 9.5 MB, less than 46.27% of C++ online submissions for Permutations.
    */
    vector<vector<int>> permute(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i++) {
            check.push_back(true);
        }
        dfs(nums, nums.size());
        return res;
    }
    void dfs(vector<int>& nums, int n) {
        if (n == 0) {
            res.push_back(tmp);
        }
        else {
            for (int i = 0; i < nums.size(); i++) {
                if (check[i]) {
                    tmp.push_back(nums[i]);
                    check[i] = false;
                    dfs(nums, n-1);
                    check[i] = true;
                    tmp.pop_back();
                }
            }
        }
    }
private:
    vector<vector<int> > res;
    vector<int> tmp;
    vector<bool> check;
};

class Solution {
public:
    /*
    47. Permutations II
    Runtime: 20 ms, faster than 94.88% of C++ online submissions for Permutations II.
    Memory Usage: 10.2 MB, less than 52.38% of C++ online submissions for Permutations II.
    */
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        bool check[nums.size()];
        memset(check, 0, sizeof(check));
        dfs(nums, nums.size(), check);
        return res;
    }
    void dfs(vector<int>& nums, int n, bool* check) {
        if (n == 0) {
            res.push_back(tmp);
        }
        else {
            for (int i = 0; i < nums.size(); i++) {
                if (i > 0 && nums[i] == nums[i-1] && check[i-1] == false && check[i] == false) continue;
                else if (!check[i]) {
                    tmp.push_back(nums[i]);
                    check[i] = true;
                    dfs(nums, n-1, check);
                    check[i] = false;
                    tmp.pop_back();
                }
            }
        }
    }
private:
    vector<vector<int> > res;
    vector<int> tmp;
};

class Solution {
public:
    /*
    44. Wildcard Matching
    Approach 2: dynamic programming
    ps: there exists a better approach, but I do not have time to work it out.
    Runtime: 40 ms, faster than 59.47% of C++ online submissions for Wildcard Matching.
    Memory Usage: 9.9 MB, less than 53.85% of C++ online submissions for Wildcard Matching.
    */
    bool isMatch(string s, string p) {
        int ssize = s.size();
        int psize = p.size();
        if (ssize == 0 && psize == 0) return true;
        else if (ssize == 0 && psize != 0 && p[0] != '*') return false;
        else if (ssize != 0 && psize == 0) return false;
        
        bool table[ssize+1][psize+1];
        memset(table, 0, sizeof(table));
        table[ssize][psize] = true;
        for (int i = psize-1; i >= 0; i--) {
            if (p[i] == '*') table[ssize][i] = true;
            else break;
        }
        for (int i = ssize-1; i >= 0; i--) {
            for (int j = psize-1; j >= 0; j--) {
                if (s[i] == p[j]) table[i][j] = table[i][j] || table[i+1][j+1];
                if (p[j] == '?') table[i][j] = table[i][j] || table[i+1][j+1];
                if (p[j] == '*') {
                    table[i][j] = table[i][j] || table[i][j+1] || table[i+1][j] || table[i+1][j+1];
                }
            }
        }
        return table[0][0];
    }
    /*
    Approach 1: recursive
    Time limit exceed
    */
    bool isMatch2(string s, string p) {
        if (s.size() == 0 && p.size() == 0) return true;
        if (s.size() != 0 && p.size() == 0) return false;
        if (p.size() != 0 && p[0] == '*' && s.size() == 0) return isMatch(s, p.substr(1, p.size()-1));
        else if (s.size() == 0) return false;
        
        if (s[0] == p[0] || p[0] == '?') {
            return isMatch(s.substr(1, s.size()-1), p.substr(1, p.size()-1));
        }
        else if (p[0] == '*') {
            if (isMatch(s.substr(1, s.size()-1), p)) return true;
            if (isMatch(s.substr(1, s.size()-1), p.substr(1, p.size()-1))) return true;
            if (isMatch(s, p.substr(1, p.size()-1))) return true;
        }
        
        return false;
    }
};

class Solution {
public:
    /*
    45. Jump Game II
    Runtime: 4 ms, faster than 99.86% of C++ online submissions for Jump Game II.
    Memory Usage: 10.1 MB, less than 80.00% of C++ online submissions for Jump Game II.
    */
    int jump(vector<int>& nums) {
        int size = nums.size();
        int table[size];
        for (int i = 0; i < size; i++) table[i] = INT_MAX;
        table[0] = 0;
        for (int i = 0; i < size; i++) {
            // should be scaned from back to front
            // the method is approximating O(N)
            // otherwise, the method is O(N^2)
            for (int j = min(nums[i], size - i - 1); j >= 0; j--) {
                if (table[i + j] <= table[i] + 1) break;
                table[i + j] = table[i] + 1;
            }
        }
        return table[size-1];
    }
};

class Solution {
public:
    /*
    48. Rotate Image
    Runtime: 4 ms, faster than 81.66% of C++ online submissions for Rotate Image.
    Memory Usage: 8.9 MB, less than 100.00% of C++ online submissions for Rotate Image.
    PS: vector.size() shoule be O(1). But seems become slower if I call this function multiple times.
    */
    void rotate(vector<vector<int>>& matrix) {
        int size = matrix.size();
        for (int i = 0; i < size; i++) {
            for (int j = i+1; j < size; j++) {
                // int tmp = matrix[i][j];
                // matrix[i][j] = matrix[j][i];
                // matrix[j][i] = tmp;
                swap(matrix[i][j], matrix[j][i]);
            }
        }
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size/2; j++) {
                // int tmp = matrix[i][j];
                // matrix[i][j] = matrix[i][size-1-j];
                // matrix[i][size-1-j] = tmp;
                swap(matrix[i][j], matrix[i][size-1-j]);
            }
        }
    }
};

class Solution {
public:
    /*
    49. Group Anagrams
    map using RB-Tree, while unordered_map using hash.
    unordered_map is much more faster.
    Runtime: 44 ms, faster than 59.16% of C++ online submissions for Group Anagrams.
    Memory Usage: 20 MB, less than 52.24% of C++ online submissions for Group Anagrams.
    */
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string> > mp;
        for (string s : strs) {
            string tmp = s;
            sort(tmp.begin(), tmp.end());
            mp[tmp].push_back(s);
        }
        vector<vector<string> > res; 
        for (auto m : mp) {
            res.push_back(m.second);   
        }
        return res;
    }
};

class Solution {
public:
    /*
    50. Pow(x, n)
    Runtime: 4 ms, faster than 59.04% of C++ online submissions for Pow(x, n).
    Memory Usage: 8.3 MB, less than 100.00% of C++ online submissions for Pow(x, n).
    */
    double myPow(double x, int n) {
        if (abs(x - 1) <= esp) return x;
        else if (abs(x + 1) <= esp) {
            if (n % 2 == 1) return x;
            else return -1 * x;
        }
        long long idx = n;
        if (idx < 0) {
            x = 1/x;
            idx *= -1;
        }
        double res = 1.0;
        while (idx > 0) {
            if (idx % 2 == 1) {
                res *= x;
                idx -= 1;
            }
            else {
                x *= x;
                idx /= 2;
            }
        }
        return res;
    }
private:
    double esp = 1e-10;
};

class Solution {
public:
    /*
    51. N-Queens
    Runtime: 4 ms, faster than 97.66% of C++ online submissions for N-Queens.
    Memory Usage: 10.9 MB, less than 43.75% of C++ online submissions for N-Queens.
    */
    vector<vector<string>> solveNQueens(int n) {
		dfs(n, n);
		return res;
	}
	void dfs(int pos, int n) {
		if (pos == 0) {
			vector<string> solut;
			for (int i = 0; i < n; i++) {
				string s(n, '.');
				s[tmp[i]] = 'Q';
				solut.push_back(s);
			}
			res.push_back(solut);
		}
		else {
			for (int i = 0; i < n; i++) {
				// check valid
				bool valid = true;
				for (int j = 0; j < tmp.size(); j++) {
					if (tmp[j] == i) {
						valid = false;
						break;
					}
					if (abs(tmp[j] - i) == abs(j - (n - pos))) {
						valid = false;
						break;
					}
				}
				if (valid) {
					tmp.push_back(i);
					dfs(pos - 1, n);
					tmp.pop_back();
				}
			}
		}
	}
private:
	vector<vector<string> > res;
	vector<int> tmp;
};

class Solution {
public:
    /*
    52. N-Queens II
    Simplest approach: solve the n-queue and return size
    Runtime: 0 ms, faster than 100.00% of C++ online submissions for N-Queens II.
    Memory Usage: 8.4 MB, less than 41.67% of C++ online submissions for N-Queens II.
    */
    int totalNQueens(int n) {
        dfs(n, n);
        return res;
    }
	void dfs(int pos, int n) {
		if (pos == 0) {
            res++;
		}
		else {
			for (int i = 0; i < n; i++) {
				// check valid
				bool valid = true;
				for (int j = 0; j < tmp.size(); j++) {
					if (tmp[j] == i) {
						valid = false;
						break;
					}
					if (abs(tmp[j] - i) == abs(j - (n - pos))) {
						valid = false;
						break;
					}
				}
				if (valid) {
					tmp.push_back(i);
					dfs(pos - 1, n);
					tmp.pop_back();
				}
			}
		}
	}
private:
	int res = 0;
	vector<int> tmp;
};

class Solution {
public:
    /*
    53. Maximum Subarray
    Runtime: 8 ms, faster than 71.57% of C++ online submissions for Maximum Subarray.
    Memory Usage: 9.2 MB, less than 97.06% of C++ online submissions for Maximum Subarray.
    */
    int maxSubArray(vector<int>& nums) {
        int size = nums.size();
        if (size == 0) return 0;
        int table[size] = {0};
        table[0] = max(0, nums[0]);
        int res = table[0];
        int minN = nums[0];
        for (int i = 1; i < size; i++) {
            table[i] = max(table[i-1]+nums[i], 0);
            res = max(res, table[i]);
            minN = max(minN, nums[i]);
        }
        if (res > 0) return res;
        else {
            return minN;
        }
    }
};

class Solution {
public:
    /*
    54. Spiral Matrix
    Runtime: 0 ms, faster than 100.00% of C++ online submissions for Spiral Matrix.
    Memory Usage: 8.5 MB, less than 100.00% of C++ online submissions for Spiral Matrix.
    */
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> res;
        if (matrix.size() == 0) return res;
        int row = matrix.size();
        int col = matrix[0].size();
        int flag = 0;
        int rowBegin = 0;
        int rowEnd = row;
        int colBegin = 0;
        int colEnd = col;
        int n = 0;
        while (n < row * col) {
            if (flag == 0) {
                for (int i = colBegin; i < colEnd; i++) {
                    res.push_back(matrix[rowBegin][i]);
                    n++;
                }
                flag = 1;
                rowBegin++;
            }
            else if (flag == 1) {
                for (int i = rowBegin; i < rowEnd; i++) {
                    res.push_back(matrix[i][colEnd-1]);
                    n++;
                }
                flag = 2;
                colEnd--;
            }
            else if (flag == 2) {
                for (int i = colEnd - 1; i >= colBegin; i--) {
                    res.push_back(matrix[rowEnd-1][i]);
                    n++;
                }
                flag = 3;
                rowEnd--;
            }
            else {
                for (int i = rowEnd-1; i >= rowBegin; i--) {
                    res.push_back(matrix[i][colBegin]);
                    n++;
                }
                flag = 0;
                colBegin++;
            }
        }
        return res;
    }
};

class Solution {
public:
    /*
    55. Jump Game
    Runtime: 12 ms, faster than 71.34% of C++ online submissions for Jump Game.
    Memory Usage: 10 MB, less than 73.68% of C++ online submissions for Jump Game.
    */
    bool canJump(vector<int>& nums) {
        int size = nums.size();
        if (size <= 1) return true; 
        bool table[size];
        memset(table, 0, sizeof(table));
        table[0] = true;
        for (int i = 0; i < nums.size(); i++) {
            if (table[i] == false) break;
            for (int j = min(size-1, i + nums[i]); j >= i; j--) {
                if (table[j] == true) break;
                else table[j] = true;
            }
        }
        return table[size-1];
    }
};

class Solution {
public:
    static bool gt(vector<int> interval1, vector<int> interval2) {
        if (interval1[0] != interval2[0]) return interval1[0] < interval2[0];
        else {
            return interval1[1] < interval2[1];
        }
    }
    /*
    Approach 2: replace vector with pair. Much faster
    Runtime: 16 ms, faster than 93.58% of C++ online submissions for Merge Intervals.
    Memory Usage: 13.1 MB, less than 36.05% of C++ online submissions for Merge Intervals.
    */
    vector<vector<int>> merge2(vector<vector<int>>& intervals) {
        vector<pair<int, int> > tmp;
        for (auto v : intervals) {
            tmp.push_back(make_pair(v[0], v[1]));
        }
        sort(tmp.begin(), tmp.end());
        int ptr = -1;
        vector<vector<int> > res;
        for (int i = 0; i < tmp.size(); i++) {
            if (ptr == -1 || res[ptr][1] < tmp[i].first) {
                res.push_back({tmp[i].first, tmp[i].second});
                ptr++;
            }
            else {
                res[ptr][1] = max(res[ptr][1], tmp[i].second);
            }
        }
        return res;
    }
    /*
    Approach 1: sort and merge. O(nlogn). But vector is expansive.
    Runtime: 76 ms, faster than 14.75% of C++ online submissions for Merge Intervals.
    Memory Usage: 27.4 MB, less than 5.81% of C++ online submissions for Merge Intervals.
    */
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), gt);
        vector<vector<int> > res;
        int ptr = -1;
        for (int i = 0; i < intervals.size(); i++) {
            if (ptr == -1 || res[ptr][1] < intervals[i][0]) {
                res.push_back(intervals[i]);
                ptr++;
            }
            else {
                res[ptr][1] = max(intervals[i][1], res[ptr][1]);
            }
        }
        return res;
    }
};

class Solution {
public:
    /*
    58. Length of Last Word
    Runtime: 4 ms, faster than 70.63% of C++ online submissions for Length of Last Word.
    Memory Usage: 8.8 MB, less than 77.78% of C++ online submissions for Length of Last Word.
    */
    int lengthOfLastWord(string s) {
        int ptr1 = s.size() - 1;
        for (; ptr1 >= 0 && s[ptr1] == ' '; ptr1--);
        int ptr2 = ptr1;
        for (; ptr2 >= 0 && s[ptr2] != ' '; ptr2--);
        return ptr1 - ptr2;
    }
};

class Solution {
public:
    /*
    57. Insert Interval
    Runtime: 20 ms, faster than 51.46% of C++ online submissions for Insert Interval.
    Memory Usage: 12.4 MB, less than 90.00% of C++ online submissions for Insert Interval.
    */
    static bool intersect(vector<int>& interval1, vector<int>& interval2) {
        if (interval1[0] <= interval2[1] && interval1[0] >= interval2[0]) return true;
        if (interval2[0] <= interval1[1] && interval2[0] >= interval1[0]) return true;
        return false;
    }
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int> > res;
        vector<int> base = newInterval;
        if (intervals.size() <= 0) {
            res.push_back(base);
            return res;
        }
        int ptr = -1;
        bool merged = false;
        if (newInterval[1] < intervals[0][0]) {
            merged = true;
            res.push_back(newInterval);
            for (auto v : intervals) {
                res.push_back(v);
            }
            return res;
        }
        else if (newInterval[0] > intervals[intervals.size()-1][1]) {
            merged = true;
            for (auto v : intervals) {
                res.push_back(v);
            }
            res.push_back(newInterval);
            return res;
        }
        bool finish = false;
        for (int i = 0; i < intervals.size(); i++) {
            if (!merged) {
                if (intersect(intervals[i], newInterval)) {
                    vector<int> tmp = intervals[i];
                    tmp[0] = min(tmp[0], newInterval[0]);
                    tmp[1] = max(tmp[1], newInterval[1]);
                    res.push_back(tmp);
                    ptr++;
                    merged = true;
                }
                else {
                    if (intervals[i][1] < newInterval[0]) {
                        res.push_back(intervals[i]);
                        ptr++;
                    }
                    else {
                        res.push_back(newInterval);
                        ptr++;
                        res.push_back(intervals[i]);
                        ptr++;
                        merged = true;
                    }
                }
            }
            else {
                if (!finish && intersect(intervals[i], res[ptr])) {
                    res[ptr][0] = min(res[ptr][0], intervals[i][0]);
                    res[ptr][1] = max(res[ptr][1], intervals[i][1]);
                }
                else {
                    res.push_back(intervals[i]);
                    ptr++;
                    finish = true;
                }
            }
        }
        return res;
        
        
    }
};

class Solution {
public:
    /*
    59. Spiral Matrix II
    Runtime: 4 ms, faster than 73.72% of C++ online submissions for Spiral Matrix II.
    Memory Usage: 8.8 MB, less than 87.50% of C++ online submissions for Spiral Matrix II.
    */
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int> > res;
        for (int i = 0; i < n; i++) {
            vector<int> tmp(n, 1);
            res.push_back(tmp);
        }
        int count = 1;
        int flag = 0;
        int rowBegin = 0;
        int rowEnd = n;
        int colBegin = 0;
        int colEnd = n;
        while (count <= n * n) {
            if (flag == 0) {
                for (int i = colBegin; i < colEnd; i++) {
                    res[rowBegin][i] = count++;
                }
                flag = 1;
                rowBegin++;
            }
            else if (flag == 1) {
                for (int i = rowBegin; i < rowEnd; i++) {
                    res[i][colEnd-1] = count++;
                }
                flag = 2;
                colEnd--;
            }
            else if (flag == 2) {
                for (int i = colEnd-1; i >= colBegin; i--) {
                    res[rowEnd-1][i] = count++;
                }
                flag = 3;
                rowEnd--;
            }
            else {
                for (int i = colEnd-1; i >= rowBegin; i--) {
                    res[i][colBegin] = count++;
                }
                flag = 0;
                colBegin++;
            }
        }
        return res;
    }
};

class Solution {
public:
    /*
    Approach 2:
    Here is something realling interesting.
    Assume n = 4, k = 14
    assign idx = 0
    for position idx = 0, start with 1 -> 3 * 2 * 1 = 6
                                     2 -> 6
                                     3 -> 6
    thus, the kth permutation must be start with 3
    complexity: probability greater than O(n) if we need to maintain the protential element
    Runtime: 0 ms, faster than 100.00% of C++ online submissions for Permutation Sequence.
    Memory Usage: 8.1 MB, less than 100.00% of C++ online submissions for Permutation Sequence.
    */
    string getPermutation(int n, int k) {
        int factorize[9] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};
        vector<char> table = {'1', '2', '3', '4', '5', '6', '7', '8', '9'};
        string res(n, '0');
        int idx = 0;
        int count = 0;
        k -= 1;
        while (count < k) {
            int start = k / factorize[n-idx-1];
            k = k - (start * factorize[n-idx-1]);
            res[idx] = table[start+idx];
            // swap(table[start+idx], table[idx]);
            // sort table[idx+1] to the table[start+idx]
            char tmp = table[start+idx];
            for (int i = start+idx; i > idx; i--) {
                table[i] = table[i-1];
            }
            table[idx] = tmp;
            idx ++;
        }
        for (; idx < n; idx++) {
            res[idx] = table[idx];
        }
        return res;
    }
    /*
    60. Permutation Sequence
    Approach: find whole permutation. O(n^2)
    Runtime: 1412 ms, faster than 5.02% of C++ online submissions for Permutation Sequence.
    Memory Usage: 8.3 MB, less than 68.42% of C++ online submissions for Permutation Sequence.
    */
    string getPermutation2(int n, int k) {
        bool check[n];
        memset(check, 0, sizeof(check));
        dfs(n, n, k, check);
        return res;
    }
    void dfs(int size, int n, int k, bool* check) {
        if (n == 0) {
            string s(tmp.begin(), tmp.end());
            res = s;
            res_size++;
        }
        else {
            for (int i = 0; i < size; i++) {
                if (res_size >= k) break;
                if (check[i]) continue;
                check[i] = true;
                tmp.push_back('1'+i);
                dfs(size, n-1, k, check);
                tmp.pop_back();
                check[i] = false;
            }
        }
    }
private:
    string res;
    int res_size = 0;
    vector<char> tmp;
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    /*
    61. Rotate List
    Runtime: 4 ms, faster than 98.88% of C++ online submissions for Rotate List.
    Memory Usage: 8.7 MB, less than 100.00% of C++ online submissions for Rotate List.
    */
    ListNode* rotateRight(ListNode* head, int k) {
        int length = 0;
        ListNode* node = head;
        while (node != NULL) {
            length++;
            node = node->next;
        }
        if (length <= 1) return head;
        k = k % length;
        if (k == 0) return head;
        node = head;
        for (int i = 0; i < length - k - 1; i++) node = node->next;
        ListNode* newHeader = node->next;
        node->next = NULL;
        ListNode* tmpnode = newHeader;
        while (tmpnode->next != NULL) tmpnode = tmpnode->next;
        tmpnode->next = head;
        return newHeader;
    }
};

class Solution {
public:
    /*
    62. Unique Paths
    Runtime: 0 ms, faster than 100.00% of C++ online submissions for Unique Paths.
    Memory Usage: 8.2 MB, less than 93.75% of C++ online submissions for Unique Paths.
    */
    int uniquePaths(int m, int n) {
        int table[m][n];
        memset(table, 0, sizeof(table));
        for (int i = 0; i < m; i++) {
            table[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            table[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                table[i][j] = table[i-1][j] + table[i][j-1];
            }
        }
        return table[m-1][n-1];
        
    }
};

class Solution {
public:
    /*
    63. Unique Paths II
    Runtime: 4 ms, faster than 74.22% of C++ online submissions for Unique Paths II.
    Memory Usage: 8.9 MB, less than 100.00% of C++ online submissions for Unique Paths II.
    */
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int row = obstacleGrid.size();
        if (row < 1) return 0;
        int col = obstacleGrid[0].size();
        long long table[row][col];
        memset(table, 0, sizeof(table));
        for (int i = 0; i < row; i++) {
            if (obstacleGrid[i][0] == 1) break;
            table[i][0] = 1;
        }
        for (int j = 0; j < col; j++) {
            if (obstacleGrid[0][j] == 1) break;
            table[0][j] = 1;
        }
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (obstacleGrid[i][j] == 1) table[i][j] = 0;
                else {
                    table[i][j] = table[i-1][j] + table[i][j-1];
                }
            }
        }
        return table[row-1][col-1];
    }

};

class Solution {
public:
    /*
    64. Minimum Path Sum
    Runtime: 8 ms, faster than 87.07% of C++ online submissions for Minimum Path Sum.
    Memory Usage: 10.7 MB, less than 68.42% of C++ online submissions for Minimum Path Sum.
    */
    int minPathSum(vector<vector<int>>& grid) {
        int row = grid.size();
        if (row < 1) return 0;
        int col = grid[0].size();
        int table[row][col] = {INT_MAX};
        table[0][0] = grid[0][0];
        for (int i = 1; i < row; i++) {
            table[i][0] = table[i-1][0] + grid[i][0];
        }
        for (int j = 1; j < col; j++) {
            table[0][j] = table[0][j-1] + grid[0][j];
        }
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                table[i][j] = min(table[i-1][j], table[i][j-1]) + grid[i][j];
            }
        }
        return table[row-1][col-1];
    }
};

class Solution {
public:
    /*
    66. Plus One
    Runtime: 4 ms, faster than 65.50% of C++ online submissions for Plus One.
    Memory Usage: 8.5 MB, less than 100.00% of C++ online submissions for Plus One.
    */
    vector<int> plusOne(vector<int>& digits) {
        // reverse(digits.begin(), digits.end());
        int carrier = 1;
        int ptr = digits.size() - 1;
        while (ptr < digits.size() && carrier == 1) {
            digits[ptr] += carrier;
            carrier = digits[ptr] / 10;
            digits[ptr--] %= 10;
        }
        if (carrier == 1) {
            digits.insert(digits.begin(), 1);
        }
        // reverse(digits.begin(), digits.end());
        return digits;
    }
};

class Solution {
public:
    /*
    67. Add Binary
    Runtime: 4 ms, faster than 80.07% of C++ online submissions for Add Binary.
    Memory Usage: 8.6 MB, less than 89.09% of C++ online submissions for Add Binary.
    */
    string addBinary(string a, string b) {
        int ptr1 = a.size()-1;
        int ptr2 = b.size()-1;
        string res(max(a.size(), b.size()), '0');
        int ptr3 = 0;
        int carrier = 0;
        while (ptr1 >= 0 && ptr2 >= 0) {
            int digit = (a[ptr1--] - '0') + (b[ptr2--] - '0') + carrier;
            if (digit == 1 || digit == 0) {
                res[ptr3++] = '0' + digit;
                carrier = 0;
            }
            else {
                res[ptr3++] = '0' + digit % 2;
                carrier = 1;
            }
        }
        while (ptr1 >= 0) {
            int digit = a[ptr1--] - '0' + carrier;
            if (digit == 1 || digit == 0) {
                res[ptr3++] = '0' + digit;
                carrier = 0;
            }
            else {
                res[ptr3++] = '0';
                carrier = 1;
            }
        }
        while (ptr2 >= 0) {
            int digit = b[ptr2--] - '0' + carrier;
            if (digit == 1 || digit == 0) {
                res[ptr3++] = '0' + digit;
                carrier = 0;
            }
            else {
                res[ptr3++] = '0';
                carrier = 1;
            }
        }
        if (carrier == 1) {
            res += "1";
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

class Solution {
public:
    /*
    69. Sqrt(x)
    Apporach 2: binary search variation
    Runtime: 4 ms, faster than 74.92% of C++ online submissions for Sqrt(x).
    Memory Usage: 8.2 MB, less than 98.25% of C++ online submissions for Sqrt(x).
    */
    int mySqrt(int x) {
        if (x == 0) return 0;
        if (x < 4) return 1;
        int left = 1;
        int right = x;
        int mid = x;
        while (left < right) {
            mid = left + (right - left) / 2;
            if (x / mid > mid) {
                left = mid + 1;
            }
            else if (x / mid < mid) {
                right = mid - 1;
            }
            else return mid;
        }
        if (x / left < left) return left - 1;
        return left;
    }
    /*
    Approach 1: binary search + linear search
    Runtime: 4 ms, faster than 74.89% of C++ online submissions for Sqrt(x).
    Memory Usage: 8.2 MB, less than 96.49% of C++ online submissions for Sqrt(x).
    */
    int mySqrt2(int x) {
        long long base = 1;
        while ((base * 2) * ( base * 2) < x) base *= 2; 
        while (base * base < x) {
            base += 1;
        }
        if (base * base != x) base -= 1;
        return base;
    }
};

class Solution {
public:
    /*
    70. Climbing Stairs
    Runtime: 4 ms, faster than 51.86% of C++ online submissions for Climbing Stairs.
    Memory Usage: 8.2 MB, less than 98.53% of C++ online submissions for Climbing Stairs.
    */
    int climbStairs(int n) {
        // f(n) = f(n-1) + f(n-2)
        if (n == 1) return 1;
        if (n == 2) return 2;
        int a = 1;
        int b = 2;
        int res = a + b;
        for (int i = 3; i < n; i++) {
            a = b;
            b = res;
            res = a + b;
        }
        return res;
    }
};

class Solution {
public:
    /*
    71. Simplify Path
    Runtime: 8 ms, faster than 74.65% of C++ online submissions for Simplify Path.
    Memory Usage: 9.8 MB, less than 78.57% of C++ online submissions for Simplify Path.
    */
    string simplifyPath(string path) {
        vector<string> absopath;
        int left = 0;
        int right = 0;
        while (right < path.size()) {
            if (path[right] == '/') {
                if (left == right) {
                    left++;
                    right++;
                    continue;
                }
                string subs = path.substr(left, right-left);
                if (subs == "..") {
                    if (!absopath.empty()) absopath.pop_back();
                }
                else if (subs == ".") {
                    // do nothing
                }
                else {
                    absopath.push_back(subs);
                }
                left = right + 1;
            }
            right++;
        }
        if (path[right-1] != '/') {
            string subs = path.substr(left, right-left);
            if (subs == "..") {
                if (!absopath.empty()) absopath.pop_back();
            }
            else if (subs == ".") {
                // do nothing
            }
            else {
                absopath.push_back(subs);
            }
        }
        string res;
        for (auto s : absopath) {
            res += '/';
            res += s;
        }
        if (res.size() == 0) res += '/';
        return res;
    }
};

class Solution {
public:
    /*
    72. Edit Distance
    Runtime: 8 ms, faster than 90.15% of C++ online submissions for Edit Distance.
    Memory Usage: 9.4 MB, less than 84.38% of C++ online submissions for Edit Distance.
    */
    int minDistance(string word1, string word2) {
        int size1 = word1.size();
        int size2 = word2.size();
        int table[size1+1][size2+1];
        memset(table, 0, sizeof(table));
        table[size1][size2] = 0;
        for (int i = size1-1; i >= 0; i--) {
            table[i][size2] = table[i+1][size2] + 1;
        }
        for (int i = size2-1; i >= 0; i--) {
            table[size1][i] = table[size1][i+1] + 1;
        }
        for (int i = size1 - 1; i >= 0; i--) {
            for (int j = size2 - 1; j >= 0; j--) {
                if (word1[i] == word2[j]) table[i][j] = table[i+1][j+1];
                else {
                    // table[i][j] = min(table[i+1][j+1], min(table[i+1][j], table[i][j+1])) + 1;
                    int m = table[i+1][j+1];
                    if (m > table[i+1][j]) {
                        m = table[i+1][j];
                    }
                    if (m > table[i][j+1]) {
                        m = table[i][j+1];
                    }
                    table[i][j] = m + 1;
                }
            }
        }
        return table[0][0];
    }
};

class Solution {
public:
    /*
    73. Set Matrix Zeroes
    This approach need O(m*n) time, O(m+n) space.
    There are algorithm the only need O(m*n) time and O(1) space. But one need to find a value that is not in possible value range.
    Runtime: 48 ms, faster than 62.21% of C++ online submissions for Set Matrix Zeroes.
    Memory Usage: 11.3 MB, less than 100.00% of C++ online submissions for Set Matrix Zeroes.
    */
    void setZeroes(vector<vector<int>>& matrix) {
        int size1 = matrix.size();
        if (size1 == 0) return;
        int size2 = matrix[0].size();
        bool row[size1];
        bool col[size2];
        memset(row, 0, sizeof(row));
        memset(col, 0, sizeof(col));
        for (int i = 0; i < size1; i++) {
            for (int j = 0; j < size2; j++) {
                if (matrix[i][j] == 0) {
                    row[i] = true;
                    col[j] = true;
                }
            }
        }
        for (int i = 0; i < size1; i++) {
            if (row[i]) {
                for (int j = 0; j < size2; j++) {
                    matrix[i][j] = 0;
                }
            }
        }
        for (int j = 0; j < size2; j++) {
            if (col[j]) {
                for (int i = 0; i < size1; i++) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
};

class Solution {
public:
    /*
    74. Search a 2D Matrix
    Approach 2: variation of binary search
    Runtime: 8 ms, faster than 93.82% of C++ online submissions for Search a 2D Matrix.
    Memory Usage: 9.7 MB, less than 100.00% of C++ online submissions for Search a 2D Matrix.
    */
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int size1 = matrix.size();
        if (size1 == 0) return false;
        int size2 = matrix[0].size();
        if (size2 == 0) return false;
        int left = 0, right = size1 * size2 - 1;
        int mid = left;
        while (left <= right) {
            mid = left + (right - left) / 2;
            int i = mid / size2;
            int j = mid % size2;
            if (matrix[i][j] == target) return true;
            else if (matrix[i][j] < target) left = mid + 1;
            else right = mid - 1;
        }
        return false;
    }
    /*
    Approach 1: linear search + binary search. O(m*logn)
    Runtime: 12 ms, faster than 51.14% of C++ online submissions for Search a 2D Matrix.
    Memory Usage: 9.7 MB, less than 100.00% of C++ online submissions for Search a 2D Matrix.
    */
    bool searchMatrix2(vector<vector<int>>& matrix, int target) {
        int size1 = matrix.size();
        if (size1 == 0) return false;
        int size2 = matrix[0].size();
        if (size2 == 0) return false;
        int i = 0, j = 0;
        while (i < size1 && matrix[i][0] <= target) i++;
        i--;
        if (i < 0) return false;
        // binary search
        int left = 0, right = size2 - 1;
        int mid = left;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (matrix[i][mid] == target) return true;
            else if (matrix[i][mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return false;      
    }
};

class Solution {
public:
    /*
    75. Sort Colors
    Approach 1: partition
    Runtime: 4 ms, faster than 69.20% of C++ online submissions for Sort Colors.
    Memory Usage: 8.4 MB, less than 100.00% of C++ online submissions for Sort Colors.
    */
    void sortColors(vector<int>& nums) {
        int left = 0, right = nums.size()-1;
        int ptr = 0;
        while (ptr <= right) {
            if (nums[ptr] == 2) {
                swap(nums[ptr], nums[right]);
                right--;
            }
            else if (nums[ptr] == 1) {
                ptr++;
            }
            else {
                swap(nums[ptr], nums[left]);
                left++;
                ptr = ptr < left ? left : ptr;
            }
        }
    }
};

class Solution {
public:
    /*
    76. Minimum Window Substring
    Solution: left and right pointer. If get all char, shrink the left to the next valid substr.
    Runtime: 12 ms, faster than 83.72% of C++ online submissions for Minimum Window Substring.
    Memory Usage: 10.5 MB, less than 46.00% of C++ online submissions for Minimum Window Substring.
    */
    string minWindow(string s, string t) {
        int table[256];
        memset(table, 0, sizeof(table));
        for (int i = 0; i < t.size(); i++) {
            table[t[i]]++;
        }
        int tsize = t.size();
        int count = 0;
        int left = 0, right = 0;
        string res;
        while (left < s.size() && table[s[left]] == 0) left++;
        while (right < s.size()) {
            if (count < tsize) {
                table[s[right]]--;
                if (table[s[right]] >= 0) {
                    count++; // find one character
                }
                right++;
            }
            if (count == tsize) {
                if (res.empty() || res.size() > right - left) {
                    res = s.substr(left, right - left);
                }
                table[s[left]]++;
                if (table[s[left]] > 0) count--;
                left++;
                // move left ptr until meet first zero table
                while (left <= right && table[s[left]] < 0) {
                    table[s[left++]]++;
                }
            }
        }
        if (count == tsize) {
			if (res.size() > right - left) {
				res = s.substr(left, right - left);
			}
		}
        
        return res;
    }
};

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        dfs(1, n, k);
        return res;
    }
    void dfs(int pos, int n, int k) {
        if (k == 0) {
            res.push_back(tmp);
        }
        else {
            for (int i = pos; i <= n; i++) {
                tmp.push_back(i);
                dfs(i+1, n, k-1);
                tmp.pop_back();
            }
        }
    }
private:
    vector<vector<int> > res;
    vector<int> tmp;
};

class Solution {
public:
    /*
    78. Subsets
    Runtime: 4 ms, faster than 97.61% of C++ online submissions for Subsets.
    Memory Usage: 9 MB, less than 93.22% of C++ online submissions for Subsets.
    */
    vector<vector<int>> subsets(vector<int>& nums) {
        res.push_back(tmp);
        dfs(nums, 0);
        return res;
    }
    void dfs(vector<int>& nums, int pos) {
        for (int i = pos; i < nums.size(); i++) {
            tmp.push_back(nums[i]);
            res.push_back(tmp);
            dfs(nums, i+1);
            tmp.pop_back();
        }
    }
private:
    vector<vector<int> > res;
    vector<int> tmp;
};

class Solution {
public:
    /*
    79. Word Search
    method: dfs
    Runtime: 40 ms, faster than 60.73% of C++ online submissions for Word Search.
    Memory Usage: 14.9 MB, less than 52.94% of C++ online submissions for Word Search.
    */
    bool exist(vector<vector<char>>& board, string word) {
        if (board.size() <= 0) return false;
        if (word.size() <= 0) return true;
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[i].size(); j++) {
                if (board[i][j] == word[0]) {
                    board[i][j] = '@';
                    if (exist_substr(board, word.substr(1, word.size()-1), i, j)) return true;
                    board[i][j] = word[0];
                }
            }
        }
        return false;
    }
    bool exist_substr(vector<vector<char>>& board, string word, int i, int j) {
        if (word.size() <= 0) return true;
        // search up
        if (i > 0) {
            if (board[i-1][j] == word[0]) {
                board[i-1][j] = '@';
                if (exist_substr(board, word.substr(1, word.size()-1), i-1, j)) return true;
                board[i-1][j] = word[0];
            }
        }
        if (i < board.size() - 1) {
            if (board[i+1][j] == word[0]) {
                board[i+1][j] = '@';
                if (exist_substr(board, word.substr(1, word.size()-1), i+1, j)) return true;
                board[i+1][j] = word[0];
            }
        }
        if (j > 0) {
            if (board[i][j-1] == word[0]) {
                board[i][j-1] = '@';
                if (exist_substr(board, word.substr(1, word.size()-1), i, j-1)) return true;
                board[i][j-1] = word[0];
            }
        }
        if (j < board[0].size() - 1) {
            if (board[i][j+1] == word[0]) {
                board[i][j+1] = '@';
                if (exist_substr(board, word.substr(1, word.size()-1), i, j+1)) return true;
                board[i][j+1] = word[0];
            }
        }
        return false;
    }
};

class Solution {
public:
    /*
    Approach 2: single scan O(n)
    Runtime: 8 ms, faster than 99.00% of C++ online submissions for Remove Duplicates from Sorted Array II.
    Memory Usage: 8.8 MB, less than 84.21% of C++ online submissions for Remove Duplicates from Sorted
    */
    int removeDuplicates2(vector<int>& nums) {
        int ptr = 0;
        int count = 0;
        int pre = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (count == 0 || pre != nums[i]) {
                count = 1;
                pre = nums[i];
                nums[ptr] = nums[i];
                ptr++;
            }
            else if (pre == nums[i]) {
                count++;
                if (count <= 2) {
                    nums[ptr] = nums[i];
                    ptr++;
                }
            }
        }
        return ptr;
    }
    /*
    Approach 1:
    swap the dup element to the end -> O(n^2)
    Runtime: 16 ms, faster than 18.83% of C++ online submissions for Remove Duplicates from Sorted Array II.
    Memory Usage: 8.7 MB, less than 97.37% of C++ online submissions for Remove Duplicates from Sorted Array
    */
    int removeDuplicates(vector<int>& nums) {
        if (nums.size() <= 0) return 0;
        int count = 1;
        int pre = nums[0];
        int right = nums.size()-1;
        for (int i = 1; i <= right; i++) {
            if (pre == nums[i]) {
                count++;
                if (count > 2) {
                    // swap to the end
                    int ptr = i;
                    while (ptr < right) {
                        swap(nums[ptr], nums[ptr+1]);
                        ptr++;
                    }
                    right--;
                    i--;
                }
            }
            else {
                pre = nums[i];
                count = 1;
            }
        }
        return right + 1;
    }
};

class Solution {
public:
    /*
    Approach 1: linear search O(n)
    Runtime: 8 ms, faster than 60.61% of C++ online submissions for Search in Rotated Sorted Array II.
    Memory Usage: 8.7 MB, less than 100.00% of C++ online submissions for Search in Rotated Sorted Array II.
    */
    bool search2(vector<int>& nums, int target) {
        for (auto i : nums) {
            if (i == target) return true;
        }
        return false;
    }
    /*
    Approach 2: binary search + linear partial search
    Runtime: 4 ms, faster than 98.16% of C++ online submissions for Search in Rotated Sorted Array II.
    Memory Usage: 8.5 MB, less than 100.00% of C++ online submissions for Search in Rotated Sorted Array II.
    */
    bool search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        int mid;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (nums[mid] == target) return true;
            else if (nums[mid] < target) {
                if (nums[mid] == nums[right]) {
                    // do not know whether it is rotated or not
                    // linear search
                    for (int i = mid; i <= right; i++) {
                        if (target == nums[i]) return true;
                    }
                    right = mid - 1;
                }
                else if (nums[mid] > nums[right]) {
                    // right part is rotated
                    if (target >= nums[right]) left = mid + 1;
                    else return false;
                }
                else {
                    // right part is not rotated
                    if (target <= nums[right]) left = mid + 1;
                    else right = mid - 1;
                }
            }
            else {
                if (nums[mid] == nums[left]) {
                    for (int i = left; i <= mid; i++) {
                        if (nums[i] == target) return true;
                    }
                    left = mid +1;
                }
                else if (nums[mid] < nums[left]) {
                    // left part is rotated
                    if (target <= nums[left]) right = mid - 1;
                    else return false;
                }
                else {
                    if (target >= nums[left]) right = mid -1;
                    else left = mid + 1;
                }
            }
        }
        return false;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    /*
    Runtime: 4 ms, faster than 98.90% of C++ online submissions for Remove Duplicates from Sorted List II.
    Memory Usage: 9 MB, less than 97.56% of C++ online submissions for Remove Duplicates from Sorted List II.
    */
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode h(0);
        h.next = head;
        ListNode* node = head;
        ListNode* parent = &h;
        while (node != NULL) {
            bool isdup = false;
            while (node != NULL && node->next != NULL) {
                if (node->val == node->next->val) {
                    ListNode* tmp = node;
                    node = node->next;
                    isdup = true;
                }
                else break;
            }
            if (isdup) {
                ListNode* tmp = node;
                parent->next = node->next;
                node = node->next;
            }
            else {
                parent = node;
                node = node->next;
            }
        }
        return h.next;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    /*
    83. Remove Duplicates from Sorted List
    Runtime: 8 ms, faster than 97.63% of C++ online submissions for Remove Duplicates from Sorted List.
    Memory Usage: 9.3 MB, less than 62.26% of C++ online submissions for Remove Duplicates from Sorted List.
    */
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* node = head;
        ListNode* parent = head;
        while (node != NULL) {
            while (node != NULL) {
                if (node->val != parent->val) break;
                else node = node->next;
            }
            parent->next = node;
            parent = node;
            // node = node->next;
        }
        return head;
    }
};

class Solution {
public:
    /*
    84. Largest Rectangle in Histogram
    Runtime: 16 ms, faster than 45.38% of C++ online submissions for Largest Rectangle in Histogram.
    Memory Usage: 10.5 MB, less than 82.86% of C++ online submissions for Largest Rectangle in Histogram.
    */
    int largestRectangleArea(vector<int>& heights) {
        stack<int> s;
        int res = 0;
        for (int i = 0; i < heights.size(); i++) {
            // if (s.empty() && heights[i] == 0) continue;
            if (s.empty() || heights[s.top()] <= heights[i]) {
                s.push(i);
            }
            else {
                while (!s.empty() && heights[s.top()] >= heights[i]) {
                    int n = s.top();
                    s.pop();
                    int area;
                    if (!s.empty())
                        area = heights[n] * (i - s.top() - 1);
                    else
                        area = heights[n] * (i);
                    res = max(res, area);
                }
                s.push(i);
            }
        }
        if (!s.empty()) {
            int size = heights.size();
            while (!s.empty()) {
                int n = s.top();
                s.pop();
                int area;
                if (!s.empty())
                    area = heights[n] * (size - s.top() - 1);
                else
                    area = heights[n] * (size);
                res = max(res, area);
            }
        }
        return res;
    }
};

class Solution {
public:
    /*
    Approach 2: sort from back to front
    Runtime: 4 ms, faster than 84.16% of C++ online submissions for Merge Sorted Array.
    Memory Usage: 8.8 MB, less than 69.57% of C++ online submissions for Merge Sorted Array.
    */
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int ptr1 = m - 1, ptr2 = n - 1, ptr3 = m + n - 1;
        while (ptr3 >= 0) {
            if (ptr1 >= 0 && ptr2 >= 0) {
                if (nums1[ptr1] > nums2[ptr2]) {
                    nums1[ptr3] = nums1[ptr1];
                    ptr1--;
                    ptr3--;
                }
                else {
                    nums1[ptr3] = nums2[ptr2];
                    ptr2--;
                    ptr3--;
                }
            }
            else {
                while (ptr1 >= 0) {
                    nums1[ptr3--] = nums1[ptr1--];
                }
                while (ptr2 >= 0) {
                    nums1[ptr3--] = nums2[ptr2--];
                }
            }
        }
    }
    /*
    Approach 1: merge and sort
    */
    void merge2(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        for (int i = m; i < m + n; i++) {
            nums1[i] = nums2[i - m];
        }
        sort(nums1.begin(), nums1.end());
    }
};

class Solution {
public:
    /*
    85. Maximal Rectangle
    Runtime: 24 ms, faster than 72.48% of C++ online submissions for Maximal Rectangle.
    Memory Usage: 11.2 MB, less than 61.11% of C++ online submissions for Maximal Rectangle.
    */
    int maxHistogram(vector<int>& hist) {
        int res = 0;
        stack<int> s;
        for (int i = 0; i < hist.size(); i++) {
            if (s.empty() || hist[s.top()] <= hist[i]) {
                s.push(i);
            }
            else {
                while (!s.empty() && hist[s.top()] >= hist[i]) {
                    int h = s.top();
                    s.pop();
                    if (s.empty()) res = max(res, hist[h] * i);
                    else res = max(res, hist[h] * (i - s.top() - 1));
                }
                s.push(i);
            }
        }
        int size = hist.size();
        while (!s.empty()) {
            int h = s.top();
            s.pop();
            if (s.empty()) res = max(res, hist[h] * (size));
            else res = max(res, hist[h] * (size - s.top() - 1));
        }
        return res;
    }
    int maximalRectangle(vector<vector<char>>& matrix) {
        int row = matrix.size();
        if (row == 0) return 0;
        int col = matrix[0].size();
        vector<int> hist(col, 0);
        int res = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] == '1') {
                    hist[j] ++;
                }
                else {
                    hist[j] = 0;
                }
            }
            res = max(res, maxHistogram(hist));
        }
        return res;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    /*
    86. Partition List
    Runtime: 8 ms, faster than 55.11% of C++ online submissions for Partition List.
    Memory Usage: 8.6 MB, less than 100.00% of C++ online submissions for Partition List.
    */
    ListNode* partition(ListNode* head, int x) {
        ListNode largeHeader(0);
        ListNode smallHeader(0);
        ListNode* node = head;
        ListNode* smallNode = &smallHeader;
        ListNode* largeNode = &largeHeader;
        ListNode* lastSmallNode = NULL;
        while (node != NULL) {
            ListNode* tmp = node;
            if (node->val < x) {
                smallNode->next = node;
                smallNode = node;
                lastSmallNode = node;
            }
            else {
                largeNode->next = node;
                largeNode = node;
            }
            node = node->next;
            tmp->next = NULL;
        }
        if (lastSmallNode == NULL) return largeHeader.next;
        lastSmallNode->next = largeHeader.next;
        return smallHeader.next;
    }
};

class Solution {
public:
    /*
    Approach 2: iterative approach. every time duplicate the subset of res
    Runtime: 4 ms, faster than 99.60% of C++ online submissions for Subsets II.
    Memory Usage: 9.2 MB, less than 100.00% of C++ online submissions for Subsets II.
    */
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int> > res = {{}};
        int s = 0;
        for (int i = 0; i < nums.size(); i++) {
            // dup all element in res and add new element
            if (i == 0 || nums[i] != nums[i-1]) s = 0;
            for (int j = res.size(); s < j; s++) {
                res.push_back(res[s]);
                res.back().push_back(nums[i]);
            }
        }
        return res;
    }
    /*
    90. Subsets II
    Approach: dfs
    Runtime: 8 ms, faster than 84.10% of C++ online submissions for Subsets II.
    Memory Usage: 9.5 MB, less than 50.00% of C++ online submissions for Subsets II.
    */
    vector<vector<int>> subsetsWithDup2(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        res.push_back(tmp);
        dfs(nums, 0);
        return res;
    }
    void dfs(vector<int>& nums, int pos) {
        for (int i = pos; i < nums.size(); i++) {
            if (i != pos && nums[i] == nums[i-1]) continue;
            tmp.push_back(nums[i]);
            res.push_back(tmp);
            dfs(nums, i+1);
            tmp.pop_back();
        }
    }
private:
    vector<vector<int> > res;
    vector<int> tmp;
};

class Solution {
public:
    /*
    89. Gray Code
    Runtime: 0 ms, faster than 100.00% of C++ online submissions for Gray Code.
    Memory Usage: 8.6 MB, less than 100.00% of C++ online submissions for Gray Code.
    */
    vector<int> grayCode(int n) {
        vector<int> nres;
        nres.push_back(0);
        int idx = 0;
        while (idx < n) {
            // duplicate s
            for (int i = nres.size()-1; i >= 0; i--) {
                int tmp = nres[i];
                tmp += pow(2, idx);
                nres.push_back(tmp);
            }
            idx++;
        }
        return nres;
    }
};

class Solution {
public:
    /*
    91. Decode Ways
    Runtime: 0 ms, faster than 100.00% of C++ online submissions for Decode Ways.
    Memory Usage: 8.3 MB, less than 98.04% of C++ online submissions for Decode Ways.
    */
    int numDecodings(string s) {
        int size = s.size();
        if (size == 0) return 0;
        if (size == 1) return s != "0";
        // table[i] -> possible solution for substr end at position i - 1
        int table[size + 1];
        memset(table, 0, sizeof(table));
        table[0] = 1;
        table[1] = 1;
        if (s[0] == '0' || (s[0] >= '3' && s[1] == '0')) {
            table[0] = 0; 
            table[1] = 0;
        }
        for (int i = 2; i <= size; i++) {
            if ((s[i-2] == '1' && s[i-1] != '0') || (s[i-2] == '2' && s[i-1] != '0' && s[i-1] <= '6')) {
                table[i] = table[i-1] + table[i-2];
            }
            else if ((s[i-2] == '1' || s[i-2] == '2') && s[i-1] == '0') {
                table[i] = table[i-2];
            }
            else if (s[i-1] != '0' ) {
                table[i] = table[i-1];
            }
        }
        return table[size];
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    /*
    92. Reverse Linked List II
    Runtime: 4 ms, faster than 66.90% of C++ online submissions for Reverse Linked List II.
    Memory Usage: 8.6 MB, less than 87.50% of C++ online submissions for Reverse Linked List II.
    */
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode header(0);
        header.next = head;
        ListNode* parent = &header;
        ListNode* node = head;
        for (int i = 1; i < m; i++) {
            parent = node;
            node = node->next;
        }
        ListNode* revParent = parent;
        ListNode* revHeader = node;
        ListNode* child = node->next;
        parent = parent->next;
        node = node->next;
        for (int i = m; i < n; i++) {
            ListNode* tmp = node->next;
            node->next = parent;
            parent = node;
            node = tmp;
        }
        revParent->next = parent;
        revHeader->next = node;
        return header.next;
    }
};

class Solution {
public:
    /*
    93. Restore IP Addresses
    Approach 1: recursive. For each try, check 1, 2, 3 digits for validation.
    Runtime: 0 ms, faster than 100.00% of C++ online submissions for Restore IP Addresses.
    Memory Usage: 9.2 MB, less than 16.67% of C++ online submissions for Restore IP Addresses.
    */
    vector<string> restoreIpAddresses(string s) {
        dfs(s.c_str(), s.size());
        return res;
    }
    void dfs(const char* s, int n) {
        if (count > 4) return;
        if (n == 0 && count == 4) {
            res.push_back(tmp);
        }
        else {
            if (valid(s, 1)) {
                if (!tmp.empty()) tmp += '.';
                tmp += s[0];
                count++;
                dfs(s+1, n-1);
                count--;
                for (int i = 0; i < 1; i++) tmp.pop_back();
                if (!tmp.empty()) tmp.pop_back();
            }
            if (valid(s, 2)) {
                if (!tmp.empty()) tmp += '.';
                tmp += s[0];
                tmp += s[1];
                count++;
                dfs(s+2, n-2);
                count--;
                for (int i = 0; i < 2; i++) tmp.pop_back();
                if (!tmp.empty()) tmp.pop_back();
            }
            if (valid(s, 3)) {
                if (!tmp.empty()) tmp += '.';
                tmp += s[0];
                tmp += s[1];
                tmp += s[2];
                count++;
                dfs(s+3, n-3);
                count--;
                for (int i = 0; i < 3; i++) tmp.pop_back();
                if (!tmp.empty()) tmp.pop_back();
            }
        }
    }
    bool valid(const char* s, int n) {
        if (n == 1) {
            if (s[0] >= '0' && s[0] <= '9') return true;
            else return false;
        }
        else if (n == 2) {
            if (s[0] >= '1' && s[0] <= '9' && s[1] >= '0' && s[1] <= '9') return true;
            else return false;
        }
        else {
            if (s[0] == '1') {
                if (s[1] >= '0' && s[1] <= '9' && s[2] >= '0' && s[2] <= '9') return true;
                else return false;
            }
            else if (s[0] == '2') {
                if (s[1] >= '0' && s[1] <= '4' && s[2] >= '0' && s[2] <= '9') return true;
                else if (s[1] == '5' && s[2] <= '5') return true;
                else return false;
            }
            else return false;
        }
    }
private:
    vector<string> res;
    string tmp;
    int count = 0;
};

/**
 * 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:
    /*
    Approach 2: iteratively. Basic idea: push node to stack if it is left child.
    Runtime: 4 ms, faster than 59.19% of C++ online submissions for Binary Tree Inorder Traversal.
    Memory Usage: 9 MB, less than 98.00% of C++ online submissions for Binary Tree Inorder Traversal.
    */
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        if (root == NULL) return res;
        stack<TreeNode*> s;
        s.push(root);
        TreeNode* node = root;
        while (!s.empty()) {
            while (node != NULL) {
                if (node->left != NULL) {
                    s.push(node->left);
                }
                node = node->left;
            }
            node = s.top();
            s.pop();
            res.push_back(node->val);
            if (node->right != NULL) {
                s.push(node->right);
            }
            node = node->right;
        }
        return res;
    }
    /*
    Approach 1: recursive
    Runtime: 4 ms, faster than 59.19% of C++ online submissions for Binary Tree Inorder Traversal.
    Memory Usage: 9.5 MB, less than 45.00% of C++ online submissions for Binary Tree Inorder Traversal.
    */
    vector<int> inorderTraversal2(TreeNode* root) {
        vector<int> res;
        dfs(res, root);
        return res;
    }
    void dfs(vector<int>& res, TreeNode* root) {
        if (root == NULL) return;
        if (root->left != NULL) {
            dfs(res, root->left);
        }
        res.push_back(root->val);
        if (root->right != NULL) {
            dfs(res, root->right);
        }
    }
};

/**
 * 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:
    /*
    95. Unique Binary Search Trees II
    Approach 1: recursive search
    Runtime: 16 ms, faster than 84.40% of C++ online submissions for Unique Binary Search Trees II.
    Memory Usage: 20.8 MB, less than 5.55% of C++ online submissions for Unique Binary Search Trees II.
    */
    vector<TreeNode*> generateTrees(int n) {
        vector<TreeNode*> res = gen(n, 0);
        return res;
    }
    vector<TreeNode*> gen(int n, int base) {
        vector<TreeNode*> res;
        if (n == 0) {
            return res;
        };
        if (n == 1) {
            res.push_back(new TreeNode(n + base));
            return res;
        }
        else {
            // bondary
            vector<TreeNode*> leftright = gen(n-1, 1 + base);
            for (int i = 0; i < leftright.size(); i++) {
                TreeNode* tmp = new TreeNode(base + 1);
                tmp->right = leftright[i];
                res.push_back(tmp);
            }
            for (int i = 2; i < n; i++) {
                vector<TreeNode*> left = gen(i-1, base);
                vector<TreeNode*> right = gen(n-i, i + base);
                for (int j = 0; j < left.size(); j++) {
                    for (int k = 0; k < right.size(); k++) {
                        if (left[j] == NULL && right[k] == NULL) continue;
                        TreeNode* node = new TreeNode(i + base);
                        node->left = left[j];
                        node->right = right[k];
                        res.push_back(node);
                    }
                }
            }
            // bondary
            vector<TreeNode*> rightleft = gen(n-1, base);
            for (int i = 0; i < rightleft.size(); i++) {
                TreeNode* tmp = new TreeNode(n + base);
                tmp->left = rightleft[i];
                res.push_back(tmp);
            }
            return res;
        }
    }
};

class Solution {
public:
    /*
    96. Unique Binary Search Trees
    Runtime: 4 ms, faster than 52.11% of C++ online submissions for Unique Binary Search Trees.
    Memory Usage: 8.2 MB, less than 100.00% of C++ online submissions for Unique Binary Search Trees.
    */
    int numTrees(int n) {
        int table[n+1];
        memset(table, 0, sizeof(table));
        table[0] = 1;
        table[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                table[i] += table[i - j] * table[j-1];
            }
        }
        return table[n];
    }
};

/**
 * 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:
    /*
    98. Validate Binary Search Tree
    Runtime: 16 ms, faster than 62.17% of C++ online submissions for Validate Binary Search Tree.
    Memory Usage: 20.3 MB, less than 97.92% of C++ online submissions for Validate Binary Search Tree.
    */
    bool isValidBST(TreeNode* root) {
        return isValidBSTHelper(root, ((long long)INT_MIN)-1, ((long long)INT_MAX)+1);
    }
    bool isValidBSTHelper(TreeNode* root, long long minval, long long maxval) {
        if (root == NULL) return true;
        if (root->val > minval && root->val < maxval) {
            if (isValidBSTHelper(root->left, minval, root->val) && isValidBSTHelper(root->right, root->val, maxval)) return true;
        }
        return false;
    }
};

/**
 * 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:
    /*
    100. Same Tree
    Runtime: 4 ms, faster than 59.00% of C++ online submissions for Same Tree.
    Memory Usage: 9.6 MB, less than 100.00% of C++ online submissions for Same Tree.
    */
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == NULL && q == NULL) return true;
        else if (p == NULL) return false;
        else if (q == NULL) return false;
        if (p->val == q->val) {
            if (isSameTree(p->left, q->left) && isSameTree(p->right, q->right)) return true;
        }
        return false;
    }
};

/**
 * 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:
    /*
    101. Symmetric Tree
    Runtime: 4 ms, faster than 83.82% of C++ online submissions for Symmetric Tree.
    Memory Usage: 14.6 MB, less than 100.00% of C++ online submissions for Symmetric Tree.
    */
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        return isSym(root->left, root->right);
    }
    bool isSym(TreeNode* left, TreeNode* right) {
        if (left == NULL && right == NULL) return true;
        else if (left == NULL || right == NULL) return false;
        if (left->val == right->val) {
            if (isSym(left->left, right->right) && isSym(left->right, right->left)) return true;
        }
        return false;
    }
};

/**
 * 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:
    /*
    Version 2: queue helper is only used to count how many node should be added to q latter. There is another way to do this. using a temp variable n to store the size of queue before add.
    Runtime: 4 ms, faster than 93.30% of C++ online submissions for Binary Tree Level Order Traversal.
    Memory Usage: 13.7 MB, less than 98.59% of C++ online submissions for Binary Tree Level Order Traversal.
    */
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int> > res;
        if (root == NULL) return res;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();
            vector<int> line;
            line.push_back(node->val);
            int n = q.size();
            if (node->left != NULL) q.push(node->left);
            if (node->right != NULL) q.push(node->right);
            for (int i = 0; i < n; i++) {
                TreeNode* n = q.front();
                q.pop();
                line.push_back(n->val);
                if (n->left != NULL) q.push(n->left);
                if (n->right != NULL) q.push(n->right);
            }
            res.push_back(line);
        }
        return res;
    }
    /*
    102. Binary Tree Level Order Traversal
    Version 1: using a helper queue to store all elements that will be added to the q latter
    Runtime: 8 ms, faster than 57.21% of C++ online submissions for Binary Tree Level Order Traversal.
    Memory Usage: 13.8 MB, less than 98.59% of C++ online submissions for Binary Tree Level Order Traversal.
    */
    vector<vector<int>> levelOrder2(TreeNode* root) {
        // bfs
        vector<vector<int> > res;
        if (root == NULL) return res;
        queue<TreeNode*> q;
        q.push(root);
        queue<TreeNode*> qbackup;
        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();
            vector<int> line;
            line.push_back(node->val);
            if (node->left != NULL) qbackup.push(node->left);
            if (node->right != NULL) qbackup.push(node->right);
            while (!q.empty()) {
                TreeNode* n = q.front();
                q.pop();
                line.push_back(n->val);
                if (n->left != NULL) qbackup.push(n->left);
                if (n->right != NULL) qbackup.push(n->right);
            }
            while (!qbackup.empty()) {
                q.push(qbackup.front());
                qbackup.pop();
            }
            res.push_back(line);
        }
        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:
    /*
    103. Binary Tree Zigzag Level Order Traversal
    Runtime: 8 ms, faster than 41.40% of C++ online submissions for Binary Tree Zigzag Level Order Traversal.
    Memory Usage: 13.5 MB, less than 93.02% of C++ online submissions for Binary Tree Zigzag Level Order Traversal.
    */
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int> > res;
        if (!root) return res;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();
            int n = q.size();
            if (node->left != NULL) q.push(node->left);
            if (node->right != NULL) q.push(node->right);
            vector<int> line;
            line.push_back(node->val);
            for (int i = 0; i < n; i++) {
                TreeNode* tmpnode = q.front();
                q.pop();
                line.push_back(tmpnode->val);
                if (tmpnode->left != NULL) q.push(tmpnode->left);
                if (tmpnode->right != NULL) q.push(tmpnode->right);
            }
            res.push_back(line);
        }
        for (int i = 0; i < res.size(); i++) {
            if (i % 2 == 1) {
                reverse(res[i].begin(), res[i].end());
            }
        }
        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:
    /*
    104. Maximum Depth of Binary Tree
    Recursive search. O(N)
    Runtime: 12 ms, faster than 57.78% of C++ online submissions for Maximum Depth of Binary Tree.
    Memory Usage: 19.5 MB, less than 64.84% of C++ online submissions for Maximum Depth of Binary Tree.
    */
    int maxDepth2(TreeNode* root) {
        if (root == NULL) return 0;
        return max(maxDepth(root->left) + 1, maxDepth(root->right) + 1);
    }
    /*
    Iteratively BFS. O(N)
    Runtime: 12 ms, faster than 57.78% of C++ online submissions for Maximum Depth of Binary Tree.
    Memory Usage: 19.2 MB, less than 94.51% of C++ online submissions for Maximum Depth of Binary Tree.
    */
    int maxDepth(TreeNode* root) {
        if (root == NULL) return 0;
        // bfs
        queue<TreeNode*> q;
        q.push(root);
        int depth = 0;
        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();
            depth += 1;
            int n = q.size();
            if (node->left != NULL) q.push(node->left);
            if (node->right != NULL) q.push(node->right);
            for (int i = 0; i < n; i++) {
                TreeNode* tn = q.front();
                q.pop();
                if (tn->left != NULL) q.push(tn->left);
                if (tn->right != NULL) q.push(tn->right);
            }
        }
        return depth;
    }
};

/**
 * 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:
    /*
    105. Construct Binary Tree from Preorder and Inorder Traversal
    Recursively construct tree
    Runtime: 16 ms, faster than 79.61% of C++ online submissions for Construct Binary Tree from Preorder and Inorder Traversal.
    Memory Usage: 16.5 MB, less than 95.24% of C++ online submissions for Construct Binary Tree from Preorder and Inorder Traversal.
    */
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return build(preorder, 0, preorder.size(), inorder, 0, inorder.size());
    }
    TreeNode* build(vector<int>& preorder, int prestart, int preend, vector<int>& inorder, int instart, int inend) {
        if (preend <= prestart || inend <= instart) return NULL;
        TreeNode* root = new TreeNode(preorder[prestart]);
        int i;
        for (i = 0; i < inend - instart; i++) {
            if (inorder[instart+i] == preorder[prestart]) break;
        }
        root->left = build(preorder, prestart+1, prestart+1+i, inorder, instart, instart+i);
        root->right = build(preorder, prestart+1+i, preend, inorder, instart+i+1, inend);
        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:
    /*
    106. Construct Binary Tree from Inorder and Postorder Traversal
    Recursive approach:
    Runtime: 20 ms, faster than 54.55% of C++ online submissions for Construct Binary Tree from Inorder and Postorder Traversal.
    Memory Usage: 16.7 MB, less than 94.44% of C++ online submissions for Construct Binary Tree from Inorder and Postorder Traversal.
    */
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return build(inorder, 0, inorder.size(), postorder, 0, postorder.size());
    }
    TreeNode* build(vector<int>& inorder, int instart, int inend, vector<int>& postorder, int poststart, int postend) {
        if (instart >= inend || poststart >= postend) return NULL;
        TreeNode* root = new TreeNode(postorder[postend-1]);
        int i = 0;
        for (i = 0; i < inend - instart; i++) {
            if (inorder[i+instart] == postorder[postend-1]) break;
        }
        root->left = build(inorder, instart, instart+i, postorder, poststart, poststart+i);
        root->right = build(inorder, instart+i+1, inend, postorder, poststart+i, postend-1);
        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:
    /*
    107. Binary Tree Level Order Traversal II
    Runtime: 4 ms, faster than 95.21% of C++ online submissions for Binary Tree Level Order Traversal II.
    Memory Usage: 13.6 MB, less than 100.00% of C++ online submissions for Binary Tree Level Order Traversal II.
    */
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int> > res;
        if (root == NULL) return res;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();
            int n = q.size();
            if (node->left != NULL) q.push(node->left);
            if (node->right != NULL) q.push(node->right);
            vector<int> line;
            line.push_back(node->val);
            for (int i = 0; i < n; i++) {
                TreeNode* n = q.front();
                q.pop();
                line.push_back(n->val);
                if (n->left != NULL) q.push(n->left);
                if (n->right != NULL) q.push(n->right);
            }
            res.push_back(line);
        }
        reverse(res.begin(), res.end());
        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:
    /*
    108. Convert Sorted Array to Binary Search Tree
    Runtime: 16 ms, faster than 86.52% of C++ online submissions for Convert Sorted Array to Binary Search Tree.
    Memory Usage: 21 MB, less than 97.30% of C++ online submissions for Convert Sorted Array to Binary Search Tree.
    */
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return toBST(nums, 0, nums.size());
    }
    TreeNode* toBST(vector<int>& nums, int start, int end) {
        if (end <= start) return NULL;
        int mid = start + (end - start) / 2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = toBST(nums, start, mid);
        root->right = toBST(nums, mid+1, end);
        return root;
    }
};

/**
 * 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 {
public:
    /*
    Approach 2: directly manuplate list
    Runtime: 36 ms, faster than 19.98% of C++ online submissions for Convert Sorted List to Binary Search Tree.
    Memory Usage: 24.6 MB, less than 50.00% of C++ online submissions for Convert Sorted List to Binary Search Tree.
    */
    TreeNode* sortedListToBST2(ListNode* head) {
        int size = 0;
        ListNode* node = head;
        while (node != NULL) {
            size += 1;
            node = node->next;
        }
        return buildBST(head, size);
    }
    TreeNode* buildBST(ListNode* head, int size) {
        if (size == 0 || head == NULL) return NULL;
        int mid = size / 2;
        ListNode* node = head;
        for (int i = 0; i < mid; i++) {
            node = node->next;
        }
        TreeNode* root = new TreeNode(node->val);
        root->left = buildBST(head, mid);
        root->right = buildBST(node->next, size-mid-1);
        return root;
    }
    /*
    109. Convert Sorted List to Binary Search Tree
    Simple approach: convert vector and then build bst
    Runtime: 32 ms, faster than 45.45% of C++ online submissions for Convert Sorted List to Binary Search Tree.
    Memory Usage: 24.7 MB, less than 22.73% of C++ online submissions for Convert Sorted List to Binary Search Tree.
    */
    TreeNode* sortedListToBST(ListNode* head) {
        vector<int> nums;
        ListNode* node = head;
        while (node != NULL) {
            nums.push_back(node->val);
            node = node->next;
        }
        return build(nums, 0, nums.size());
    }
    TreeNode* build(vector<int>& nums, int start, int end) {
        if (start >= end) return NULL;
        int mid = start + (end - start) / 2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = build(nums, start, mid);
        root->right = build(nums, mid+1, end);
        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:
    /*
    Better approach: think about a sorted list that 2 nums are swapped. what will be the best solution to recover it?
    just scan fron left to right, record the num that are not in order. and swap them after scaning.
    Runtime: 20 ms, faster than 87.56% of C++ online submissions for Recover Binary Search Tree.
    Memory Usage: 17.5 MB, less than 100.00% of C++ online submissions for Recover Binary Search Tree.
    */
    void recoverTree(TreeNode* root) {
        inorder(root);
        if (first != NULL && second != NULL) {
            swap(first->val, second->val);
        }
    }
    void inorder(TreeNode* root) {
        if (root == NULL) return;
        inorder(root->left);
        if (pre != NULL && pre->val >= root->val) {
            if (first == NULL) {
                first = pre;
            }
            second = root;
        }
        pre = root;
        inorder(root->right);
    }
    /*
    99. Recover Binary Search Tree
    Simple solution. store all values and assign value.
    Runtime: 24 ms, faster than 69.24% of C++ online submissions for Recover Binary Search Tree.
    Memory Usage: 18.5 MB, less than 42.10% of C++ online submissions for Recover Binary Search Tree.
    */
    void recoverTree2(TreeNode* root) {
        dfs(root);
        sort(nodelist.begin(), nodelist.end());
        dfs2(root);
    }
    void dfs(TreeNode* root) {
        if (root == NULL) return;
        dfs(root->left);
        nodelist.push_back(root->val);
        dfs(root->right);
    }
    void dfs2(TreeNode* root) {
        if (root == NULL) return;
        dfs2(root->left);
        root->val = nodelist[ptr++];
        dfs2(root->right);
    }
private:
    vector<int> nodelist;
    int ptr = 0;
    TreeNode* pre = NULL, *first = NULL, *second = NULL;
};

class Solution {
public:
    /*
    97. Interleaving String
    dynamic programming: 2D table to store s1 prefix and s2 prefix will be interleave of s3 prefix
    Runtime: 4 ms, faster than 78.66% of C++ online submissions for Interleaving String.
    Memory Usage: 8.3 MB, less than 100.00% of C++ online submissions for Interleaving String.
    */
    bool isInterleave2(string s1, string s2, string s3) {
        int size1 = s1.size();
        int size2 = s2.size();
        if (size1 + size2 != s3.size()) return false;
        bool table[size1+1][size2+1];
        memset(table, 0, sizeof(table));
        table[0][0] = true;
        for (int i = 1; i <= size1; i++) {
            if (table[i-1][0] && s1[i-1] == s3[i-1]) table[i][0] = true;
            else break;
        }
        for (int j = 1; j <= size2; j++) {
            if (table[0][j-1] && s2[j-1] == s3[j-1]) table[0][j] = true;
            else break;
        }
        for (int i = 1; i <= size1; i++) {
            for (int j = 1; j <= size2; j++) {
                if (table[i-1][j] && s1[i-1] == s3[i+j-1]) table[i][j] = true;
                if (table[i][j-1] && s2[j-1] == s3[i+j-1]) table[i][j] = true;
            }
        }
        return table[size1][size2];
    }
};

/**
 * 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:
    /*
    110. Balanced Binary Tree
    recursive search
    Runtime: 16 ms, faster than 55.65% of C++ online submissions for Balanced Binary Tree.
    Memory Usage: 17.2 MB, less than 96.61% of C++ online submissions for Balanced Binary Tree.
    */
    bool isBalanced(TreeNode* root) {
        if (root == NULL) return true;
        return height(root) != -1;
    }
    int height(TreeNode* root) {
        if (root == NULL) return 0;
        int left = height(root->left);
        if (left == -1) return -1;
        int right = height(root->right);
        if (right == -1) return -1;
        return abs(left-right) > 1 ? -1 : max(left, right) + 1;
    }
};

/**
 * 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:'
    /*
    recursive approach.
    Runtime: 16 ms, faster than 41.15% of C++ online submissions for Minimum Depth of Binary Tree.
    Memory Usage: 19.8 MB, less than 69.05% of C++ online submissions for Minimum Depth of Binary Tree.
    */
    int minDepth(TreeNode* root) {
        if (root == NULL) return 0;
        if (!root->left) return 1 + minDepth(root->right);
        if (!root->right) return 1 + minDepth(root->left);
        return min(minDepth(root->left), minDepth(root->right)) + 1;
    }
    /*
    111. Minimum Depth of Binary Tree
    iterative approach.
    Runtime: 16 ms, faster than 41.15% of C++ online submissions for Minimum Depth of Binary Tree.
    Memory Usage: 19.3 MB, less than 100.00% of C++ online submissions for Minimum Depth of Binary Tree.
    */
    int minDepth2(TreeNode* root) {
        if (root == NULL) return 0;
        // BFS
        queue<TreeNode*> q;
        q.push(root);
        int height = 0;
        while (!q.empty()) {
            height += 1;
            TreeNode* node = q.front();
            q.pop();
            int n = q.size();
            if (node->left == NULL && node->right == NULL) return height;
            if (node->left != NULL) q.push(node->left);
            if (node->right != NULL) q.push(node->right);
            for (int i = 0; i < n; i++) {
                node = q.front();
                q.pop();
                if (node->left == NULL && node->right == NULL) return height; 
                if (node->left != NULL) q.push(node->left);
                if (node->right != NULL) q.push(node->right);
            }
        }
        return height;
    }
};

/**
 * 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:
    /*
    112. Path Sum
    Runtime: 12 ms, faster than 75.44% of C++ online submissions for Path Sum.
    Memory Usage: 19.6 MB, less than 100.00% of C++ online submissions for Path Sum.
    */
    bool hasPathSum(TreeNode* root, int sum) {
        if (root == NULL) return false;
        if (root->left == NULL && root->right == NULL) return root->val == sum;
        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:
    /*
    113. Path Sum II
    Runtime: 12 ms, faster than 86.18% of C++ online submissions for Path Sum II.
    Memory Usage: 19.7 MB, less than 92.11% of C++ online submissions for Path Sum II.
    */
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        dfs(root, sum);
        return res;
    }
    void dfs(TreeNode* root, int sum) {
        if (root == NULL) return;
        else if (root->left == NULL && root->right == NULL && sum == root->val) {
            tmp.push_back(root->val);
            res.push_back(tmp);
            tmp.pop_back();
        }
        else {
            tmp.push_back(root->val);
            dfs(root->left, sum - root->val);
            dfs(root->right, sum - root->val);
            tmp.pop_back();
        }
    }
private:
    vector<vector<int> > res;
    vector<int> tmp;
};

/**
 * 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:
    /*
    Approach 2: modify the dfs
    Runtime: 4 ms, faster than 93.50% of C++ online submissions for Flatten Binary Tree to Linked List.
    Memory Usage: 9.7 MB, less than 87.50% of C++ online submissions for Flatten Binary Tree to Linked List.
    */
    void flatten(TreeNode* root) {
        if (!root) return;
        stack<TreeNode*> s;
        s.push(root);
        while (!s.empty()) {
            TreeNode* node = s.top();
            s.pop();
            if (node->right) {
                s.push(node->right);
            }
            if (node->left) {
                s.push(node->left);
            }
            node->left = NULL;
            node->right = NULL;
            if (!s.empty()) node->right = s.top();
        }
    }
    /*
    Approach: used a vector to store the node
    Runtime: 4 ms, faster than 93.50% of C++ online submissions for Flatten Binary Tree to Linked List.
    Memory Usage: 9.9 MB, less than 50.00% of C++ online submissions for Flatten Binary Tree to Linked List.
    */
    void flatten2(TreeNode* root) {
        if (!root) return;
        // bfs
        stack<TreeNode*> s;
        s.push(root);
        vector<TreeNode*> store;
        while (!s.empty()) {
            TreeNode* node = s.top();
            s.pop();
            store.push_back(node);
            if (node->right != NULL) s.push(node->right);
            if (node->left != NULL) s.push(node->left);

        }
        TreeNode* node = root;
        for (int i = 1; i < store.size(); i++) {
            node->right = store[i];
            node->left = NULL;
            node = store[i];
        }
    }
};

/*
// 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:
    /*
    Iterative BFS
    Runtime: 60 ms, faster than 45.75% of C++ online submissions for Populating Next Right Pointers in Each Node.
    Memory Usage: 27.2 MB, less than 92.86% of C++ online submissions for Populating Next Right Pointers in Each Node.
    */
    Node* connect2(Node* root) {
        if (!root) return NULL;
        queue<Node*> q;
        q.push(root);
        while (!q.empty()) {
            Node* node = q.front();
            q.pop();
            int n = q.size();
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
            for (int i = 0; i < n; i++) {
                Node* tmpnode = q.front();
                q.pop();
                if (tmpnode->left) q.push(tmpnode->left);
                if (tmpnode->right) q.push(tmpnode->right);
                node->next = tmpnode;
                node = tmpnode;
            }
        }
        return root;
    }
};

/*
// 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:
    /*
    117. Populating Next Right Pointers in Each Node II
    Runtime: 384 ms, faster than 96.40% of C++ online submissions for Populating Next Right Pointers in Each Node II.
    Memory Usage: 66.7 MB, less than 47.83% of C++ online submissions for Populating Next Right Pointers in Each Node II.
    */
    Node* connect(Node* root) {
        if (!root) return root;
        queue<Node*> q;
        q.push(root);
        while (!q.empty()) {
            int n = q.size();
            Node* parent = NULL;
            for (int i = 0; i < n; i++) {
                Node* node = q.front();
                q.pop();
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
                if (parent != NULL) {
                    parent->next = node;
                }
                parent = node;
            }
        }
        return root;
    }
};

class Solution {
public:
    /*
    118. Pascal's Triangle
    Runtime: 4 ms, faster than 60.36% of C++ online submissions for Pascal's Triangle.
    Memory Usage: 8.8 MB, less than 74.07% of C++ online submissions for Pascal's Triangle.
    */
    vector<vector<int>> generate(int numRows) {
        vector<vector<int> > res;
        if (numRows == 0) return res;
        res.push_back({1});
        for (int i = 1; i < numRows; i++) {
            vector<int> line(i+1);
            line[0] = 1;
            line[i] = 1;
            for (int j = 1; j < i; j++) {
                line[j] = res[i-1][j] + res[i-1][j-1];
            }
            res.push_back(line);
        }
        return res;
    }
};

class Solution {
public:
    /*
    119. Pascal's Triangle II
    Runtime: 4 ms, faster than 59.24% of C++ online submissions for Pascal's Triangle II.
    Memory Usage: 8.4 MB, less than 93.55% of C++ online submissions for Pascal's Triangle II.
    */
    vector<int> getRow(int rowIndex) {
        vector<int> line1(rowIndex+1, 0);
        vector<int> line2(rowIndex+1, 0);
        line1[0] = 1;
        line2[0] = 1;
        bool flag = true;
        for (int i = 1; i <= rowIndex; i++) {
            for (int j = 1; j <= i; j++) {
                if (flag) {
                    line2[j] = line1[j] + line1[j-1];
                }
                else {
                    line1[j] = line2[j] + line2[j-1];
                }
            }
            flag = !flag;
        }
        if (flag) return line1;
        else return line2;
    }
};

class Solution {
public:
    /*
    120. Triangle
    viterbi algorithm.
    Runtime: 4 ms, faster than 95.91% of C++ online submissions for Triangle.
    Memory Usage: 9.7 MB, less than 100.00% of C++ online submissions for Triangle.v
    */
    int minimumTotal(vector<vector<int>>& triangle) {
        int size = triangle.size();
        int minlength = INT_MAX;
        for (int i = 1; i < size; i++) {
            for (int j = 0; j < triangle[i].size(); j++) {
                if (j == 0) triangle[i][j] += triangle[i-1][j];
                else if (j == triangle[i].size() - 1) triangle[i][j] += triangle[i-1][j-1];
                else triangle[i][j] = min(triangle[i-1][j], triangle[i-1][j-1]) + triangle[i][j];
            }
        }
        for (int i = 0; i < triangle[size-1].size(); i++) {
            if (minlength > triangle[size-1][i]) minlength = triangle[size-1][i];
        }
        return minlength;
    }
};

class Solution {
public:
    /*
    Approach 2: using one element to store the minvalue
    Runtime: 4 ms, faster than 98.21% of C++ online submissions for Best Time to Buy and Sell Stock.
    Memory Usage: 9.5 MB, less than 95.41% of C++ online submissions for Best Time to Buy and Sell Stock.
    */
    int maxProfit(vector<int>& prices) {
        int minprice = INT_MAX;
        int maxprofit = 0;
        for (int i = 0; i < prices.size(); i++) {
            if (minprice > prices[i]) minprice = prices[i];
            int profit = prices[i] - minprice;
            if (profit > maxprofit) maxprofit = profit;
        }
        return maxprofit;
    }
    /*
    121. Best Time to Buy and Sell Stock
    approach 1: use two array to store the current highest price and lowest price
    Runtime: 4 ms, faster than 98.21% of C++ online submissions for Best Time to Buy and Sell Stock.
    Memory Usage: 9.7 MB, less than 25.69% of C++ online submissions for Best Time to Buy and Sell Stock.
    */
    int maxProfit2(vector<int>& prices) {
        int size = prices.size();
        if (size == 0) return 0;
        int largetable[size];
        int smalltable[size];
        memset(largetable, 0, sizeof(largetable));
        memset(smalltable, 0, sizeof(smalltable));
        for (int i = 0; i < size; i++) {
            if (i == 0) {
                smalltable[i] = prices[i];
            }
            else {
                smalltable[i] = min(prices[i], smalltable[i-1]);
            }
        }
        for (int i = size-1; i >= 0; i--) {
            if (i == size-1) {
                largetable[i] = prices[i];
            }
            else {
                largetable[i] = max(prices[i], largetable[i+1]);
            }
        }
        int maxprofit = 0;
        for (int i = 0; i < size; i++) {
            int profit = largetable[i] - smalltable[i];
            if (profit > maxprofit) maxprofit = profit;
        }
        return maxprofit;
    }
};

class Solution {
public:
    /*
    Approach 2: since the time of transaction is not limited, we can always buy today and sell tomorry.
    Runtime: 4 ms, faster than 98.07% of C++ online submissions for Best Time to Buy and Sell Stock II.
    Memory Usage: 9.4 MB, less than 100.00% of C++ online submissions for Best Time to Buy and Sell Stock II.
    */
    int maxProfit(vector<int>& prices) {
        int size = prices.size();
        if (size == 0) return 0;
        int profit = 0;
        for (int i = 1; i < size; i++) {
            int pro = prices[i]-prices[i-1];
            if (pro > 0) profit += pro;
        }
        return profit;
    }
    /*
    122. Best Time to Buy and Sell Stock II
    Approach 1: similar to the previous problem. table[i][j] represent the maxprofit of the sub array start at i and end at j. 
    runtime: O(n^2), memeory: O(n)
    Runtime: 1344 ms, faster than 7.58% of C++ online submissions for Best Time to Buy and Sell Stock II.
    Memory Usage: 9.6 MB, less than 52.38% of C++ online submissions for Best Time to Buy and Sell Stock II.
    */
    int maxProfit2(vector<int>& prices) {
        int size = prices.size();
        if (size == 0) return 0;
        int table[size];
        memset(table, 0, sizeof(table));
        for (int i = 0; i < size; i++) {
            int minprice = INT_MAX;
            int maxprofit = 0;
            int base = 0;
            if (i > 0) base = table[i];
            for (int j = i; j < size; j++) {
                table[j] = base;
                if (minprice > prices[j]) minprice = prices[j];
                table[j] += prices[j] - minprice;
            }
        }
        return table[size-1];
    }
};

class Solution {
public:
    /*
    123. Best Time to Buy and Sell Stock III
    Approach 1: similar to previous approach
    Runtime: 1140 ms, faster than 5.04% of C++ online submissions for Best Time to Buy and Sell Stock III.
    Memory Usage: 9.7 MB, less than 50.00% of C++ online submissions for Best Time to Buy and Sell Stock III.
    */
    int maxProfit(vector<int>& prices) {
        int size = prices.size();
        if (size == 0) return 0;
        int table[size];
        memset(table, 0, sizeof(table));
        table[0] = 0;
        int minprice = prices[0];
        for (int i = 1; i < size; i++) {
            if (minprice > prices[i]) minprice = prices[i];
            table[i] = max(table[i-1], prices[i] - minprice);
        }
        int res = 0;
        for (int i = 1; i < size; i++) {
            minprice = INT_MAX;
            for (int j = i; j < size; j++) {
                if (minprice > prices[j]) minprice = prices[j];
                int profit = prices[j] - minprice;
                int maxprofit = profit + table[i];
                if (maxprofit > res) res = maxprofit;
            }
        }
        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:
    /*
    124. Binary Tree Maximum Path Sum
    Approach 1: simple dfs. for every root, path is either left + root + right, or parent + root + left / right
    Runtime: 40 ms, faster than 13.33% of C++ online submissions for Binary Tree Maximum Path Sum.
    Memory Usage: 25.2 MB, less than 45.45% of C++ online submissions for Binary Tree Maximum Path Sum.
    */
    int maxPathSum(TreeNode* root) {
        if (root == NULL) return 0;
        res = root->val;
        dfs(root);
        return res;
    }
    int dfs(TreeNode* root) {
        if (root == NULL) {
            return 0;
        }
        else {
            int left = max(0, dfs(root->left));
            int right = max(0, dfs(root->right));
            int path = root->val + left + right;
            res = max(path, res);
            return root->val + max(left, right);
        }
    }
private:
    int res = 0;
};

class Solution {
public:
    /*
    125. Valid Palindrome
    Runtime: 4 ms, faster than 99.21% of C++ online submissions for Valid Palindrome.
    Memory Usage: 9.3 MB, less than 89.80% of C++ online submissions for Valid Palindrome.
    */
    bool isSame(char a, char b) {
        if (a >= '0' && a <= '9' && b >= '0' && b <= '9') return a == b;
        else if ((a >= '0' && a <= '9') || b >= '0' && b <= '9') return false;
        else if (a == b || abs(a - b) == 'a' - 'A') return true;
        else return false;
    }
    bool isAlphanumeric(char a) {
        if (a >= 'a' && a <= 'z') return true;
        if (a >= 'A' && a <= 'Z') return true;
        if (a >= '0' && a <= '9') return true;
        return false;
    }
    bool isPalindrome(string s) {
        int left = 0, right = s.size() - 1;
        while (left < right) {
            if (!isAlphanumeric(s[left])) left++;
            else if (!isAlphanumeric(s[right])) right--;
            else if (!isSame(s[left], s[right])) return false;
            else {
                left++;
                right--;
            }
        }
        return true;
    }
};

class Solution {
public:
    /*
    using unordered set instead of mp will improve the performance.
    Runtime: 80 ms, faster than 80.06% of C++ online submissions for Word Ladder.
    Memory Usage: 13 MB, less than 90.91% of C++ online submissions for Word Ladder.
    */
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> mp;
        for (auto s : wordList) {
            mp.insert(s);
        }
        if (mp.find(endWord) == mp.end()) return 0;
        int len = 1;
        queue<string> q;
        q.push(beginWord);
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                string s = q.front();
                q.pop();
                for (int i = 0; i < s.size(); i++) {
                    char tmp = s[i];
                    for (char j = 'a'; j <= 'z'; j++) {
                        s[i] = j;
                        if (mp.find(s) != mp.end()) {
                            q.push(s);
                            mp.erase(s);
                        }
                    }
                    s[i] = tmp;
                }
            }
            len++;
            if (mp.find(endWord) == mp.end()) return len;
        }
        return 0;
    }
    /*
    127. Word Ladder
    Runtime: 564 ms, faster than 36.28% of C++ online submissions for Word Ladder.
    Memory Usage: 13.8 MB, less than 68.18% of C++ online submissions for Word Ladder.
    */
    int ladderLength2(string beginWord, string endWord, vector<string>& wordList) {
        map<string, int> mp;
        for (auto s : wordList) {
            mp[s] = 0;
        }
        if (mp.find(endWord) == mp.end()) return 0;
        mp[beginWord] = 1;
        queue<string> q;
        q.push(beginWord);
        while (!q.empty()) {
            string s = q.front();
            int idx = mp[s];
            q.pop();
            for (int i = 0; i < s.size(); i++) {
                char tmp = s[i];
                for (char j = 'a'; j <= 'z'; j++) {
                    s[i] = j;
                    if (mp.find(s) != mp.end() && mp[s] == 0) {
                        q.push(s);
                        mp[s] += idx + 1;
                    }
                }
                s[i] = tmp;
            }
            if (mp[endWord] != 0) break;
        }
        return mp[endWord];
    }
};

/**
 * 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:
    /*
    129. Sum Root to Leaf Numbers
    Runtime: 4 ms, faster than 74.27% of C++ online submissions for Sum Root to Leaf Numbers.
    Memory Usage: 12.6 MB, less than 57.69% of C++ online submissions for Sum Root to Leaf Numbers.
    */
    int sumNumbers(TreeNode* root) {
        dfs(root);
        return res;
    }
    void dfs(TreeNode* root) {
        if (root == NULL) {
            return;
        }
        else {
            tmp.push_back(root->val);
            if (root->left == NULL && root->right == NULL) {
                int num = 0;
                for (int i = 0; i < tmp.size(); i++) {
                    num *= 10;
                    num += tmp[i];
                }
                res += num;
            }
            if (root->left != NULL) dfs(root->left);
            if (root->right != NULL) dfs(root->right);
            tmp.pop_back();
        }
    }
private:
    vector<int> tmp;
    int res = 0;
};

class Solution {
public:
    /*
    130. Surrounded Regions
    Runtime: 24 ms, faster than 97.07% of C++ online submissions for Surrounded Regions.
    Memory Usage: 13.9 MB, less than 100.00% of C++ online submissions for Surrounded Regions.
    */
    void solve(vector<vector<char>>& board) {
        int row = board.size();
        if (row == 0) return;
        int col = board[0].size();
        for (int i = 0; i < row; i++) {
            if (board[i][0] == 'O') propagation(board, i, 0, row-1, col-1);
            if (board[i][col-1] == 'O') propagation(board, i, col-1, row-1, col-1);
        }
        for (int j = 1; j < col-1; j++) {
            if (board[0][j] == 'O') propagation(board, 0, j, row-1, col-1);
            if (board[row-1][j] == 'O') propagation(board, row-1, j, row-1, col-1);
        }
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (board[i][j] == 'O') board[i][j] = 'X';
                else if (board[i][j] == '.') board[i][j] = 'O';
            }
        }
    }
    void propagation(vector<vector<char> >& board, int i, int j, int row, int col) {
        board[i][j] = '.';
        if (i > 0 && board[i-1][j] == 'O') propagation(board, i-1, j, row, col);
        if (i < row && board[i+1][j] == 'O') propagation(board, i+1, j, row, col);
        if (j > 0 && board[i][j-1] == 'O') propagation(board, i, j-1, row, col);
        if (j < col && board[i][j+1] == 'O') propagation(board, i, j+1, row, col);
    }
};

class Solution {
public:
    /*
    131. Palindrome Partitioning
    Runtime: 16 ms, faster than 74.62% of C++ online submissions for Palindrome Partitioning.
    Memory Usage: 13.4 MB, less than 91.67% of C++ online submissions for Palindrome Partitioning.
    */
    vector<vector<string>> partition(string s) {
        int size = s.size();
        if (size == 0) return res;
        vector<vector<bool> > table(size, vector<bool>(size, false));
        for (int i = size-1; i >= 0; i--) {
            for (int j = i; j < size; j++) {
                if ((i == j || j - 1 == i) && s[i] == s[j]) table[i][j] = true;
                else if (s[i] == s[j] && table[i+1][j-1]) table[i][j] = true;
            }
        }
        dfs(table, 0, size, s);
        return res;
    }
    void dfs(vector<vector<bool> >& table, int pos, int size, string& s) {
        if (pos == size) {
            res.push_back(tmp);
            return;
        }
        else {
            for (int i = pos; i < size; i++) {
                if (table[pos][i]) {
                    tmp.push_back(s.substr(pos, i-pos+1));
                    dfs(table, i+1, size, s);
                    tmp.pop_back();
                }
            }
        }
    }
private:
    vector<vector<string> > res;
    vector<string> tmp;
};

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

    Node() {}

    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/
class Solution {
public:
    /*
    133. Clone Graph
    Runtime: 24 ms, faster than 72.34% of C++ online submissions for Clone Graph.
    Memory Usage: 16.7 MB, less than 83.33% of C++ online submissions for Clone Graph.
    */
    // dfs
    Node* cloneGraph(Node* node) {
        if (node == NULL) return NULL;
        if (mp.find(node->val) != mp.end()) return mp[node->val];
        Node* n = new Node(node->val);
        mp[node->val] = n;
        for (int i = 0; i < node->neighbors.size(); i++) {
            Node* nei = node->neighbors[i];
            n->neighbors.push_back(cloneGraph(nei));
        }
        return n;
        
    }
private:
    unordered_map<int, Node*> mp;
};

class Solution {
public:
    /*
    134. Gas Station
    Runtime: 4 ms, faster than 99.11% of C++ online submissions for Gas Station.
    Memory Usage: 8.9 MB, less than 100.00% of C++ online submissions for Gas Station.
    */
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int size = gas.size();
        int idx = -1;
        int current = 0;
        int s = 0;
        for (int i = 0; i < size; i++) {
            int pureCost = gas[i] - cost[i];
            if (idx == -1) idx = i;
            current += pureCost;
            s += pureCost;
            if (current < 0) {
                idx = -1;
                current = 0;
            }
        }
        return s >= 0? idx : -1;
        
    }
};

class Solution {
public:
    /*
    135. Candy
    Runtime: 28 ms, faster than 67.15% of C++ online submissions for Candy.
    Memory Usage: 10.6 MB, less than 46.15% of C++ online submissions for Candy.
    */
    int candy(vector<int>& ratings) {
        int size = ratings.size();
        if (size == 0) return 0;
        vector<int> table(size, 1);
        table[0] = 1;
        // monotone increasing
        for (int i = 1; i < size; i++) {
            if (ratings[i] > ratings[i-1]) {
                table[i] = table[i-1] + 1;
            }
        }
        for (int i = size-1; i > 0; i--) {
            if (ratings[i] < ratings[i-1]) {
                table[i-1] = max(table[i-1], table[i] + 1);
            }
        }
        return std::accumulate(table.begin(), table.end(), 0);
    }
};

class Solution {
public:
    /*
    136. Single Number
    Runtime: 16 ms, faster than 66.95% of C++ online submissions for Single Number.
    Memory Usage: 9.8 MB, less than 66.67% of C++ online submissions for Single Number.
    */
    int singleNumber(vector<int>& nums) {
        int num = 0;
        for (auto n : nums) {
            num ^= n;
        }
        return num;
    }
};

class Solution {
public:
    /*
    Approach 2: count number at every digit
    Time: O(n), Space: O(1)
    Runtime: 12 ms, faster than 70.74% of C++ online submissions for Single Number II.
    Memory Usage: 9.6 MB, less than 87.50% of C++ online submissions for Single Number II.
    */
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for (int i = 0; i < 32; i++) {
            int digit = 0;
            for (auto n : nums) {
                digit += (n >> i) & 1;
            }
            res += (digit % 3) << i;
        }
        return res;
    }
    /*
    137. Single Number II
    Approach: using set to store uniq element.
    Time: O(n), Space: O(n)
    Runtime: 16 ms, faster than 20.59% of C++ online submissions for Single Number II.
    Memory Usage: 10.5 MB, less than 12.50% of C++ online submissions for Single Number II.
    */
    int singleNumber2(vector<int>& nums) {
        unordered_set<int> mp;
        long long s = 0;
        for (auto n : nums) {
            mp.insert(n);
            s += n;
        }
        long long ss = 0;
        for (auto it : mp) {
            ss += it;
        }
        return (3 * ss - s) / 2;
    }
};

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

    Node() {}

    Node(int _val, Node* _next, Node* _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};
*/
class Solution {
public:
    /*
    Recursive approach. O(n), O(n)
    Runtime: 36 ms, faster than 36.18% of C++ online submissions for Copy List with Random Pointer.
    Memory Usage: 22.4 MB, less than 23.81% of C++ online submissions for Copy List with Random Pointer.
    */
    unordered_map<int, Node*> visited;
    Node* copyRandomList(Node* head) {
        if (head == NULL) return NULL;
        if (visited.find(head->val) != visited.end()) return visited[head->val];
        
        Node* tmp = new Node(head->val, NULL, NULL);
        visited[tmp->val] = tmp;
        tmp->next = copyRandomList(head->next);
        tmp->random = copyRandomList(head->random);
        return tmp;
    }
    /*
    138. Copy List with Random Pointer
    Runtime: 32 ms, faster than 73.44% of C++ online submissions for Copy List with Random Pointer.
    Memory Usage: 21.9 MB, less than 100.00% of C++ online submissions for Copy List with Random Pointer.
    */
    Node* copyRandomList2(Node* head) {
        Node* hd = new Node(0);
        hd->next = head;
        Node* node = head;
        while (node != NULL) {
            Node* tmp = new Node(node->val);
            tmp->next = NULL;
            tmp->random = NULL;
            tmp->next = node->next;
            node->next = tmp;
            node = tmp->next;
        }
        node = head;
        while (node != NULL) {
            Node* tmp = node->next;
            if (node->random != NULL) {
                tmp->random = node->random->next;
            }
            node = tmp->next;
        }
        Node* parent = hd;
        node = head;
        while (node != NULL) {
            parent->next = node->next;
            node->next = node->next->next;
            parent = parent->next;
            node = node->next;
        }
        return hd->next;
    }
};

class Solution {
public:
    /*
    Approach 2: dynamic programming
    O(n^2), O(n)
    Runtime: 8 ms, faster than 76.38% of C++ online submissions for Word Break.
    Memory Usage: 10.6 MB, less than 73.58% of C++ online submissions for Word Break.
    */
    bool wordBreak(string s, vector<string>& wordDict) {
        int size = s.size();
        bool table[size+1];
        memset(table, 0, sizeof(table));
        for (auto str:wordDict) {
            mp.insert(str);
        }
        table[0] = true;
        for (int i = 1; i <= size; i++) {
            for (int j = i-1; j >= 0; j--) {
                if (table[j] && (mp.find(s.substr(j, i-j)) != mp.end())) {
                    table[i] = true;
                    break;
                }
            }
        }
        return table[size];
    }
    /*
    Approach 1: recursively dfs
    */
    bool wordBreak2(string s, vector<string>& wordDict) {
        for (auto st:wordDict) {
            mp.insert(st);
            size = max(size, (int)st.size());
        }
        dfs(s, 0);
        return res;
    }
    void dfs(string str, int pos) {
        if (pos == str.size()) {
            res = true;
            return;
        }
        else {
            for (int i = size + pos; i >= 0; i--) {
                if (res) return;
                if (mp.find(str.substr(pos, i-pos)) != mp.end()) {
                    dfs(str, i);
                }
            }
        }
    }
private:
    unordered_set<string> mp;
    bool res = false;
    int size = 0;
};

class Solution {
public:
    /*
    Approach: modified dfs. using map to memorize all element.
    Runtime: 20 ms, faster than 49.08% of C++ online submissions for Word Break II.
    Memory Usage: 15.7 MB, less than 48.48% of C++ online submissions for Word Break II.
    */
    unordered_map<string, vector<string> > mp;
    vector<string> wordBreak2(string s, vector<string>& wordDict) {
        unordered_set<string> dict(wordDict.begin(), wordDict.end());
        return dfs2(s, dict);
    }
    vector<string> dfs2(string s, unordered_set<string>& dict) {
        vector<string> res;
        if (mp.find(s) != mp.end()) return mp[s];
        for (int i = s.size()-1; i >= 0; i--) {
            string word = s.substr(i);
            if (dict.find(word) != dict.end()) {
                if (i == 0) {
                    res.push_back(word);
                }
                else {
                    vector<string> shit = dfs2(s.substr(0, s.size()-word.size()), dict);
                    for (auto str : shit) {
                        res.push_back(str + " " + word);
                    }
                }

            }
        }
        mp[s] = res;
        return res;
    }
    /*
    Approach 1: dfs
    Time Limited Exceed
    */
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        int size = s.size();
        int sz = wordDict.size();
        vector<vector<bool> > table(size+1, vector<bool>(sz, false));
        for (int i = 1; i <= size; i++) {
            for (int j = 0; j < sz; j++) {
                int szt = wordDict[j].size();
                if (wordDict[j] == s.substr(i-1, szt)) {
                    table[i-1+szt][j] = true;
                }
            }
        }
        dfs(table, s, wordDict, size);
        return res;
    }
    void dfs(vector<vector<bool> >& table, string& s, vector<string>& wordDict, int pos) {
        if (pos == 0) {
            string str;
            for (int i = tmp.size()-1; i >= 0; i--) {
                str += tmp[i];
                if (i != 0) str += " ";
            }
            res.push_back(str);
        }
        else {
            for (int j = 0; j < wordDict.size(); j++) {
                if (table[pos][j]) {
                    tmp.push_back(wordDict[j]);
                    dfs(table, s, wordDict, pos-wordDict[j].size());
                    tmp.pop_back();
                }
            }
        }
    }
private:
    vector<string> res;
    vector<string> tmp;
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    /*
    141. Linked List Cycle
    Runtime: 12 ms, faster than 73.22% of C++ online submissions for Linked List Cycle.
    Memory Usage: 9.7 MB, less than 100.00% of C++ online submissions for Linked List Cycle.
    */
    bool hasCycle(ListNode *head) {
        ListNode* ptr1 = head;
        ListNode* ptr2 = head;
        while (ptr1 != NULL && ptr2 != NULL) {
            ptr1 = ptr1->next;
            if (ptr2->next != NULL) ptr2 = ptr2->next->next;
            else return false;
            if (ptr1 == ptr2) return true;
        }
        if (ptr2 == NULL || ptr1 == NULL) return false;
        else return true;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    /*
    142. Linked List Cycle II
    Runtime: 12 ms, faster than 74.94% of C++ online submissions for Linked List Cycle II.
    Memory Usage: 9.9 MB, less than 64.29% of C++ online submissions for Linked List Cycle II.
    */
    ListNode *detectCycle(ListNode *head) {
        if (head == NULL) return NULL;
        ListNode* ptr1 = head;
        ListNode* ptr2 = head->next;
        int step = 0;
        while (ptr2 != NULL && ptr1 != ptr2) {
            ptr1 = ptr1->next;
            ptr2 = ptr2->next;
            if (ptr2 != NULL) ptr2 = ptr2->next;
            step ++;
        }
        if (ptr2 == NULL) return NULL;
        ptr2 = head;
        ptr1 = head;
        for (int i = 0; i <= step; i++) ptr2 = ptr2->next;
        while (ptr1 != ptr2) {
            ptr1 = ptr1->next;
            ptr2 = ptr2->next;
        }
        return ptr1;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    /*
    143. Reorder List
    Runtime: 48 ms, faster than 77.05% of C++ online submissions for Reorder List.
    Memory Usage: 12.2 MB, less than 76.47% of C++ online submissions for Reorder List.
    */
    void reorderList(ListNode* head) {
        if (head == NULL) return;
        ListNode* node = head;
        int length = 0;
        while (node != NULL) {
            node = node->next;
            length ++;
        }
        node = head;
        ListNode* tail = head;
        ListNode* parent = tail;
        for (int i = 0; i < (length + 1) / 2; i++) {
            tail = tail->next;
            if (i != 0) parent = parent->next;
        }
        parent->next = NULL;
        while (tail != NULL) {
            ListNode* tmp = tail;
            ListNode* tmpChild = tail->next;
            tail->next = parent;
            parent = tmp;
            tail = tmpChild;
        }
        tail = parent;
        while (node != NULL && tail != NULL) {
            ListNode* tmp = node->next;
            ListNode* tmpTail = tail->next;
            node->next = tail;
            tail->next = tmp;
            node = tmp;
            tail = tmpTail;
        }
    }
};

/**
 * 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:
    /*
    144. Binary Tree Preorder Traversal
    Runtime: 0 ms, faster than 100.00% of C++ online submissions for Binary Tree Preorder Traversal.
    Memory Usage: 9.2 MB, less than 93.10% of C++ online submissions for Binary Tree Preorder Traversal.
    */
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> q;
        vector<int> res;
        if (root == NULL) return res;
        q.push(root);
        while (!q.empty()) {
            TreeNode* node = q.top();
            q.pop();
            res.push_back(node->val);
            if (node->right != NULL) q.push(node->right);
            if (node->left != NULL) q.push(node->left);
        }
        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:
    /*
    This is a inorder iteratively solution
    */
    vector<int> inorder(TreeNode* root) {
        stack<TreeNode*> s;
        while (!s.empty() || root) {
            while (root != NULL) {
                s.push(root);
                root = root->left;
            }
            root = s.top();
            res.push_back(root->val);
            s.pop();
            root = root->right;
        }
        return res;
    }
    /*
    Iteratively solution
    Runtime: 0 ms, faster than 100.00% of C++ online submissions for Binary Tree Postorder Traversal.
    Memory Usage: 9.1 MB, less than 93.55% of C++ online submissions for Binary Tree Postorder Traversal.
    */
    void postorder(TreeNode* root) {
        if (root == NULL) return;
        stack<TreeNode*> s;
        s.push(root);
        while (!s.empty()) {
            TreeNode* node = s.top();
            s.pop();
            res.push_back(node->val);
            if (node->left) s.push(node->left);
            if (node->right) s.push(node->right);
        }
        reverse(res.begin(), res.end());
    }
    vector<int> postorderTraversal(TreeNode* root) {
        // dfs(root);
        // inorder(root);
        postorder(root);
        return res;
    }
    /*
    Recursive solution
    Runtime: 0 ms, faster than 100.00% of C++ online submissions for Binary Tree Postorder Traversal.
    Memory Usage: 9.3 MB, less than 67.74% of C++ online submissions for Binary Tree Postorder Traversal.
    */
    void dfs(TreeNode* root) {
        if (root == NULL) return;
        dfs(root->left);
        dfs(root->right);
        res.push_back(root->val);
    }
private:
    vector<int> res;
};

/*
146. LRU Cache
Intuitive approach using linked list
Runtime: 124 ms, faster than 30.78% of C++ online submissions for LRU Cache.
Memory Usage: 40 MB, less than 37.81% of C++ online submissions for LRU Cache.
*/
class LRUCache {
public:
    LRUCache(int capacity) {
        size = capacity;
    }
    int get(int key) {
        bool find = false;
        int value = -1;
        if (mp.find(key) != mp.end()) {
            value = mp[key]->second;
            table.erase(mp[key]);
            table.push_front(make_pair(key, value));
            mp[key] = table.begin();
        }
        return value;
    }
    
    void put(int key, int value) {
        if (mp.find(key) != mp.end()) {
            table.erase(mp[key]);
        }
        table.push_front(make_pair(key, value));
        mp[key] = table.begin();
        if (table.size() > size) {
            mp.erase(table.back().first);
            table.pop_back();
        }
    }
private:
    list<pair<int, int> > table;
    unordered_map<int, list<pair<int, int> >::iterator> mp;
    int size = 0;
};

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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    /*
    insertion sort
    Runtime: 12 ms, faster than 100.00% of C++ online submissions for Insertion Sort List.
    Memory Usage: 9.5 MB, less than 85.19% of C++ online submissions for Insertion Sort List.
    */
    ListNode* insertionSortList(ListNode* head) {
        if (head == NULL) return head;
        ListNode* hd = new ListNode(INT_MIN);
        hd->next = head;
        ListNode* node = head;
        ListNode* pnode = hd;
        while (node != NULL) {
            if (pnode->val < node->val) {
                pnode = node;
                node = node->next;
            }
            else {
                ListNode* parent = hd;
                ListNode* p = hd->next;;
                while (p != node && p->val < node->val) {
                    parent = parent->next;
                    p = p->next;
                }
                ListNode* child = node->next;
                parent->next = node;
                pnode->next = node->next;
                node->next = p;
                node = child;
            }
        }
        return hd->next;;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    /*
    cheating
    Runtime: 44 ms, faster than 84.05% of C++ online submissions for Sort List.
    Memory Usage: 12.2 MB, less than 35.00% of C++ online submissions for Sort List.
    */
    ListNode* sortList2(ListNode* head) {
        ListNode* node = head;
        vector<int> nums;
        while (node != NULL) {
            nums.push_back(node->val);
            node = node->next;
        }
        sort(nums.begin(), nums.end());
        node = head;
        int ptr = 0;
        while (node != NULL) {
            node->val = nums[ptr++];
            node = node->next;
        }
        return head;
    }
    /*
    quick sort
    Runtime: 1244 ms, faster than 5.04% of C++ online submissions for Sort List.
    Memory Usage: 14.4 MB, less than 15.00% of C++ online submissions for Sort List.
    */
    ListNode* sortList3(ListNode* head) {
        if (head == NULL) return head;
        ListNode* pivot = head;
        ListNode preEle(0);
        ListNode postEle(0);
        ListNode* pre = &preEle;
        ListNode* post = &postEle;
        ListNode* node = head->next;
        while (node != NULL) {
            if (node->val <= pivot->val) {
                ListNode* child = node->next;
                pre->next = node;
                pre = node;
                pre->next = NULL;
                node = child;
            }
            else {
                ListNode* child = node->next;
                post->next = node;
                post = node;
                post->next = NULL;
                node = child;
            }
        }
        ListNode* sortedPre = sortList(preEle.next);
        ListNode* sortedPost = sortList(postEle.next);
        if (sortedPre != NULL) {
            node = sortedPre;
            while (node && node->next != NULL) {
                node = node->next;
            } 
            node->next = pivot;
            pivot->next = sortedPost;
            return sortedPre;
        }
        else {
            node = pivot;
            pivot->next = sortedPost;
            return pivot;
        }
    }
    /*
    Merge sort.
    Runtime: 40 ms, faster than 97.16% of C++ online submissions for Sort List.
    Memory Usage: 11.6 MB, less than 97.50% of C++ online submissions for Sort List.
    */
    ListNode* sortList(ListNode* head) {
        if (head == NULL || head->next == NULL) return head;
        ListNode* slow = head;
        ListNode* fast = head->next;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        fast = slow->next;
        slow->next = NULL;
        ListNode* first = sortList(head);
        ListNode* second = sortList(fast);
        ListNode N(0);
        ListNode* node = &N;
        while (first && second) {
            if (first->val <= second->val) {
                node->next = first;
                ListNode* child = first->next;
                first->next = NULL;
                first = child;
                node = node->next;
            }
            else {
                node->next = second;
                ListNode* child = second->next;
                second->next = NULL;
                second = child;
                node = node->next;
            }
        }
        while (first) {
            node->next = first;
            ListNode* child = first->next;
            first->next = NULL;
            first = child;
            node = node->next;
        }
        while (second) {
            node->next = second;
            ListNode* child = second->next;
            second->next = NULL;
            second = child;
            node = node->next;
        }
        return N.next;
    }
};

class Solution {
public:
    /*
    150. Evaluate Reverse Polish Notation
    Runtime: 16 ms, faster than 55.44% of C++ online submissions for Evaluate Reverse Polish Notation.
    Memory Usage: 11.6 MB, less than 73.68% of C++ online submissions for Evaluate Reverse Polish Notation.
    */
    bool isChar(string s) {
        if (s == "+" || s == "-" || s == "*" || s == "/") return true;
        else return false;
    } 
    int evalRPN(vector<string>& tokens) {
        stack<int> s;
        for (int i = 0; i < tokens.size(); i++) {
            if (!isChar(tokens[i])) {
                s.push(stoi(tokens[i]));
            }
            else {
                int first = s.top();
                s.pop();
                int second = s.top();
                s.pop();
                int res;
                if (tokens[i] == "+") {
                    res = first + second;
                }
                else if (tokens[i] == "-") {
                    res = second - first;
                }
                else if (tokens[i] == "*") {
                    res = first * second;
                }
                else {
                    res = second / first;
                }
                s.push(res);
            }
        }
        return s.top();
    }
};

class Solution {
public:
    /*
    151. Reverse Words in a String
    Runtime: 8 ms, faster than 78.15% of C++ online submissions for Reverse Words in a String.
    Memory Usage: 10 MB, less than 75.68% of C++ online submissions for Reverse Words in a String.
    */
    string reverseWords(string s) {
        int ptr1 = 0;
        int ptr2 = 0;
        while (ptr2 < s.size()) {
            if (s[ptr2] == ' ' && ptr1 == ptr2) {
                ptr1++;
                ptr2++;
            }
            else if (s[ptr2] != ' ') {
                ptr2++;
            }
            else {
                reverse(s.begin()+ptr1, s.begin()+ptr2);
                ptr2++;
                ptr1 = ptr2;
            }
        }
        if (ptr1 != ptr2) {
            reverse(s.begin()+ptr1, s.begin()+ptr2);
        }
        reverse(s.begin(), s.end());
        ptr1 = -1;
        string res;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] != ' ' || (ptr1 >= 0 && res[ptr1] != ' ')) {
                res += s[i];
                ptr1++;
            }
        }
        return res[ptr1] != ' '? res : res.substr(0, res.size()-1);
    }
};

class Solution {
public:
    /*
    152. Maximum Product Subarray
    Consider positive and negative separately. time: O(n), space: O(n)
    Runtime: 4 ms, faster than 88.85% of C++ online submissions for Maximum Product Subarray.
    Memory Usage: 9.2 MB, less than 67.50% of C++ online submissions for Maximum Product Subarray.
    */
    int maxProduct2(vector<int>& nums) {
        int size = nums.size();
        if (size == 0) return 0;
        int positive[size];
        int negative[size];
        memset(positive, -1, sizeof(positive));
        memset(negative, 1, sizeof(negative));
        positive[0] = max(-1, nums[0]);
        negative[0] = min(1, nums[0]);
        for (int i = 1; i < size; i++) {
            if (nums[i] > 0) {
                positive[i] = max(nums[i], nums[i]*positive[i-1]);
                negative[i] = min(nums[i], nums[i]*negative[i-1]);
            }
            else if (nums[i] < 0) {
                positive[i] = max(nums[i], nums[i]*negative[i-1]);
                negative[i] = min(nums[i], nums[i]*positive[i-1]);
            }
            else {
                positive[i] = 0;
                negative[i] = 0;
            }
        }
        int res = INT_MIN;
        for (int i = 0; i < size; i++) {
            if (positive[i] >= 0) {
                res = max(res, positive[i]);
            }
            if (negative[i] <= 0) {
                res = max(res, negative[i]);
            }
        }
        return res;
    }
    /*
    advance version: time: O(n), space: O(1)
    */
    int maxProduct(vector<int>& nums) {
        int size = nums.size();
        if (size == 0) return 0;
        int res = nums[0];
        int local_max = res;
        int local_min = res;
        for (int i = 1; i < size; i++) {
            if (nums[i] >= 0) {
                local_max = max(nums[i], nums[i]*local_max);
                local_min = min(nums[i], nums[i]*local_min);
            }
            else {
                local_min = min(nums[i], nums[i]*local_max);
                local_max = max(nums[i], nums[i]*local_min);
            }
            if (local_max > res) res = local_max;
        }
        return res;
    }
};

class Solution {
public:
    /*
    153. Find Minimum in Rotated Sorted Array
    Runtime: 4 ms, faster than 76.11% of C++ online submissions for Find Minimum in Rotated Sorted Array.
    Memory Usage: 8.8 MB, less than 73.33% of C++ online submissions for Find Minimum in Rotated Sorted Array.
    */
    int findMin2(vector<int>& nums) {
        if (nums.size() <= 0) return 0;
        int res = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] < res) res = nums[i];
        }
        return res;
    }
    /*
    binary search
    Runtime: 4 ms, faster than 76.11% of C++ online submissions for Find Minimum in Rotated Sorted Array.
    Memory Usage: 8.8 MB, less than 84.44% of C++ online submissions for Find Minimum in Rotated Sorted Array.
    */
    int findMin(vector<int>& nums) {
        if (nums.size() <= 0) return 0;
        int left = 0, right = nums.size()-1;
        int mid;
        int res = nums[left];
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (nums[left] > nums[mid]) {
                // left part is rotated
                right = mid - 1;
            }
            else if (nums[mid] > nums[right]) {
                // right part is rotated
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
            res = min(res, nums[mid]);
        }
        return res;
    }
};

class Solution {
public:
    /*
    version 1: binary search. O(logn) -> O(n)
    Runtime: 8 ms, faster than 59.83% of C++ online submissions for Find Minimum in Rotated Sorted Array II.
    Memory Usage: 9 MB, less than 31.25% of C++ online submissions for Find Minimum in Rotated Sorted Array II.
    */
    int findMin2(vector<int>& nums) {
        int left = 0, right = nums.size()-1;
        int mid;
        int res = nums[left];
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (nums[left] > nums[mid]) {
                right = mid - 1;
            }
            else if (nums[mid] > nums[right]) {
                left = mid + 1;
            }
            else if (nums[left] == nums[mid]) left++;
            else if (nums[right] == nums[mid]) right--;
            else right = mid - 1;
            if (res > nums[mid]) res = nums[mid];
        }
        return res;
    }
    /*
    version 2
    Runtime: 4 ms, faster than 98.71% of C++ online submissions for Find Minimum in Rotated Sorted Array II.
    Memory Usage: 8.7 MB, less than 100.00% of C++ online submissions for Find Minimum in Rotated Sorted Array II.
    */
    int findMin(vector<int>& nums) {
        int left = 0, right = nums.size()-1;
        int mid;
        while (left < right) {
            mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) left = mid + 1;
            else if (nums[mid] < nums[right]) right = mid;
            else right--;
        }
        return nums[left];
    }
};

class MinStack {
public:
    /*
    155. Min Stack
    Runtime: 32 ms, faster than 67.37% of C++ online submissions for Min Stack.
    Memory Usage: 17 MB, less than 56.36% of C++ online submissions for Min Stack.
    */
    /** initialize your data structure here. */
    MinStack() {
        
    }
    void push(int x) {
        s.push(x);
        if (minS.empty()) minS.push(x);
        else {
            if (minS.top() < x) minS.push(minS.top());
            else minS.push(x);
        }
    }
    
    void pop() {
        s.pop();
        minS.pop();
    }
    
    int top() {
        return s.top();
    }
    
    int getMin() {
        return minS.top();
    }
    stack<int> s;
    stack<int> minS;
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    /*
    160. Intersection of Two Linked Lists
    Simple list search
    Runtime: 48 ms, faster than 82.15% of C++ online submissions for Intersection of Two Linked Lists.
    Memory Usage: 16.9 MB, less than 59.26% of C++ online submissions for Intersection of Two Linked Lists.
    */
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int length1 = 0;
        int length2 = 0;
        ListNode* nodea = headA;
        while (nodea != NULL) {
            length1 ++;
            nodea = nodea->next;
        }
        ListNode* nodeb = headB;
        while (nodeb != NULL) {
            length2 ++;
            nodeb = nodeb->next;
        }
        nodea = headA;
        for (int i = 0; i < length1 - length2; i++) {
            nodea = nodea->next;
        }
        nodeb = headB;
        for (int i = 0; i < length2 - length1; i++) {
            nodeb = nodeb->next;
        }
        while (nodea != NULL && nodeb != NULL && nodea != nodeb) {
            nodea = nodea->next;
            nodeb = nodeb->next;
        }
        return nodea;
       
    }
};

class Solution {
public:
    /*
    162. Find Peak Element
    Runtime: 4 ms, faster than 96.76% of C++ online submissions for Find Peak Element.
    Memory Usage: 8.6 MB, less than 95.45% of C++ online submissions for Find Peak Element.
    */
    int findPeakElement(vector<int>& nums) {
        int size = nums.size();
        if (size < 2) return 0;
        int left = 0, right = size - 1;
        if (nums[left] > nums[left+1]) return left;
        if (nums[right] > nums[right-1]) return right;
        left++;
        right--;
        int mid;
        while (left < right) {
            mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid-1] && nums[mid] > nums[mid+1]) return mid;
            else if (nums[mid] > nums[mid-1]) left = mid + 1;
            else right = mid;
        }
        return left;
    }
};

struct Bucket {
    int minNum = INT_MAX;
    int maxNum = INT_MIN;
    bool used = false;
};
class Solution {
public:
    /*
    164. Maximum Gap
    use space to trade speed -> variation of bucket sort.
    speed roughly: O(n) space roughly: O(n/gaps)
    Runtime: 8 ms, faster than 85.74% of C++ online submissions for Maximum Gap.
    Memory Usage: 9.2 MB, less than 100.00% of C++ online submissions for Maximum Gap.
    */
    int maximumGap(vector<int>& nums) {
        // init the basic gap array
        int minN = INT_MAX;
        int maxN = INT_MIN;
        for (auto n : nums) {
            minN = min(n, minN);
            maxN = max(n, maxN);
        }
        int size = nums.size();
        if (size < 2) return 0;
        int gaps = (maxN - minN) / (size - 1);
        gaps = max(gaps, 1);
        int sizeBucket = (maxN - minN) / gaps + 1;
        Bucket buckets[sizeBucket];
        // shrink the interval of every bucket
        for (auto n : nums) {
            int idx = (n - minN) / gaps;
            buckets[idx].used = true;
            buckets[idx].minNum = min(buckets[idx].minNum, n);
            buckets[idx].maxNum = max(buckets[idx].maxNum, n);
        }
        int preMax = minN;
        int res = 0;
        for (int i = 0; i < sizeBucket; i++) {
            if (buckets[i].used) {
                res = max(res, buckets[i].minNum - preMax);
                preMax = buckets[i].maxNum;
            }
        }
        return res;
    }
};

class Solution {
public:
    /*
    167. Two Sum II - Input array is sorted
    Runtime: 8 ms, faster than 57.41% of C++ online submissions for Two Sum II - Input array is sorted.
    Memory Usage: 9.5 MB, less than 86.27% of C++ online submissions for Two Sum II - Input array is sorted.
    */
    vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int> res;
        int left = 0, right = numbers.size()-1;
        while (left <= right) {
            int s = numbers[left] + numbers[right];
            if (s < target) left++;
            else if (s > target) right--;
            else {
                res.push_back(left+1);
                res.push_back(right+1);
                return res;
            }
        }
        return res;
    }
};

class Solution {
public:
    /*
    168. Excel Sheet Column Title
    Runtime: 0 ms, faster than 100.00% of C++ online submissions for Excel Sheet Column Title.
    Memory Usage: 8 MB, less than 100.00% of C++ online submissions for Excel Sheet Column Title.
    */
    string convertToTitle(int n) {
        string s;
        while (n > 0) {
            n = n-1;
            int digit = n % 26;
            s += 'A'+digit;
            n = n / 26;
        }
        reverse(s.begin(), s.end());
        return s;
    }
};

class Solution {
public:
    /*
    169. Majority Element
    Runtime: 16 ms, faster than 96.67% of C++ online submissions for Majority Element.
    Memory Usage: 11 MB, less than 98.48% of C++ online submissions for Majority Element.
    */
    int majorityElement(vector<int>& nums) {
        int res;
        int count = 0;
        for (auto i : nums) {
            if (count > 0 && res != i) count--;
            else {
                count++;
                res = i;
            }
        }
        return res;
    }
};

class Solution {
public:
    /*
    165. Compare Version Numbers
    simple stoi and vector version
    Runtime: 4 ms, faster than 57.46% of C++ online submissions for Compare Version Numbers.
    Memory Usage: 8.6 MB, less than 52.17% of C++ online submissions for Compare Version Numbers.
    */
    int compareVersion(string version1, string version2) {
        vector<int> ver1vec;
        vector<int> ver2vec;
        int left = 0, right = 0;
        while (right < version1.size()) {
            if (version1[right] == '.') {
                int v = stoi(version1.substr(left, right - left));
                ver1vec.push_back(v);
                right++;
                left = right;
            }
            else right++;
        }
        ver1vec.push_back(stoi(version1.substr(left, right - left)));
        left = 0, right = 0;
        while (right < version2.size()) {
            if (version2[right] == '.') {
                int v = stoi(version2.substr(left, right - left));
                ver2vec.push_back(v);
                right++;
                left = right;
            }
            else right++;
        }
        ver2vec.push_back(stoi(version2.substr(left, right - left)));
        left = 0;
        while (left < ver1vec.size() && left < ver2vec.size()) {
            if (ver1vec[left] > ver2vec[left]) return 1;
            else if (ver1vec[left] < ver2vec[left]) return -1;
            else left++;
        }
        while (left < ver1vec.size()) {
            if (ver1vec[left] != 0) return 1;
            left++;
        }
        while (left < ver2vec.size()) {
            if (ver2vec[left] != 0) return -1;
            left++;
        }
        return 0;
    }
};

class Solution {
public:
    /*
    172. Factorial Trailing Zeroes
    Runtime: 0 ms, faster than 100.00% of C++ online submissions for Factorial Trailing Zeroes.
    Memory Usage: 8.2 MB, less than 92.86% of C++ online submissions for Factorial Trailing Zeroes.
    Actually, this problem is quit interesting. N! = 1 * 2 * ... * N;
    Numboer of 0 = Number of 5 since 5 * 2 = 10 and number of 2 is always greater than 10;
    thus, the problem becomes calculate the number of 5 appear in the equation.
    it is a variation of digit in number. we need to consider level by level.
    For example, 5, 10, 15, 20 will be included in N / 5;
    But 25, 125, will only be count as one.
    */
    int trailingZeroes(int n) {
        int divide = 5;
        int numOfFive = 0;
        while ((divide = (n / 5)) > 0) {
            numOfFive += divide;
            n = divide;
        }
        return numOfFive;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
/*
Approach 2: store left branch in stack.
time: O(n), space: O(h) where h is the height of tree.
Runtime: 60 ms, faster than 36.04% of C++ online submissions for Binary Search Tree Iterator.
Memory Usage: 24 MB, less than 100.00% of C++ online submissions for Binary Search Tree Iterator.
*/
class BSTIterator {
public:
    BSTIterator(TreeNode* root) {
        while (root) {
            s.push(root);
            root = root->left;
        }
    }
    
    /** @return the next smallest number */
    int next() {
        TreeNode* node = s.top();
        s.pop();
        int res = node->val;
        node = node->right;
        while (node) {
            s.push(node);
            node = node->left;
        }
        return res;
    }
    
    /** @return whether we have a next smallest number */
    bool hasNext() {
        return !s.empty();
    }
private:
    stack<TreeNode*> s;
};

/*
Approach 1: store all the element in a vector
time: O(n), space: O(n)
Runtime: 48 ms, faster than 95.66% of C++ online submissions for Binary Search Tree Iterator.
Memory Usage: 24.3 MB, less than 86.96% of C++ online submissions for Binary Search Tree Iterator.
*/
class BSTIterator2 {
public:
    BSTIterator2(TreeNode* root) {
        stack<TreeNode*> q;
        while (root || !q.empty()) {
            while (root != NULL) {
                q.push(root);
                root = root->left;
            }
            root = q.top();
            q.pop();
            inner.push_back(root->val);
            root = root->right;
        }
    }
    
    /** @return the next smallest number */
    int next() {
        return inner[idx++];
    }
    
    /** @return whether we have a next smallest number */
    bool hasNext() {
        if (idx >= inner.size()) return false;
        return true;
    }
private:
    vector<int> inner;
    int idx = 0;
};

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator* obj = new BSTIterator(root);
 * int param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */

```MySQL
# 175. Combine Two Tables
SELECT FirstName, LastName, City, State 
FROM Person left join Address
on Person.PersonId = Address.PersonId;

# left join will show all person in Person table

# Write your MySQL query statement below
# approach 1:

SELECT 
(SELECT DISTINCT Salary
FROM Employee 
ORDER BY Salary DESC 
LIMIT 1 OFFSET 1)
AS SecondHighestSalary;

# approach 2:
SELECT max(Salary) AS SecondHighestSalary 
FROM Employee 
where Salary < (select max(Salary) FROM Employee);

# 177. Nth Highest Salary
# Runtime: 185 ms, faster than 60.08% of MySQL online submissions for Nth Highest Salary.
# Memory Usage: 0B, less than 100.00% of MySQL online submissions for Nth Highest Salary.
CREATE FUNCTION getNthHighestSalary(N INT) RETURNS INT
BEGIN
  SET N=N-1;
  RETURN (
      # Write your MySQL query statement below.
      SELECT DISTINCT Salary FROM Employee ORDER BY Salary DESC LIMIT 1 OFFSET N
  );
END

class Solution {
public:
    /*
    174. Dungeon Game
    Runtime: 8 ms, faster than 69.19% of C++ online submissions for Dungeon Game.
    Memory Usage: 9.8 MB, less than 94.12% of C++ online submissions for Dungeon Game.
    */
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        // viterbi algotithm
        int row = dungeon.size();
        if (row == 0) return 0;
        int col = dungeon[0].size();
        // move to i, j the minimal cost
        int table[row][col]; 
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                table[i][j] = -1;
            }
        }
        table[row-1][col-1] = max(0, -1*dungeon[row-1][col-1]);
        for (int i = row-1; i >= 0; i--) {
            for (int j = col-1; j >= 0; j--) {
                if (i == row - 1 && j == col - 1) continue;
                int needCost = INT_MAX;
                if (i < row-1) {
                    needCost = min(needCost, table[i+1][j]);
                }
                if (j < col-1) {
                    needCost = min(needCost, table[i][j+1]);
                }
                table[i][j] = max(0, needCost - dungeon[i][j]);
            }
        }
        return table[0][0] + 1;
    }
};

# Write your MySQL query statement below
# 178. Rank Scores
SELECT Score, (SELECT COUNT(DISTINCT Score) from Scores as s2 where s2.score >= s1.score) AS Rank
FROM Scores as s1
order by Score DESC;

class Solution {
public:
    /*
    179. Largest Number
    Runtime: 8 ms, faster than 77.76% of C++ online submissions for Largest Number.
    Memory Usage: 9.3 MB, less than 27.27% of C++ online submissions for Largest Number.
    */
    static bool gt(string astr, string bstr) {
        return astr + bstr > bstr + astr;
    }
    string largestNumber(vector<int>& nums) {
        vector<string> nstr;
        for (auto i : nums) {
            nstr.push_back(to_string(i));
        }
        sort(nstr.begin(), nstr.end(), gt);
        string s;
        for (auto i : nstr) {
            s += i;
        }
        if (s.size() > 0 && s[0] == '0') return "0";
        return s;
    }
};

# Write your MySQL query statement below
# 180. Consecutive Numbers
select distinct a.num as ConsecutiveNums 
from Logs as a
inner join Logs as b on a.id+1 = b.id and a.num = b.num
inner join Logs as c on b.id+1 = c.id and a.num = c.num;

# Write your MySQL query statement below
# 181. Employees Earning More Than Their Managers
select tb1.Name as Employee
from Employee as tb1
inner join Employee as tb2
on tb1.ManagerId = tb2.Id and tb1.Salary > tb2.Salary;

# Write your MySQL query statement below
# 182. Duplicate Emails
select Email From 
(
    select Email, count(Email) as num
    from Person
    group by Email
) as tmp
where num > 1;

select Email from Person
group by Email
having count(Email) > 1;

# Write your MySQL query statement below
# 183. Customers Who Never Order
Select Name As Customers
from Customers
where Customers.Id not in
(
    Select CustomerId From orders
);

# Write your MySQL query statement below
# 184. Department Highest Salary
select Department.Name as Department, Employee.name as Employee, Employee.Salary as Salary
From Employee
join Department
on Department.Id = Employee.DepartmentId
where (Employee.DepartmentId, Employee.Salary) IN
(Select DepartmentId, max(Salary) from Employee group by DepartmentId);

class Solution {
public:
    /*
    187. Repeated DNA Sequences
    set approach
    Runtime: 52 ms, faster than 55.71% of C++ online submissions for Repeated DNA Sequences.
    Memory Usage: 20.6 MB, less than 59.09% of C++ online submissions for Repeated DNA Sequences.
    */
    vector<string> findRepeatedDnaSequences(string s) {
        vector<string> res;
        if (s.size() < 10) return res;
        unordered_set<string> pre;
        unordered_set<string> res_set;
        for (int i = 0; i < s.size() - 9; i++) {
            string subs = s.substr(i, 10);
            if (pre.find(subs) != pre.end()) {
                res_set.insert(subs);
            }
            pre.insert(subs);
        }
        for (unordered_set<string>::iterator it = res_set.begin(); it != res_set.end(); it++) {
            res.push_back(*it);
        }
        return res;
    }
};

class Solution {
public:
    /*
    189. Rotate Array
    Linear approach
    Runtime: 16 ms, faster than 85.77% of C++ online submissions for Rotate Array.
    Memory Usage: 9.3 MB, less than 100.00% of C++ online submissions for Rotate Array.
    */
    void rotate(vector<int>& nums, int k) {
        int size = nums.size();
        k = k % size;
        reverse(nums.begin()+size-k, nums.end());
        reverse(nums.begin(), nums.begin()+size-k);
        reverse(nums.begin(), nums.end());
    }
};

class Solution {
public:
    /*
    190. Reverse Bits
    Approach 1: using binary converation. need two pass and conversion from bit to int
    Runtime: 4 ms, faster than 68.66% of C++ online submissions for Reverse Bits.
    Memory Usage: 8.2 MB, less than 45.83% of C++ online submissions for Reverse Bits.
    */
    uint32_t reverseBits2(uint32_t n) {
        vector<int> bits;
        while (n > 0) {
            int bit = n % 2;
            n /= 2;
            bits.push_back(bit);
        }
        for (int i = bits.size(); i < 32; i++) bits.push_back(0);
        // reverse(bits.begin(), bits.end());
        uint32_t res = 0;
        for (int i = 0; i < 32; i++) {
            res *= 2;
            res += bits[i];
        }
        return res;
    }
    /*
    Approach 2: using bit  operation
    Runtime: 0 ms, faster than 100.00% of C++ online submissions for Reverse Bits.
    Memory Usage: 8.3 MB, less than 41.67% of C++ online submissions for Reverse Bits.
    */
    uint32_t reverseBits(uint32_t n) {
        uint32_t res = 0;
        for (int i = 0; i < 32; i++) {
            // find the i-th bit of n
            int bit = n & (1 << i);
            // put bit to the 32-i th bit
            if (bit != 0) res = res | (1 << (31 - i));
        }
        return res;
    }
};

class Solution {
public:
    /*
    191. Number of 1 Bits
    Runtime: 0 ms, faster than 100.00% of C++ online submissions for Number of 1 Bits.
    Memory Usage: 8.3 MB, less than 65.85% of C++ online submissions for Number of 1 Bits.
    */
    int hammingWeight2(uint32_t n) {
        int count = 0;
        while (n > 0) {
            count += n % 2;
            n /= 2;
        }
        return count;
    }
    /*
    Runtime: 4 ms, faster than 66.56% of C++ online submissions for Number of 1 Bits.
    Memory Usage: 8.3 MB, less than 41.46% of C++ online submissions for Number of 1 Bits.
    */
    int hammingWeight(uint32_t n) {
        int count = 0;
        for (int i = 0; i < 32; i++) {
            int digit = n & (1 << i);
            if (digit != 0) count++;
        }
        return count;
    }
};

class Solution {
public:
    /*
    198. House Robber
    Runtime: 0 ms, faster than 100.00% of C++ online submissions for House Robber.
    Memory Usage: 8.6 MB, less than 88.68% of C++ online submissions for House Robber.
    */
    int rob(vector<int>& nums) {
        int size = nums.size();
        if (size == 0) return 0;
        if (size == 1) return nums[0];
        if (size == 2) return max(nums[0], nums[1]);
        int table[size];
        memset(table, 0, sizeof(table));
        table[0] = nums[0];
        for (int i = 1; i < size; i++) {
            if (i < 2) {
                table[i] = max(nums[i], table[i-1]);
            }
            else {
                table[i] = max(nums[i] + table[i-2], table[i-1]);
            }
        }
        return table[size-1];
    }
};

/**
 * 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:
    /*
    199. Binary Tree Right Side View
    Runtime: 0 ms, faster than 100.00% of C++ online submissions for Binary Tree Right Side View.
    Memory Usage: 9.4 MB, less than 100.00% of C++ online submissions for Binary Tree Right Side View.
    */
    vector<int> rightSideView(TreeNode* root) {
        // bfs
        vector<int> res;
        if (root == NULL) return res;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int n = q.size();
            for (int i = 0; i < n; i++) {
                TreeNode* node = q.front();
                q.pop();
                if (node->left != NULL) q.push(node->left);
                if (node->right != NULL) q.push(node->right);
                if (i == n-1) {
                    res.push_back(node->val);
                }
            }
        }
        return res;
    }
};

class Solution {
public:
    /*
    200. Number of Islands
    Runtime: 16 ms, faster than 59.35% of C++ online submissions for Number of Islands.
    Memory Usage: 10.6 MB, less than 100.00% of C++ online submissions for Number of Islands.
    */
    void connectedComponent(vector<vector<char>>& grid, int i, int j) {
        if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size()) return;
        if (grid[i][j] != '1') return;
        grid[i][j] = '2';
        connectedComponent(grid, i+1, j);
        connectedComponent(grid, i-1, j);
        connectedComponent(grid, i, j+1);
        connectedComponent(grid, i, j-1);
    }
    int numIslands(vector<vector<char>>& grid) {
        int row = grid.size();
        if (row == 0) return 0;
        int col = grid[0].size();
        int count = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    connectedComponent(grid, i, j);
                }
            }
        }
        return count;
    }
};

class Solution {
public:
    /*
    166. Fraction to Recurring Decimal
    Runtime: 8 ms, faster than 58.63% of C++ online submissions for Fraction to Recurring Decimal.
    Memory Usage: 8.7 MB, less than 100.00% of C++ online submissions for Fraction to Recurring Decimal.
    */
    string fractionToDecimal(long long numerator, long long denominator) {
        if (numerator == 0) return "0";
        int flag = 1;
        if (numerator < 0 && denominator > 0) flag = -1;
        else if (numerator > 0 && denominator < 0) flag = -1;
        numerator = abs(numerator);
        denominator = abs(denominator);
        string res;
        // get the interger part
        if (numerator >= denominator) {
            long long digit = numerator / denominator;
            res += to_string(digit);
            numerator = numerator % denominator;
        }
        vector<int> remaining;
        if (res.size() == 0) res += '0';
        if (numerator > 0) {
            res += '.';
            remaining.push_back(numerator);
            numerator *= 10;
        }
        int idx = 0;
        bool recu = false;    
        while (numerator) {
            long long digit = numerator / denominator;
            numerator = numerator % denominator;
            for (idx = 0; idx < remaining.size(); idx++) {
                if (numerator == remaining[idx]) {
                    recu = true;
                    break;
                }
            }
            res += '0' + digit;
            remaining.push_back(numerator);
            if (recu) break;
            numerator *= 10;
        }
        if (recu) {
            int start = 0;
            for (; start < res.size() && res[start] != '.'; start++);
            string s = res.substr(0, start+1+idx);
            s += '(';
            s += res.substr(start+1+idx, res.size()-1-start-idx);
            s += ')';
            if (flag == -1) s = "-" + s;
            return s;
        }
        else {
            if (flag == -1) res = "-" + res;
            return res;
        }
    }
};

class Solution {
public:
    /*
    201. Bitwise AND of Numbers Range
    approach 1: straightforward bit and
    Runtime: 4 ms, faster than 98.82% of C++ online submissions for Bitwise AND of Numbers Range.
    Memory Usage: 8.3 MB, less than 63.64% of C++ online submissions for Bitwise AND of Numbers Range.
    */
    int rangeBitwiseAnd2(int m, int n) {
        if (n - m >= m) return 0;
        if ((n & m) == 0) return 0;
        int res = m;
        if (res == INT_MAX) return res;
        for (int i = m+1; i <= n; i++) {
            res &= i;
            if (i == INT_MAX) break;
        }
        return res;
    }
    /*
    approach 2: for continuous array, left common part would be the result
    Runtime: 8 ms, faster than 92.65% of C++ online submissions for Bitwise AND of Numbers Range.
    Memory Usage: 8.3 MB, less than 54.55% of C++ online submissions for Bitwise AND of Numbers Range.
    */
    int rangeBitwiseAnd(int m, int n) {
        int c = 0;
        while (m != n) {
            n>>=1;
            m>>=1;
            c++;
        }
        return n<<c;
    }
};

class Solution {
public:
    /*
    202. Happy Number
    approach 1: straightforward method
    Runtime: 4 ms, faster than 66.65% of C++ online submissions for Happy Number.
    Memory Usage: 8.7 MB, less than 23.08% of C++ online submissions for Happy Number.
    */
    bool isHappy2(int n) {
        if (n == 1) return true;
        if (s.find(n) != s.end()) return false;
        s.insert(n);
        int res = 0;
        while (n) {
            int digit = n % 10;
            res += digit * digit;
            n /= 10;
        }
        return isHappy(res);
    }
    /*
    Approach 2: simulate graph -> the problem become find the start position of loop
    Runtime: 4 ms, faster than 66.65% of C++ online submissions for Happy Number.
    Memory Usage: 8.1 MB, less than 100.00% of C++ online submissions for Happy Number.
    */
    int helper(int n) {
        int res = 0;
        while (n) {
            int digit = n % 10;
            res += digit * digit;
            n /= 10;
        }
        return res;
    }
    bool isHappy(int n) {
        int slow = n, fast = helper(n);
        while (slow != fast) {
            slow = helper(slow);
            fast = helper(fast);
            fast = helper(fast);
        }
        return slow == 1;
    }
private:
    unordered_set<int> s;
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    /*
    203. Remove Linked List Elements
    Runtime: 24 ms, faster than 94.94% of C++ online submissions for Remove Linked List Elements.
    Memory Usage: 11 MB, less than 67.92% of C++ online submissions for Remove Linked List Elements.
    */
    ListNode* removeElements(ListNode* head, int val) {
        ListNode hd(0);
        hd.next = head;
        ListNode* parent = &hd;
        ListNode* node = head;
        while (node != NULL) {
            if (node->val == val) {
                parent->next = node->next;
                // free(node);
                node = parent->next;
            }
            else {
                parent = parent->next;
                node = node->next;
            }
        }
        return hd.next;
    }
};

class Solution {
public:
    /*
    204. Count Primes
    approach 1: simple appraoch
    Runtime: 480 ms, faster than 14.96% of C++ online submissions for Count Primes.
    Memory Usage: 8.3 MB, less than 91.67% of C++ online submissions for Count Primes.
    */
    int countPrimes2(int n) {
        int cnt = 0;
        for (int i = 1; i < n; i++) {
            if (isPrime(i)) cnt++;
        }
        return cnt;
    }
    bool isPrime(int n) {
        if (n < 2) return false;
        int sq = sqrt(n);
        for (int i = 2; i <= sq; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
    /*
    approach 2: bottom up appraoch based on the fact that all non prime number will be constructed by prime number
    Runtime: 32 ms, faster than 80.25% of C++ online submissions for Count Primes.
    Memory Usage: 9.8 MB, less than 16.67% of C++ online submissions for Count Primes.
    */
    int countPrimes(int n) {
        if (n < 2) return 0;
        bool table[n];
        for (int i = 0; i < n; i++) table[i] = true;
        int cnt = 0;
        for (int i = 2; i < n; i++) {
            if (table[i-1]) {
                cnt ++;
                for (int j = 2; i * j < n; j++) {
                    table[i*j-1] = false;
                }
            }
        }
        return cnt;
    }
};

class Solution {
public:
    /*
    205. Isomorphic Strings
    Runtime: 8 ms, faster than 86.51% of C++ online submissions for Isomorphic Strings.
    Memory Usage: 9.2 MB, less than 82.00% of C++ online submissions for Isomorphic Strings.
    */
    bool isIsomorphic(string s, string t) {
        int size = s.size();
        if (size != t.size()) return false;
        char table[256];
        memset(table, 0, sizeof(table));
        for (int i = 0; i < size; i++) {
            if (table[s[i]] == 0) {
                table[s[i]] = t[i];
            }
            else {
                if (table[s[i]] != t[i]) return false;
            }
        }
        memset(table, 0, sizeof(table));
        for (int i = 0; i < size; i++) {
            if (table[t[i]] == 0) {
                table[t[i]] = s[i];
            }
            else {
                if (table[t[i]] != s[i]) return false;
            }
        }
        return true;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    /*
    206. Reverse Linked List
    approach 1: iterative approach
    Runtime: 4 ms, faster than 98.92% of C++ online submissions for Reverse Linked List.
    Memory Usage: 9.2 MB, less than 92.37% of C++ online submissions for Reverse Linked List.
    */
    ListNode* reverseList2(ListNode* head) {
        if (head == NULL) return head;
        ListNode hd(0);
        ListNode* parent = &hd;
        hd.next = head;
        ListNode* node = head;
        while (node != NULL) {
            ListNode* child = node->next;
            node->next = parent;
            parent = node;
            node = child;
        }
        head->next = NULL;
        return parent;
    }
    /*
    Apprach 2: recursive approach
    Runtime: 8 ms, faster than 77.35% of C++ online submissions for Reverse Linked List.
    Memory Usage: 9.4 MB, less than 22.14% of C++ online submissions for Reverse Linked List.
    */
    ListNode* recurReverse(ListNode* head) {
        if (head == NULL) return NULL;
        ListNode* parent = recurReverse(head->next);
        if (parent == NULL) {
            res = head;
            return head;
        }
        parent->next = head;
        return head;
    }
    ListNode* reverseList(ListNode* head) {
        if (head == NULL) return head;
        recurReverse(head);
        head->next = NULL;
        return res;
    }
private:
    ListNode* res;
};

class Solution {
public:
    /*
    207. Course Schedule
    Approach 1: brute force search
    Runtime: 76 ms, faster than 12.83% of C++ online submissions for Course Schedule.
    Memory Usage: 11.6 MB, less than 100.00% of C++ online submissions for Course Schedule.
    */
    bool canFinish2(int numCourses, vector<vector<int>>& prerequisites) {
        // topologic sort
        int count = 0;
        if (numCourses < 2) return true;
        bool table[numCourses];
        bool found[numCourses];
        memset(found, 0, sizeof(found));
        if (prerequisites.size() < 1) return true;
        bool mask[prerequisites.size()];
        memset(mask, 0, sizeof(mask));
        while (true) {
            bool change = false;
            memset(table, 0, sizeof(table));
            for (int i = 0; i < prerequisites.size(); i++) {
                if (mask[i]) continue;
                table[prerequisites[i][1]] = true;
            }
            for (int i = 0; i < numCourses; i++) {
                if (!table[i] && !found[i]) {
                    found[i] = true;
                    count++;
                    change = true;
                    for (int j = 0; j < prerequisites.size(); j++) {
                        if (prerequisites[j][0] == i) mask[j] = true;
                    }
                }
            }
            if (!change) break;
        }
        return count == numCourses;
    }
    /*
    appraoch 2: using queue
    Runtime: 76 ms, faster than 12.83% of C++ online submissions for Course Schedule.
    Memory Usage: 17.1 MB, less than 16.36% of C++ online submissions for Course Schedule.
    */
    bool canFinish(int n, vector<vector<int> >& prerequisites) {
        // generate adjacent matrix
        bool table[n][n];
        int adjacent[n];
        memset(table, 0, sizeof(table));
        memset(adjacent, 0, sizeof(adjacent));
        for (auto v : prerequisites) {
            table[v[1]][v[0]] = true;
        }
        for (int i = 0; i < n; i++) {
            int s = 0;
            for (int j = 0; j < n; j++) {
                s += table[i][j];
            }
            adjacent[i] = s;
        }
        queue<int> q;
        int count = 0;
        bool found[n];
        memset(found, 0, sizeof(found));
        while (true) {
            bool change = false;
            for (int i = 0; i < n; i++) {
                if (adjacent[i] == 0 && !found[i]) {
                    found[i] = true;
                    q.push(i);
                    count++;
                }
            }
            while (!q.empty()) {
                int idx = q.front();
                q.pop();
                for (int i = 0; i < n; i++) {
                    if (table[i][idx] == true) {
                        change = true;
                        table[i][idx] = false;
                        adjacent[i]--;
                    }
                }
            }
            if (!change) break;
        }
        return count == n;
        
    }
};

/*
208. suffix tria
This approach is quit straightforward.
Using similar approach of link hash
*/
class Node {
public:
    Node* table[26] = {NULL};
    bool end = false;
    Node() {

    }
    Node* get(char ch) {
        if (table[ch - 'a'] != NULL) return table[ch - 'a'];
        return NULL;
    }
    Node* put(char ch) {
        if (table[ch - 'a'] != NULL) return table[ch - 'a'];
        else {
            table[ch - 'a'] = new Node();
            return table[ch - 'a'];
        }
    }
    bool isEnd() {
        return end;
    }
};
class Trie {
public:
    /** Initialize your data structure here. */
    Node* root;
    Trie() {
        root = new Node();
    }
    
    /** Inserts a word into the trie. */
    void insert(string word) {
        Node* node = root;
        for (int i = 0; i < word.size(); i++) {
            Node* child = node->get(word[i]);
            if (child != NULL) {
                node = child;
            }
            else {
                node = node->put(word[i]);
            }
        }
        node->end = true;
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
        Node* node = root;
        for (int i = 0; i < word.size(); i++) {
            Node* child = node->get(word[i]);
            if (child == NULL) return false;
            node = child;
        }
        return node->isEnd();
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        Node* node = root;
        for (int i = 0; i < prefix.size(); i++) {
            Node* child = node->get(prefix[i]);
            if (child == NULL) return false;
            node = child;
        }
        return true;
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

class Solution {
public:
    /*
    209. Minimum Size Subarray Sum
    Slip window: O(n)
    Runtime: 12 ms, faster than 65.76% of C++ online submissions for Minimum Size Subarray Sum.
    Memory Usage: 10 MB, less than 64.71% of C++ online submissions for Minimum Size Subarray Sum.
    */
    int minSubArrayLen(int s, vector<int>& nums) {
        int left = 0, right = 0;
        int num = 0;
        int length = INT_MAX;
        while (left < nums.size()) {
            if (num < s && right < nums.size()) {
                num += nums[right];
                right ++;
            }
            else {
                // num >= s
                if (num >= s) length = min(length, right-left);
                num -= nums[left];
                left++;
            }
        }
        return length == INT_MAX ? 0 : length;
    }
};

class Solution {
public:
    /*
    210. Course Schedule II
    Runtime: 672 ms, faster than 5.21% of C++ online submissions for Course Schedule II.
    Memory Usage: 193.5 MB, less than 6.90% of C++ online submissions for Course Schedule II.
    */
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        // topologic sort
        vector<int> res;
        bool table[numCourses];
        bool found[numCourses];
        memset(found, 0, sizeof(found));
        int n = 0;
        while (true) {
            bool change = false;
            // search for 0 degree
            memset(table, 0, sizeof(table));
            for (auto v : prerequisites) {
                if (!found[v[1]]) {
                    table[v[0]] = true;
                }
            }
            for (int i = 0; i < numCourses; i++) {
                if (!found[i] && !table[i]) {
                    found[i] = true;
                    res.push_back(i);
                    n++;
                    change = true;
                }
            }
            if (!change) break;
        }
        if (n != numCourses) res.clear();
        return res;
    }
};

class Solution {
public:
    /*
    213. House Robber II
    Runtime: 0 ms, faster than 100.00% of C++ online submissions for House Robber II.
    Memory Usage: 8.6 MB, less than 94.29% of C++ online submissions for House Robber II.
    */
    int helper(vector<int>& nums, int start, int end) {
        if (end - start <= 0) return 0;
        if (end - start == 1) return nums[start];
        if (end - start == 2) return max(nums[start], nums[start+1]);
        int table[end-start];
        memset(table, 0, sizeof(table));
        table[0] = nums[start];
        table[1] = max(nums[start+1], nums[start]);
        for (int i = 2; i < end - start; i++) {
            table[i] = max(table[i-2] + nums[start+i], table[i-1]);
        }
        return table[end-start-1];
    }
    int rob(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        if (nums.size() == 1) return nums[0];
        return max(helper(nums, 0, nums.size()-1), helper(nums, 1, nums.size()));
    }
};

/*
211. Add and Search Word - Data structure design
Runtime: 112 ms, faster than 47.54% of C++ online submissions for Add and Search Word - Data structure design.
Memory Usage: 61.2 MB, less than 40.91% of C++ online submissions for Add and Search Word - Data structure design.
*/
struct Node {
    Node() {
        
    }
    void put(char ch) {
        Node* node = new Node();
        table[ch-'a'] = node;
    }
    Node* get(char ch) {
        return table[ch-'a'];
    }
    Node* table[26] = {NULL};
    bool isEnd = false;
};
class WordDictionary {
public:

    /** Initialize your data structure here. */
    WordDictionary() {
        root = new Node();
    }
    
    /** Adds a word into the data structure. */
    void addWord(string word) {
        int ptr = 0;
        Node* node = root;
        while (ptr < word.length()) {
            if (node->get(word[ptr]) == NULL) {
                node->put(word[ptr]);
            }
            node = node->get(word[ptr]);
            ptr++;
        }
        node->isEnd = true;
    }
    
    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    bool search(string word) {
        int ptr = 0;
        queue<Node*> q;
        q.push(root);
        bool isEnd = false;
        while (!q.empty() && ptr < word.length()) {
            if (word[ptr] == '.') {
                int k = q.size();
                for (; k > 0; k--) {
                    Node* node = q.front();
                    q.pop();
                    for (int i = 'a'; i <= 'z'; i++) {
                        Node* child = node->get(i);
                        if (child != NULL) q.push(child);
                    }
                }
            }
            else {
                int k = q.size();
                for (; k > 0; k--) {
                    Node* node = q.front();
                    q.pop();
                    Node* child = node->get(word[ptr]);
                    if (child != NULL) q.push(child);
                }
            }
            ptr++;
        }
        while (!q.empty()) {
            Node* node = q.front();
            q.pop();
            if (node->isEnd) isEnd = true;
        }
        return isEnd;
    }
private:
    Node* root;
};

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary* obj = new WordDictionary();
 * obj->addWord(word);
 * bool param_2 = obj->search(word);
 */

class Solution {
public:
    /*
    212. Word Search II
    dfs
    Runtime: 784 ms, faster than 10.07% of C++ online submissions for Word Search II.
    Memory Usage: 12.8 MB, less than 100.00% of C++ online submissions for Word Search II.
    */
    /*
    a better solution is build a suffix trie so that search for prefix could be reused
    */
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        row = board.size();
        col = board[0].size();
        vector<string> res;
        for (auto s : words) {
            bool found = false;
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    if (search(board, s, 0, i, j)) {
                        found = true;
                        res.push_back(s);
                        break;
                    }
                }
                if (found) break;
            }
        }
        return res;
    }
    bool search(vector<vector<char> >& board, string& words, int ptr, int x, int y) {
        if (ptr >= words.length()) return true;
        if (x < 0 || y < 0 || x >= row || y >= col) return false;
        if (board[x][y] == -1) return false;
        if (board[x][y] != words[ptr]) return false;
        char tmp = board[x][y];
        board[x][y] = -1;
        if (search(board, words, ptr+1, x-1, y)) {
            board[x][y] = tmp;
            return true;
        }
        if (search(board, words, ptr+1, x+1, y)) {
            board[x][y] = tmp;
            return true;
        }
        if (search(board, words, ptr+1, x, y-1)) {
            board[x][y] = tmp;
            return true;
        }
        if (search(board, words, ptr+1, x, y+1)) {
            board[x][y] = tmp;
            return true;
        }
        board[x][y] = tmp;
        return false;
    }
private:
    int row;
    int col;
};

class Solution {
public:
    /*
    215. Kth Largest Element in an Array
    O(nlogk)
    Runtime: 132 ms, faster than 5.52% of C++ online submissions for Kth Largest Element in an Array.
    Memory Usage: 9.3 MB, less than 75.76% of C++ online submissions for Kth Largest Element in an Array.
    */
    static bool cmp(int a, int b) {
        return a > b;
    }
    int findKthLargest2(vector<int>& nums, int k) {
        vector<int> heap(nums.begin(), nums.begin()+k);
        make_heap(heap.begin(), heap.end(), cmp);
        for (int i = k; i < nums.size(); i++) {
            if (nums[i] > heap[0]) {
                heap[0] = nums[i];
                make_heap(heap.begin(), heap.end(), cmp);
            }
        }
        return heap[0];
    }
};

class Solution {
public:
    /*
    216. Combination Sum III
    Runtime: 0 ms, faster than 100.00% of C++ online submissions for Combination Sum III.
    Memory Usage: 8.7 MB, less than 83.33% of C++ online submissions for Combination Sum III.
    */
    vector<vector<int>> combinationSum3(int k, int n) {
        dfs(k, n, 1);
        return res;
    }
    void dfs(int k, int n, int pos) {
        if (k == 0) {
            if (n == 0) res.push_back(tmp);
        }
        else {
            for (int i = pos; i <= 9; i++) {
                tmp.push_back(i);
                dfs(k-1, n-i, i+1);
                tmp.pop_back();
            }
        }
    }
private:
    vector<vector<int> > res;
    vector<int> tmp;
};

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> s;
        for (int i = 0; i < nums.size(); i++) {
            if (s.find(nums[i]) == s.end()) {
                s.insert(nums[i]);
            }
            else return true;
        }
        return false;
    }
};

class Solution {
public:
    /*
    brute force search
    */
    bool containsNearbyDuplicate2(vector<int>& nums, int k) {
        for (int i = 0; i < nums.size(); i++) {
            for (int j = 1; j <= k && i + j < nums.size(); j++) {
                if (nums[i] == nums[i+j]) return true;
            }
        }
        return false;
    }
    /*
    slip window + set
    Runtime: 28 ms, faster than 84.79% of C++ online submissions for Contains Duplicate II.
    Memory Usage: 14.6 MB, less than 88.24% of C++ online submissions for Contains Duplicate II.
    */
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_set<int> s;
        int size = nums.size();
        for (int i = 0; i < k && i < size; i++) {
            if (s.find(nums[i]) != s.end()) return true;
            s.insert(nums[i]);
        }
        
        for (int i = 0; i < size - k; i++) {
            if (s.find(nums[i+k]) != s.end()) return true;
            s.insert(nums[i+k]);
            s.erase(nums[i]);
        }
        
        return false;
    }
};