krahets/CodingSolution

class Solution:
    def twoSum(self, nums, target):
        dic = {}
        for i in range(len(nums)):
            if str(target - nums[i]) in dic:
                return [dic[str(target - nums[i])], i]
            dic[str(nums[i])] = i

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length;i++) {
            int x = nums[i];
            if(map.containsKey(target - x)){
                return new int[] { map.get(target-x), i};
            }
            map.put(x, i);
        }
        return null;
    }
}

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        carry = 0
        head = ListNode(0)
        res = head
        while l1 or l2:
            num1 = l1.val if l1 else 0
            num2 = l2.val if l2 else 0
            tmp = num1 + num2 + carry
            carry = 1 if tmp >= 10 else 0
            head.next = ListNode(tmp % 10)
            head = head.next
            if l1: l1 = l1.next
            if l2: l2 = l2.next
        if carry: head.next = ListNode(1)
        return res.next

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode res = head;
        int carry = 0;
        while(l1 != null || l2!= null){
            int num1 = l1 != null ? l1.val : 0;
            int num2 = l2 != null ? l2.val : 0;
            int tmp = num1 + num2 + carry;
            carry = tmp / 10;
            head.next = new ListNode(tmp % 10);
            head = head.next;
            if(l1 != null) l1 = l1.next;
            if(l2 != null) l2 = l2.next;
        }
        if(carry == 1) head.next = new ListNode(1);
        return res.next;
    }
}

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        dic = {}
        l, res = 0, 0
        for r in range(len(s)):
            if s[r] in dic:
                l = max(dic[s[r]], l)
            dic[s[r]] = r + 1
            res = max(res, r - l + 1)
        return res

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int res = 0;
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0, j = 0; j < s.length(); j++) {
            if (map.containsKey(s.charAt(j))) {
                i = Math.max(map.get(s.charAt(j)), i);
            }
            map.put(s.charAt(j), j + 1);
            res = Math.max(res, j - i + 1);
        }
        return res;
    }
}

class Solution:
    def longestPalindrome(self, s: str) -> str:
        left, right = 0, 0
        for i in range(len(s)):
            odd = self.mid_expand(s, i, i)
            even = self.mid_expand(s, i, i+1)
            m = max(odd, even)
            if m > right - left:
                left = i - (m - 1) // 2
                right = i + m // 2
        return s[left:right+1]

    def mid_expand(self, s, left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return right - left - 1

class Solution {
    public String longestPalindrome(String s) {
        if(s.length() == 0) return "";
        int left = 0, right = 0;
        for (int i = 0; i < s.length(); i++) {
            int odd = midExpand(s, i, i);
            int even = midExpand(s, i, i + 1);
            int m = Math.max(odd, even);
            if (m > right - left) {
                left = i - (m - 1) / 2;
                right = i + m / 2;
            }
        }
        return s.substring(left, right + 1);
    }

    private int midExpand(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }
}

class Solution:
    def reverse(self, x: int) -> int:
        y, res = abs(x), 0
        of = (1 << 31) - 1 if x > 0 else 1 << 31
        while y != 0:
            res = res * 10 + y % 10
            if res > of: return 0
            y //= 10
        return res if x > 0 else -res

class Solution {
    public int reverse(int x) {
        int res = 0;
        int of = ((1 << 31) - 1) / 10;
        while (x != 0) {
            if (Math.abs(res) > ((1 << 31) - 1) / 10) return 0;
            res = res * 10 + x % 10;
            x /= 10;
        }
        return res;
    }
}

class Solution:
    def myAtoi(self, s: str) -> int:
        i, res, neg, over = 0, 0, False, (1 << 31) - 1
        while i < len(s) and s[i] == ' ': # ignore space first
            i += 1
        if i < len(s) and (s[i] == '-' or s[i] == '+'): # save '-'
            neg = s[i] == '-'
            i += 1
        while i < len(s) and '0' <= s[i] <= '9': # generate number
            res = res * 10 + int(s[i])
            i += 1
        if res > over: # handle the overflow
            res = over + 1 if neg else over
        return -res if neg else res

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0 or not x % 10 and x: return False
        r = 0
        while x > r:
            x, rem = x // 10, x % 10
            r = r * 10 + rem
        return x == r or x == r // 10

class Solution {
    public boolean isPalindrome(int x) {
        if(x < 0 || x % 10 == 0 && x != 0) return false;
        int y = 0;
        while(x > y){
            y = y * 10 + x % 10;
            x = x / 10;
        }
        return x == y || x == y / 10;
    }
}

class Solution:
    def maxArea(self, height: List[int]) -> int:
        i, j, res = 0, len(height) - 1, 0
        while i < j:
            if height[i] < height[j]:
                res = max(res, height[i] * (j - i))
                i += 1
            else:
                res = max(res, height[j] * (j - i))
                j -= 1
        return res

class Solution {
    public int maxArea(int[] height) {
        int i = 0, j = height.length - 1, res = 0;
        while(i < j){
            res = height[i] < height[j] ? 
                Math.max(res, (j - i) * height[i++]): 
                Math.max(res, (j - i) * height[j--]); 
        }
        return res;
    }
}

class Solution:
    def intToRoman(self, num: int) -> str:
        res = ""
        values = [1000, 900, 500, 400,
                  100, 90, 50, 40,
                  10, 9, 5, 4,
                  1]
        symbols = ['M', 'CM', 'D', 'CD',
                   'C', 'XC', 'L', 'XL',
                   'X', 'IX', 'V', 'IV',
                   'I']
        i = 0
        while num > 0:
            count = num // values[i]
            res += "".join([symbols[i] for _ in range(count)])
            num -= count * values[i]
            i += 1
        return res

class Solution {
    private static final int[] values = {
        1000, 900, 500, 400,
        100, 90, 50, 40,
        10, 9, 5, 4,
        1};
    private static final String[] symbols = {
        "M", "CM", "D", "CD",
        "C", "XC", "L", "XL",
        "X", "IX", "V", "IV",
        "I"};
    public String intToRoman(int num) {
        StringBuilder res = new StringBuilder();
        int k = 0;
        while(num > 0){
            int count = num / values[k];
            for(int i = 0; i< count;i++){
                res.append(symbols[k]);
                num -= values[k];
            }
            k++;
        }
        return res.toString();
    }
}

class Solution:
    def romanToInt(self, s: str) -> int:
        dic =  {'M':1000, 'CM': 900, 'D': 500, 'CD': 400, 
                'C':100, 'XC':90, 'L':50, 'XL':40,
                'X':10, 'IX': 9, 'V':5, 'IV':4,
                'I':1}
        i = res = 0
        while i < len(s):
            if i+1 < len(s) and s[i] + s[i+1] in dic:
                res += dic[s[i] + s[i+1]]
                i += 2
            elif s[i] in dic:
                res += dic[s[i]]
                i += 1
        return res

class Solution {
    private Map<Character, Integer> roman = new HashMap<Character, Integer>() {
        {
            put('M', 1000);
            put('D', 500);
            put('C', 100);
            put('L', 50);
            put('X', 10);
            put('V', 5);
            put('I', 1);
        }
    };

    public int romanToInt(String s) {
        int res = 0, pre = 0;
        for(Character c : s.toCharArray()){
            int cur = roman.get(c);
            res += cur > pre ? cur - 2 * pre : cur;
            pre = cur;
        }
        return res;
    }
}

class Solution:
    def longestCommonPrefix(self, strs: [str]) -> str:
        if not strs: return ""
        mi = len(strs[0])
        for s in strs[1:]: mi = min(mi, len(s))
        for i in range(mi):
            for j in range(len(strs) - 1):
                if strs[j][i] != strs[j + 1][i]:
                    return strs[j][:i]
        return strs[0][:i+1] if mi else ""

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs.length == 0) return "";
        int min = strs[0].length(), i = 0;
        for(String s : strs) min = Math.min(min, s.length());
        for(; i < min; i++) {
            for(int j = 0; j < strs.length - 1; j++){
                if(strs[j].charAt(i) != strs[j+1].charAt(i)) return strs[j].substring(0,i);
            }
        }
        return min > 0 ? strs[0].substring(0, i) : "";
    }
}

class Solution:
    def threeSum(self, nums: [int]) -> [[int]]:
        nums.sort()
        res, k = [], 0
        for k in range(len(nums) - 2):
            if nums[k] > 0: break # 1. because of j > i > k.
            if k > 0 and nums[k] == nums[k - 1]: continue # 2. skip the same `nums[k]`.
            i, j = k + 1, len(nums) - 1
            while i < j: # 3. double pointer
                s = nums[k] + nums[i] + nums[j]
                if s < 0:
                    i += 1
                    while i < j and nums[i] == nums[i - 1]: i += 1
                elif s > 0:
                    j -= 1
                    while i < j and nums[j] == nums[j + 1]: j -= 1
                else:
                    res.append([nums[k], nums[i], nums[j]])
                    i += 1
                    j -= 1
                    while i < j and nums[i] == nums[i - 1]: i += 1
                    while i < j and nums[j] == nums[j + 1]: j -= 1
        return res

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for(int k = 0; k < nums.length - 2; k++){
            if(nums[k] > 0) break;
            if(k > 0 && nums[k] == nums[k - 1]) continue;
            int i = k + 1, j = nums.length - 1;
            while(i < j){
                int sum = nums[k] + nums[i] + nums[j];
                if(sum < 0){
                    while(i < j && nums[i] == nums[++i]);
                } else if (sum > 0) {
                    while(i < j && nums[j] == nums[--j]);
                } else {
                    res.add(new ArrayList<Integer>(Arrays.asList(nums[k], nums[i], nums[j])));
                    while(i < j && nums[i] == nums[++i]);
                    while(i < j && nums[j] == nums[--j]);
                }
            }
        }
        return res;
    }
}

class Solution:
    def threeSumClosest(self, nums: [int], target: int) -> int:
        nums.sort()
        res = float("inf")
        for k in range(len(nums) - 2):
            if k > 0 and nums[k] == nums[k - 1]: continue
            i, j = k + 1, len(nums) - 1
            while i < j:
                tmp = nums[k] + nums[i] + nums[j]
                if abs(tmp - target) < abs(res - target): res = tmp
                if tmp > target: j -= 1
                elif tmp < target: i += 1
                else: return target
        return res

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        long res = (long)Integer.MAX_VALUE;
        for (int k = 0; k < nums.length - 2; k++) {
            if(k > 0 && nums[k] == nums[k - 1]) continue;
            int i = k + 1, j = nums.length - 1;
            while(i < j) {
                int tmp = nums[k] + nums[i] + nums[j];
                if(Math.abs(tmp - target) < Math.abs(res - target)) res = tmp;
                if(tmp > target) while(i < j && nums[j] == nums[--j]);
                else if(tmp < target) while(i < j && nums[i] == nums[++i]);
                else return target;
            }
        }
        return (int)res;
    }
}

class Solution:
    def isValid(self, s: str) -> bool:
        dic = {'{': '}',  '[': ']', '(': ')'}
        if s and s[0] not in dic: return False
        stack = []
        for c in s:
            if not stack or c in dic: stack.append(c)
            elif stack[-1] in dic and dic[stack[-1]] == c: stack.pop()
            else: return False  
        return not stack

