LeetCode 解题报告

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null)
            return l1;
        if (l2 == null)
            return l2;
        ListNode resu = new ListNode(0);
        ListNode node = resu;
        int temp = 0;
        while (l1 != null || l2 != null || temp != 0) {
            if (l1 != null) {
                temp += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                temp += l2.val;
                l2 = l2.next;
            }
            node.next = new ListNode(temp % 10);
            node = node.next;
            temp /= 10;
        }
        return resu.next;
    }
}

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) return 0;
        int[] count = new int[256];
        // 因为0也是位置，所以全部-1防止误判断
        Arrays.fill(count, -1);
        int start = -1, result = 0;
        for (int i = 0; i < s.length(); i++){
            // 更新重复的字符最后一次出现的位置
            start = Math.max(count[s.charAt(i)], start);
            // 修改当前字符出现的位置
            count[s.charAt(i)] = i;
            // 取最大值
            result = Math.max(result, i - start);
        }
        return result;
    }
}

class Solution {
    public static String longestPalindrome(String s) {
        boolean[][] dp = new boolean[1005][1005];
        int left = 0;
        int right = 0;
        int maxl = 1;
        int n = s.length();
        for (int j = 0; j < n; j++) {
            // 单个字符肯定是回文字符串
            dp[j][j] = true;
            for (int i = 0; i < j; i++) {
                if (s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                }
                if (dp[i][j] && maxl < j - i + 1) {
                    maxl = j - i + 1;
                    left = i;
                    right = j;
                }
            }
        }
        return (s == null || s.length() <= 1) ? s : s.substring(left, right + 1);
    }
}

class Solution {
    public String convert(String s, int nRows) {
        char[] c = s.toCharArray();
        int len = c.length;
        StringBuffer[] sb = new StringBuffer[nRows];
        for (int i = 0; i < sb.length; i++)
            sb[i] = new StringBuffer();
        int i = 0;
        while (i < len) {
            for (int idx = 0; idx < nRows && i < len; idx++) // 竖着的
                sb[idx].append(c[i++]);
            for (int idx = nRows - 2; idx >= 1 && i < len; idx--) // 斜向上的
                sb[idx].append(c[i++]);
        }
        for (int idx = 1; idx < sb.length; idx++)
            sb[0].append(sb[idx]);
        return sb[0].toString();
    }
}

class Solution {
    public int myAtoi(String str) {
        if (str == null || str.length() == 0)
            return 0;
        str = str.trim();
        if (str.length() == 0)
            return 0;
        int start = 0, sign = 1, base = 0;
        if (str.charAt(start) == '-' || str.charAt(start) == '+') {
            sign = (str.charAt(start) == '-' ? -1 : 1);
            start++;
        }
        while (start < str.length() && str.charAt(start) >= '0' && str.charAt(start) <= '9') {
            if (base > Integer.MAX_VALUE / 10
                    || (base == Integer.MAX_VALUE / 10 && (str.charAt(start) - '0' > Integer.MAX_VALUE % 10))) {
                return sign > 0 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }
            base = base * 10 + (str.charAt(start++) - '0');
        }
        return base * sign;
    }
}

class Solution {
    public boolean isPalindrome(int x) {
        String str = String.valueOf(x);
        StringBuilder sb = new StringBuilder(str);
        return sb.reverse().toString().equals(str);
    }
}

