class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode prev = null, slow = head, fast = head;
        while (fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        prev.next = null;
        return merge(sortList(head), sortList(slow));
    }

    public ListNode merge(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(0), ptr = dummy;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                ptr.next = list1;
                list1 = list1.next;
            } else {
                ptr.next = list2;
                list2 = list2.next;
            }
            ptr = ptr.next;
        }
        if (list1 != null) {
            ptr.next = list1;
        } else {
            ptr.next = list2;
        }
        return dummy.next;
    }
}

class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode left = head, right = reverseList(slow), dummy = new ListNode(0), ptr = dummy;
        while (left != right && right != null) {
            ptr.next = left;
            left = left.next;
            ptr = ptr.next;
            ptr.next = right;
            right = right.next;
            ptr = ptr.next;
        }
        if (left == right) {
            ptr.next = left;
        }
    }

    private ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode prev = null, curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

class Solution {
    public List<List<String>> partition(String s) {
        if (s == null || s.length() == 0) {
            return new ArrayList<>();
        }
        List<List<String>> ans = new ArrayList<>();
        helper(ans, new ArrayList<>(), 0, s);
        return ans;
    }

    private void helper(List<List<String>> ans, List<String> currAns, int pos, String s) {
        if (pos == s.length()) {
            ans.add(new ArrayList<>(currAns));
            return;
        }
        for (int i = pos; i < s.length(); i++) {
            if (isPalindrome(pos, i, s)) {
                currAns.add(s.substring(pos, i + 1));
                helper(ans, currAns, i + 1, s);
                currAns.remove(currAns.size() - 1);
            }
        }
    }

    private boolean isPalindrome(int left, int right, String s) {
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left += 1;
            right -= 1;
        }
        return true;

class Solution {
    private class Data {
        int lastSoldPrice;
        int lastBuyPrice;
        int total;

        Data(int lastSoldPrice, int lastBuyPrice, int total) {
            this.lastSoldPrice = lastSoldPrice;
            this.lastBuyPrice = lastBuyPrice;
            this.total = total;
        }
    }

    public int maxProfit(int[] prices) {
        Data[] dp = new Data[prices.length];
        dp[0] = new Data(prices[0], prices[0], 0);
        for (int i = 1; i < dp.length; i++) {
            if (prices[i] >= dp[i - 1].lastSoldPrice) {
                int currTotal = dp[i - 1].total + prices[i] - dp[i - 1].lastSoldPrice;
                dp[i] = new Data(prices[i], dp[i - 1].lastBuyPrice, currTotal);
            } else {
                dp[i] = new Data(prices[i], prices[i], dp[i - 1].total);
            }
        }
        return dp[dp.length - 1].total;
    }
}

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null)
            return false;
        return helper(root, 0, targetSum);
    }

    private boolean helper(TreeNode node, int sum, int targetSum) {
        sum += node.val;
        if (node.left == null && node.right == null && sum == targetSum)
            return true;
        if (node.left != null && helper(node.left, sum, targetSum))
            return true;
        if (node.right != null)
            return helper(node.right, sum, targetSum);
        return false;
    }
}

// From right to left, pop last, add to first
// From left to right, pop first, add to last
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if (root == null)
            return new ArrayList<>();
        boolean fromLeft = true;
        Deque<TreeNode> q = new LinkedList<>();
        q.offer(root);
        List<List<Integer>> ans = new ArrayList<>();
        while (!q.isEmpty()) {
            int currLength = q.size();
            List<Integer> currLevel = new ArrayList<>();
            for (int i = 0; i < currLength; i++) {
                TreeNode currNode = fromLeft ? q.removeFirst() : q.removeLast();
                currLevel.add(currNode.val);
                if (fromLeft) {
                    if (currNode.left != null) {
                        q.addLast(currNode.left);
                    }
                    if (currNode.right != null) {
                        q.addLast(currNode.right);
                    }
                } else {
                    if (currNode.right != null) {
                        q.addFirst(currNode.right);
                    }
                    if (currNode.left != null) {
                        q.addFirst(currNode.left);
                    }
                }
            }
            ans.add(currLevel);
            fromLeft = !fromLeft;
        }
        return ans;
    }
}

class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            int ans = 0;
            for (int j = 1; j <= i; j++) {
                int leftNodesCount = j - 1;
                int rightNodesCount = i - j;
                ans += dp[leftNodesCount] * dp[rightNodesCount];
            }
            dp[i] = ans;
        }
        return dp[n];
    }
}

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int row = 0;
        while (row < matrix.length && target > matrix[row][matrix[0].length - 1]) {
            row += 1;
        }
        if (row == matrix.length)
            return false;
        int left = 0, right = matrix[row].length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (matrix[row][mid] == target) {
                return true;
            } else if (matrix[row][mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
}

class Solution {
    public void setZeroes(int[][] matrix) {
        // 有个问题就是(0, 0)这个元素既记录第0行是否有0, 也记录第0列是否有0, 这样会冲突, 于是
        // 我们单独用一个变量记录第0列是否有0, 那么(0, 0)记录的就是第0行是否有0.
        boolean isColZero = false;
        for (int i = 0; i < matrix.length; i++) {
            // 每一行第0个元素和剩下的元素遇到是0的情况处理的方式不同, 因此单独拎出来处理.
            if (matrix[i][0] == 0)
                isColZero = true;
            for (int j = 1; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        // 为什么要倒着遍历? 如果从头开始, 假设第0行之前在标记前出现了0, 那么(0, 0)就会标记为0.
        // 我们往后遍历的时候会发现(0, 0)是0, 表明这一行出现了0, 那么应该第0行全部设置为0, 但是这一行
        // 还记录了其他位置是否有0的情况(也就是第0行有的位置是0, 有的不是0). 从头开始会让第0行记录的信息被覆盖
        // 如果都被设置为0, 那么其他位置看该列情况的时候会发现是0, 但有可能之前这一列并没有0出现.
        // 类似地, 如果第0列
        // 在记录前就有0出现, 那么我们在遍历到每行第0个位置的时候, 会发现isColZero是0, 那么就会把
        // 这个该行第0个位置标记为0, 然而这个位置还记录着当前行是否有0出现, 这样一标记就会让该行其他元素认为
        // 这一行有0出现, 然而实际是可能会有, 可能会没有. 但当我们倒着遍历, 在每一行遍历完后, 第0个元素
        // 的值才会被改变(根据isColZero的值). 这样在每行第0个元素的信息被覆盖前, 该行其他的元素都设置好了.

        for (int i = matrix.length - 1; i >= 0; i--) {
            for (int j = matrix[0].length - 1; j > 0; j--) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
            if (isColZero) {
                matrix[i][0] = 0;
            }
        }
    }
}

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