class Solution {
    private static final Map<Character,Character> map = new HashMap<Character,Character>(){{
        put('{','}'); put('[',']'); put('(',')');
    }};
    public boolean isValid(String s) {
        if(s.length() > 0 && !map.containsKey(s.charAt(0))) return false;
        Stack<Character> stack = new Stack<>();
        for(Character c : s.toCharArray()){
            if(stack.isEmpty() || map.containsKey(c)) stack.push(c);
            else if(map.get(stack.peek()) == c) stack.pop();
            else return false;
        }
        return stack.isEmpty();
    }
}

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        head = ListNode(0)
        res = head
        while l1 and l2:
            if l1.val <= l2.val: head.next, l1 = l1, l1.next
            else: head.next, l2 = l2, l2.next
            head = head.next
        head.next = l1 if not l2 else l2
        return res.next

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode res = head;
        while (l1 != null && l2 != null) {
            if(l1.val <= l2.val){
                head.next = l1;
                l1 = l1.next;
            }
            else{
                head.next = l2;
                l2 = l2.next;
            }
            head = head.next;
        }
        head.next = l2 == null ? l1 : l2;
        return res.next;
    }
}

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        while len(lists) > 1:
            lists.append(self.merge(lists.pop(0), lists.pop(0)))
        return lists[0] if lists else None
    def merge(self, h1, h2):
        res = head = ListNode(0)
        while h1 and h2:
            if h1.val <= h2.val: head.next, h1 = h1, h1.next
            else: head.next, h2 = h2, h2.next
            head = head.next
        head.next = h1 if not h2 else h2
        return res.next

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        LinkedList<ListNode> res = new LinkedList(Arrays.asList(lists));
        while (res.size() > 1) {
            res.addLast(merge(res.removeFirst(),res.removeFirst()));
        }
        return res.size() == 0 ? null : res.get(0);
    }

    private ListNode merge(ListNode h1, ListNode h2) {
        ListNode head = new ListNode(0);
        ListNode res = head;
        while (h1 != null && h2 != null) {
            if (h1.val <= h2.val) {
                head.next = h1;
                h1 = h1.next;
            } else {
                head.next = h2;
                h2 = h2.next;
            }
            head = head.next;
        }
        head.next = h2 == null ? h1 : h2;
        return res.next;
    }
}

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        pre = ListNode(0)
        res = pre
        while head and head.next:
            nex = head.next.next
            pre.next = head.next
            pre = head
            head.next.next = head
            head = nex
        pre.next = head
        return res.next

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if not head or not head.next: return head
        nex = head.next
        head.next = self.swapPairs(nex.next)
        nex.next = head
        return nex

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode pre = new ListNode(0);
        ListNode res = pre;
        while(head != null && head.next != null){
            ListNode nex = head.next.next;
            pre.next = head.next;
            pre = head;
            head.next.next = head;
            head = nex;
        }
        pre.next = head;
        return res.next;
    }
}

class Solution:
    def removeDuplicates(self, nums: [int]) -> int:
        if not nums: return 0
        k = 1
        for i in range(1, len(nums)):
            if nums[i] != nums[i - 1]:
                nums[k] = nums[i]
                k += 1
        return k

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;
        int k = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i - 1]) {
                nums[k] = nums[i];
                k++;
            }
        }
        return k;
    }
}

class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        if not needle: return 0
        l_h, l_n = len(haystack), len(needle)
        for i in range(l_h + 1):
            for j in range(l_n + 1):
                if j == l_n: return i
                if i + j == l_h: return -1
                if haystack[i+j] != needle[j]: break

    def strStr1(self, haystack, needle):
        return haystack.find(needle)

class Solution {
    public int strStr(String haystack, String needle) {
        if (needle == "") return 0;
        for (int i = 0;; i++) {
            for (int j = 0;; j++) {
                if (j == needle.length()) return i;
                if (i + j == haystack.length()) return -1;
                if (haystack.charAt(i + j) != needle.charAt(j)) break;
            }
        }
    }
}

class Solution:
    def search(self, nums: [int], target: int) -> int:
        if not nums: return -1
        i, j = 0, len(nums) - 1
        while i < j:
            m = (i + j) // 2
            if nums[m] < nums[j]: j = m
            else: i = m + 1
        if nums[i] <= target <= nums[-1]: i, j = i, len(nums) - 1
        elif nums[0] <= target <= nums[i - 1]: i, j = 0, i - 1
        else: return -1
        while i <= j:
            m = (i + j) // 2
            if nums[m] > target: j = m - 1
            elif nums[m] < target: i = m + 1
            else: return m
        return -1

class Solution {
    public int search(int[] nums, int target) {
        if(nums.length == 0) return -1;
        int i = 0, j = nums.length - 1;
        while(i < j){
            int m = (i + j) / 2;
            if(nums[m] < nums[j]) j = m;
            else i = m + 1;
        }
        if(i == 0 || nums[i] <= target && target <= nums[nums.length - 1])
            j = nums.length - 1;
        else if(nums[0] <= target && target <= nums[i - 1]){
            j = i - 1;
            i = 0;
        }
        else return -1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(nums[m] < target) i = m + 1;
            else if(nums[m] > target) j = m - 1;
            else return m;
        }
        return -1;
    }
}

class Solution:
    def searchInsert(self, nums: [int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] < target: left = mid + 1 # insert left side
            else: right = mid - 1
        return left

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return left;
    }
}

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if num1 == "0" or num2 == "0": return "0"
        res = []
        for loc in range(len(num2)): # multiply
            x2 = ord(num2[len(num2) - 1 - loc]) - ord('0')
            ans, tmp, car = [], 0, 0
            for n1 in num1[::-1]:
                x1 = ord(n1) - ord('0')
                tmp = x1 * x2 + car
                car = tmp // 10
                ans.append(str(tmp % 10))
            if car: ans.append(str(car))
            ans.reverse()
            ans.extend(['0' for _ in range(loc)])
            i, j, car = len(res) - 1, len(ans) - 1, 0
            res_tmp = []
            while i >= 0 or j >= 0: # add
                a1 = ord(res[i]) - ord('0') if i >= 0 else 0
                a2 = ord(ans[j]) - ord('0') if j >= 0 else 0
                tmp = a1 + a2 + car
                car = tmp // 10
                res_tmp.append(str(tmp % 10))
                i, j = i - 1, j - 1
            if car: res_tmp.append("1")
            res_tmp.reverse()
            res = res_tmp
        return "".join(res)

class Solution:
    def permute(self, nums: [int]) -> [[int]]:
        self.res = []
        self.swap(nums, 0)
        return self.res
    def swap(self, nums, j):
        if j == len(nums) - 1: self.res.append(list(nums))
        for i in range(j, len(nums)):
            nums[i], nums[j] = nums[j], nums[i]
            self.swap(nums, j+1)
            nums[i], nums[j] = nums[j], nums[i]

class Solution {
    private List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        swap(nums, 0);
        return res;
    }
    private void swap(int[] nums, int j) {
        if (j == nums.length - 1) {
            List<Integer> list = new ArrayList<>();
            for (int num : nums) list.add(num);
            res.add(list);
        }
        for (int i = j; i < nums.length; i++) {
            int tmp = nums[i];
            nums[i] = nums[j]; nums[j] = tmp;
            swap(nums, j + 1);
            nums[j] = nums[i]; nums[i] = tmp;
        }
    }
}

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        for i in range(1,len(nums)):
            nums[i] = max(nums[i-1] + nums[i], nums[i])
        return max(nums)

class Solution {
    public int maxSubArray(int[] nums) {
        int res = Integer.MIN_VALUE;
        for(int i = 1; i < nums.length; i++){
            nums[i] = Math.max(nums[i], nums[i] + nums[i - 1]);
            res = Math.max(res, nums[i]);
        }
        return res;
    }
}

class Solution:
    def spiralOrder(self, matrix: [[int]]) -> [int]:
        if not matrix: return []
        res = []
        h, l = len(matrix), len(matrix[0])
        i, j = 0, -1
        while True:
            for _ in range(l):
                j += 1
                res.append(matrix[i][j])
            h -= 1
            if not h: break
            for _ in range(h):
                i += 1
                res.append(matrix[i][j])
            l -= 1
            if not l: break
            for _ in range(l):
                j -= 1
                res.append(matrix[i][j])
            h -= 1
            if not h: break
            for _ in range(h):
                i -= 1
                res.append(matrix[i][j])
            l -= 1
            if not l: break
        return res

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        if (matrix.length == 0) return res;
        int h = matrix.length, l = matrix[0].length;
        int i = 0, j = -1;
        while (true) {
            for (int k = 0; k < l; k++)
                res.add(matrix[i][++j]);
            if (--h == 0) break;
            for (int k = 0; k < h; k++)
                res.add(matrix[++i][j]);
            if (--l == 0) break;
            for (int k = 0; k < l; k++)
                res.add(matrix[i][--j]);
            if (--h == 0) break;
            for (int k = 0; k < h; k++)
                res.add(matrix[--i][j]);
            if (--l == 0) break;
        }
        return res;
    }
}

class Solution {
    public int[][] generateMatrix(int n) {
        int l = 0, r = n - 1, t = 0, b = n - 1;
        int[][] mat = new int[n][n];
        int num = 1, tar = n * n;
        while(num <= tar){
            for(int i = l; i <= r; i++) mat[t][i] = num++; // left to right.
            t++;
            for(int i = t; i <= b; i++) mat[i][r] = num++; // top to bottom.
            r--;
            for(int i = r; i >= l; i--) mat[b][i] = num++; // right to left.
            b--;
            for(int i = b; i >= t; i--) mat[i][l] = num++; // bottom to top.
            l++;
        }
        return mat;
    }
}

class Solution:
    def generateMatrix(self, n: int) -> [[int]]:
        l, r, t, b = 0, n - 1, 0, n - 1
        mat = [[0 for _ in range(n)] for _ in range(n)]
        num, tar = 1, n * n
        while num <= tar:
            for i in range(l, r + 1): # left to right
                mat[t][i] = num
                num += 1
            t += 1
            for i in range(t, b + 1): # top to bottom
                mat[i][r] = num
                num += 1
            r -= 1
            for i in range(r, l - 1, -1): # right to left
                mat[b][i] = num
                num += 1
            b -= 1
            for i in range(b, t - 1, -1): # bottom to top
                mat[i][l] = num
                num += 1
            l += 1
        return mat

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        matrix = [[0 for _ in range(n+1)] for _ in range(m+1)]
        matrix[0][1] = 1
        for i in range(1, len(matrix)):
            for j in range(1, len(matrix[0])):
                matrix[i][j] = matrix[i-1][j] + matrix[i][j-1]
        return matrix[-1][-1]

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] matrix = new int[m + 1][n + 1];
        matrix[0][1] = 1;
        for (int i = 1; i < matrix.length; i++) {
            for (int j = 1; j < matrix[0].length; j++) {
                matrix[i][j] = matrix[i - 1][j] + matrix[i][j - 1];
            }
        }
        return matrix[m][n];
    }
}

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        matrix = [[0 for _ in range(len(obstacleGrid[0])+1)]
                  for _ in range(len(obstacleGrid)+1)]
        matrix[0][1] = 1
        for i in range(1, len(matrix)):
            for j in range(1, len(matrix[0])):
                matrix[i][j] = matrix[i-1][j] + matrix[i][j - 1] \
                    if obstacleGrid[i-1][j-1] != 1 else 0
        return matrix[-1][-1]

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid.length == 0) return 0;
        int[][] matrix = new int[obstacleGrid.length + 1][obstacleGrid[0].length + 1];
        matrix[0][1] = 1;
        for (int i = 1; i < matrix.length; i++) {
            for (int j = 1; j < matrix[0].length; j++) {
                matrix[i][j] = obstacleGrid[i - 1][j - 1] != 1 ? matrix[i - 1][j] + matrix[i][j - 1] : 0;
            }
        }
        return matrix[matrix.length - 1][matrix[0].length - 1];
    }
}

class Solution:
    def isNumber(self, s: str) -> bool:
        states = [
            { 'b': 0, 's': 1, 'd': 2, '.': 4 }, # 0. start
            { 'd': 2, '.': 4 } ,                # 1. 'sign' before 'e'
            { 'd': 2, '.': 3, 'e': 5, 'b': 8 }, # 2. 'digit' before 'dot'
            { 'd': 3, 'e': 5, 'b': 8 },         # 3. 'dot' with 'digit'
            { 'd': 3 },                         # 4. no 'digit' before 'dot'
            { 's': 6, 'd': 7 },                 # 5. 'e'
            { 'd': 7 },                         # 6. 'sign' after 'e'
            { 'd': 7, 'b': 8 },                 # 7. 'digit' after 'e'
            { 'b': 8 }                          # 8. end with
        ]
        p = 0
        for c in s:
            if '0' <= c <= '9': typ = 'd'
            elif c == ' ': typ = 'b'
            elif c == '.': typ = '.'
            elif c == 'e': typ = 'e'
            elif c in "+-": typ = 's'
            else: typ = '?'
            if typ not in states[p]: return False
            p = states[p][typ]
        return p in [2, 3, 7, 8]

class Solution:
    def plusOne(self, digits: [int]) -> [int]:
        for i in range(len(digits)-1, -1, -1):
            if digits[i] != 9:
                digits[i] += 1
                return digits
            digits[i] = 0
        digits[0] = 1
        digits.append(0)
        return digits