class Solution {
    public static boolean isPalindrome(int x) {
        if (x < 0) return false;
        int[] a = new int[33];
        int i = 0;
        while (x != 0) {
            a[i++] = x % 10;
            x /= 10;
        }
        for (int j = 0; j < i; j++) {
            if (a[j] != a[i - j - 1]) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(isPalindrome(1234564321));
    }
}

class Solution {
    public boolean isMatch(String s, String p) {
        int l1 = s.length(), l2 = p.length();
        boolean[][] dp = new boolean[l1 + 1][l2 + 1];
        dp[0][0] = true;
        for (int i = 2; i < l2 + 1; i += 2) {
            if (p.charAt(i - 1) == '*' && dp[0][i - 2]) {
                dp[0][i] = true;
            }
        }
        for (int i = 1; i < l1 + 1; i++) {
            for (int j = 1; j < l2 + 1; j++) {
                if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (p.charAt(j - 1) == '*') {
                    if (p.charAt(j - 2) != s.charAt(i - 1) && p.charAt(j - 2) != '.') {
                        dp[i][j] = dp[i][j - 2];
                    } else {
                        dp[i][j] = dp[i - 1][j] || dp[i - 1][j - 2] || dp[i][j - 2];
                    }
                }
            }
        }
        return dp[l1][l2];
    }
}

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length == 0) return result;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++){
            if (nums[i] > 0){
                break;
            }
            if (i > 0 && nums[i] == nums[i - 1])
                continue;
            int left = i + 1, right = nums.length - 1;
            while (left < right){
                int l = nums[left];
                int r = nums[right];
                int m = nums[i];
                if (l + r + m == 0){
                    result.add(Arrays.asList(m, l, r));
                    while (left < right && nums[left] == l) left ++;
                    while (left < right && nums[right] == r) right --;
                } else if (l + r + m < 0){
                    left ++;
                } else {
                    right --;
                }
            }
        }
        return result;
    }
}

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums.length == 0)
            return result;
        Arrays.sort(nums);
        int left, right, temp;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0)
                break;
            if (i > 0 && nums[i] == nums[i - 1])
                continue;
            left = i + 1;
            right = nums.length - 1;
            while (left < right) {
                temp = nums[left] + nums[right] + nums[i];
                if (temp == 0) {
                    List<Integer> resu = new ArrayList<>();
                    int lll = nums[left];
                    int rrr = nums[right];
                    resu.add(nums[i]);
                    resu.add(nums[left]);
                    resu.add(nums[right]);
                    result.add(resu);
                    while (left < right && nums[left] == lll)
                        left++;
                    while (left < right && nums[right] == rrr)
                        right--;
                } else if (temp > 0)
                    right--;
                else
                    left++;
            }
        }
        return result;
    }
}

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int resu = 0;
        int sub = Integer.MAX_VALUE; // 这里要注意一下。
        for (int i = 0; i < nums.length - 1; i++) {
            int mid = i + 1;
            int right = nums.length - 1;
            while (mid < right) {
                int sum = nums[i] + nums[right] + nums[mid];
                if (Math.abs(sum - target) < sub) {
                    sub = Math.abs(sum - target);
                    resu = sum;
                }
                if (sum < target) {
                    mid++;
                } else if (sum > target) {
                    right--;
                } else {
                    return target;
                }
            }
        }
        return resu;
    }
}

class Solution {
    public boolean isValid(String s) {
        HashMap<Character, Character> map = new HashMap<>();
        map.put('{','}');
        map.put('(',')');
        map.put('[',']');
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i< s.length(); i++){
            char sa = s.charAt(i);
            // 判断是不是左括号，左括号压入
            if (map.containsKey(sa)){
                stack.push(sa);
                continue;
            }
            if (map.containsValue(sa)){
                if (stack.isEmpty()) return false;
                char tmp = stack.peek();
                if (map.get(tmp) == sa){
                    stack.pop();
                } else {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

class Solution {
    public List<String> generateParenthesis(int n) {
        Set<String> set = new HashSet<>();
        if (n == 0) {
            return new ArrayList<>(set);
        }
        if (n == 1) {
            set.add("()");
            return new ArrayList<>(set);
        }
        List<String> tmp = generateParenthesis(n - 1);
        for (String s : tmp) {
            for (int i = 0; i < s.length(); i++) {
                set.add(s.substring(0, i) + "()" + s.substring(i +));
            }
        }
        return new ArrayList<>(set);
    }
}

public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<>();
        help(list, n, 0, 0, "");
        return list;
    }
    public void help(List<String> list, int n, int l, int r, String s) {
        if (s.length() == 2 * n) {
            list.add(s);
        }
        if (l < n) {
            help(list, n, l + 1, r, s + '(');
        }
        if (r < l) {
            help(list, n, l, r + 1, s + ')');
        }
    }
}

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> queue = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        });
        ListNode result = new ListNode(0);
        ListNode tmp = result;
        for (ListNode l : lists) {
            tmp = l;
            if (tmp != null) {
                queue.add(tmp);
            }
        }
        ListNode iter = result;
        while (!queue.isEmpty()) {
            tmp = queue.poll();
            iter.next = tmp;
            iter = iter.next;
            if (iter.next != null) {
                queue.add(iter.next);
            }
        }
        return result.next;
    }
}

