LeetCode

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> m;
        for (int i = 0; i < (int) nums.size(); i++) {
            if (m.count(target - nums[i])) return {m[target - nums[i]], i};
            else m[nums[i]] = i;
        }
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        return addHelper(l1, l2, 0);
    }
private:
    ListNode* addHelper(ListNode* l1, ListNode* l2, int carry) {
        if (!l1 && !l2) {
            if (carry) return new ListNode(carry);
            else return NULL;
        } else {
            int l1v = l1 ? l1->val : 0;
            int l2v = l2 ? l2->val : 0;
            ListNode* node = new ListNode((l1v + l2v + carry) % 10);
            carry = (l1v + l2v + carry) / 10;
            l1 = l1 ? l1->next : NULL;
            l2 = l2 ? l2->next : NULL;
            node->next = addHelper(l1, l2, carry);
            return node;
        }
    }
};

class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        d = []
        ntmp = 0
        nmax = 0
        for c in s:
            if not c in d:
                d.append(c)
                ntmp += 1
            else:
                loc = len(d) - d[::-1].index(c)
                d = d[loc:]
                d.append(c)
                ntmp = len(d)
            if ntmp > nmax:
                nmax = ntmp
        return nmax

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        i = 0
        j = 0
        s = []
        while i < len(nums1) and j < len(nums2):
            if nums1[i] < nums2[j]:
                s.append(nums1[i])
                i += 1
            else:
                s.append(nums2[j])
                j += 1
        if i == len(nums1):
            s = s + nums2[j:]
        else:
            s = s + nums1[i:]
        if len(s) % 2 != 0:
            ind = int((len(s) + 1) / 2)
            return float(s[ind-1])
        else:
            ind = int(len(s) / 2)
            return float((s[ind-1] + s[ind]) / 2)

class Solution:
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        s = list(s)
        ret = []
        maxl = 0
        for i in range(len(s)):
            # as a middle element
            for hf in range(len(s)):
                if i - hf < 0 or i + hf >= len(s):
                    break
                if s[i-hf] == s[i+hf]:
                    l = 2 * hf + 1
                    if l > maxl:
                        maxl = l
                        ret = s[i-hf:i+hf+1]
                else:
                    break
            # as a left element
            for hf in range(len(s)):
                if i - hf < 0 or i + hf + 1 >= len(s):
                    break
                if s[i-hf] == s[i+hf+1]:
                    l = 2 * (hf + 1)
                    if l > maxl:
                        maxl = l
                        ret = s[i-hf:i+hf+2]
                else:
                    break
        return "".join(ret)

class Solution:
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        n = len(s)
        rn = []
        if numRows == 1:
            return s
        for i in range(numRows):
            pd = 2 * (numRows - 1 - i)
            qd = 2 * i
            if pd == 0 or qd == 0:
                d = [max(pd, qd), max(pd, qd)]
            else:
                d = [pd, qd]
            ii = i
            flag = True
            while ii < len(s):
                rn.append(s[ii])
                ii += d[0] if flag == True else d[1]
                flag = not flag
        return "".join(rn)

class Solution:
    def reverse(self, x):
        """
        :type x: int
        :rtype: int
        """
        x_abs = abs(x)
        y_abs = 0
        n = 1
        while int(x_abs / (10**n)) > 0:
            n += 1
        while x_abs / 10 > 0:
            n -= 1
            y_abs += int(x_abs % 10) * (10 ** n)
            x_abs  = int(x_abs / 10)
        y = y_abs if x > 0 else 0 - y_abs
        if y >= -2**31 and y <= 2**31-1:
            return y
        else:
            return 0

class Solution:
    digits = [str(x) for x in range(10)]
    def initFilter(self, str):
        istr = ''
        for s in str:
            if s in self.digits:
                istr += s
            else:
                break
        return istr
    def myAtoi(self, str):
        """
        :type str: str
        :rtype: int
        """
        str = str.lstrip(' ')
        if len(str) == 0 or str == '+' or str == '-':
            return 0
        if str[0] not in self.digits + ['+', '-']:
            return 0
        if str[0] in self.digits:
            d = int(self.initFilter(str))
            if d > (2 ** 31 - 1):
                return 2**31 - 1
            else:
                return d
        if str[0] in ['+', '-']:
            if str[1] in self.digits:
                if str[0] == '+':
                    d = int(self.initFilter(str[1:]))
                else:
                    d = -int(self.initFilter(str[1:]))
            else:
                d = 0
            if d < -2**31:
                return -2**31
            elif d > 2**31 - 1:
                return 2**31 - 1
            else:
                return d