class Solution {
    public int[] plusOne(int[] digits) {
        for (int i = digits.length - 1; i >= 0; i--) {
            if(digits[i] != 9){
                digits[i]++;
                return digits;
            }
            digits[i] = 0;
        }
        digits = new int[digits.length + 1];
        digits[0] = 1;
        return digits;
    }
}

class Solution:
    def climbStairs(self, n: int) -> int:
        a, b = 1, 1
        for _ in range(n-1):
            a, b = a + b, a
        return a

class Solution {
    public int climbStairs(int n) {
        int a = 1, b = 1;
        for(int i = 0; i < n - 1; i++){
            int tmp = a;
            a = a + b;
            b = tmp;
        }
        return a;
    }
}

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        dp = [[0 for _ in range(len(word2) + 1)] for _ in range(len(word1) + 1)]
        for i in range(1, len(dp)): dp[i][0] = i
        for i in range(1, len(dp[0])): dp[0][i] = i
        for i in range(1, len(dp)):
            for j in range(1, len(dp[0])):
                dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) if word1[i-1] != word2[j-1] else dp[i-1][j-1]
        return dp[-1][-1]

class Solution {
    public int minDistance(String word1, String word2) {
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        for(int i = 1; i < dp.length; i++) dp[i][0] = i;
        for(int i = 1; i < dp[0].length; i++) dp[0][i] = i;
        for(int i = 1; i < dp.length; i++) {
            for(int j = 1; j < dp[0].length; j++) {
                dp[i][j] = word1.charAt(i - 1) != word2.charAt(j - 1) ? 
                1 + Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) : dp[i-1][j-1];
            }
        }
        return dp[word1.length()][word2.length()];
     }
}

class Solution(object):
    def subsets(self, nums):
        res = []
        def children(j, tmp):
            res.append(tmp)
            for i in range(j, len(nums)):
                children(i + 1, tmp + [nums[i]])
        children(0, [])
        return res

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        children(nums, 0, res, new ArrayList<>());
        return res;
    }
    private void children(int[] nums, int j, List<List<Integer>> res, List<Integer> tmp) {
        res.add(new ArrayList<>(tmp));
        for(int i = j; i < nums.length; i++){
            tmp.add(nums[i]);
            children(nums, i + 1, res, tmp);
            tmp.remove(tmp.size() - 1);
        }
    }
}

class Solution:
    def subsets(self, nums: [int]) -> [[int]]:
        res = [[]]
        for i in nums:
            res = res + [num + [i] for num in res]
        return res

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        res.add(new ArrayList<Integer>());
        for(int num : nums){
            int size = res.size();
            for(int i = 0; i < size; i++) {
                List<Integer> tmp = new ArrayList<>(res.get(i));
                tmp.add(num);
                res.add(tmp);
            }
        }
        return res;
    }
}

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        tail, i, j = m + n - 1, m - 1, n - 1
        while i >= 0 and j >= 0:
            if nums1[i] > nums2[j]:
                nums1[tail] = nums1[i]
                i -= 1
            else:
                nums1[tail] = nums2[j]
                j -= 1
            tail -= 1
        for k in range(j, -1, -1): nums1[k] = nums2[k]

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int tail = m + n - 1, i = m - 1, j = n - 1;
        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) nums1[tail] = nums1[i--];
            else nums1[tail] = nums2[j--];
            tail--;
        }
        for(int k = j; k >= 0; k--) nums1[k] = nums2[k];
    }
}

class Solution:
    def grayCode(self, n: int) -> List[int]:
        res, head = [0], 1
        for i in range(n):
            for j in range(len(res) - 1, -1, -1):
                res.append(head + res[j])
            head <<= 1
        return res

class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> res = new ArrayList<Integer>() {{ add(0); }};
        int head = 1;
        for (int i = 0; i < n; i++) {
            for (int j = res.size() - 1; j >= 0; j--)
                res.add(head + res.get(j));
            head <<= 1;
        }
        return res;
    }
}

class Solution:
    def __init__(self):
        self.tmp = -float('inf')
    def isValidBST(self, root: TreeNode) -> bool:
        if not root: return True
        if not self.isValidBST(root.left): return False
        if self.tmp >= root.val: return False
        self.tmp = root.val
        if not self.isValidBST(root.right): return False
        return True

class Solution {
    long tmp = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if(root == null) return true;
        if (isValidBST(root.left)) {
            if (tmp < root.val) {
                tmp = root.val;
                return isValidBST(root.right);
            }
        }
        return false;
   }
}

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        def match(l, r):
            if not l and not r: return True
            if not l or not r: return False
            return l.val == r.val and \
                match(l.left, r.right) and \
                match(l.right, r.left)
        return match(root, root)

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return match(root, root);
    }
    private boolean match(TreeNode l, TreeNode r) {
        if (l == null && r == null) return true;
        if (l == null || r == null) return false;
        return l.val == r.val && 
            match(l.left, r.right) && 
            match(l.right, r.left);
    }
}

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root: return []
        cur, nex, tmp, res = [root], [], [], []
        while cur:
            for r in cur:
                tmp.append(r.val)
                if r.left: nex.append(r.left)
                if r.right: nex.append(r.right)
            res.append(tmp[:])
            cur, nex, tmp = nex, [], []
        return res

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null) return new ArrayList<>();
        List<TreeNode> cur = new ArrayList<>(), nex = new ArrayList<>();
        cur.add(root);
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> tmp = new ArrayList<>();
        while(cur.size() > 0){
            for(TreeNode r : cur) {
                tmp.add(r.val);
                if(r.left != null) nex.add(r.left);
                if(r.right != null) nex.add(r.right);
            }
            res.add(tmp);
            cur = nex;
            tmp = new ArrayList<>();
            nex = new ArrayList<>();
        }
        return res;
    }
}

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root: return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

class Solution:
    def buildTree(self, preorder: [int], inorder: [int]) -> TreeNode:
        if not inorder: return
        root = TreeNode(preorder.pop(0))
        i = inorder.index(root.val)
        root.left = self.buildTree(preorder, inorder[:i])
        root.right = self.buildTree(preorder, inorder[i+1:])
        return root

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder, 0, inorder, 0, inorder.length);
    }
    private TreeNode build(int[] preorder, int p, int[] inorder, int i, int j){
        if(i >= j) return null;
        TreeNode root = new TreeNode(preorder[p]);
        int k = 0;
        while(inorder[k] != root.val) k++;
        root.left = build(preorder, p + 1, inorder, i, k);
        root.right = build(preorder, p + 1 + k - i, inorder, k + 1, j);
        return root;
    }
}

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        if not nums: return
        mid = len(nums) // 2
        root = TreeNode(nums[mid])
        root.left = self.sortedArrayToBST(nums[:mid])
        root.right = self.sortedArrayToBST(nums[mid+1:])
        return root

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return toBST(nums, 0, nums.length - 1);
    }

    private TreeNode toBST(int[] nums, int left, int right) {
        if(left > right) return null;
        int mid = (left + right) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = toBST(nums, left, mid - 1);
        root.right = toBST(nums, mid + 1, right);
        return root;
    }
}

class Solution:
    def __init__(self):
        self.head = None
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        n, self.head = 0, head
        while head:
            head = head.next
            n += 1
        return self.to_bst(0, n - 1)
    def to_bst(self, left, right):
        if left > right: return
        m = (left + right) // 2
        left_child = self.to_bst(left, m - 1)
        father = TreeNode(self.head.val)
        self.head = self.head.next
        father.left = left_child
        father.right = self.to_bst(m + 1, right)
        return father

class Solution {
    private ListNode node;
    public TreeNode sortedListToBST(ListNode head) {
        int n = 0;
        node = head;
        while(head != null){
            head = head.next;
            n++;
        }
        return toBST(0, n-1);
    }
    private TreeNode toBST(int left, int right){
        if(left > right) return null;
        int m = (left + right) / 2;
        TreeNode left_child = toBST(left, m-1);
        TreeNode father = new TreeNode(node.val);
        node = node.next;
        father.left = left_child;
        father.right = toBST(m+1, right);
        return father;
    }
}

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        return self.depth(root) != -1

    def depth(self, root):
        if not root: return 0
        left = self.depth(root.left)
        if left == -1: return -1
        right = self.depth(root.right)
        if right == -1: return -1
        return max(left, right) + 1 if abs(left - right) < 2 else -1

class Solution {
    public boolean isBalanced(TreeNode root) {
        return depth(root) != -1;
    }

    private int depth(TreeNode root) {
        if (root == null) return 0;
        int left = depth(root.left);
        if(left == -1) return -1;
        int right = depth(root.right);
        if(right == -1) return -1;
        return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
    }
}

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        if not root: return True
        return abs(self.depth(root.left) - self.depth(root.right)) <= 1 and \
            self.isBalanced(root.left) and self.isBalanced(root.right)

    def depth(self, root):
        if not root: return 0
        return max(self.depth(root.left), self.depth(root.right)) + 1

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }

    private int depth(TreeNode root) {
        if (root == null) return 0;
        return Math.max(depth(root.left), depth(root.right)) + 1;
    }
}

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root: return 0
        if not root.left: return self.minDepth(root.right) + 1
        if not root.right: return self.minDepth(root.left) + 1
        return min(self.minDepth(root.left), self.minDepth(root.right)) + 1

class Solution {
    public int minDepth(TreeNode root) {
        if(root == null) return 0;
        if(root.left == null) return minDepth(root.right) + 1;
        if(root.right == null) return minDepth(root.left) + 1;
        return Math.min(minDepth(root.left),minDepth(root.right)) + 1;
    }
}

class Solution:
    def __init__(self):
        self.pre = None
    def flatten(self, root: TreeNode) -> None:
        if not root: return
        if self.pre: self.pre.right, self.pre.left = root, None
        self.pre = root
        right = root.right
        self.flatten(root.left)
        self.flatten(right)

class Solution {
    private TreeNode pre;
    public void flatten(TreeNode root) {
        if(root == null) return;
        if(pre != null){
            pre.right = root;
            pre.left = null;
        }
        pre = root;
        TreeNode right = root.right;
        flatten(root.left);
        flatten(right);
    }
}

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        cost, profit = float("+inf"), 0
        for price in prices:
            cost = min(price, cost)
            profit = max(price - cost, profit)
        return profit

class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0, cost = Integer.MAX_VALUE;
        for (int price : prices) {
            cost = Math.min(cost, price);
            profit = Math.max(profit, price - cost);
        }
        return profit;
    }
}

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        for i in range(1, len(prices)):
            tmp = prices[i] - prices[i - 1]
            if tmp > 0: profit += tmp
        return profit

class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;
        for (int i = 1; i < prices.length; i++) {
            int tmp = prices[i] - prices[i - 1];
            if (tmp > 0) profit += tmp;
        }
        return profit;
    }
}

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        self.max = float('-inf')
        self.max_path(root)
        return self.max
    def max_path(self, root):
        if not root: return 0
        left = self.max_path(root.left)
        right = self.max_path(root.right)
        self.max = max(left + right + root.val, self.max)
        tmp = max(left, right) + root.val
        return tmp if tmp > 0 else 0

class Solution {
    private int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        maxPath(root);
        return max;
    }
    private int maxPath(TreeNode root){
        if(root == null) return 0;
        int left = maxPath(root.left);
        int right = maxPath(root.right);
        max = Math.max(root.val + left + right, max);
        int tmp = Math.max(left, right) + root.val;
        return tmp > 0 ? tmp : 0;
    }
}

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left, right = 0, len(s) - 1
        case = abs(ord('a') - ord('A'))
        while left < right:
            while left < right and self.not_letters_digits(s[left]): left += 1
            while left < right and self.not_letters_digits(s[right]): right -= 1
            s_l = ord(s[left]) - case if s[left] >= 'a' else ord(s[left])
            s_r = ord(s[right]) - case if s[right] >= 'a' else ord(s[right])
            if s_l != s_r: return False
            left += 1
            right -= 1
        return True
    def not_letters_digits(self, c):
        return not 'A' <= c <= 'Z' and not 'a' <= c <= 'z' and not '0' <= c <= '9'