//递归
class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode origin = head.next;
        head.next = swapPairs(head.next.next);
        origin.next = head;
        return origin;
    }
}
//接头
public ListNode swapPairs(ListNode head) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode point = dummy;
    while (point.next != null && point.next.next != null) { 
        ListNode swap1 = point.next;
        ListNode swap2 = point.next.next;
        point.next = swap2;
        swap1.next = swap2.next;
        swap2.next = swap1;
        point = swap1;
    }
    return dummy.next;
}

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null || k <= 1) {
            return head;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pointer = dummy;
        while (pointer != null) {
            // 记录上一个子链表的尾
            ListNode lastGroup = pointer;
            int i = 0;
            for (; i < k; ++i) {
                pointer = pointer.next;
                if (pointer == null) {
                    break;
                }
            }
            // 如果当前子链表的节点数满足 k, 就进行反转
            // 反之，说明程序到尾了，节点数不够，不用反转
            if (i == k) {
                // 记录下一个子链表的头
                ListNode nextGroup = pointer.next;
                // 反转当前子链表，reverse 函数返回反转后子链表的头
                ListNode reversedList = reverse(lastGroup.next, nextGroup);
                // lastGroup 是上一个子链表的尾，其 next 指向当前反转子链表的头
                // 但是因为当前链表已经被反转，所以它指向的是反转后的链表的尾
                pointer = lastGroup.next;
                // 将上一个链表的尾连向反转后链表的头
                lastGroup.next = reversedList;
                // 当前反转后的链表的尾连向下一个子链表的头
                pointer.next = nextGroup;
            }
        }
        return dummy.next;
    }
    private ListNode reverse(ListNode head, ListNode tail) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode prev = null, temp = null;
        while ((head != null) && (head != tail)) {
            temp = head.next;
            head.next = prev;
            prev = head;
            head = temp;
        }
        return prev;
    }
}

class Solution {
    public int strStr(String haystack, String needle) {
        if (needle.equals("")) return 0;
        if (haystack.equals("") || haystack.length() < needle.length()) return -1;
        int index = 0;
        for (int i = 0; i < haystack.length(); i++) {
            int ni = 0;
            int hi = i;
            while (ni < needle.length()&&hi < haystack.length()) {
                if (haystack.charAt(hi) == needle.charAt(ni)) {
                    if (ni == needle.length() - 1) {
                        return i;
                    }
                    ni++;
                    hi++;
                } else {
                    break;
                }
            }
        }
        return -1;
    }
}

//1
public List<Integer> findSubstring(String s, String[] words) {
    List<Integer> res = new ArrayList<Integer>();
    int wordNum = words.length;
    if (wordNum == 0) {
        return res;
    }
    int wordLen = words[0].length();
    //HashMap1 存所有单词
    HashMap<String, Integer> allWords = new HashMap<String, Integer>();
    for (String w : words) {
        int value = allWords.getOrDefault(w, 0);
        allWords.put(w, value + 1);
    }
    //遍历所有子串
    for (int i = 0; i < s.length() - wordNum * wordLen + 1; i++) {
        //HashMap2 存当前扫描的字符串含有的单词
        HashMap<String, Integer> hasWords = new HashMap<String, Integer>();
        int num = 0;
        //判断该子串是否符合
        while (num < wordNum) {
            String word = s.substring(i + num * wordLen, i + (num + 1) * wordLen);
            //判断该单词在 HashMap1 中
            if (allWords.containsKey(word)) {
                int value = hasWords.getOrDefault(word, 0);
                hasWords.put(word, value + 1);
                //判断当前单词的 value 和 HashMap1 中该单词的 value
                if (hasWords.get(word) > allWords.get(word)) {
                    break;
                }
            } else {
                break;
            }
            num++;
        }
        //判断是不是所有的单词都符合条件
        if (num == wordNum) {
            res.add(i);
        }
    }
    return res;
}
//2
class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<Integer>();
        int wordNum = words.length;
        if (wordNum == 0) {
            return res;
        }
        int wordLen = words[0].length();
        HashMap<String, Integer> allWords = new HashMap<String, Integer>();
        for (String w : words) {
            int value = allWords.getOrDefault(w, 0);
            allWords.put(w, value + 1);
        }
        // 将所有移动分成 wordLen 类情况
        for (int j = 0; j < wordLen; j++) {
            HashMap<String, Integer> hasWords = new HashMap<String, Integer>();
            int num = 0; // 记录当前 HashMap2（这里的 hasWords 变量）中有多少个单词
            // 每次移动一个单词长度
            for (int i = j; i < s.length() - wordNum * wordLen + 1; i = i + wordLen) {
                boolean hasRemoved = false; // 防止情况三移除后，情况一继续移除
                while (num < wordNum) {
                    String word = s.substring(i + num * wordLen, i + (num + 1) * wordLen);
                    if (allWords.containsKey(word)) {
                        int value = hasWords.getOrDefault(word, 0);
                        hasWords.put(word, value + 1);
                        // 出现情况三，遇到了符合的单词，但是次数超了
                        if (hasWords.get(word) > allWords.get(word)) {
                            // hasWords.put(word, value);
                            hasRemoved = true;
                            int removeNum = 0;
                            // 一直移除单词，直到次数符合了
                            while (hasWords.get(word) > allWords.get(word)) {
                                String firstWord = s.substring(i + removeNum * wordLen, i + (removeNum + 1) * wordLen);
                                int v = hasWords.get(firstWord);
                                hasWords.put(firstWord, v - 1);
                                removeNum++;
                            }
                            num = num - removeNum + 1; // 加 1 是因为我们把当前单词加入到了 HashMap 2 中
                            i = i + (removeNum - 1) * wordLen; // 这里依旧是考虑到了最外层的 for 循环，看情况二的解释
                            break;
                        }
                        // 出现情况二，遇到了不匹配的单词，直接将 i 移动到该单词的后边（但其实这里
                        // 只是移动到了出现问题单词的地方，因为最外层有 for 循环， i 还会移动一个单词
                        // 然后刚好就移动到了单词后边）
                    } else {
                        hasWords.clear();
                        i = i + num * wordLen;
                        num = 0;
                        break;
                    }
                    num++;
                }
                if (num == wordNum) {
                    res.add(i);

                }
                // 出现情况一，子串完全匹配，我们将上一个子串的第一个单词从 HashMap2 中移除
                if (num > 0 && !hasRemoved) {
                    String firstWord = s.substring(i, i + wordLen);
                    int v = hasWords.get(firstWord);
                    hasWords.put(firstWord, v - 1);
                    num = num - 1;
                }

            }

        }
        return res;
    }
}