class Solution:
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """
        s = str(x)
        return True if s == s[::-1] else False

class Solution:
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        if len(p) == 0:
            return True if len(s) == 0 else False
        if len(p) == 1:
            if len(s) == 0:
                return False
            elif len(s) == 1 and p == '.':
                return True
            elif p == s:
                return True
            else:
                return False
        if p[1] != '*':
            if len(s) == 0:
                return False
            if p[0] == s[0] or p[0] == '.':
                return self.isMatch(s[1:], p[1:])
            else:
                return False
        else:
            if len(s) == 0:
                return self.isMatch(s, p[2:])
            if p[0] == s[0] or p[0] == '.':
                return self.isMatch(s[1:], p) or self.isMatch(s, p[2:])
            else:
                return self.isMatch(s, p[2:])

class Solution:
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        cap = 0
        i = 0
        j = len(height) - 1
        while i < j:
            cap_tmp = (j - i) * min(height[i], height[j])
            if cap_tmp > cap:
                cap = cap_tmp
            if height[i] > height[j]:
                j -= 1
            else:
                i += 1
        return cap

class Solution:
    def intToRoman(self, num):
        """
        :type num: int
        :rtype: str
        """
        roman_tbl = {1: 'I', 4: 'IV', 5: 'V', 9: 'IX', 10: 'X',
                     40: 'XL', 50: 'L', 90: 'XC', 100: 'C',
                     400: 'CD', 500: 'D', 900: 'CM', 1000: 'M'}
        max_sort_keys = list(roman_tbl.keys())
        max_sort_keys.sort(reverse=True)
        num_roman = ""
        for i in max_sort_keys:
            while num / i >= 1:
                num -= i
                num_roman += roman_tbl.get(i)
        return num_roman

class Solution:
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        roman_tbl = {'I': 1, 'IV': 4, 'V': 5, 'IX': 9, 'X': 10,
                     'XL': 40, 'L': 50, 'XC': 90, 'C': 100,
                     'CD': 400, 'D': 500, 'CM': 900, 'M': 1000}
        num = 0
        while len(s) > 0:
            if len(s) >= 2 and s[:2] in roman_tbl.keys():
                num += roman_tbl.get(s[:2])
                s = s[2:]
            else:
                if s[:1] in roman_tbl.keys():
                    num += roman_tbl.get(s[:1])
                    s = s[1:]
        return num

class Solution:
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if len(strs) == 0:
            return ""
        min_str = min(strs, key=len)
        out_str = ""
        for i in range(len(min_str)):
            test_str = min_str[:i+1]
            test_results = [s.startswith(test_str) for s in strs]
            if all(test_results):
                out_str = test_str
            else:
                break
        return out_str

class Solution:
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        nums.sort()
        for t in range(0, len(nums) - 2):
            if t > 0 and nums[t] == nums[t-1]: continue
            l = t + 1; r = len(nums) - 1
            while l < r:
                three_sum = nums[t] + nums[l] + nums[r]
                if three_sum == 0:
                    res.append([nums[t], nums[l], nums[r]])
                    l += 1; r -= 1
                    while l < r and nums[l] == nums[l-1]: l += 1
                    while l < r and nums[r] == nums[r+1]: r -= 1
                elif three_sum < 0:
                    l += 1
                else:
                    r -= 1
        return res

class Solution:
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        nums.sort()
        d = float('inf')
        result = target
        for t in range(len(nums) - 2):
            if t != 0 and nums[t] == nums[t-1]:
                continue
            l = t + 1; r = len(nums) - 1
            while l < r:
                sum_tri = nums[t] + nums[l] + nums[r]
                if sum_tri - target == 0:
                    return sum_tri
                elif sum_tri > target:
                    if sum_tri - target < d:
                        d = sum_tri - target
                        result = sum_tri
                    r -= 1
                else: # sum_tri < target
                    if target - sum_tri < d:
                        d = target - sum_tri
                        result = sum_tri
                    l += 1
        return result

import itertools

class Solution:
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if len(digits) == 0:
            return []
        calc_tbl = {'1': [], '2': ['a', 'b', 'c'], '3': ['d', 'e', 'f'],
                    '4': ['g', 'h', 'i'], '5': ['j', 'k', 'l'], '6': ['m', 'n', 'o'],
                    '7': ['p', 'q', 'r', 's'], '8': ['t', 'u', 'v'], '9': ['w', 'x', 'y', 'z']}
        alt_btn = []
        for d in digits:
            alt_btn.append(calc_tbl.get(d))
        print(alt_btn)
        res = list(itertools.product(*alt_btn))
        return ["".join(x) for x in res]

class Solution:
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        nums.sort()
        results = []
        for i1 in range(len(nums) - 3):
            if i1 != 0 and nums[i1] == nums[i1-1]:
                continue
            for i2 in range(i1+1, len(nums) - 2):
                if i2 != i1+1 and nums[i2] == nums[i2-1]:
                    continue
                target_p = target - nums[i1] - nums[i2]
                i3 = i2 + 1; i4 = len(nums) - 1
                while i3 < i4:
                    duo_sum = nums[i3] + nums[i4]
                    if duo_sum == target_p:
                        results.append([nums[x] for x in [i1, i2, i3, i4]])
                        i3 += 1; i4 -= 1
                        while i3 < i4 and nums[i3] == nums[i3-1]: i3 += 1
                        while i3 < i4 and nums[i4] == nums[i4+1]: i4 -= 1
                    elif duo_sum > target_p:
                        i4 -= 1
                    else:
                        i3 += 1
        return results

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        slider = head
        cache = []
        i = 0
        while slider != None:
            cache.append(slider)
            slider = slider.next
            i += 1
        if i == n:
            head = head.next
        else:
            target = cache[i - n - 1]
            target.next = target.next.next
        return head

class Solution:
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        par_pairs = [('{', '}'), ('[', ']'), ('(', ')')]
        par_stack = []
        for c in s:
            if c in [p[0] for p in par_pairs]:
                par_stack.append(c)
            else:
                if par_stack == []:
                    return False
                ppair = (par_stack[-1], c)
                if ppair in par_pairs:
                    par_stack = par_stack[:-1]
                else:
                    return False
        return False if par_stack else True

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if not l1 and not l2:
            return None
        x = ListNode(0)
        head = x
        while l1 and l2:
            if l1.val < l2.val:
                tmp = l1
                l1 = l1.next
            else:
                tmp = l2
                l2 = l2.next
            x.val = tmp.val
            x.next = tmp
            x = x.next
        if l1 != None:
            x.val = l1.val
            x.next = l1.next
        if l2 != None:
            x.val = l2.val
            x.next = l2.next
        return head

class Solution:
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        def genP(pstr, l, r):
            if r >= l >= 0:
                if not r:
                    yield pstr
                for i in genP(pstr + "(", l - 1, r): yield i
                for i in genP(pstr + ")", l, r - 1): yield i
        return list(genP("", n, n))

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        def mergeSort(x, y):
            header = ListNode(0)
            live_header = header
            while x and y:
                if x.val < y.val:
                    live_header.next = x
                    x = x.next
                else:
                    live_header.next = y
                    y = y.next
                live_header = live_header.next
            live_header.next = x if x else y
            return header.next

        k = len(lists)
        if k == 0:
            return []
        if k == 1:
            return lists[0]
        if k == 2:
            return mergeSort(lists[0], lists[1])
        if k > 2:
            return mergeSort(self.mergeKLists(lists[0:int(k/2)]), self.mergeKLists(lists[int(k/2):]))

class Solution:
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return None
        if not head.next:
            return head
        remaining = head.next.next
        header = head.next
        head.next.next = head
        head.next = self.swapPairs(remaining)
        return header

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseKGroup(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if not head: return None
        s = []
        raw_k = k
        while head and k > 0:
            s.append(head)
            head = head.next
            k -= 1
        rheader = ListNode(0)
        header = rheader
        if k > 0: s.reverse()
        while s:
            header.next = s.pop()
            header = header.next
        header.next = self.reverseKGroup(head, raw_k)
        return rheader.next

class Solution:
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        j = 0
        for i in range(1, len(nums)):
            if not nums[i] == nums[j]:
                nums[j+1] = nums[i]
                j += 1
        return len(nums[:j+1])

class Solution:
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        j = 0
        for i in range(len(nums)):
            if not nums[i] == val:
                nums[j] = nums[i]
                j += 1
        return len(nums[:j])

class Solution:
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        return haystack.find(needle)

class Solution:
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        r = int(dividend / divisor)
        if r < -2**31:
            return -2**31
        elif r > 2**31 - 1:
            return 2**31 - 1
        else:
            return r

class Solution:
    def findSubstring(self, s, words):
        """
        :type s: str
        :type words: List[str]
        :rtype: List[int]
        """
        res = []
        if not words: return res
        w = words.copy()
        wl = len(w[0])
        anchor = 0
        i = anchor
        while anchor + wl * len(words) <= len(s):
            win = s[i:i+wl]
            if win in w:
                w.remove(win)
                i += wl
            else:
                w = words.copy()
                anchor += 1
                i = anchor
            if not w:
                res.append(anchor)
                w = words.copy()
                anchor += 1
                i = anchor
        return res

class Solution:
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        a = len(nums)
        for i in range(len(nums) - 1):
            if nums[i] < nums[i+1]:
                a = i
        if not a < len(nums):
            for i in range(int(len(nums)/2)):
                tmp = nums[i]
                nums[i] = nums[len(nums) - 1 - i]
                nums[len(nums) - 1 - i] = tmp
        else:
            b = len(nums)
            for i in range(a, len(nums)):
                if nums[i] > nums[a]:
                    b = i
            tmp = nums[a]
            nums[a] = nums[b]
            nums[b] = tmp
            for i in range(int((len(nums) - a) / 2)):
                tmp = nums[a + i + 1]
                nums[a + i + 1] = nums[len(nums) - i - 1]
                nums[len(nums) - i - 1] = tmp

class Solution {
public:
    int longestValidParentheses(string s) {
        vector<int> dp(s.size(), 0);
        int maxLen = 0;
        for (int i = 0; i < dp.size(); i++) {
            if (s[i] == '(') dp[i] = 0;
            else {
                // assert(s[i] == ')');
                if (s[i-1] == '(') dp[i] = i >= 2 ? dp[i-2] + 2 : 2;
                else {
                    // assert(s[i-1] == ')');
                    if (i - dp[i-1] - 1 >= 0 && s[i - dp[i-1] - 1] == '(') 
                        dp[i] = dp[i-1] + 2 + (i - dp[i-1] - 2 >= 0 ? dp[i - dp[i-1] - 2] : 0);
                }
            }
            maxLen = dp[i] > maxLen ? dp[i] : maxLen;
        }
        return maxLen;
    }
};

class Solution {
public:
    int search(vector<int>& nums, int target) {
        return searchHelper(nums, target, 0, (int)nums.size()-1);
    }
private:
    int searchHelper(vector<int>& nums, int target, int l, int r) {
        if (l > r) return -1;
        int mid = (l + r) / 2;
        if (target < nums[mid]) {
            if (nums[mid] < nums[r]) return searchHelper(nums, target, l, mid-1);
            else {
                if (nums[l] > target) return searchHelper(nums, target, mid+1, r);
                else return searchHelper(nums, target, l, mid);
            }
        } else if (target > nums[mid]) {
            if (nums[mid] > nums[l]) return searchHelper(nums, target, mid+1, r);
            else {
                if (target > nums[r]) return searchHelper(nums, target, l, mid-1);
                else return searchHelper(nums, target, mid+1, r);
            }
        } else return mid;
    }
};
int main() {
    Solution *s = new Solution();
    vector<int> nums = {4, 5, 6, 7, 0, 1, 2};
    int target = 0;
    cout << s->search(nums, target) << endl;
}

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int t = bsearch(nums, target, 0, (int)nums.size()-1);
        int x = t, y = t;
        while (x-1 >= 0 && nums[x-1] == target) x--;
        while (y+1 < (int)nums.size() && nums[y+1] == target) y++;
        return {x, y};
    }
private:
    int bsearch(vector<int>& nums, int target, int l, int r) {
        if (l > r) return -1;
        int mid = (l + r) / 2;
        if (nums[mid] < target) return bsearch(nums, target, mid+1, r);
        else if (nums[mid] > target) return bsearch(nums, target, l, mid-1);
        else return mid;
    }
};

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> ans;
        vector<int> alt;
        sort(candidates.begin(), candidates.end());
        dfs(candidates, alt, target, ans, 0);
        return ans;
    }
private:
    void dfs(vector<int>& candidates, vector<int>& alt, int rest, vector<vector<int>>& ans, int s) {
        for (int i = s; i < (int) candidates.size(); i++) {
            if (candidates[i] > rest) break;
            else if (candidates[i] == rest) {
                alt.push_back(candidates[i]);
                ans.push_back(alt);
                alt.pop_back();
                break;
            }
            else {
                alt.push_back(candidates[i]);
                dfs(candidates, alt, rest - candidates[i], ans, i);
                alt.pop_back();
            }
        }
    }
};

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        do {
            ans.push_back(nums);
        } while (next_permutation(nums.begin(), nums.end()));
        return ans;
    }
};

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = (int) matrix.size();
        for (int i = 0; i < n/2; i++) {
            for (int j = i; j < n-1-i; j++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[n-1-j][i];
                matrix[n-1-j][i] = matrix[n-1-i][n-1-j];
                matrix[n-1-i][n-1-j] = matrix[j][n-1-i];
                matrix[j][n-1-i] = tmp;
            }
        }
    }
};

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> um;
        for (auto& x : strs) {
            string tmp = x;
            sort(tmp.begin(), tmp.end());
            if (um.count(tmp) > 0) um[tmp].push_back(x);
            else um[tmp] = {x};
        }
        vector<vector<string>> ans;
        for (auto& x : um) {
            ans.push_back(x.second);
        }
        return ans;
    }
};

class Solution {
public:
    bool canJump(vector<int>& nums) {
        vector<int> dp(nums.size(), 0);
        for (int i = 1; i < nums.size(); i++) {
            dp[i] = max(dp[i-1], nums[i-1]) - 1;
            if (dp[i] < 0) return false;
        }
        return dp.back() >= 0;
    }
};

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector<Interval> merge(vector<Interval>& intervals) {
        sort(intervals.begin(), intervals.end(),
             [](auto& x, auto& y) {return x.start < y.start;});
        vector<Interval> ans;
        for (int i = 0; i < intervals.size(); i++) {
            if (i == 0) ans.push_back(intervals[i]);
            else {
                Interval& tmp = ans.back();
                if (intervals[i].start > tmp.end) ans.push_back(intervals[i]);
                else tmp.end = intervals[i].end > tmp.end ? intervals[i].end : tmp.end;
            }
        }
        return ans;
    }
};

class Solution {
public:
    string addBinary(string a, string b) {
        int alen = (int) a.size();
        int blen = (int) b.size();
        int carry = 0;
        string res;
        while (alen > 0 || blen > 0) {
            int abit = alen <= 0 ? 0 : a.at(alen - 1) - '0';
            int bbit = blen <= 0 ? 0 : b.at(blen - 1) - '0';
            int cbit = carry;
            int bits = abit + bbit + cbit;
            res.insert(res.begin(), '0' + bits % 2);
            carry = bits / 2;
            alen--;
            blen--;
        }
        if (carry) res.insert(res.begin(), '1');
        return res;
    }
};

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int i = 0;
        int l = 0, r = (int)nums.size() - 1;
        while (i <= r) {
            if (nums[i] == 0) swap(nums[l++], nums[i]);
            if (nums[i] == 2) swap(nums[r--], nums[i]);
            else i++;
        }
    }
};

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ans = {{}};
        for (int i = 0; i < (int)nums.size(); i++) {
            int n = (int) ans.size();
            for (int j = 0; j < n; j++) {
                vector<int> tmp = ans[j];
                tmp.push_back(nums[i]);
                ans.push_back(tmp);
            }
        }
        return ans;
    }
};

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board.at(0).size(); j++) {
                if (this->search(board, word, i, j)) return true;
            }
        }
        return false;
    }
private:
    bool search(vector<vector<char>> board, string word, int i, int j) {
        int row = (int) board.size();
        int col = (int) board[0].size();
        if (word.empty()) return true;
        if (i < 0 || i >= row || j < 0 || j >= col) return false;
        if (board[i][j] == '*' || board[i][j] != word[0]) return false;
        word.erase(word.begin());
        board[i][j] = '*';
        bool res = search(board, word, i + 1, j) ||
                   search(board, word, i - 1, j) ||
                   search(board, word, i, j + 1) ||
                   search(board, word, i, j - 1);
        return res;
    }
};

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        return binary_search(nums.begin(), nums.end(), target);
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode *left = new ListNode(0);
        ListNode *right = new ListNode(0);
        ListNode *left_head = left;
        ListNode *right_head = right;
        while (head) {
            if (head->val < x) {
                left->next = head;
                left = left->next;
            } else {
                right->next = head;
                right = right->next;
            }
            head = head->next;
        }
        right->next = NULL;
        left->next = right_head->next;
        return left_head->next;
    }
};

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans = {{}};
        for (auto num : nums) {
            int n = (int) ans.size();
            for (int i = 0; i < n; i++) {
                vector<int> tmp(ans[i].begin(), ans[i].end());
                tmp.push_back(num);
                if (!count(ans.begin(), ans.end(), tmp)) ans.push_back(tmp);
            }
        }
        return ans;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == NULL && q == NULL) return true;
        else if (p == NULL || q == NULL) return false;
        else if (p->val != q->val) return false;
        else {
            return isSameTree(p->left, q->left) && isSameTree(p->right, q->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:
    bool isSymmetric(TreeNode* root) {
        if (!root) return true;
        return helper(root->left, root->right);
    }
private:
    bool helper(TreeNode* l, TreeNode* r) {
        if (!l && !r) return true;
        else if (!l || !r) return false;
        else if (l->val != r->val) return false;
        else {
            return helper(l->left, r->right) && helper(l->right, r->left);
        }
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (!root) return 0;
        vector<TreeNode*> vec;
        TreeNode* node;
        int depth = 0;
        vec.push_back(root);
        while (!vec.empty()) {
            int n = (int)vec.size();
            for (int i = 0; i < n; i++) {
                if (vec[i]->left) vec.push_back(vec[i]->left);
                if (vec[i]->right) vec.push_back(vec[i]->right);
            }
            vec.erase(vec.begin(), vec.begin() + n);
            depth++;
        }
        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:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return helper(preorder, inorder, 0, (int)preorder.size(), 0, (int)inorder.size());
    }
private:
    TreeNode* helper(vector<int>& preorder, vector<int>& inorder,
                     int pre1, int pre2, int in1, int in2) {
        if (pre1 >= pre2 || in1 >= in2) return NULL;
        int m = preorder[pre1];
        int insplit = distance(inorder.begin(), find(inorder.begin() + in1, inorder.begin() + in2, m));
        int presplit = pre1 + insplit - in1 + 1;
        TreeNode* root = new TreeNode(m);
        root->left = this->helper(preorder, inorder, pre1 + 1, presplit, in1, insplit);
        root->right = this->helper(preorder, inorder, presplit, pre2, insplit + 1, in2);
        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:
    bool hasPathSum(TreeNode* root, int sum) {
        if (!root) return false;
        if (!root->left && !root->right && root->val == sum) return true;
        sum -= root->val;
        return hasPathSum(root->left, sum) || hasPathSum(root->right, sum);
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        if (!root) return {};
        vector<vector<int>> res;
        stack<pair<TreeNode*, vector<int>>> stk;
        stk.push({root, {root->val}});
        while (!stk.empty()) {
            TreeNode *pNode = stk.top().first;
            vector<int> vVals = stk.top().second;
            stk.pop();
            if (pNode->left) {
                vector<int> vTmp = vVals;
                vTmp.push_back(pNode->left->val);
                stk.push({pNode->left, vTmp});
            }
            if (pNode->right) {
                vector<int> vTmp = vVals;
                vTmp.push_back(pNode->right->val);
                stk.push({pNode->right, vTmp});
            }
            if (!pNode->left && !pNode->right) {
                if (accumulate(vVals.begin(), vVals.end(), 0, plus<int>()) == sum)
                    res.push_back(vVals);
            }
        }
        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:
    void flatten(TreeNode* root) {
        if (!root) return;
        if (root->left) flatten(root->left);
        if (root->right) flatten(root->right);
        TreeNode* tmp = root->right;
        root->right = root->left;
        root->left = NULL;
        while (root->right) root = root->right;
        root->right = tmp;
    }
};

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> up = {1};
        while (rowIndex--) {
            vector<int> down = {};
            up.insert(up.begin(), 0);
            up.push_back(0);
            for (int i = 0; i < (int)up.size() - 1; i++) {
                down.push_back(up[i] + up[i + 1]);
            }
            up = down;
        }
        return up;
    }
};

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        queue<string> words;
        set<string> dict(wordList.begin(), wordList.end());
        if (!dict.count(endWord)) return 0;
        words.push(beginWord);
        int steps = 0;
        while (!words.empty()) {
            size_t t = words.size();
            steps++;
            while (t--) {
                string word = words.front();
                words.pop();
                if (word == endWord) return steps;
                for (auto i = 0; i < (int)word.length(); i++) {
                    char ch = word[i];
                    for (char c = 'a'; c <= 'z'; c++) {
                        word[i] = c;
                        if (word == endWord) return steps + 1;
                        if (!dict.count(word)) continue;
                        dict.erase(word);
                        words.push(word);
                    }
                    word[i] = ch;
                }
            }
        }
        return 0;
    }
};

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<bool> dp(s.size() + 1, false);
        dp[0] = true;
        for (int i = 1; i <= s.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && find(wordDict.begin(), wordDict.end(), s.substr(j, i-j)) != wordDict.end()) {
                    dp[i] = true; break;
                }
            }
        }
        return dp[s.size()];
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (!head) return NULL;
        ListNode *slow = head;
        ListNode *fast = head;
        while (slow->next && fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                ListNode *node = head;
                while (node != slow) {
                    slow = slow->next;
                    node = node->next;
                }
                return node;
            }
        }
        return NULL;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        ListNode* newHead = new ListNode(-numeric_limits<int>::max());
        while (head) {
            ListNode* tmp = head->next;
            this->insertOne(newHead, head);
            head = tmp;
        }
        return newHead->next;
    }
private:
    ListNode* insertOne(ListNode* head, ListNode* node) {
        ListNode* cHead = head;
        while (head->next != NULL && head->next->val < node->val) {
            head = head->next;
        }
        node->next = head->next;
        head->next = node;
        return cHead;
    }
};

class Solution {
public:
    int trailingZeroes(int n) {
        int ans = 0;
        while (n) {
            ans += n / 5;
            n /= 5;
        }
        return ans;
    }
};

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = (int) nums.size();
        if (n > 1) {
            k %= n;
            reverse(nums.begin(), nums.begin() + n - k);
            reverse(nums.end() - k, nums.end());
            reverse(nums.begin(), nums.end());
        }
    }
};

class Solution {
public:
    int hammingWeight(uint32_t n) {
        bitset<32> b(n);
        return b.count();
    }
};

class Solution:
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0: return 0
        s = [0 for _ in range(len(nums))]
        for i in range(len(nums)):
            if i == 0:
                s[0] = nums[0]
            elif i == 1:
                s[1] = max(s[0], nums[1])
            else:
                s[i] = max(s[i-1], s[i-2] + nums[i])
        return max(s)

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int i = 0;
        while (m != n) {
            m >>= 1;
            n >>= 1;
            i++;
        }
        return (m << i);
    }
};

class Solution {
public:
    bool isHappy(int n) {
        unordered_set<int> us = {n};
        vector<int> sn;
        while (true) {
            sn = splitNum(n);
            for_each(sn.begin(), sn.end(), [](int& x){x *= x;});
            n = accumulate(sn.begin(), sn.end(), 0, plus<int>());
            if (n == 1) return true;
            else if (us.count(n)) break;
            else us.insert(n);
        }
        return false;
    }
private:
    vector<int> splitNum(int n) {
        vector<int> ans;
        while (n) {
            ans.push_back(n % 10);
            n /= 10;
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        map<int, vector<int>> dict;
        int key;
        for (int i = 0; i < (int)nums.size(); i++) {
            key = nums[i];
            if (dict.count(key) == 0) dict[key].push_back(i);
            else if (i - dict[key].back() <= k) return true;
            else dict[key].push_back(i);
        }
        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:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) return root;
        if (!root->left && !root->right) return root;
        TreeNode *tmp;
        tmp = root->left;
        root->left = invertTree(root->right);
        root->right = invertTree(tmp);
        return root;
    }
};

class Solution {
public:
    bool isPowerOfTwo(int n) {
        if (n == 0) {
            return false;
        }
        while ((n & 1) != 1) {
            n = (n >> 1);
        }
        if (n == 1) {
            return true;
        } else {
            return false;
        }
    }
};

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = (int)nums.size();
        vector<int> before(n, 1);
        vector<int> after(n, 1);
        int tmp = 1;
        for (int i = 1; i < n; i++) {
            before[i] = nums[i - 1] * tmp;
            tmp = before[i];
        }
        tmp = 1;
        for (int i = n - 2; i >= 0; i--) {
            after[i] = nums[i + 1] * tmp;
            tmp = after[i];
        }
        vector<int> res(n);
        for (int i = 0; i < n; i++) {
            res[i] = before[i] * after[i];
        }
        return res;
    }
};

class Solution {
public:
    int hIndex(vector<int>& citations) {
        sort(citations.begin(), citations.end(), greater<int>());
        for (int i = 0; i < (int)citations.size(); i++) {
            if (citations[i] >= i + 1) {
                if (i == citations.size() - 1) return i + 1;
                if (citations[i + 1] <= i + 1) return i + 1;
            }
        }
        return 0;
    }
};

class Solution {
public:
    int bulbSwitch(int n) {
        return sqrt(n);
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (!head) return head;
        if (!head->next) return head;
        ListNode *odd = head;
        ListNode *even = head->next;
        ListNode *oddHead = odd;
        ListNode *evenHead = even;
        ListNode *node = head->next->next;
        bool isOdd = true;
        while (node) {
            if (isOdd) {
                odd->next = node;
                odd = odd->next;
            }
            else {
                even->next = node;
                even = even->next;
            }
            isOdd = !isOdd;
            node = node->next;
        }
        odd->next = evenHead;
        even->next = NULL;
        return oddHead;
    }
};

class Solution {
public:
    bool isPowerOfFour(int num) {
        return (num > 0) && !(num & (num - 1)) && ((num - 1) % 3 == 0);
    }
};

class Solution {
public:
    int longestSubstring(string s, int k) {
        int n = (int)s.size();
        if (n == 0 || n < k) return 0;
        map<char, int> dict;
        for (char c = 'a'; c <= 'z'; c++) {
            dict.insert({c, 0});
        }
        for (auto i : s) {
            dict.at(i)++;
        }
        for (int i = 0; i < n; i++) {
            if (dict[s[i]] < k) {
                int left = this->longestSubstring(s.substr(0, i), k);
                int right = this->longestSubstring(s.substr(i + 1), k);
                return max({left, right});
            }
        }
        return n;
    }
};

class Solution {
public:
    string toHex(int num) {
        string alpha[] = {"a", "b", "c", "d", "e", "f"};
        string ans;
        int rem;
        unsigned x = num;
        while (x) {
            rem = x % 16;
            if (rem < 10) ans = to_string(rem) + ans;
            else ans = alpha[rem - 10] + ans;
            x -= rem;
            x /= 16;
        }
        return ans.empty() ? "0" : ans;
    }
};

class Solution {
public:
    int minMutation(string start, string end, vector<string>& bank) {
        queue<string> q;
        set<string> visited;
        q.push(start);
        visited.insert(start);
        int mutations = 0;
        while (!q.empty()) {
            size_t t = q.size();
            while (t--) {
                string aq = q.front();
                q.pop();
                if (aq == end) return mutations;
                for (const string& gene : bank) {
                    if (visited.count(gene)) continue;
                    if (this->validMutation(aq, gene)) {
                        q.push(gene);
                        visited.insert(gene);
                    }
                }
            }
            mutations++;
        }
        return -1;
    }
private:
    bool validMutation(const string& x, const string& y) {
        int diff = 0;
        for (auto i = 0; i < (int)x.length(); i++) {
            if (x[i] != y[i]) diff++;
            if (diff > 1) break;
        }
        return diff > 1 ? false : true;
    }
};

class Solution {
public:
    int minMoves2(vector<int>& nums) {
        int n = (int) nums.size();
        sort(nums.begin(), nums.end());
        int target = nums[n / 2];
        int ans = 0;
        for (auto num : nums) {
            ans += abs(num - target);
        }
        return ans;
    }
};

class Solution {
public:
    int totalHammingDistance(vector<int>& nums) {
        int res = 0;
        int n = (int)nums.size();
        vector<int> vb(32);
        for (auto num : nums) {
            bitset<32> v(num);
            for (int i = 0; i < 32; i++) {
                if (v[i] == 1) vb[i]++;
            }
        }
        for (auto k : vb) {
            res += k * (n - k);
        }
        return res;
    }
};

class Solution {
public:
    bool PredictTheWinner(vector<int>& nums) {
        int i = 0;
        int j = nums.size() - 1;
        int res = pickOne(nums, i, j);
        return res >= 0;
    }
private:
    int pickOne(vector<int>& nums, int i, int j) {
        if (i == j) return nums.at(i);
        int res1 = nums[i] - pickOne(nums, i + 1, j);
        int res2 = nums[j] - pickOne(nums, i, j - 1);
        return res1 > res2 ? res1 : res2;
    }
};

class Solution {
public:
    bool detectCapitalUse(string word) {
        int n = (int)word.size();
        if (n == 0 || n == 1) return true;
        bool isCap = (word[0] >= 'a' && word[0] <= 'z') ? false : true;
        set<bool> res_set;
        for (auto c : word.substr(1)) {
            if (!isCap) {
                if (c < 'a' || c > 'z') return false;
            } else {
                if (c >= 'a' && c <= 'z') res_set.insert(true);
                else res_set.insert(false);
            }
        }
        return res_set.size() > 1 ? false : true;
    }
};

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

    Node() {}

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
public:
    int maxDepth(Node* root) {
        if (!root) return 0;
        if (root->children.empty()) return 1;
        int depth = 1;
        for (auto v : root->children) {
            depth = max(depth, this->maxDepth(v));
        }
        return depth + 1;
    }
};

class Solution {
public:
    int findPaths(int m, int n, int N, int i, int j) {
        vector<vector<vector<int>>> dp(N + 1, vector<vector<int>>(m, vector<int>(n, 0)));
        for (int k = 1; k <= N; k++) {
            for (int x = 0; x < m; x++) {
                for (int y = 0; y < n; y++) {
                    long long v1 = (x == 0) ? 1 : dp[k - 1][x - 1][y];
                    long long v2 = (x == m - 1) ? 1 : dp[k - 1][x + 1][y];
                    long long v3 = (y == 0) ? 1 : dp[k - 1][x][y - 1];
                    long long v4 = (y == n - 1) ? 1 : dp[k - 1][x][y + 1];
                    dp[k][x][y] = (v1 + v2 + v3 + v4) % (int)(1e9 + 7);
                }
            }
        }
        return dp[N][i][j];
    }
};

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

    Node() {}

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
public:
    vector<int> preorder(Node* root) {
        if (!root) return {};
        stack<Node*> st;
        vector<int> result;
        Node* tmp;
        st.emplace(root);
        while (!st.empty()) {
            tmp = st.top(); st.pop();
            result.emplace_back(tmp->val);
            for (auto it = tmp->children.rbegin(); it < tmp->children.rend(); it++)
                st.emplace(*it);
        }
        return result;
    }
};

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        bool prev = true;
        if (flowerbed.size() == 0) {
            return n == 0 ? true : false;
        }
        for (int i = 0; i < flowerbed.size(); i++) {
            if (flowerbed[i] == 1) prev = false;
            else if (!prev) prev = true;
            else if ((i == flowerbed.size() - 1) ||
                     (flowerbed[i+1] == 0)) {
                n--;
                prev = false;
            }
            if (n <= 0) return true;
        }
        return n > 0 ? false : true;
    }
};

class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        int x, y;
        unordered_set<int> us(nums.begin(), nums.end());
        int sum_nums = accumulate(nums.begin(), nums.end(), 0, plus<int>());
        int sum_us   = accumulate(us.begin(), us.end(), 0, plus<int>());
        x = sum_nums - sum_us;   
        y = (1 + (int)nums.size()) * (int)nums.size() / 2 - sum_us;
        return {x, y};
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        if (nums.empty()) return NULL;
        vector<int>::iterator target = max_element(nums.begin(), nums.end());
        vector<int> left(nums.begin(), target);
        vector<int> right(target + 1, nums.end());
        TreeNode *root = new TreeNode(*target);
        root->left = constructMaximumBinaryTree(left);
        root->right = constructMaximumBinaryTree(right);
        return root;
    }
};

class Solution {
public:
    int findShortestSubArray(vector<int>& nums) {
        map<int, int> m;
        for (auto i : nums) {
            if (m.count(i) == 0) m.insert(make_pair(i, 1));
            else m[i]++;
        }
        auto maxFreqIt = max_element(m.begin(), m.end(),
                                     [](const pair<int, int>& x, const pair<int, int>& y) {
                                         return x.second < y.second;});
        int maxFreq = (*maxFreqIt).second;
        vector<int> alts;
        for (auto i : m) {
            if (i.second == maxFreq) alts.push_back(i.first);
        }
        int ans = INT_MAX;
        int first, last;
        for (auto i : alts) {
            first = distance(nums.begin(), find(nums.begin(), nums.end(), i));
            last = distance(find(nums.rbegin(), nums.rend(), i), nums.rend() - 1);
            ans = min(ans, last - first + 1);
        }
        return ans;
    }
};

class Solution {
public:
    string longestWord(vector<string>& words) {
        string ans = "";
        set<string> s;
        sort(words.begin(), words.end());
        for (auto word : words) {
            if (word.size() == 1 || s.count(word.substr(0, word.size() - 1))) {
                ans = (word.size() > ans.size()) ? word : ans;
                s.insert(word);
            }
        }
        return ans;
    }
};

class Solution {
public:
    int monotoneIncreasingDigits(int N) {
        string sn = to_string(N);
        int l = sn.size();
        if (l == 1) return N;
        int anchor = l;
        for (int i = l - 1; i > 0; i--) {
            if (sn[i - 1] > sn[i]) {
                sn[i - 1]--;
                anchor = i - 1;
            }
        }
        while(++anchor < l) {
            sn[anchor] = '9';
        }
        return stoi(sn);
    }
};

class Solution {
public:
    int rotatedDigits(int N) {
        int must_have[10] = {0};
        int cant_have[10] = {0};
        for (int i : {2, 5, 6, 9}) must_have[i] = 1;
        for (int i : {3, 4, 7}) cant_have[i] = 1;
        int ans = 0;
        for (int i = 1; i <= N; i++) {
            int num = i;
            bool bMustHave = false;
            bool bCantHave = false;
            while (num > 0) {
                int r = num % 10;
                if (must_have[r]) bMustHave = true;
                if (cant_have[r]) {
                    bCantHave = true;
                    break;
                }
                num = num / 10;
            }
            if (bMustHave && !bCantHave) ans++;
        }
        return ans;
    }
};

class Solution {
public:
    int uniqueMorseRepresentations(vector<string>& words) {
        vector<string> morse = {".-","-...","-.-.","-..",".","..-.",
                                "--.","....","..",".---","-.-",".-..",
                                "--","-.","---",".--.","--.-",".-.",
                                "...","-","..-","...-",".--","-..-",
                                "-.--","--.."};
        unordered_set<string> us;
        string tmp;
        for (auto& w : words) {
            tmp.clear();
            for (auto& c : w) {
                tmp += morse[c - 'a'];
            }
            us.emplace(tmp);
        }
        return (int)us.size();
    }
};

class Solution {
public:
    int numFactoredBinaryTrees(vector<int>& A) {
        const long m = pow(10, 9) + 7;
        sort(A.begin(), A.end());
        map<int, long> dp;
        for (int i = 0; i < A.size(); i++) {
            dp.insert(make_pair(A[i], 1));
            for (int j = 0; j < i; j++) {
                if (A[i] % A[j] == 0 && dp.count(A[i] / A[j])) {
                    dp[A[i]] += (dp[A[j]] * dp[A[i] / A[j]]) % m;
                }
            }
        }
        long ans = 0;
        for (auto& kv : dp) ans += kv.second;
        return ans % m;
    }
};

class Solution {
public:
    string goatLatinWord(string s, int ind) {
        set<char> vowels({'a', 'e', 'i', 'o', 'u',
                          'A', 'E', 'I', 'O', 'U'});
        if (vowels.count(s[0])) {
            s += "ma";
        } else {
            char c = s[0];
            s.erase(s.begin());
            s.push_back(c);
            s += "ma";
        }
        while (ind--) {
            s += "a";
        }
        return s;
    }
    string toGoatLatin(string S) {
        int n = (int) S.size();
        string result;
        int begin = 0;
        int counter = 0;
        int ind = 1;
        string word;
        for (int i = 0; i < n; i++) {
            if (S[i] == ' ') {
                word = S.substr(begin, counter);
                result += this->goatLatinWord(word, ind++);
                result += " ";
                begin = i + 1;
                counter = 0;
            } else {
                counter++;
                continue;
            }
        }
        word = S.substr(begin, n);
        result += this->goatLatinWord(word, ind);
        return result;
    }
};

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& A) {
        if (A.size() == 0 || A.size() == 1) return 0;
        int prev = A[0];
        for (int i = 1; i < (int)A.size(); i++) {
            if (A[i] > prev) prev = A[i];
            else return i - 1;
        }
        return A.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:
    vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {
        buildGraph(nullptr, root);
        queue<TreeNode*> q;
        unordered_set<TreeNode*> seen;
        vector<int> results;
        q.push(target);
        seen.insert(target);
        int depth = 0;
        while (!q.empty() && depth <= K) {
            int num = (int)q.size();
            while (num--) {
                TreeNode* node = q.front(); q.pop();
                if (depth == K) results.push_back(node->val);
                for (auto& child : graph[node]) {
                    if (!seen.count(child)) {
                        q.push(child);
                        seen.insert(child);
                    }
                }
            }
            depth++;
        }
        return results;
    }
private:
    unordered_map<TreeNode*, vector<TreeNode*>> graph;
    void buildGraph(TreeNode* parent, TreeNode* child) {
        if (parent) {
            graph[parent].push_back(child);
            graph[child].push_back(parent);
        }
        if (child->left) buildGraph(child, child->left);
        if (child->right) buildGraph(child, child->right);
    }
};

class Solution {
public:
    vector<vector<int>> transpose(vector<vector<int>>& A) {
        vector<vector<int>> res;
        if (A.size() == 0) return res;
        if (A[0].size() == 0) return res;
        for (int i = 0; i < (int) A[0].size(); i++) {
            vector<int> tmp;
            for (int j = 0; j < (int) A.size(); j++) {
                tmp.push_back(A[j][i]);
            }
            res.push_back(tmp);
        }
        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:
    vector<TreeNode*> allPossibleFBT(int N) {
        if (N % 2 == 0) return {};
        if (N == 1) return {new TreeNode(0)};
        vector<TreeNode*> ans;
        for (int i = 1; i < N; i += 2) {
            for (const auto& left : allPossibleFBT(i)) {
                for (const auto& right : allPossibleFBT(N - i - 1)) {
                    TreeNode *root = new TreeNode(0);
                    root->left = left;
                    root->right = right;
                    ans.push_back(root);
                }
            }
        }
        return ans;
    }
};

class Solution {
public:
    bool isMonotonic(vector<int>& A) {
        set<bool> sb;
        for (size_t i = 0; i < A.size() - 1; i++) {
            if (A[i] > A[i + 1]) sb.insert(true);
            if (A[i] < A[i + 1]) sb.insert(false);
        }
        return sb.size() == 2 ? false : true;
    }
};

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& A) {
        int n = (int) A.size();
        vector<vector<int>> mat(n+1, vector<int>(n, 0));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int v1 = j > 0 ? mat[i][j-1] : INT_MAX;
                int v2 = mat[i][j];
                int v3 = j < n-1 ? mat[i][j+1] : INT_MAX;
                mat[i+1][j] = min(min(v1, v2), v3) + A[i][j];
            }
        }
        return *min_element(mat[n].begin(), mat[n].end());
    }
};