class Solution {
    public boolean isPalindrome(String s) {
        int i = 0, j = s.length() - 1;
        while(i < j){
            while(i < j && !Character.isLetterOrDigit(s.charAt(i))) i++;
            while(i < j && !Character.isLetterOrDigit(s.charAt(j))) j--;
            if(Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j))) return false;
            i++; j--;
        }
        return true;
    }
}

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        self.dic = {} # store all the copy nodes: dic[node] = copy
        return self.dfs(node)

    def dfs(self, node):
        if node not in self.dic:
            self.dic[node] = copy = Node(node.val, []) # get copy of the node 'node' and add it into the dictionary.
            for nei in node.neighbors: # recursive: get the neighbors of the node 'copy'.
                copy.neighbors.append(self.dfs(nei))
        return self.dic[node] # return the node 'copy'.

class Solution {
    private Map<Node, Node> map;
    public Node cloneGraph(Node node) {
        map = new HashMap<>();
        return dfs(node);
    }
    private Node dfs(Node node) {
        if(!map.containsKey(node)){
            Node copy = new Node(node.val, new ArrayList<Node>());
            map.put(node, copy);
            for(Node nei : node.neighbors){
                copy.neighbors.add(dfs(nei));
            }
        }
        return map.get(node);
    }
}

class Solution:
    def candy(self, ratings: List[int]) -> int:
        left = [1 for _ in range(len(ratings))]
        right = left[:]
        for i in range(1, len(ratings)):
            if ratings[i] > ratings[i - 1]: left[i] = left[i - 1] + 1
        count = left[-1]
        for i in range(len(ratings) - 2, -1, -1):
            if ratings[i] > ratings[i + 1]: right[i] = right[i + 1] + 1
            count += max(left[i], right[i])
        return count

class Solution {
    public int candy(int[] ratings) {
        int[] left = new int[ratings.length];
        int[] right = new int[ratings.length];
        Arrays.fill(left, 1);
        Arrays.fill(right, 1);
        for(int i = 1; i < ratings.length; i++)
            if(ratings[i] > ratings[i - 1]) left[i] = left[i - 1] + 1;
        int count = left[ratings.length - 1];
        for(int i = ratings.length - 2; i >= 0; i--) {
            if(ratings[i] > ratings[i + 1]) right[i] = right[i + 1] + 1;
            count += Math.max(left[i], right[i]);
        }
        return count;
    }
}

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res = 0
        for num in nums:
            res ^= num
        return res

class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for(int num : nums){
            res ^= num;
        }
        return res;
    }
}

class Solution:
    def singleNumber(self, nums: [int]) -> int:
        ones, twos, threes = 0, 0, 0
        for num in nums:
            twos |= ones & num # 二进制某位出现1次时twos = 0，出现2, 3次时twos = 1；
            ones ^= num  # 二进制某位出现2次时ones = 0，出现1, 3次时ones = 1；
            threes = ones & twos # 二进制某位出现3次时（即twos = ones = 1时）three = 1，其余即出现1, 2次时three = 0；
            ones &= ~threes # 将二进制下出现3次的位置零，实现`三进制下不考虑进位的加法`；
            twos &= ~threes
        return ones

class Solution {
    public int singleNumber(int[] nums) {
        int ones = 0, twos = 0, threes = 0;
        for(int num : nums){
            twos |= ones & num;
            ones ^= num;
            threes = ones & twos;
            ones &= ~threes;
            twos &= ~threes;
        }
        return ones;
    }
}

class Solution:
    def singleNumber(self, nums: [int]) -> int:
        ones, twos = 0, 0
        for num in nums:
            ones = ones ^ num & ~twos
            twos = twos ^ num & ~ones
        return ones

class Solution {
    public int singleNumber(int[] nums) {
        int ones = 0, twos = 0;
        for(int num : nums){
            ones = ones ^ num & ~twos;
            twos = twos ^ num & ~ones;
        }
        return ones;
    }
}

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head: return
        pre, cur = Node(0, None, None), head
        while cur: # copy and merge.
            nex = cur.next
            pre.next = cur
            cur.next = Node(cur.val, None, None)
            pre = cur.next
            cur = nex
        cur = head
        while cur: # set the 'random' nodes.
            cur.next.random = cur.random.next if cur.random else None
            cur = cur.next.next
        cur, res = head, head.next
        while cur.next: # divide the two linked lists.
            nex = cur.next
            cur.next = nex.next
            cur = nex
        return res

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        Node pre = new Node(0, null, null), cur = head, nex = cur.next;
        while(cur != null){
            nex = cur.next;
            pre.next = cur;
            cur.next = new Node(cur.val, null, null);
            pre = cur.next;
            cur = nex;
        }
        cur = head;
        while(cur != null){
            cur.next.random = cur.random != null ? cur.random.next : null;
            cur = cur.next.next;
        }
        cur = head;
        Node res = head.next;
        while(cur.next != null){
            nex = cur.next;
            cur.next = nex.next;
            cur = nex;
        }
        return res;
    }
}

class Solution(object):
    def hasCycle(self, head):
        fast, slow = head, head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow: return True
        return False

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) return true;
        }
        return false;
    }
}

class Solution(object):
    def detectCycle(self, head):
        fast, slow = head, head
        while True:
            if not (fast and fast.next): return
            fast, slow = fast.next.next, slow.next
            if fast == slow: break
        fast = head
        while fast != slow:
            fast, slow = fast.next, slow.next
        return fast

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while (true) {
            if (fast == null || fast.next == null) return null;
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) break;
        }
        fast = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return fast;
    }
}

class LRUCache:
    def __init__(self, capacity: int):
        self.dic, self.cap = collections.OrderedDict(), capacity

    def get(self, key: int) -> int:
        if key not in self.dic: return -1
        self.dic.move_to_end(key)
        return self.dic[key]

    def put(self, key: int, value: int) -> None:
        if key in self.dic: del self.dic[key]
        elif len(self.dic) == self.cap: self.dic.popitem(0)
        self.dic[key] = value

class LRUCache {
    private LinkedHashMap<Integer, Integer> map;
    public LRUCache(int capacity) {
        map = new LinkedHashMap<Integer, Integer>(capacity, .75F, true) {
            private static final long serialVersionUID = 4267176411845948333L;
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                return map.size() > capacity;
            }
        };
    }
    public int get(int key) {
        return map.getOrDefault(key, -1);
    }
    public void put(int key, int value) {
        map.put(key,value);
    }
}

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        if not head or not head.next: return head # termination.
        # cut the LinkedList at the mid index.
        slow, fast = head, head.next
        while fast and fast.next:
            fast, slow = fast.next.next, slow.next
        mid, slow.next = slow.next, None # save and cut.
        # recursive for cutting.
        left, right = self.sortList(head), self.sortList(mid)
        # merge `left` and `right` linked list and return it.
        h = res = ListNode(0)
        while left and right:
            if left.val < right.val: h.next, left = left, left.next
            else: h.next, right = right, right.next
            h = h.next
        h.next = left if left else right
        return res.next

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode fast = head.next, slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode tmp = slow.next;
        slow.next = null;
        ListNode left = sortList(head);
        ListNode right = sortList(tmp);
        ListNode h = new ListNode(0);
        ListNode res = h;
        while (left != null && right != null) {
            if (left.val < right.val) {
                h.next = left;
                left = left.next;
            } else {
                h.next = right;
                right = right.next;
            }
            h = h.next;
        }
        h.next = left != null ? left : right;
        return res.next;
    }
}

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        h, length, intv = head, 0, 1
        while h: h, length = h.next, length + 1
        res = ListNode(0)
        res.next = head
        # merge the list in different intv.
        while intv < length:
            pre, h = res, res.next
            while h:
                # get the two merge head `h1`, `h2`
                h1, i = h, intv
                while i and h: h, i = h.next, i - 1
                if i: break # no need to merge because the `h2` is None.
                h2, i = h, intv
                while i and h: h, i = h.next, i - 1
                c1, c2 = intv, intv - i # the `c2`: length of `h2` can be small than the `intv`.
                # merge the `h1` and `h2`.
                while c1 and c2:
                    if h1.val < h2.val: pre.next, h1, c1 = h1, h1.next, c1 - 1
                    else: pre.next, h2, c2 = h2, h2.next, c2 - 1
                    pre = pre.next
                pre.next = h1 if c1 else h2
                while c1 > 0 or c2 > 0: pre, c1, c2 = pre.next, c1 - 1, c2 - 1
                pre.next = h
            intv *= 2
        return res.next

class Solution:
    def evalRPN(self, tokens: [str]) -> int:
        symbol = ['+', '-', '*', '/']
        stack = []
        for t in tokens:
            if t in symbol:
                stack.append(self.eval(stack.pop(-2), stack.pop(), t))
            else:
                stack.append(int(t))
        return stack[-1]
    def eval(self, x, y, symbol):
        if symbol == '+': return x + y
        if symbol == '-': return x - y
        if symbol == '*': return x * y
        if symbol == '/': return int(x / y)

class Solution {
    private static final Set<String> SYMBOLS = new HashSet<>(Arrays.asList("+","-","*","/"));
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for(String t : tokens){
            if(SYMBOLS.contains(t)){
                int y = stack.pop();
                int x = stack.pop();
                stack.push(eval(x, y, t));
            } else {
                stack.push(Integer.parseInt(t));
            }
        }
        return stack.peek();
    }
    private int eval(int x, int y, String symbol){
        switch(symbol){
            case "+": return x + y;
            case "-": return x - y;
            case "*": return x * y;
            default:  return x / y;
        }
    }
}

class Solution:
    def reverseWords(self, s: str) -> str:
        s = s.strip()
        res = ""
        i, j = len(s) - 1, len(s)
        while i > 0:
            if s[i] == ' ':
                res += s[i + 1: j] + ' '
                while s[i] == ' ': i -= 1
                j = i + 1
            i -= 1
        return res + s[:j]

    def reverseWords1(self, s: str) -> str:
        return " ".join(s.split()[::-1])

class Solution {
    public String reverseWords(String s) {
        StringBuffer res = new StringBuffer();
        s = s.trim(); // delete leading or trailing spaces.
        int i = s.length() - 1, j = s.length();
        while (i > 0) {
            if (s.charAt(i) == ' ') {
                res.append(s.substring(i + 1, j));
                res.append(' ');
                while (s.charAt(i) == ' ') i--; // ignore extra spaces between words.
                j = i + 1;
            }
            i--;
        }
        return res.append(s.substring(0, j)).toString();
    }
}

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        mi = ma = res = nums[0]
        for i in range(1, len(nums)):
            if nums[i] < 0: mi, ma = ma, mi
            ma = max(ma * nums[i], nums[i])
            mi = min(mi * nums[i], nums[i])
            res = max(res, ma)
        return res

class Solution {
    public int maxProduct(int[] nums) {
        int max = nums[0], min = nums[0], res = nums[0];
        for(int i = 1; i < nums.length; i++){
            if(nums[i] < 0){
                int tmp = max;
                max = min;
                min = tmp;
            }
            max = Math.max(nums[i], max * nums[i]);
            min = Math.min(nums[i], min * nums[i]);
            res = Math.max(max, res);
        }
        return res;
    }
}

class Solution:
    def findMin(self, nums: [int]) -> int:
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) // 2
            if nums[mid] > nums[right]: left = mid + 1
            else: right = mid
        return nums[left]

class Solution {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        while(left < right){
            int mid = (left + right) / 2;
            if(nums[mid] > nums[right]) left = mid + 1;
            else right = mid;
        }
        return nums[left];
    }
}

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) // 2
            if nums[mid] > nums[right]: left = mid + 1
            elif nums[mid] < nums[right]: right = mid
            else: right = right - 1 # key
        return nums[left]

class Solution {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] > nums[right]) left = mid + 1;
            else if (nums[mid] < nums[right]) right = mid;
            else right = right - 1;
        }
        return nums[left];
    }
}

class MinStack:
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.min_stack = []
    def push(self, x: int) -> None:
        self.stack.append(x)
        if not self.min_stack or x <= self.min_stack[-1]:
            self.min_stack.append(x)
    def pop(self) -> None:
        if self.stack.pop() == self.min_stack[-1]:
            self.min_stack.pop()
    def top(self) -> int:
        return self.stack[-1]
    def getMin(self) -> int:
        return self.min_stack[-1]