class Solution {
    public void nextPermutation(int[] nums) {
        // 先从后往前找到第一次出现升序的两个数，i指向前一个数
        int n = nums.length;
        int i = n - 2;
        while (i >= 0 && nums[i] >= nums[i + 1])
            i--;
        // 然后从后向前找到第一个大于nums[i]的数
        if (i >= 0) {
            int j = nums.length - 1;
            while (nums[j] <= nums[i])
                j--;
            // 交换2个下标对应的元素
            swap(nums, i, j);
        }
        // 逆置i之后的所有元素
        reverse(nums, i + 1);
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public void reverse(int[] nums, int start) {
        int i = start;
        int j = nums.length - 1;
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }
}

import java.util.Stack;
class Solution {
    public static int longestValidParentheses(String s) {
        int res = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (!stack.isEmpty()) {
                if (s.charAt(stack.peek()) == '(' && s.charAt(i) == ')') {
                    stack.pop();
                } else {
                    stack.push(i);
                }
            } else {
                stack.push(i);
            }
            if (!stack.isEmpty()) {
                res = Math.max(res, i - stack.peek());
            } else {
                res = Math.max(res, i + 1);
            }
        }
        return res;
    }
}

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

class Solution {
    public void solveSudoku(char[][] board) {
        solver(board);
    }

    private boolean solver(char[][] board) {
        for (int i = 0; i < 9; i++)
            for (int j = 0; j < 9; j++)
                if (board[i][j] == '.') {
                    char count = '1';
                    while (count <= '9') {
                        if (isValid(i, j, board, count)) {
                            board[i][j] = count;
                            if (solver(board))
                                return true;
                            else
                                board[i][j] = '.';
                        }
                        count++;
                    }
                    return false;
                }
        return true;
    }

    private boolean isValid(int row, int col, char[][] board, char c) {
        for (int i = 0; i < 9; i++)
            if (board[row][i] == c)
                return false;
        for (int i = 0; i < 9; i++)
            if (board[i][col] == c)
                return false;
        int start_row = row / 3 * 3;
        int start_col = col / 3 * 3;
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                if (board[start_row + i][start_col + j] == c)
                    return false;
        return true;
    }
}

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> list = new ArrayList<>();
        backtrack(list, new ArrayList<>(), candidates, target, 0);
        return list;
    }

    private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums, int remain, int start) {
        if (remain < 0)
            return;
        else if (remain == 0)
            list.add(new ArrayList<>(tempList));
        else {
            for (int i = start; i < nums.length; i++) {
                tempList.add(nums[i]);
                backtrack(list, tempList, nums, remain - nums[i], i);
                tempList.remove(tempList.size() - 1);
            }
        }
    }
}

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(candidates);
        backtrack(list, new ArrayList<>(), candidates, target, 0);
        return list;
    }

    private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums, int remain, int start) {
        if (remain < 0)
            return;
        else if (remain == 0) {
            list.add(new ArrayList<>(tempList));
        } else {
            for (int i = start; i < nums.length; i++) {
                // 避免多余计算，剪枝
                if (i > start && nums[i] == nums[i - 1])
                    continue;
                tempList.add(nums[i]);
                // 每个数只能用一次，从自己的下一个计算
                backtrack(list, tempList, nums, remain - nums[i], i + 1);
                tempList.remove(tempList.size() - 1);
            }
        }
    }
}

