public int mySqrt(int x) {
        if (x <= 1) return x;
        int l = 1, r = x;
        while (l < r) {
            int m = l + (r - l) / 2; // 防止溢出
            if (x / m > m) l = m + 1;
            else r = m ;
        }
        return r - 1;
    }

    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (!set.add(nums[i])) {
                return true;
            }
        }
        return false;
    }

    public TreeNode invertTree(TreeNode root) {
        if (root == null) return root;

        TreeNode t = root.left;
        root.left = root.right;
        root.right = t;

        invertTree(root.left);
        invertTree(root.right);

        return root;
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> s1 = newStack(l1), s2 = newStack(l2);

        ListNode h = null;
        int carry = 0;
        while(!s1.isEmpty() && !s2.isEmpty()) {
            int t = s1.pop() + s2.pop() + carry;
            h = concat(h, t % 10);
            carry = t >= 10 ? 1 : 0;
        }

        Stack<Integer> s = s1.isEmpty() ? s2 : s1;

        while(!s.isEmpty()) {
            int t = carry + s.pop();
            h = concat(h, t % 10);
            carry = t >= 10 ? 1 : 0;
        }
        if (carry != 0) h = concat(h, carry);

        return h;
    }

    private Stack newStack(ListNode l) {
        Stack s =  new Stack();
        while (l != null) {
            s.push(l.val);
            l = l.next;
        }
        return s;
    }

    private ListNode concat(ListNode h, Integer v) {
        ListNode t = new ListNode(v);
        t.next = h;
        return t;
    }

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList();
        result.add(new ArrayList());

        for(int n : nums) {
            int size = result.size();
            for(int i = 0; i< size; i ++){
                List<Integer> subset = new ArrayList<>(result.get(i));
                subset.add(n);
                result.add(subset);
            }
        }

        return result;
    }

    public String decodeString(String s) {
        String res = "";
        Stack<Integer> countStack = new Stack<>();
        Stack<String> resStack = new Stack<>();
        int idx = 0;
        while (idx < s.length()) {
            if (Character.isDigit(s.charAt(idx))) {
                int count = 0;
                while (Character.isDigit(s.charAt(idx))) {
                    count = 10 * count + (s.charAt(idx) - '0');
                    idx++;
                }
                countStack.push(count);
            }
            else if (s.charAt(idx) == '[') {
                resStack.push(res);
                res = "";
                idx++;
            }
            else if (s.charAt(idx) == ']') {
                StringBuilder temp = new StringBuilder(resStack.pop());
                int repeatTimes = countStack.pop();
                for (int i = 0; i < repeatTimes; i++) {
                    temp.append(res);
                }
                res = temp.toString();
                idx++;
            }
            else {
                res += s.charAt(idx++);
            }
        }
        return res;
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode h = new ListNode(0);
        ListNode c = h;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                c.next = l1;
                l1 = l1.next;
            } else {
                c.next = l2;
                l2 = l2.next;
            }
            c = c.next;
        }

        ListNode l = l1 == null ? l2 : l1;
        while(l != null){
            c.next = l;
            l = l.next;
            c = c.next;
        }

        return h.next;
    }

    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++ ) {
            int n = Math.abs(nums[i]) - 1;
            if (nums[n] < 0) {
                res.add(n + 1);
            } else {
                nums[n] = -nums[n];
            }
        }
        return res;
    }

    private static class Pos {
        int start;
        int end;
        int count;
    }

    public int findShortestSubArray(int[] nums) {
        Map<Integer, Pos> m = new HashMap<>();
        
        for (int i = 0; i < nums.length; i++) {
            Pos p = m.get(nums[i]);
            if (p == null){
                p = new Pos();
                p.start = i;
                p.end = i;
                p.count = 1;
                m.put(nums[i], p);
            } else {
                p.end = i;
                p.count++;
            }
        }

        Pos max = null;
        for(Map.Entry<Integer, Pos> entry : m.entrySet()) {
            Pos t = entry.getValue();
            if (max == null
                || t.count > max.count
                || (t.count == max.count && (t.end - t.start) < (max.end - max.start)))
                max = t;
        }
        return max.end - max.start + 1;
    }

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

    public int reverse(int x) {
        public int reverse(int x) {
        long res = 0;
        while(x != 0) {
            res = res * 10 + x % 10;
            x = x / 10;
        }

        return (int) res == res ? (int)res : 0;
    }

    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int i = 0, j = 0, max = 0;

        while(j < s.length()) {
            if (!set.contains(s.charAt(j))) {
                set.add(s.charAt(j++));
                max = Math.max(max, set.size());
            } else {
                set.remove(s.charAt(i++));
            }
        }

        return max;
    }

    public int hammingDistance(int x, int y) {
        int xor = x ^ y, count = 0;
        for (int i = 0; i < 32; i++) count += (xor >> i) & 1;
        return count;
    }

    public int totalHammingDistance(int[] nums) {
        int n = 31;
        int len = nums.length;
        int[] countOfOnes = new int[n];
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < n; j++) {
                countOfOnes[j] += (nums[i] >> j) & 1;
            }
        }
        int sum = 0;
        for (int count: countOfOnes) {
            sum += count * (len - count);
        }
        return sum;
    }

    public int myAtoi(String str) {
        str = str.trim();
        if (str.isEmpty()) return 0;

		int i = 0, ans = 0, sign = 1, len = str.length();
		if (str.charAt(i) == '-' || str.charAt(i) == '+')
			sign = str.charAt(i++) == '+' ? 1 : -1;
		for (; i < len; ++i) {
			int tmp = str.charAt(i) - '0';
			if (tmp < 0 || tmp > 9)
				break;
			if (ans > Integer.MAX_VALUE / 10
					|| (ans == Integer.MAX_VALUE / 10 && Integer.MAX_VALUE % 10 < tmp))
				return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
			else
				ans = ans * 10 + tmp;
		}
		return sign * ans;
    }