class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> min_stack;
    /** initialize your data structure here. */
    public MinStack() {
        stack = new Stack<>();
        min_stack = new Stack<>();
    }
    public void push(int x) {
        stack.push(x);
        if(min_stack.isEmpty() || x <= min_stack.peek())
            min_stack.push(x);
    }
    public void pop() {
        if(stack.pop().equals(min_stack.peek()))
            min_stack.pop();
    }
    public int top() {
        return stack.peek();
    }
    public int getMin() {
        return min_stack.peek();
    }
}

class Solution:
    def upsideDownBinaryTree(self, root: TreeNode) -> TreeNode:
        parent = parent_right = None
        while root:
            root_left = root.left
            root.left = parent_right
            parent_right = root.right
            root.right = parent
            parent = root
            root = root_left
        return parent

class Solution {
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        TreeNode parent = null, parent_right = null;
        while(root != null){
            TreeNode root_left = root.left;
            root.left = parent_right;
            parent_right = root.right;
            root.right = parent;
            parent = root;
            root = root_left;
        }
        return parent;
    }
}

class Solution:
    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
        dic = {}
        i, dist, res = 0, 0, 0
        for j in range(len(s)):
            if s[j] in dic and dic[s[j]]:
                dic[s[j]] += 1
            else:
                dic[s[j]] = 1
                dist += 1
            while dist > 2:
                dic[s[i]] -= 1
                if not dic[s[i]]: dist -= 1
                i += 1
            res = max(res, j - i + 1)
        return res

class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        int[] count = new int[256];
        int i = 0, numDistinct = 0, maxLen = 0;
        for (int j = 0; j < s.length(); j++) {
            if (count[s.charAt(j)] == 0) numDistinct++;
            count[s.charAt(j)]++;
            while (numDistinct > 2) {
                count[s.charAt(i)]--;
                if (count[s.charAt(i)] == 0) numDistinct--;
                i++;
            }
            maxLen = Math.max(maxLen, j - i + 1);
        }
        return maxLen;
    }
}

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        ha, hb = headA, headB
        while ha != hb:
            ha = ha.next if ha else headB
            hb = hb.next if hb else headA
        return ha

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode ha = headA, hb = headB;
        while (ha != hb) {
            ha = ha != null ? ha.next : headB;
            hb = hb != null ? hb.next : headA;
        }
        return ha;
    }
}

class Solution:
    def isOneEditDistance(self, s: str, t: str) -> bool:
        i, dif = 0, len(t) - len(s)
        if dif < 0: s, t, dif = t, s, -dif
        if dif > 1: return False # 1.
        while i < len(s) and s[i] == t[i]: i += 1 # 2.
        if i == len(s): return bool(dif)
        if not dif: i += 1 # 3.1
        while i < len(s) and s[i] == t[i + dif]: i += 1 # 3.
        return i == len(s) #5.

class Solution {
    public boolean isOneEditDistance(String s, String t) {
        int dif = t.length() - s.length(), i = 0;
        if (dif < 0) return isOneEditDistance(t, s);
        if (dif > 1) return false;
        while (i < s.length() && s.charAt(i) == t.charAt(i)) i++;
        if (i == s.length()) return dif > 0;
        if (dif == 0) i++;
        while (i < s.length() && s.charAt(i) == t.charAt(i + dif)) i++;
        return i == s.length();
    }
}

class Solution:
    def findMissingRanges(self, nums: [int], lower: int, upper: int) -> [str]:
        res = []
        low = lower - 1
        nums.append(upper + 1)
        for num in nums:
            dif = num - low
            if dif == 2: res.append(str(low+1))
            elif dif > 2: res.append(str(low+1) + "->" + str(num-1))
            low = num
        return res

class Solution {
    public List<String> findMissingRanges(int[] nums, int lower, int upper) {
        List<String> res = new ArrayList<>();
        long pre = (long)lower - 1; // prevent 'int' overflow
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] - pre == 2) res.add(String.valueOf(pre + 1));
            else if (nums[i] - pre > 2) res.add((pre + 1) + "->" + (nums[i] - 1));
            pre = nums[i]; // 'int' to 'long'
        }
        if (upper - pre == 1) res.add(String.valueOf(pre + 1));
        else if (upper - pre > 1) res.add((pre + 1) + "->" + upper);
        return res;
    }
}

class Solution:
    def majorityElement(self, nums: [int]) -> int:
        count = 0
        for num in nums:
            if not count: res = num
            count += 1 if num == res else -1
        return res

class Solution {
    public int majorityElement(int[] nums) {
        int res = 0, count = 0;
        for(int num : nums){
            if(count == 0) res = num;
            count += num == res ? 1 : -1;
        }
        return res;
    }
}

class TwoSum:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.nums = []
        self.dic = {}

    def add(self, number: int) -> None:
        """
        Add the number to an internal data structure..
        """
        self.nums.append(number)
        self.dic[number] = len(self.nums) - 1  

    def find(self, value: int) -> bool:
        """
        Find if there exists any pair of numbers which sum is equal to the value.
        """
        for i in range(len(self.nums)):
            tar = value - self.nums[i]
            if tar in self.dic and self.dic[tar] != i: return True
        return False

class TwoSum {
    private Map<Integer, Integer> map;
    private List<Integer> nums = new ArrayList<>();
    /** Initialize your data structure here. */
    public TwoSum() {
        map = new HashMap<>();
    }
    /** Add the number to an internal data structure.. */
    public void add(int number) {
        nums.add(number);
        map.put(number, nums.size() - 1);
    }
    /** Find if there exists any pair of numbers which sum is equal to the value. */
    public boolean find(int value) {
        for(int i = 0; i < nums.size(); i++){
            int tar = value - nums.get(i);
            if(map.containsKey(tar) && map.get(tar) > i) return true;
        }
        return false;
    }
}

class Solution:
    def reverseWords(self, s: [str]) -> None:
        """
        Do not return anything, modify str in-place instead.
        """
        i = 0
        for j in range(len(s)): # aT bT c
            if s[j] != ' ': continue
            self.reverse(s, i, j)
            i = j + 1
        self.reverse(s, i, len(s)) # aT bT cT
        self.reverse(s, 0, len(s)) # c b a
    def reverse(self, s, i, j):
        for k in range(i, (i + j) // 2):
            g = j - 1 - k + i
            s[k], s[g] = s[g], s[k]

class Solution {
    public void reverseWords(char[] str) {
        int i = 0;
        for(int j = 0; j < str.length; j++){ // aTbTc
            if(str[j] != ' ') continue;
            reverse(str, i, j);
            i = j + 1;
        }
        reverse(str, i, str.length); // aTbTcT
        reverse(str, 0, str.length); // cba
    }
    private void reverse(char[] str, int i, int j){
        for(int k = i; k < (i + j) / 2; k++){
            char tmp = str[k];
            int g = j - 1 - k + i;
            str[k] = str[g];
            str[g] = tmp;
        }
    }
}

class Solution:
    def numIslands(self, grid: [[str]]) -> int:
        def dfs(grid, i, j):
            if not 0 <= i < len(grid) or not 0 <= j < len(grid[0]) or grid[i][j] == '0': return
            grid[i][j] = '0'
            dfs(grid, i + 1, j)
            dfs(grid, i, j + 1)
            dfs(grid, i - 1, j)
            dfs(grid, i, j - 1)
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    dfs(grid, i, j)
                    count += 1
        return count

class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                if(grid[i][j] == '1'){
                    dfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }
    private void dfs(char[][] grid, int i, int j){
        if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0') return;
        grid[i][j] = '0';
        dfs(grid, i + 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i - 1, j);
        dfs(grid, i, j - 1);
    }
}

class Solution:
    def numIslands(self, grid: [[str]]) -> int:
        def bfs(grid, i, j):
            queue = [[i, j]]
            while queue:
                [i, j] = queue.pop(0)
                if 0 <= i < len(grid) and 0 <= j < len(grid[0]) and grid[i][j] == '1':
                    grid[i][j] = '0'
                    queue += [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '0': continue
                bfs(grid, i, j)
                count += 1
        return count

class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                if(grid[i][j] == '1'){
                    bfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }
    private void bfs(char[][] grid, int i, int j){
        Queue<int[]> list = new LinkedList<>();
        list.add(new int[] { i, j });
        while(!list.isEmpty()){
            int[] cur = list.remove();
            i = cur[0]; j = cur[1];
            if(0 <= i && i < grid.length && 0 <= j && j < grid[0].length && grid[i][j] == '1') {
                grid[i][j] = '0';
                list.add(new int[] { i + 1, j });
                list.add(new int[] { i - 1, j });
                list.add(new int[] { i, j + 1 });
                list.add(new int[] { i, j - 1 });
            }
        }
    }
}

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head: return
        pre = None
        while head.next:
            nex = head.next
            head.next = pre
            pre = head
            head = nex
        head.next = pre
        return head

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null) return null;
        ListNode pre = null, nex = null;
        while(head.next != null) {
            nex = head.next;
            head.next = pre;
            pre = head;
            head = nex;
        }
        head.next = pre;
        return head;
    }
}

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        indegrees = [0 for _ in range(numCourses)]
        adjacency = [[] for _ in range(numCourses)]
        queue = []
        # Get the indegree and adjacency of every course.
        for cur, pre in prerequisites:
            indegrees[cur] += 1
            adjacency[pre].append(cur)
        # Get all the courses with the indegree of 0.
        for i in range(len(indegrees)):
            if not indegrees[i]: queue.append(i)
        # BFS TopSort.
        while queue:
            pre = queue.pop(0)
            numCourses -= 1
            for cur in adjacency[pre]:
                indegrees[cur] -= 1
                if not indegrees[cur]: queue.append(cur)
        return not numCourses

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] indegrees = new int[numCourses];
        for(int[] cp : prerequisites) indegrees[cp[0]]++;
        LinkedList<Integer> queue = new LinkedList<>();
        for(int i = 0; i < numCourses; i++){
            if(indegrees[i] == 0) queue.addLast(i);
        }
        while(!queue.isEmpty()) {
            Integer pre = queue.removeFirst();
            numCourses--;
            for(int[] req : prerequisites) {
                if(req[1] != pre) continue;
                if(--indegrees[req[0]] == 0) queue.add(req[0]);
            }
        }
        return numCourses == 0;
    }
}

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        def dfs(i, adjacency, flags):
            if flags[i] == -1: return True
            if flags[i] == 1: return False
            flags[i] = 1
            for j in adjacency[i]:
                if not dfs(j, adjacency, flags): return False
            flags[i] = -1
            return True
        adjacency = [[] for _ in range(numCourses)]
        flags = [0 for _ in range(numCourses)]
        for cur, pre in prerequisites:
            adjacency[pre].append(cur)
        for i in range(numCourses):
            if not dfs(i, adjacency, flags): return False
        return True

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[][] adjacency = new int[numCourses][numCourses];
        int[] flags = new int[numCourses];
        for(int[] cp : prerequisites)
            adjacency[cp[1]][cp[0]] = 1;
        for(int i = 0; i < numCourses; i++){
            if(!dfs(adjacency, flags, i)) return false;
        }
        return true;
    }
    private boolean dfs(int[][] adjacency, int[] flags, int i) {
        if(flags[i] == 1) return false;
        if(flags[i] == -1) return true;
        flags[i] = 1;
        for(int j = 0; j < adjacency.length; j++) {
            if(adjacency[i][j] == 1 && !dfs(adjacency, flags, j)) return false;
        }
        flags[i] = -1;
        return true;
    }
}

import heapq
class Solution:
    def findKthLargest(self, nums: [int], k: int) -> int:
        heap = []
        for num in nums[:k]:
            heapq.heappush(heap, num)
        for num in nums[k:]:
            if num > heap[0]:
                heapq.heappop(heap)
                heapq.heappush(heap, num)
        return heap[0]

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Queue<Integer> heap = new PriorityQueue<>();
        for (int i = 0; i < k; i++)
            heap.add(nums[i]);
        for (int i = k; i < nums.length; i++) {
            if (nums[i] > heap.peek()) {
                heap.remove();
                heap.add(nums[i]);
            }
        }
        return heap.peek();
    }
}

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        dic = {}
        for n in nums:
            if n in dic: return True
            dic[n] = 1
        return False

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>(nums.length);
        for(int n : nums){
            if(set.contains(n)) return true;
            set.add(n);
        }
        return false;
    }
}

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        self.res, self.count = None, k
        def inorder(root):
            if not (root and self.count): return
            inorder(root.left)
            self.count -= 1
            if not self.count: self.res = root.val
            inorder(root.right)
        inorder(root)
        return self.res