class Solution {
    public int firstMissingPositive(int[] nums) {
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            while (nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] != nums[i]) {
                swap(nums, i, nums[i] - 1);
            }
        }
        for (int i = 0; i < len; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return len + 1;
    }
    public void swap(int[] nums, int left, int right) {
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
    }
}

class Solution {
    public int trap(int[] height) {
        if (height == null || height.length <= 2) return 0;
        int len = height.length, temp = 0, res = 0;
        int[] left = new int[len];
        int[] right = new int[len];
        for (int i = 0; i < len; i++) {
            temp = Math.max(temp, height[i]);
            left[i] = temp;
        }
        temp = 0;
        for (int i = len - 1; i >= 0; i--) {
            temp = Math.max(temp, height[i]);
            right[i] = temp;
        }
        for (int i = 0; i < len; i++) {
            res += Math.min(left[i], right[i]) - height[i];
        }
        return res;
    }
}

class Solution {
    public String multiply(String num1, String num2) {
        // 特殊情况的处理
        if (num1.equals("0") || num2.equals("0")) return "0";
        if (num1.equals("1") || num2.equals("1")) return num1.equals("1") ? num2 : num1;
        // 逐个和字符相乘 然后后面追加0相加
        String resu = "0";
        for (int i = num2.length() - 1; i >= 0; i--) {
            String ts = mul(num1, num2.charAt(i));
            for (int j = num2.length() - 1; j > i; j--) {
                ts += "0";
            }
            System.out.println(ts);
            resu = add(ts, resu);
        }
        return resu;
    }
    // 两个数相乘得到得字符串
    public String mul(String num1, char c) {
        // 从0开始算，算出来的数
        String resu = "";
        int flag = 0;
        for (int i = num1.length() - 1; i >= 0; i--) {
            int tmp = (num1.charAt(i) - '0') * (c - '0') + flag;
            flag = tmp / 10;
            tmp %= 10;
            resu = tmp + resu;
        }
        if (flag != 0) resu = flag + resu;
        return resu;
    }
    // 两个字符串相加
    public String add(String num1, String num2) {
        String resu = "";
        int flag = 0;
        int i = num1.length() - 1;
        int j = num2.length() - 1;
        while (i >= 0 && j >= 0) {
            int tmp = num1.charAt(i) - '0' + num2.charAt(j) - '0' + flag;
            flag = tmp / 10;
            tmp %= 10;
            resu = tmp + resu;
            i--;
            j--;
        }
        while (i >= 0) {
            int tmp = num1.charAt(i) - '0' + flag;
            flag = tmp / 10;
            tmp %= 10;
            resu = tmp + resu;
            i--;
        }
        while (j >= 0) {
            int tmp = num2.charAt(j) - '0' + flag;
            flag = tmp / 10;
            tmp %= 10;
            resu = tmp + resu;
            j--;
        }
        if (flag == 1) resu = '1' + resu;
        return resu;
    }
}

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int j = 1; j <= n; j++) {
            dp[0][j] = dp[0][j - 1] && p.charAt(j - 1) == '*';
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p.charAt(j - 1) == '?') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = (dp[i - 1][j - 1] && s.charAt(i - 1) == p.charAt(j - 1)) // 完全匹配了
                            || (dp[i - 1][j] && p.charAt(j - 1) == '*') // * 匹配了0个字符
                            || (dp[i][j - 1] && p.charAt(j - 1) == '*');// * 匹配了s的第i个字符
                }
            }
        }
        return dp[m][n];
    }
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> resu = new ArrayList<>();
        backtrack(nums, 0, resu);
        return resu;
    }

    public void backtrack(int[] nums, int start, List<List<Integer>> resu) {
        if (start >= nums.length) {
            // 因为asList只能接受包装类型，因此需要自动装箱至 Integer
            List<Integer> list = Arrays.stream(nums).boxed().collect(Collectors.toList());
            resu.add(list);
        }
        // 把当前元素和后面每个元素交换，并在此基础上继续交换
        for (int i = start; i < nums.length; i++) {
            swap(nums, start, i);
            backtrack(nums, start + 1, resu);
            swap(nums, start, i);
        }
    }

    public void swap(int[] nums, int left, int right) {
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
    }
}