class Solution {
    private int res, count;
    public int kthSmallest(TreeNode root, int k) {
        count = k;
        inorder(root);
        return res;
    }
    private void inorder(TreeNode root) {
        if(root == null || count == 0) return;
        inorder(root.left);
        if(--count == 0) res = root.val;
        inorder(root.right);
    }
}

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n > 0 and n & (n - 1) == 0

class Solution {
    public boolean isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }
}

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if p.val > q.val: p, q = q, p
        while root:
            if root.val < p.val: root = root.right
            elif root.val > q.val: root = root.left
            else: return root

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        int pv = Math.min(p.val, q.val), qv = Math.max(p.val, q.val);
        while (root != null) {
            if (root.val < pv) root = root.right;
            else if (root.val > qv) root = root.left;
            else return root;
        }
        return null;
    }
}

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        self.res = None
        self.dfs(root, p, q)
        return self.res
    def dfs(self, root, p, q):
        if not root: return 0
        left = self.dfs(root.left, p, q)
        right = self.dfs(root.right,p ,q)
        mid = root == p or root == q
        if left + right + mid > 1: self.res = root
        return left or right or mid

class Solution {
    TreeNode res = null;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root, p, q);
        return res;
    }
    private int dfs(TreeNode root, TreeNode p, TreeNode q){
        if(root == null) return 0;
        int left = dfs(root.left, p, q);
        int right = dfs(root.right, p, q);
        int mid = root == p || root == q ? 1 : 0;
        if(left + right + mid > 1) res = root;
        return left + right + mid > 0 ? 1 : 0;
    }
}

class Solution:
    def deleteNode(self, node):
        node.val = node.next.val
        node.next = node.next.next

class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

class Solution:
    def productExceptSelf(self, nums: [int]) -> [int]:
        res, p, q = [1], 1, 1
        for i in range(len(nums) - 1): # top triangle
            p *= nums[i]
            res.append(p)
        for i in range(len(nums) - 1, 0, -1): # bottom triangle
            q *= nums[i]
            res[i - 1] *= q
        return res

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] res = new int[nums.length];
        int p = 1, q = 1;
        for (int i = 0; i < nums.length; i++) {
            res[i] = p;
            p *= nums[i];
        }
        for (int i = nums.length - 1; i > 0 ; i--) {
            q *= nums[i];
            res[i - 1] *= q;
        }
        return res;
    }
}

class Solution:
    def canWinNim(self, n: int) -> bool:
        return n % 4 != 0

class Solution {
    public boolean canWinNim(int n) {
        return n % 4 != 0;
    }
}

class Solution:
    def minPatches(self, nums: List[int], n: int) -> int:
        add, i, count = 1, 0, 0
        while add <= n:
            if i < len(nums) and nums[i] <= add:
                add += nums[i] # from [1, add] to [1, add + nums[i]]
                i += 1
            else:
                add += add # from [1, add] to [1, 2add]
                count += 1
        return count

class Solution {
    public int minPatches(int[] nums, int n) {
        int i = 0, count = 0;
        long add = 1;
        while(add <= n){
            if(i < nums.length && nums[i] <= add) add += nums[i++];
            else {
                add += add;
                count ++;
            }
        }
        return count;
    }
}

class Solution:
    def reverseString(self, s: List[str]) -> None:
        i, j = 0, len(s) - 1
        while i < j:
            s[i], s[j] = s[j], s[i]
            i, j = i + 1, j - 1

class Solution {
    public void reverseString(char[] s) {
        int i = 0, j = s.length - 1;
        while(i < j) {
            char tmp = s[i];
            s[i] = s[j];
            s[j] = tmp;
            i++; j--;
        }
    }
}

class Solution:
    def decodeString(self, s: str) -> str:
        stack, res, multi = [], "", 0
        for c in s:
            if c == '[':
                stack.append([multi, res])
                res, multi = "", 0
            elif c == ']':
                cur_multi, last_res = stack.pop()
                res = last_res + cur_multi * res
            elif '0' <= c <= '9':
                multi = multi * 10 + int(c)
            else:
                res += c
        return res

class Solution {
    public String decodeString(String s) {
        StringBuilder res = new StringBuilder();
        int multi = 0;
        LinkedList<Integer> stack_multi = new LinkedList<>();
        LinkedList<String> stack_res = new LinkedList<>();
        for(Character c : s.toCharArray()) {
            if(c == '[') {
                stack_multi.addLast(multi);
                stack_res.addLast(res.toString());
                multi = 0;
                res = new StringBuilder();
            }
            else if(c == ']') {
                StringBuilder tmp = new StringBuilder();
                int cur_multi = stack_multi.removeLast();
                for(int i = 0; i < cur_multi; i++) tmp.append(res);
                res = new StringBuilder(stack_res.removeLast() + tmp);
            }
            else if(c >= '0' && c <= '9') multi = multi * 10 + Integer.parseInt(c + "");
            else res.append(c);
        }
        return res.toString();
    }
}

class Solution:
    def decodeString(self, s: str) -> str:
        def dfs(s, i):
            res, multi = "", 0
            while i < len(s):
                if '0' <= s[i] <= '9':
                    multi = multi * 10 + int(s[i])
                elif s[i] == '[':
                    i, tmp = dfs(s, i + 1)
                    res += multi * tmp
                    multi = 0
                elif s[i] == ']':
                    return i, res
                else:
                    res += s[i]
                i += 1
            return res
        return dfs(s,0)

class Solution {
    public String decodeString(String s) {
        return dfs(s, 0)[0];
    }
    private String[] dfs(String s, int i) {
        StringBuilder res = new StringBuilder();
        int multi = 0;
        while(i < s.length()) {
            if(s.charAt(i) >= '0' && s.charAt(i) <= '9') 
                multi = multi * 10 + Integer.parseInt(String.valueOf(s.charAt(i))); 
            else if(s.charAt(i) == '[') {
                String[] tmp = dfs(s, i + 1);
                i = Integer.parseInt(tmp[0]);
                while(multi > 0) {
                    res.append(tmp[1]);
                    multi--;
                }
            }
            else if(s.charAt(i) == ']') 
                return new String[] { String.valueOf(i), res.toString() };
            else
                res.append(String.valueOf(s.charAt(i)));
            i++;
        }
        return new String[] { res.toString() };
    }
}

class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        res = ""
        i, j, carry = len(num1) - 1, len(num2) - 1, 0
        while i >= 0 or j >= 0:
            n1 = int(num1[i]) if i >= 0 else 0
            n2 = int(num2[j]) if j >= 0 else 0
            tmp = n1 + n2 + carry
            carry = tmp // 10
            res = str(tmp % 10) + res
            i, j = i - 1, j - 1
        return "1" + res if carry else res

class Solution {
    public String addStrings(String num1, String num2) {
        StringBuilder res = new StringBuilder("");
        int i = num1.length() - 1, j = num2.length() - 1, carry = 0;
        while(i >= 0 || j >= 0){
            int n1 = i >= 0 ? num1.charAt(i) - '0' : 0;
            int n2 = j >= 0 ? num2.charAt(j) - '0' : 0;
            int tmp = n1 + n2 + carry;
            carry = tmp / 10;
            res.append(tmp % 10);
            i--; j--;
        }
        if(carry == 1) res.append(1);
        return res.reverse().toString();
    }
}

class Solution:
    def reverseWords(self, s: str) -> str:
        l = []
        i, left, right = 0, 0, -2
        while i < len(s) + 1:
            if i == len(s) or s[i] == ' ':
                left, right = right + 1, i - 1
                for j in range(right, left, -1):
                    l.append(s[j])
                l.append(' ')
            i += 1
        return "".join(l[:-1])

class Solution:
    def reverseWords(self, s: str) -> str:
        return ' '.join(i[::-1] for i in s.split())

class Solution557 {
    public String reverseWords(String s) {
        String[] strs = s.split(" ");
        StringBuffer res = new StringBuffer("");
        for(String str : strs){
            StringBuffer tmp = new StringBuffer(str);
            res.append(" ");
            res.append(tmp.reverse().toString());
        }
        return res.toString().trim();
    }
}

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        five, ten = 0, 0
        for b in bills:
            if b == 5:
                five += 1
            elif b == 10:
                if not five: return False
                five -= 1
                ten += 1
            else:
                if ten and five:
                    ten -= 1
                    five -= 1
                elif five > 2:
                    five -= 3
                else:
                    return False
        return True

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int five = 0, ten = 0;
        for(int b : bills){
            if(b == 5) five ++;
            else if(b == 10) {
                if(five-- == 0) return false;
                ten++;
            }
            else {
                if(five > 0 && ten > 0){
                    five--; ten--;
                }
                else if(five > 2){
                    five -= 3;
                }
                else return false;
            }
        }
        return true;
    }
}

class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        row = len(array)-1
        col = 0
        while row>=0 and col<len(array[0]):
            if target == array[row][col]:
                return True
            elif target > array[row][col]:
                col+=1
            else:
                row-=1
        return False

# -*- coding:utf-8 -*-
class Solution:
    # s 源字符串
    def replaceSpace(self, s):
        # write code here
        l = list(s)
        count = 0
        for k in l:
            if k == ' ':
                count+=1
                l.extend(['1','1'])
        for i in range(len(s)-1,-1,-1):
            if l[i]!=' ':
                l[i+2*count]=l[i]
            else:
                count-=1 
                l[i+2*count]='%'
                l[i+2*count+1]='2'
                l[i+2*count+2]='0'
        return ''.join(l)

class Solution:
    # 返回从尾部到头部的列表值序列，例如[1,2,3]
    def printListFromTailToHead(self, listNode):
        # write code here
        return self.printListFromTailToHead(listNode.next) + [listNode.val] if listNode else []

class Solution:
    def reConstructBinaryTree(self, pre, tin):
        if not tin: return
        root = TreeNode(pre.pop(0))
        for i in range(len(tin)):
            if root.val == tin[i]: break
        root.left = self.reConstructBinaryTree(pre, tin[:i])
        root.right = self.reConstructBinaryTree(pre, tin[i+1:])
        return root

class Solution:
    def __init__(self):
        self.que, self.asi = [], []
    def push(self, node):
        # write code here
        self.que.append(node)
    def pop(self):
        # return xx
        if not self.asi:
            if not self.que: return
            while self.que:
                self.asi.append(self.que.pop())
        return self.asi.pop()

# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, nums):
        # write code here
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) // 2
            if nums[mid] > nums[right]: left = mid + 1
            elif nums[mid] < nums[right]: right = mid
            else: right = right - 1 # key
        return nums[left]

# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        # write code here
        a, b = 0, 1
        for _ in range(n-1):
            a, b = b, a + b
        return b if n > 0 else 0

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloor(self, number):
        # write code here
        if number == 1:
            return number
        a=0
        b=1
        for _ in range(number):
            a,b = b,a+b
        return b

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloorII(self, number):
        # write code here
        return 2 ** (number - 1) # or pow(2, number - 1)

# -*- coding:utf-8 -*-
class Solution:
    def rectCover(self, number):
        # write code here
        if number == 0 or number == 1:
            return number
        a=0
        b=1
        for _ in range(number):
            a,b = b,a+b
        return b

# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1(self, n):
        # write code here
        n &= 0xffffffff
        count = 0
        while n:
            count += n & 1
            n >>= 1
        return count

print(hex(1)) #0x1
print(hex(-1)) #-0x1 = 0xffffffff（补码，二进制第一位是符号位，前面还有无限个1）
print(hex(1& 0xffffffff)) #0x1 = 0x00000001
print(hex(-1& 0xffffffff)) #0xffffffff，相当于把前面无限个1变为0，从符号位至最后一位保持不变，但符号位的1被提出到与其他位等价。
print(-1& 0xffffffff) #4294967295 = 2^32-1 = -1的无符号形式

# -*- coding:utf-8 -*-
class Solution:
    def Power(self, base, exponent):
        # write code here
        res, exp = 1, abs(exponent)
        while exp != 0:
            if exp & 1 != 0: res *= base
            base *= base
            exp >>= 1
        return res if exponent > 0 else 1/res

# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        # write code here
        odd, even = [], []
        for a in array:
            odd.append(a) if a & 1 else even.append(a)
        return odd + even

class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        node1, node2 = head, head
        for _ in range(k):
            if not node1: return
            node1 = node1.next
        while node1:
            node1, node2 = node1.next, node2.next
        return node2

class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        cur, pre = pHead, None
        while cur:
            nex = cur.next
            cur.next = pre
            pre = cur
            cur = nex
        return pre

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        tmp = ListNode(0)
        head = tmp
        while pHead1 and pHead2:
            if pHead1.val < pHead2.val:
                tmp.next, pHead1 = pHead1, pHead1.next
            else:
                tmp.next, pHead2 = pHead2, pHead2.next
            tmp = tmp.next
        tmp.next = pHead2 if not pHead1 else pHead1
        return head.next

class Solution:
    def HasSubtree(self, pRoot1, pRoot2):
        # write code here
        if not pRoot1 or not pRoot2: return False
        return self.is_subtree(pRoot1, pRoot2) or self.HasSubtree(pRoot1.left, pRoot2) or self.HasSubtree(pRoot1.right, pRoot2)

    def is_subtree(self, r1, r2):
        if not r2: return True
        if not r1 or r1.val != r2.val: return False
        return self.is_subtree(r1.left, r2.left) and self.is_subtree(r1.right, r2.right)

class Solution:
    # 返回镜像树的根节点
    def Mirror(self, root):
        # write code here
        if not root: return
        root.left, root.right = root.right, root.left
        self.Mirror(root.left)
        self.Mirror(root.right)
        return root

# -*- coding:utf-8 -*-
class Solution:
    # matrix类型为二维列表，需要返回列表
    def printMatrix(self, matrix):
        # write code here
        res = matrix.pop(0)
        while matrix:
            matrix = [[matrix[i][j] for i in range(len(matrix))] for j in range(len(matrix[0])-1, -1, -1)]
            res += matrix.pop(0)
        return res

# -*- coding:utf-8 -*-
class Solution:
    # matrix类型为二维列表，需要返回列表
    def printMatrix(self, matrix):
        if not matrix: return []
        res = []
        h, l = len(matrix), len(matrix[0])
        i, j = 0, -1
        while True:
            for _ in range(l):
                j += 1
                res.append(matrix[i][j])
            h -= 1
            if not h: break
            for _ in range(h):
                i += 1
                res.append(matrix[i][j])
            l -= 1
            if not l: break
            for _ in range(l):
                j -= 1
                res.append(matrix[i][j])
            h -= 1
            if not h: break
            for _ in range(h):
                i -= 1
                res.append(matrix[i][j])
            l -= 1
            if not l: break
        return res

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack = []
        self.m_stack = []
    def push(self, node):
        # write code here
        self.stack.append(node)
        if not self.m_stack or self.m_stack[-1] >= node:
            self.m_stack.append(node)
    def pop(self):
        # write code here
        if self.stack.pop() == self.m_stack[-1]:
            self.m_stack.pop()
    def top(self):
        # write code here
        return self.stack[-1]
    def min(self):
        # write code here
        return self.m_stack[-1]

# -*- coding:utf-8 -*-
class Solution:
    def IsPopOrder(self, pushV, popV):
        # write code here
        imi = [pushV.pop(0)]
        while imi:
            cur = popV.pop(0)
            while imi[-1] != cur:
                if not pushV: return False
                imi.append(pushV.pop(0))
            imi.pop()
        return True

class Solution:
    # 返回从上到下每个节点值列表，例：[1,2,3]
    def PrintFromTopToBottom(self, root):
        # write code here
        if not root: return []
        res, tmp = [], [root]
        while tmp:
            t = tmp.pop(0)
            res.append(t.val)
            if t.left: tmp.append(t.left)
            if t.right: tmp.append(t.right)
        return res

# -*- coding:utf-8 -*-
class Solution:
    def VerifySquenceOfBST(self, sequence):
        # write code here
        return self.verify(sequence) if sequence else False
    def verify(self, sequence):
        if not sequence: return True
        for i in range(len(sequence)):
            if sequence[i] >= sequence[-1]: break
        for j in range(i, len(sequence)-1):
            if sequence[j] <= sequence[-1]: return False
        return self.verify(sequence[:i]) and self.verify(sequence[i+1:-1])

class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    def FindPath(self, root, expectNumber):
        # write code here
        self.res, self.path = [], []
        self.search(root, expectNumber)
        return self.res
    def search(self, root, target):
        if not root or target < 0: return
        target -= root.val
        self.path.append(root.val)
        if not (root.left or root.right or target):
            self.res.append(list(self.path))
        self.search(root.left, target)
        self.search(root.right, target)
        self.path.pop()

# -*- coding:utf-8 -*-
# class RandomListNode:
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None
class Solution:
    # 返回 RandomListNode
    def Clone(self, head):
        # write code here
        if not head: return
        h = head
        while h:
            tmp = RandomListNode(h.label)
            nex = h.next
            h.next, h, tmp.next = tmp, nex, nex
        h = head
        while h.next.next:
            if h.random: h.next.random = h.random.next
            h = h.next.next
        h, res = head, head.next
        while h.next:
            tmp = h.next
            h.next, h = h.next.next, tmp
        return res

class Solution:
    def Convert(self, pRootOfTree):
        # write code here
        self.pre = TreeNode(0)
        res = self.pre
        self.traversal(pRootOfTree)
        if res.right: res.right.left = None
        return res.right
    def traversal(self, root):
        if not root: return
        self.traversal(root.left)
        self.pre.right = root
        root.left = self.pre
        self.pre = root
        self.traversal(root.right)

# -*- coding:utf-8 -*-
class Solution:
    def Permutation(self, ss):
        # write code here
        self.res, self.sort = [], list(ss)
        self.sort_dic(0, len(ss))
        self.res.sort()
        return self.res
    def sort_dic(self, s, e):
        if e - s == 1: self.res.append(''.join(self.sort))
        same = {}
        for i in range(s, e):
            if self.sort[i] in same: continue
            same[self.sort[i]] = 1
            self.sort[s], self.sort[i] = self.sort[i], self.sort[s]
            self.sort_dic(s+1, e)
            self.sort[s], self.sort[i] = self.sort[i], self.sort[s]

# -*- coding:utf-8 -*-
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        tmp = list(numbers) # copy the list
        i = 1
        while i < len(tmp):
            if tmp[0] == tmp[i]:
                i += 1
            else:
                del tmp[0], tmp[i-1]
                i = 1
        if not tmp: return 0
        count = 0
        for num in numbers:
            if num == tmp[0]: count += 2
        return tmp[0] if count > len(numbers) else 0

import heapq
# -*- coding:utf-8 -*-
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        if not k or k > len(tinput): return []
        heap, res = [], []
        for n in tinput:
            if len(heap) < k:
                heapq.heappush(heap, -n)
            elif -n > heap[0]:
                heapq.heappush(heap, -n)
                heapq.heappop(heap)
        while heap:
            res.append(-heapq.heappop(heap))
        res.reverse()
        return res

# -*- coding:utf-8 -*-
class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        tmp = [array[0]]
        for i in range(1, len(array)):
            tmp += [array[i]] if tmp[i-1] < 0 else [array[i] + tmp[i-1]]
        return max(tmp)

# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        total, deno, count, end = 0, 1, 0, 0
        while n != 0:
            num = n % (deno * 10)
            n -= num
            if num > deno:
                count += total * num / deno + deno
            elif num == deno:
                count += total + 1 + end
            total = total*10 + deno
            end += num
            deno *= 10
        return int(count)

# -*- coding:utf-8 -*-
class Solution:
    def PrintMinNumber(self, numbers):
        # write code here
        self.quick_sort(numbers, 0, len(numbers)-1)
        return "".join([str(num) for num in numbers])

    def quick_sort(self, arr, l, r):
        if l > r: return
        base, i, j = arr[l], l, r
        while i != j:
            while self.compare(arr[j], base) and i < j: j -= 1
            while self.compare(base, arr[i]) and i < j: i += 1
            arr[i], arr[j] = arr[j], arr[i]
        arr[l], arr[i] = arr[i], arr[l]
        self.quick_sort(arr, l, i-1)
        self.quick_sort(arr, i+1, r)

    def compare(self, a, b):
        str1, str2 = str(a) + str(b), str(b) + str(a)
        return 0 if str1 < str2 else 1

# -*- coding:utf-8 -*-class Solution:
    def GetUglyNumber_Solution(self, index):
        # write code here
        if index < 7: return index
        t2 = t3 = t5 = 0
        res = [1]
        for i in range(1,index):
            r2, r3, r5 = res[t2] * 2, res[t3] * 3, res[t5] * 5
            res.append(min([r2, r3, r5])) 
            if res[i] == r2: t2 += 1
            if res[i] == r3: t3 += 1
            if res[i] == r5: t5 += 1
        return res[-1]

# -*- coding:utf-8 -*-
class Solution:
    def FirstNotRepeatingChar(self, s): 
        # write code here
        dic = {}
        for c in s:
            if c in dic: dic[c] += 1
            else: dic[c] = 1
        for i in range(len(s)):
            if dic[s[i]] == 1: return i
        return -1

# -*- coding:utf-8 -*-
class Solution:
    def InversePairs(self, data):
        # write code here
        self.arr, self.count = data, 0
        self.merge_sort(0, len(data)-1)
        return self.count % 1000000007
    def merge_sort(self, l, r):
        if l >= r: return
        m = int((l+r+1)/2)
        self.merge_sort(l, m-1)
        self.merge_sort(m, r)
        i, j, merge = l, m, []
        while i < m and j <= r:
            if self.arr[i] < self.arr[j]:
                merge.append(self.arr[i])
                i += 1
            else:
                merge.append(self.arr[j])
                j += 1
                self.count += m - i
        for x in range(j,r+1): merge.append(self.arr[x])
        for x in range(i,m): merge.append(self.arr[x])
        for i in range(l, r+1): self.arr[i] = merge[i-l]

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def FindFirstCommonNode(self, pHead1, pHead2):
        # write code here
        length1 = length2 = 0
        head1, head2 = pHead1, pHead2
        while head1:
            head1 = head1.next
            length1 += 1
        while head2:
            head2 = head2.next
            length2 += 1
        [k, lon, sho] = [length1 - length2, pHead1, pHead2] if length1 > length2 else [length2 - length1, pHead2, pHead1]
        for _ in range(k):
            lon = lon.next
        while lon:
            if lon == sho: return lon
            lon, sho = lon.next, sho.next

# -*- coding:utf-8 -*-
class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        return self.findLocation(data, k + 0.1) - self.findLocation(data, k - 0.1)

    def findLocation(self, data, k):
        left, right = 0, len(data) - 1
        while left <= right:
            mid = int((left + right) / 2)
            if data[mid] > k: right = mid - 1
            else: left = mid + 1
        return left

class Solution:
    def TreeDepth(self, pRoot):
        # write code here
        if not pRoot: return 0
        return max(self.TreeDepth(pRoot.left), self.TreeDepth(pRoot.right)) + 1

class Solution:
    def IsBalanced_Solution(self, pRoot):
        # write code here
        return self.getDepth(pRoot) != -1
    def getDepth(self, pRoot):
        if not pRoot: return 0
        dl = self.getDepth(pRoot.left)
        dr = self.getDepth(pRoot.right)
        return max(dl,dr) + 1 if dl != -1 and dr != -1 and -2 < dl - dr < 2 else -1

# -*- coding:utf-8 -*-
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        num_xor = array[0]
        for a in array[1:]:
            num_xor ^= a
        index = 0
        while num_xor & 1 != 1:
            num_xor >>= 1
            index += 1
        n0, n1 = 0, 0
        for a in array:
            if a >> index & 1: n0 ^= a
            else: n1 ^= a
        return [n0,n1]

# -*- coding:utf-8 -*-
class Solution:
    def FindContinuousSequence(self, tsum):
        # write code here
        res, l, r, s = [], 1, 2, 3
        while l < r:
            if s >= tsum: 
                if s == tsum: res.append(list(range(l,r+1)))
                s -= l
                l += 1
            else: 
                r += 1
                s += r
        return res