import java.util.*;
import java.util.stream.Collectors;

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        Set<List<Integer>> resu = new HashSet<>();
        backtrack(nums, 0, resu);
        return new ArrayList<>(resu);
    }

    public void backtrack(int[] nums, int start, Set<List<Integer>> resu) {
        if (start >= nums.length) {
            List<Integer> list = Arrays.stream(nums).boxed().collect(Collectors.toList());
            resu.add(list);
        }
        for (int i = start; i < nums.length; i++) {
            if (i != start && nums[i] == nums[start]) continue;
            swap(nums, start, i);
            backtrack(nums, start + 1, resu);
            swap(nums, start, i);
        }
    }

    public void swap(int[] nums, int left, int right) {
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
    }
}

class Solution {
    public int maxSubArray(int[] nums) {
        int max = nums[0];
        int sum = 0;
        for (int num: nums){
            sum += num;
            max = Math.max(max, sum);
            sum = sum <= 0? 0: sum;
        }
        return max;
    }
}

import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public int[][] merge(int[][] intervals) {
        // 对二维数组首元素按照升序排列
        Comparator<int[]> comparator = new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] == o2[0]) {
                    return o1[1] - o2[1];
                } else {
                    return o1[0] - o2[0];
                }
            }
        };
        Arrays.sort(intervals, comparator);
        // 创建结果数组
        int[][] resu = new int[intervals.length][2];
        // 结果集的索引
        int idx = -1;
        for (int[] interval : intervals) {
            // 如果结果集为空，新键一个区间，或者当前区间的元素比结果集中最后一个区间的末尾大，说明非重叠区间
            if (idx == -1 || interval[0] > resu[idx][1]) {
                resu[++idx] = interval;
            } else if (interval[0] <= resu[idx][1]) {
                // 重叠了，选择最大的元素作为区间末尾
                resu[idx][1] = Math.max(resu[idx][1], interval[1]);
            }
        }
        return Arrays.copyOf(resu, idx + 1);
    }
}

class Solution {
    public int uniquePaths(int m, int n) {
        if (m == 1 || n==1) return 1;
        int[][] dp = new int[n+1][m+1];
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= m; j++){
                if (i == 1 || j == 1) dp[i][j] = 1;
                else {
                    dp[i][j] = dp[i][j-1] + dp[i-1][j];
                }
            }
        }
        return dp[n][m];
    }
}

class Solution {
    public int uniquePathsWithObstacles(int[][] o) {
        int m = o.length, n = o[0].length;
        if (m == 0 || n == 0) return 1;
        int[][] dp = new int[m+1][n+1];
        dp[0][1] = dp[1][0] = 1;
        for (int i = 1; i <= m; i++){
            for (int j = 1; j <= n; j++){
                if (i == 1){
                    dp[i][j] = o[i-1][j-1] == 0 ? dp[i][j-1]: 0;
                } else if (j == 1){
                    dp[i][j] = o[i-1][j-1] == 0 ? dp[i-1][j]: 0;
                } else {
                    dp[i][j] = o[i-1][j-1] == 1 ? 0: (dp[i-1][j] + dp[i][j-1]);
                }
            }
        }
        return dp[m][n];
    }
}

class Solution {
    public int minPathSum(int[][] grid) {
        for (int i = grid.length - 1; i >= 0; i--) {
            for (int j = grid[i].length - 1; j >= 0; j--) {
                if (i == grid.length - 1 && j == grid[i].length - 1) {
					// 啥也不做
                } else if (i == grid.length - 1) {
                    grid[i][j] +=grid[i][j + 1];
                } else if (j == grid[i].length - 1) {
                    grid[i][j] += grid[i + 1][j];
                } else {
                    grid[i][j] += Math.min(grid[i + 1][j], grid[i][j + 1]);
                }
            }
        }
        return grid[0][0];
    }
}

class Solution {
    public int mySqrt(int x) {
        if (x <= 1) return x;
        int left = 1, right = x, sqrt = 0;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            sqrt = x / mid;
            if (sqrt == mid){
                return mid;
            } else if (sqrt < mid) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return right;
    }
}