# -*- coding:utf-8 -*-
class Solution:
    def FindNumbersWithSum(self, array, tsum):
        # write code here
        l, r = 0, len(array) - 1
        while l < r:
            if array[l] + array[r] < tsum: l += 1
            elif array[l] + array[r] > tsum: r -= 1
            else: return [array[l], array[r]]
        return []

# -*- coding:utf-8 -*-
class Solution:
    def LeftRotateString(self, s, n):
        # write code here
        res, length = list(s), len(s)
        if n > length : return ""
        for i in range(int(n/2)):
            res[i], res[n-1-i] = res[n-1-i], res[i]
        for i in range(n, int((n+length)/2)):
            res[i], res[length-1-i+n] = res[length-1-i+n], res[i]
        for i in range(int(length/2)):
            res[i], res[length-1-i] = res[length-1-i], res[i]
        return "".join(res)

# -*- coding:utf-8 -*-
class Solution:
    def ReverseSentence(self, s):
        # write code here
        res, length, last = list(s), len(s), -1
        for i in range(len(res)):
            if res[i] == ' ': 
                self.reverse(res, last + 1, i)
                last = i
        self.reverse(res, 0, length)
        return "".join(res)

    def reverse(self, res, l, r):
        while l < r:
            res[l], res[r-1] = res[r-1], res[l]
            l += 1
            r -= 1

# -*- coding:utf-8 -*-
class Solution:
    def IsContinuous(self, numbers):
        # write code here
        numbers.sort()
        joker = 0
        for n in numbers[:4]:
            if not n: joker += 1
        for i in range(joker, len(numbers) - 1):
            tmp = numbers[i+1] - numbers[i] - 1
            joker -= tmp
            if joker < 0 or tmp < 0: return False
        return True if numbers else False

# -*- coding:utf-8 -*-
class Solution:
    def LastRemaining_Solution(self, n, m):
        # write code here
        if not n: return -1
        res = list(range(n))
        length, index = len(res), 0
        while length > 1:
            index = (index + m - 1) % length
            res.pop(index)
            length = len(res)
        return res[0]

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.sum = 0
    def Sum_Solution(self, n):
        # write code here
        n and self.Sum_Solution(n-1)
        self.sum += n
        return self.sum

# -*- coding:utf-8 -*-
class Solution:
    def Add(self, num1, num2):
        # write code here
        while num2:
            num1, num2 = (num1 ^ num2) & 0xFFFFFFFF, (num1 & num2) << 1 & 0xFFFFFFFF
        return num1 if num1 <= 0x7FFFFFFF else ~(num1 ^ 0xFFFFFFFF)

# -*- coding:utf-8 -*-
class Solution:
    def StrToInt(self, s):
        # write code here 
        if not s: return 0
        res, bit = 0, 1
        end = -1 if s[0] != '+' and s[0] != '-' else 0
        for i in range(len(s)-1, end, -1):
            num = ord(s[i]) - 48
            if num > 9 or num < 0: return 0
            res += num * bit
            bit *= 10
        return -res if s[0] == "-" else res

# -*- coding:utf-8 -*-
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        table = [0 for _ in range(len(numbers))]
        for n in numbers:
            if table[n] > 0:
                duplication[0] = n
                return True
            table[n] += 1
        return False

# -*- coding:utf-8 -*-
class Solution:
    def multiply(self, A):
        # write code here
        B, tmp = [1], 1
        for i in range(len(A)-1):
            B.append(B[i]*A[i])
        for i in range(len(A)-1, 0, -1):
            tmp *= A[i]
            B[i-1] *= tmp
        return B

# -*- coding:utf-8 -*-
class Solution:
    # s, pattern都是字符串
    def match(self, s, pattern):
        # write code here
        return self.match_str(s, pattern, 0, 0)

    def match_str(self, s, p, i, j):
        ls, lp = len(s), len(p)
        if not j < lp:
            if not i < ls: return True
            return False
        if j+1 < lp and p[j+1] == '*':
            if i < ls and (s[i] == p[j] or p[j] == '.'):
                return self.match_str(s, p, i+1, j) or self.match_str(s, p, i, j+2)
            return self.match_str(s, p, i, j+2)
        if i < ls and (s[i] == p[j] or p[j] == '.'):
            return self.match_str(s, p, i+1, j+1)
        return False

# -*- coding:utf-8 -*-
class Solution:
    # s字符串
    def isNumeric(self, s):
        # write code here
        ls, i, dot = len(s), 1, 0
        # 首位必须为“+/-/number”
        if s[0] != '+' and s[0] != '-' and (s[0] < '0' or s[0] > '9'): return False
        # 遍历1~(len-1)位，如果发现E or e就跳到下一个while
        while i < ls - 1:
            if s[i] == 'E' or s[i] == 'e':
                i += 1
                break
            elif s[i] == '.':
                if dot: return False
                dot += 1
            elif s[i] < '0' or s[i] > '9': return False
            i += 1
        # e后面首位必须为“+/-/number”
        if s[i] != '+' and s[i] != '-' and (s[i] < '0' or s[i] > '9'): return False
        i += 1
        # e不能出现两次，并且e后面的数字组合不能有小数点，其余和前面一样
        while i < ls:
            if s[i] < '0' or s[i] > '9': return False
            i += 1
        return True

# -*- coding:utf-8 -*-
class Solution:
    # 返回对应char
    def __init__(self):
        self.s = ''
        self.dic = {}

    def FirstAppearingOnce(self):
        # write code here
        for c in self.s:
            if self.dic[c] == 1: return c
        return '#'

    def Insert(self, char):
        # write code here
        self.s += char
        if char in self.dic: self.dic[char] += 1
        else: self.dic[char] = 1

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here 
        p1, p2, step= pHead, pHead, 0
        while p1 != p2 or step == 0:
            if not p1.next or not p2.next.next: return None
            p1, p2 = p1.next, p2.next.next
            step += 1
        p1, p2 = pHead, pHead
        for _ in range(step):
            p1 = p1.next
        while p1 != p2:
            p1, p2 = p1.next, p2.next
        return p1

class Solution:
    def deleteDuplication(self, pHead):
        # write code here
        if not pHead: return
        pre, h1, h2 = ListNode(pHead.val - 1), pHead, pHead
        res, pre.next = pre, h2
        while h2:
            while h2 and h1.val == h2.val:
                tmp, h2 = h2, h2.next
            if tmp == h1: pre.next, pre = tmp, h1
            h1 = h2
        pre.next = None
        return res.next

class Solution:
    def GetNext(self, pNode):
        # write code here
        if pNode.right: # 1
            node = pNode.right
            while node.left: node = node.left
            return node
        while pNode.next:  # 2
            if pNode == pNode.next.left: return pNode.next
            pNode = pNode.next
        return # 3

class Solution:
    def isSymmetrical(self, pRoot):
        if not pRoot: return True
        return self.match(pRoot.left, pRoot.right)
    def match(self, lef, rig):
        if not lef and not rig: return True
        if not lef or not rig or lef.val != rig.val: return False
        return self.match(lef.left, rig.right) and self.match(lef.right, rig.left)

class Solution:
    def Print(self, pRoot):
        # write code here
        if not pRoot: return []
        res, roots, reverse = [], [pRoot], False
        while roots:
            tmp = []
            for _ in range(len(roots)):
                r = roots.pop(0)
                tmp.append(r.val)
                if r.left: roots.append(r.left)
                if r.right: roots.append(r.right)
            if reverse: tmp.reverse()
            reverse = not reverse
            res.append(tmp)
        return res

class Solution:
    # 返回二维列表[[1,2],[4,5]]
    def Print(self, pRoot):
        # write code here
        res = []
        self.line(res, [pRoot])
        return res

    def line(self, res, roots):
        if not roots or not roots[0]: return
        tmp, re = [], []
        for r in roots:
            re.append(r.val)
            if r.left: tmp.append(r.left)
            if r.right: tmp.append(r.right)
        res.append(re)
        self.line(res, tmp)

class Solution:
    def Serialize(self, root):
        # write code here
        return self.serialize(root)[:-1]

    def serialize(self, root):
        res = ""
        if not root: return '#,'
        res += str(root.val) + ','
        res += self.serialize(root.left)
        res += self.serialize(root.right)
        return res

    def Deserialize(self, s):
        root, i = self.deserialize(s.split(","),0)
        return root

    def deserialize(self, s, i):
        if i >= len(s) or s[i] == '#':
            return None, i + 1
        root = TreeNode(int(s[i]))
        root.left, i = self.deserialize(s, i+1)
        root.right, i = self.deserialize(s, i)
        return root, i

class Solution:
    # 返回对应节点TreeNode
    def KthNode(self, pRoot, k):
        # write code here
        self.res, self.k, self.count = None, k - 1, 0
        self.recur(pRoot)
        return self.res
    def recur(self, root):
        if not root: return
        self.recur(root.left)
        if self.res: return
        if self.count == self.k: self.res = root
        self.count += 1
        self.recur(root.right)

import heapq
# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.q = []
        self.p = []
    def Insert(self, num):
        # write code here
        if not self.p or num <= -self.p[0]: heapq.heappush(self.p, -num)
        else: heapq.heappush(self.q, num)
        if len(self.p) == len(self.q) + 2: heapq.heappush(self.q, -heapq.heappop(self.p))
        elif len(self.p) + 1 == len(self.q): heapq.heappush(self.p, -heapq.heappop(self.q))
    def GetMedian(self, data):
        # write code here
        return (self.q[0] - self.p[0]) / 2.0 if len(self.q) == len(self.p) else -self.p[0]

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.arr = []
    def Insert(self, num):
        # write code here、
        i, j = 0, len(self.arr)-1
        while i <= j:
            m = (i+j) // 2
            if self.arr[m] < num: i = m + 1
            else: j = m - 1
        self.arr = self.arr[:i] + [num] + self.arr[i:]
    def GetMedian(self, data):
        # write code here
        m = len(self.arr)//2
        return (self.arr[m]+self.arr[m-1])/2.0 if not len(self.arr) % 2 else self.arr[m]

# -*- coding:utf-8 -*-
class Solution:
    def maxInWindows(self, num, size):
        # write code here
        queue, res = [], []
        for i in range(len(num)):
            while queue and num[queue[-1]] <= num[i]: queue.pop()
            while queue and queue[0] <= i - size: queue.pop(0)
            queue.append(i)
            if size and i > size: res.append(num[queue[0]])
        return res

# -*- coding:utf-8 -*-
class Solution:
    def hasPath(self, matrix, rows, cols, path):
        # write code here
        self.flags = [0 for _ in range(len(matrix))]
        self.matrix, self.rows, self.cols, self.path = matrix, rows, cols, path
        for i in range(rows):
            for j in range(cols):
                if self.search(i, j, 0): return True
        return False

    def search(self, i, j, k):
        index = self.cols * i + j
        if not 0 <= i < self.rows or not 0 <= j < self.cols or \
        self.flags[index] or self.matrix[index] != self.path[k]:
            return False # 越界 or 已经走过 or 不是所需节点 
        if k == len(self.path) - 1:
            return True # 已经找完，不需要继续递归
        self.flags[index] = 1 # 走过这个点，寻找下个点
        if self.search(i+1, j, k+1) or self.search(i-1, j, k+1) or \
        self.search(i, j+1, k+1) or self.search(i, j-1, k+1):  
            return True # 四条路中有一条可以走通
        self.flags[index] = 0 # 如果无法走通，要释放这个点，以防影响其他路线中走此点
        return False

# -*- coding:utf-8 -*-
class Solution:
    def movingCount(self, threshold, rows, cols):
        # write code here
        self.matrix, self.k, self.rows, self.cols = \
        [[0 for _ in range(cols)] for _ in range(rows)], threshold, rows, cols
        return self.moving(0, 0)
    def moving(self, i, j):
        if not 0 <= i < self.rows or not 0 <= j < self.cols or \
        self.matrix[i][j] or self.k < self.sums(i) + self.sums(j):
            return 0
        self.matrix[i][j] = 1
        return 1 + self.moving(i+1, j) + self.moving(i-1, j) + \
            self.moving(i, j+1) + self.moving(i, j-1) # still pass without self.moving(i, j-1).
    def sums(self, i):
        m = 0
        while i:
            i, b = i // 10, i % 10
            m += b
        return m