剑指 Offer

class Solution {
    public int findRepeatNumber(int[] nums) {
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            int index = nums[i] % len;
            if (nums[index] >= len) return index;
            nums[index] += len;
        }
        return -1;
    }
}

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        int row = matrix.length;
        if (row == 0) return false;
        int col = matrix[0].length;
        for (int i = 0, j = col - 1; i < row && j >= 0;) {
            if (matrix[i][j] == target) {
                return true;
            } else if (matrix[i][j] < target) {
                i++;
            } else {
                j--;
            }
        }
        return false;
    }
}

class Solution {
    public String replaceSpace(String s) {
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == ' ') {
                result.append("%20");
            } else result.append(ch);
        }
        return result.toString();
        // return s.replace(" ", "%20"); // 库函数
    }
}

class CQueue {

    private Stack<Integer> stack1;
    private Stack<Integer> stack2;

    public CQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }
    
    public void appendTail(int value) {
        stack1.push(value);
    }
    
    public int deleteHead() {
        if (!stack2.empty()) return stack2.pop();
        while (!stack1.empty()) {
            stack2.push(stack1.pop());
        }
        if (!stack2.empty()) return stack2.pop();
        return -1;
    }
}

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */

class Solution {
    public int minArray(int[] numbers) {
        int left = 0, right = numbers.length - 1;
        while (left < right) { // 查找旋转数组分界点右边的第一个元素：即为最小元素（**分界点两边的子数组都为升序**，并且左子数组中的值大于等于右子数组中的值）
            int mid = left + (right - left) / 2;
            if (numbers[mid] > numbers[right]) { // 右半部分无序：分界点存在于右半部分
                left = mid + 1; // 中轴值 numbers[mid] 大于最右端元素，故其一定不为最小元素，查找范围的左边界由 mid 加一（舍去 mid）
            } else if (numbers[mid] < numbers[right]) { // 右半部分有序：分界点存在于左半部分
                right = mid; // 中轴值 numbers[mid] 小于最右端元素，其可能为最小元素，故查找范围的右边界应包含 mid，eg：88567
            } else if (numbers[left] > numbers[mid]) { // numbers[mid] == numbers[right] 的情况，无法判断右半部分是否有序，当前半部分无序时（则右半部分一定有序也即有半部分的值全都相等）：分界点存在于左半部分
                right = mid;
            } else { // numbers[mid] == numbers[right] == numbers[right] 的情况：无法判断分界点存在于哪半部分（即无法判断哪半部分无序）
                right--;
            }
        } // 退出循环后 left == right
        return numbers[left];
    }
}

class Solution {

    int m; // 成员变量
    int n;
    int k;
    boolean[][] isVisited; // 记录当前单元格是否被访问的二维数组

    public int movingCount(int m, int n, int k) {
        this.m = m; // 初始化
        this.n = n;
        this.k = k;
        this.isVisited = new boolean[m][n];
        return dfs(0, 0, 0, 0);
    }

    private int dfs(int i, int j, int si, int sj) { // i 和 j 为当前递归层级访问单元格的索引，si 和 sj 为索引 i 和 j 的数位和
        if (i >= m || j >= n || si + sj > k || isVisited[i][j]) return 0; // 当前访问单元格越界或者数位和大于k或者已被访问则返回0：递归边界条件
        isVisited[i][j] = true; // 标记当前单元格为已访问
        return 1 + dfs(i + 1, j, (i + 1) % 10 == 0 ? si - 8 : si + 1, sj) + dfs(i, j + 1, si, (j + 1) % 10 == 0 ? sj - 8 : sj + 1); // 下右的顺序递归深度搜索下一单元格，返回 1 + 下方搜索的可达解总数 + 右方搜索的可达解总数
    }
}

class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int result = 0;
        while (n != 0) {
            n &= n - 1;
            result++;
        }
        return result;
    }
}

/*class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int result = 0;
        int con = 1;
        for (int i = 0; i < 32; i++) {
            if ((n & con) != 0) result++; // != 的优先级高于 &
            con <<= 1;
        }
        return result;
        // return Integer.bitCount(n); // 库函数
    }
}*/

// 迭代+数学
class Solution {
    public double myPow(double x, int n) {
        double result = 1; // 结果的初始值
        if (n < 0) {
            x = 1 / x;
            if (n == -2147483648) {
                n++; // int范围为-2^31~2^31-1，-2^31转为正数会越界，将幂n减一
                result = x; // 幂n减一后结果的初始值应为x
            }
            n = -n;
        }
        while (n != 0) {
            if (n % 2 == 1) result *= x;
            x *= x; // 对下一位有效 x^(2^i)
            n >>= 1;
        }
        return result;
    }
}

// 递归
/*class Solution {
    public double myPow(double x, int n) {
        if (n == 0) { // 放在第一个判断，防止死循环（对2取模总为0）
            return 1;
        } else if (n % 2 == 0) {
            return myPow(x * x, n / 2);
        } else if (n % 2 == 1) {
            return x * myPow(x, n - 1);
        } else { // n < 0 将其转为正数
            x = 1 / x;
            return x * myPow(x, - n - 1); // int范围为-2^31~2^31-1，-2^31转为正数会越界，将幂n减一且结果乘以x
        }
    }
}*/

class Solution {
    public boolean isNumber(String s) {
        int len = s.length();
        int index = 0;
        boolean hasNum = false;
        boolean hasSign = false;
        boolean hasE = false;
        boolean hasDot = false;
        while (index < len && s.charAt(index) == ' ') index++;
        while (index < len) {
            while (index < len && s.charAt(index) >= '0' && s.charAt(index) <= '9') {
                index++;
                hasNum = true;
            }
            if (index == len) break; // 此处不能少了这个判断，否则在前一步判断数字时index已经到达len，继续判断后面非数字的情形会产生越界
            char ch = s.charAt(index);
            if (ch == 'e' || ch == 'E') {
                if (hasE || !hasNum) return false;
                hasE = true;
                hasNum = false;
                hasSign = false;
                hasDot = false;
            } else if (ch == '+' || ch == '-') {
                if (hasNum || hasDot || hasSign) return false;
                hasSign = true;
            } else if (ch == '.') {
                if (hasE || hasDot) return false;
                hasDot = true;
            } else if (ch == ' ') {
                break;
            } else return false;
            index++; // 继续判断下一位
        }
        while (index < len && s.charAt(index) == ' ') index++;
        return index == len && hasNum; // 不使用 if (index == len && hasNum) return true else return false 的形式
    }
}

// 快慢指针
class Solution {
    public int[] exchange(int[] nums) {
        int left = 0, right = 0;
        while (right < nums.length) {
            if (nums[right] % 2 == 1) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                left++;
            }
            right++;
        }
        return nums;
    }
}

// 对撞指针
/*class Solution {
    public int[] exchange(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            while (left < right && nums[left] % 2 == 1) left++;
            while (left < right && nums[right] % 2 == 0) right--;
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
        return nums;
    }
}*/

class Solution {
    public int[] spiralOrder(int[][] matrix) {
        if (matrix.length == 0) return new int[0];
        int l = 0, r = matrix[0].length - 1, t = 0, b = matrix.length - 1; // 矩阵matrix的左右上下边界索引
        int[] result = new int[(r + 1) * (b + 1)]; // 结果数组
        int index = 0; // 结果数组的索引
        while (true) {
            for (int i = l; i <= r; i++) result[index++] = matrix[t][i];
            if (++t > b) break;
            for (int i = t; i <= b; i++) result[index++] = matrix[i][r];
            if (l > --r) break;
            for (int i = r; i >= l; i--) result[index++] = matrix[b][i];
            if (t > --b) break;
            for (int i = b; i >= t; i--) result[index++] = matrix[i][l];
            if (++l > r) break;
        }
        return result;
    }
}

class MinStack {

    Node head;

    /** initialize your data structure here. */
    public MinStack() {

    }
    
    public void push(int x) {
        if (head == null) {
            head = new Node(x, x);
        } else head = new Node(x, Math.min(x, head.minVal), head);
    }
    
    public void pop() {
        head = head.next;
    }
    
    public int top() {
        return head.val;
    }
    
    public int min() {
        return head.minVal;
    }
}

class Node {
    int val;
    int minVal;
    Node next;
    public Node(int val, int minVal) {
        this(val, minVal, null);
    }
    public Node(int val, int minVal, Node next) {
        this.val = val;
        this.minVal = minVal;
        this.next = next;
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.min();
 */

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int index = 0; // 栈中下一个该弹出的元素在 popped 数组（栈的弹出顺序）中的索引
        for (int ele : pushed) {
            stack.push(ele);
            while (!stack.empty() && stack.peek() == popped[index]) {
                stack.pop();
                index++;
            }
        }
        return stack.empty();
    }
}

class Solution {
    public int majorityElement(int[] nums) {
        int vote = 1;
        int result = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (result == nums[i]) {
                vote++;
            } else if (--vote == 0) {
                result = nums[i];
                vote = 1;
            }
        }
        return result;
    }
}

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0) return new int[0];
        int index = k - 1; // 第k小元素的索引
        randomPartition(arr, 0, arr.length - 1, index);
        return Arrays.copyOf(arr, k); // 最终结果即为改进快速排序后数组的前k个元素
    }

    // 用于判别继续向左半部分还是右半部分划分（迭代），pivot中轴值在下一迭代部分中随机选取
    private int randomPartition(int[] arr, int left, int right, int index) {
        int pivotIndex = new Random().nextInt(right - left + 1) + left;
        swap(arr, pivotIndex, right); // 将pivot中值交换到数组末尾
        int result = partition(arr, left, right);
        if (result == index) return arr[result];
        return result < index ? randomPartition(arr, result + 1, right, index) : randomPartition(arr, left, result - 1, index);
    }

    // 划分的方法
    private int partition(int[] arr, int left, int right) {
        int pivot = arr[right]; // 中轴值（位于数组末尾）
        int i = left - 1; // [left, ..., i]的元素都小于pivot，[i + 1, ..., right]的元素都大于等于pivot
        for (int j = left; j < right; j++) {
            if (arr[j] < pivot) {
                swap(arr, ++i, j);
            }
        }
        swap(arr, i + 1, right); // 将中轴值归于正确的位置
        return i + 1; // 中轴值的索引
    }

    // 数组中索引i及索引j处的元素对调位置
    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

class MedianFinder {

    Queue<Integer> minHeap; // 小顶堆，用于存储数据流中的较大半部分，优先队列的头元素即为数据流的中间元素
    Queue<Integer> maxHeap; // 大顶堆，用于存储数据流中的较小半部分，优先队列的头元素即为数据流的中间元素

    /** initialize your data structure here. */
    public MedianFinder() {
        this.minHeap = new PriorityQueue<>();
        this.maxHeap = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) { // 这里重写的方法为int compare(T o1, T o2) 比较用来排序的两个参数。参数应为范型 Integer 而不是 int
                return o2 - o1; // 降序
            }
        });
    }
    
    public void addNum(int num) {
        if (minHeap.size() == maxHeap.size()) { // 需要将新元素插入正确位置，且大顶堆元素数 + 1
            minHeap.add(num);
            maxHeap.add(minHeap.poll());
        } else { // 需要将新元素插入正确位置，且小顶堆元素数 + 1
            maxHeap.add(num);
            minHeap.add(maxHeap.poll());
        }
    }
    
    public double findMedian() {
        return minHeap.size() ==  maxHeap.size() ? (maxHeap.peek() + minHeap.peek()) * 0.5 : maxHeap.peek();
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

class Solution {
    public int countDigitOne(int n) {
        int result = 0;
        int high = n / 10, cur = n % 10, low = 0, digit = 1; // 高位、当前位、低位、位因子（10^i，从个位i=0开始）参数变量的初始化
        while (high != 0 || cur != 0) { // 高位和当前位都为0代表每位都遍历结束则退出循环
            if (cur == 0) {
                result += high * digit;
            } else if (cur == 1) {
                result += (high * digit + low + 1);
            } else result += (high + 1) * digit; // cur > 1 (2 ~ 9)
            // 更新下一轮的高位、当前位、低位、位因子参数变量（从个位到最高位的递推公式如下）
            low += cur * digit;
            cur = high % 10;
            high /= 10;
            digit *= 10;
        }
        return result;
    }
}

class Solution {
    public int findNthDigit(int n) {
        if (n < 10) return n; // 当 n 为 0~9 时直接返回 n 的值
        n++;
        int digit = 1; // 位数的初始值，1位
        long start = 1; // 1 位数的起始数字
        long count = 10; // 1 位数的数字总数量，0~9
        while (n > count) {
            n -= count;
            digit++;
            start *= 10;
            count = 9 * start * digit;
        }
        long num = start + (n - 1) / digit;
        return Long.toString(num).charAt((n - 1) % digit) - '0';
    }
}

class Solution {
    public String minNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for (int i = 0; i < nums.length; i++) strs[i] = String.valueOf(nums[i]); 
        Arrays.sort(strs, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return (o1 + o2).compareTo(o2 + o1);
            }
        });
        StringBuilder result = new StringBuilder();
        for (String str : strs) result.append(str);
        return result.toString();
    }
}

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] charFreq = new int[128]; // 存储ASCII为数组索引值的字符在子串（滑动窗口）中出现的频率
        int left = 0, right = -1; // nums[left, right]为滑动窗口
        int maxLen = 0;
        while (left < s.length()) {
            if (right + 1 < s.length() && charFreq[s.charAt(right + 1)] == 0) {
                charFreq[s.charAt(++right)]++;
            } else {
                charFreq[s.charAt(left++)]--;
            }
            maxLen = Math.max(maxLen, right - left + 1); // 当前子串（滑动窗口）一定不含有重复字符
        }
        return maxLen;
    }
}

class Solution {
    public char firstUniqChar(String s) {
        Map<Character, Boolean> map = new LinkedHashMap<>();
        for (int i = 0; i < s.length(); i++) map.put(s.charAt(i), !map.containsKey(s.charAt(i)));
        for (Map.Entry<Character, Boolean> entry : map.entrySet()) {
            if (entry.getValue()) return entry.getKey();
        }
        return ' ';
    }
}

class Solution {

    private int result;

    public int reversePairs(int[] nums) {
        result = 0;
        int[] tempArray = new int[nums.length];
        mergeSort(nums, 0, nums.length - 1, tempArray);
        return result;
    }

    // 分：递归拆分子序列 & 最后从栈顶开始治（将两个已经有序的子序列合并成一个有序序列）
    private void mergeSort(int[] nums, int left, int right, int[] tempArray) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSort(nums, left, mid, tempArray); // 向左递归进行拆分
            mergeSort(nums, mid + 1, right, tempArray); // 向右递归进行拆分
            merge(nums, left, mid, right, tempArray); // 治：将两个已经有序的子序列合并成一个有序序列
        }
    }

    /**
     * 治：将两个已经有序的子序列合并成一个有序序列
     * @param array 排序的原始数组
     * @param left  左边有序序列的初始索引（最左端索引）
     * @param mid   中间索引
     * @param right 右边有序序列的最右端索引
     * @param tempArray  用于中转的数组
     */
    private void merge(int[] nums, int left, int mid, int right, int[] tempArray) {
        int i = left; // 左边有序序列的初始索引（最左端索引）
        int j = mid + 1; // 右边有序序列的初始索引（最左端索引）
        int index = 0; // 指向用于中转的数组temp的当前索引
        while (i <= mid && j <= right) { // 将左右两边的有序序列按照规则填充到中转数组，直到左右两边的有序序列有一边处理完毕
            if (nums[i] <= nums[j]) { // 左边有序序列的当前元素**小于等于**右边有序序列的当前元素则将左边有序序列的当前元素填充到中转数组
                tempArray[index++] = nums[i++];
            } else { // 右边有序序列的当前元素**小于**左边有序序列的当前元素则将右边有序序列的当前元素填充到中转数组，同时更新结果（结果增加左半部分剩余元素的个数）
                tempArray[index++] = nums[j++];
                result += mid - i + 1; // 左半部分剩余几个元素就表示对于当前添加的右半部分元素的不同逆序对的个数
            }
        }
        // 将有剩余数据的一边有序数组依次全部填充到中转数组（当右半部分有剩余元素时，左半部分数组已为空，故不需更新结果）
        while (i <= mid) tempArray[index++] = nums[i++];
        while (j <= right) tempArray[index++] = nums[j++];
        index = 0; // 中转数组的索引重新置0，用于将中转数组排序好的元素覆盖到原数组中的正确位置
        int indexNums = left; // 原数组的索引
        while (indexNums <= right) nums[indexNums++] = tempArray[index++]; // 将中转数组的元素拷贝到原数组中（并非拷贝所有）
    }
}

class Solution {
    public int search(int[] nums, int target) {
        int len = nums.length;
        if (len == 0) return 0;
        int begin = -1, end = -1; // 数字 target 在排序数组中的起始和终止索引
        int left = 0, right = len - 1;
        while (left < right) {
            int mid = left + right >> 1;
            if (target <= nums[mid]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        if (nums[left] != target) {
            return 0;
        } else {
            begin = left;
            right = len - 1; // 不再重新定义left = 0，使搜索范围缩小为target开始位置到数组末尾，提高程序执行效率
            while (left < right) {
                int mid = left + right + 1 >> 1;
                if (target >= nums[mid]) {
                    left = mid;
                } else {
                    right = mid - 1;
                }
            }
            end = left; // 即使target只出现了一次，进入此循环的有效数组范围任包括target开始位置，故可找到其结束位置=开始位置
            return end - begin + 1;
        }
    }
}

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

class Solution {
    public int[] singleNumbers(int[] nums) {
        int x = 0, excl = 0, util = 1; // x为两个只出现一次的数字中的一个；excl为数组nums中所有元素异或运算的结果；util为与运算用于分组的数
        for (int num : nums) excl ^= num;
        while ((excl & util) == 0) util <<= 1;
        for (int num : nums) {
            if ((num & util) == 0) x ^= num;
        }
        return new int[] {x, x ^ excl};
    }
}

class Solution {
    public int singleNumber(int[] nums) {
        int[] oneFreq = new int[32];
        for (int num : nums) {
            for (int i = 0; i < 32; i++) {
                oneFreq[i] += num & 1;
                num >>= 1;
            }
        }
        int result = 0; // 结果的初始值为0
        for (int i = 0; i < 32; i++) {
            result <<= 1; // 需先执行左移运算，否则在最后一次循环内结果已经先生成但是又左移了一次导致答案错误（后执行左移运算：左移32次，错误；先执行左移运算：左移31次，正确，实际执行了32次，但是第一次result=0，左移还为0）
            result |= oneFreq[31 - i] % 3; // 从高位开始
        }
        return result;
    }
}

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum == target) {
                return new int[] {nums[left], nums[right]};
            } else if (sum < target) {
                left++;
            } else right--;
        }
        return null;
    }
}

class Solution {
    public int[][] findContinuousSequence(int target) {
        List<int[]> result = new ArrayList<>();
        for (int l = 1, r = 2; l < r;) {
            int sum = (l + r) * (r - l + 1) / 2;
            if (sum == target) {
                int[] ele = new int[r - l + 1];
                for (int i = l; i <= r; i++) ele[i - l] = i;
                result.add(ele);
                l++; // 防止陷入死循环，需查找下一个结果，l++（以l开头的连续序列唯一）
            } else if (sum < target) {
                r++;
            } else { // 当满足最后一个区间（指针 r 移动到了 (target+1)/2 的位置）后，l++总会等于r而退出循环
                l++;
            }
        }
        return result.toArray(new int[result.size()][]);
    }
}

class Solution {
    public String reverseWords(String s) {
        String[] words = s.trim().split("\\s+");
        StringBuilder result = new StringBuilder();
        for (int i = words.length - 1; i > 0; i--) result.append(words[i]).append(" ");
        result.append(words[0]);
        return result.toString();
    }
}

class Solution {
    public String reverseLeftWords(String s, int n) {
        return s.substring(n) + s.substring(0, n);
    }
}

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (k == 0) return new int[0];
        int[] result = new int[nums.length - k + 1];
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            while (deque.size() > 0 && nums[i] > nums[deque.getLast()]) deque.removeLast();
            deque.addLast(i);
            if (i - k + 1 >= 0) result[i - k + 1] = nums[deque.getFirst()];
            if (i - k + 1 >= deque.getFirst()) deque.removeFirst();
        }
        return result;
    }
}

class MaxQueue {

    private Queue<Integer> queue;
    private Deque<Integer> deque;

    public MaxQueue() {
        queue = new LinkedList<>();
        deque = new LinkedList<>();
    }
    
    public int max_value() {
        return deque.isEmpty() ? -1 : deque.peekFirst();
    }
    
    public void push_back(int value) {
        while (!deque.isEmpty() && value > deque.peekLast()) deque.pollLast();
        deque.offerLast(value);
        queue.offer(value);
    }
    
    public int pop_front() {
        if (queue.isEmpty()) return -1;
        if (queue.peek().equals(deque.peekFirst())) deque.pollFirst();
        return queue.poll();
    }
}

/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue obj = new MaxQueue();
 * int param_1 = obj.max_value();
 * obj.push_back(value);
 * int param_3 = obj.pop_front();
 */

class Solution {
    public boolean isStraight(int[] nums) {
        int[] poker = new int[14]; // 用于判断是否有重复的牌
        int max = 0, min = 13; // 数组中除0外最大值的初始值为0（为一数组可能出现的最小的值），除0外最小值的初始值需为13不能为0（为一数组可能出现的最大的值）
        for (int num : nums) {
            if (num == 0) continue; // 遇到大小王则直接跳过
            if (poker[num]++ == 1) return false; // 除大小王外有重复牌则直接返回false
            max = Math.max(max, num);
            min = Math.min(min, num);
        }
        return max - min < 5;
    }
}

class Solution {
    public int maxProfit(int[] prices) {
        int result = 0;
        if (prices.length == 0) return result;
        int min = prices[0];
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] < min) {
                min = prices[i];
            } else {
                result = Math.max(result, prices[i] - min);
            }
        }
        return result;
    }
}

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

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

class Solution {
    public int strToInt(String str) {
        int len = str.length();
        if (len == 0) return 0;
        int signed = 1; // 数字的正负值
        int result = 0;
        int index = 0; // 用于1)在读取到有效数字前字符串的遍历、2)符号位的判断及3)有效数字的遍历（字符串str的索引）
        while (str.charAt(index) == ' ') if (++index == len) return 0; // 1)在读取到有效数字前字符串的遍历：在仅用于读取有效数字的遍历外（之前）
        if (str.charAt(index) == '-') signed = -1; // 2)符号位的判断
        if (str.charAt(index) == '-' || str.charAt(index) == '+') index++; // 上一步符号位为负时索引index并未++，或者读取到'+'，则索引index++
        for (int i = index; i < len; i++) { // 3)有效数字的遍历
            char ch = str.charAt(i);
            if (ch < '0' || ch > '9') break;
            if (result > 214748364 || result == 214748364 && ch - '0' > 7) return signed == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            result = result * 10 + ch - '0';
        }
        return signed * result;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        ListNode cur = head; // 用于统计链表的长度
        int len = 0; // 链表长度
        while (cur != null) {
            len++;
            cur = cur.next;
        }
        int[] result = new int[len];
        for (int i = len - 1; i >= 0; i--) {
            result[i] = head.val;
            head = head.next;
        }
        return result;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;
        ListNode cur = dummyHead;
        while (cur.next.val != val) cur = cur.next;
        cur.next = cur.next.next;
        return dummyHead.next;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode cur = head, end = head;
        for (int i = 0; i < k; i++) end = end.next;
        while (end != null) {
            cur = cur.next;
            end = end.next;
        }
        return cur;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

// 递归
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head; // head==null用于判断当原链表长度为0时返回null，head.next==null用于判断当原链表递归到最后一个节点（递归结束条件）
        ListNode newHead = reverseList(head.next); // 用于保存反转后链表的头节点，即原链表的最后一个节点（第一次回溯时返回的值）
        head.next.next = head; // 反转
        head.next = null; // 用于当递归回溯到原链表的头节点（也即反转链表的最后一个节点）时，其next应指向null，否则其next还指向原链表的next节点，会使得反转后的链表产生循环
        return newHead;
    }
}

// 迭代
/*class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null, cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}*/

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

// 递归
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) return l1 == null ? l2 : l1; // 递归结束条件
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

// 迭代
/*class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode();
        ListNode cur = dummyHead;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = l1 == null ? l2 : l1;
        return dummyHead.next;
    }
}*/

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        Node cur = head; // 指向原链表中的节点
        while (cur != null) {
            Node node = new Node(cur.val); // 由原链表节点的值复制节点
            node.next = cur.next;
            cur.next = node;
            cur = cur.next.next;
        }
        cur = head;
        while (cur != null) {
            if (cur.random != null) cur.next.random = cur.random.next; // 成员变量random可能为null
            cur = cur.next.next;
        }
        Node copyHead = head.next; // 复制链表的头节点
        cur = head;
        Node copyCur = head.next; // 指向复制链表中的节点
        while (copyCur.next != null) { // 拆分两个链表：复制原链表同时，原链表需要保持不变（即原链表的成员变量next不能改变）
            cur.next = cur.next.next;
            copyCur.next = copyCur.next.next;
            cur = cur.next;
            copyCur = copyCur.next;
        }
        cur.next = null; // 将原链表的末尾节点的next置空（原来指向复制链表的末尾节点）
        return copyHead;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null; // 优化
        ListNode cur = headA, cur2 = headB;
        while (cur != cur2) {
            cur = cur == null ? headB : cur.next;
            cur2 = cur2 == null ? headA : cur2.next;
        }
        return cur;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    int[] preorder; // 前序遍历的数组
    Map<Integer, Integer> indexMap; // 用于获取中序遍历数组中某值对应的索引

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        indexMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) indexMap.put(inorder[i], i);
        return buildTree(0, preorder.length - 1, 0, inorder.length - 1);
    }

    private TreeNode buildTree(int preLeft, int preRight, int inLeft, int inRight) { // 方法的重载
        if (preLeft > preRight || inLeft > inRight) return null; // 递归结束的条件
        TreeNode root = new TreeNode(preorder[preLeft]);
        int rootIndex = indexMap.get(preorder[preLeft]); // 每次递归得到的此次根节点的值及其在中序遍历数组中的索引
        root.left =  buildTree(preLeft + 1, preLeft + rootIndex - inLeft, inLeft, rootIndex - 1);
        root.right = buildTree(preLeft + rootIndex - inLeft + 1, preRight, rootIndex + 1, inRight);
        return root;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) { // 递归：后序遍历
        if (A == null || B == null) return false; // 递归边界条件（B == null 仅用于当传入的 B 为空时则一定不为子结构直接返回 false）
        return isSubStructure(A.left, B) || isSubStructure(A.right, B) || isSameTree2(A, B); // 当其中一个条件判断为 true 时就不断回溯返回 true（剪枝）
    }

    private boolean isSameTree2(TreeNode A, TreeNode B) { // 递归：前序遍历（以相同的遍历方式访问两颗子树）
        if (B == null) return true; // 因为并非要求两子树相同（要求B为A的子结构），故当前访问的 B 中的节点为null时满足要求
        if (A == null || A.val != B.val) return false; // 相同位置处的 A 中节点为 null 但 B 中节点不为 null 或者 都不为空但是值不相等时，则表示 B 不是 A 的子结构
        if (!isSameTree2(A.left, B.left)) return false; // 当前两节点的左子节点满足要求需要继续递归检查下去
        return isSameTree2(A.right, B.right); // 访问右子节点
    } // 当其中一个条件判断为 false 时就不断回溯返回 false（剪枝）
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if (root == null) return null;
        TreeNode temp = root.left; // 指针：交换当前节点的两个子节点，需要使用临时变量保存首先被重定向的待交换节点
        root.left = mirrorTree(root.right);
        root.right = mirrorTree(temp);
        return root; // 返回当前翻转左右子树（节点）后的根（当前）节点
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return check(root, root);
    }

    private boolean check(TreeNode p, TreeNode q) { // 以相反的递归方式深度遍历两颗二叉树
        if (p == null && q == null) return true;
        if (p == null || q == null) return false; // 在结构上不对称
        if (p.val != q.val) return false;
        if (!check(p.left, q.right)) return false; // 当前两镜像对称节点的一对镜像对称子节点相等（满足要求）需要继续递归检查下去
        return check(p.right, q.left); // 访问另一对镜像对称子节点
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] levelOrder(TreeNode root) {
        if (root == null) return new int[0];
        List<Integer> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int count = queue.size(); // 当前层级节点的个数
            while (count != 0) {
                TreeNode node = queue.poll();
                result.add(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
                count--;
            }
        }
        int[] resultArray = new int[result.size()];
        for (int i = 0; i < result.size(); i++) resultArray[i] = result.get(i);
        return resultArray;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int count = queue.size();
            List<Integer> level = new ArrayList<>();
            while (count != 0) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
                count--;
            }
            result.add(level);
        }
        return result;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        boolean isReverse = false; // 当前层级是否需要逆序（需要从右往左遍历的层级），初始值为 false
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int count = queue.size();
            List<Integer> level = new ArrayList<>();
            while (count != 0) {
                TreeNode node = queue.poll();
                if (isReverse) { // 需要从右往左遍历的层级进行倒序插入
                    level.add(0, node.val);
                } else {
                    level.add(node.val);
                }
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
                count--;
            }
            result.add(level);
            isReverse = !isReverse; // 将 isReverse 取反（下一层的遍历状态不同）
        }
        return result;
    }
}

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return check(postorder, 0, postorder.length - 1);
    }

    private boolean check(int[] postorder, int left, int right) { // left和right为当前递归层级检查子树的后序遍历序列区间的左右索引
        if (left >= right) return true; // 等于的情况：当前子树仅有一个元素（满足要求）；也可能存在大于的情况：当前子树为空（满足要求）
        int index = left; // 用于遍历当前子树的后序遍历序列区间的索引
        while (postorder[index] < postorder[right]) index++; // 查找第一个大于根节点的元素（当前子树的根节点即postorder[right]）
        int mid = index; // 第一个大于根节点元素的索引：右子树后序遍历序列的起始
        while (postorder[index] > postorder[right]) index++; // 查找第一个小于等于根节点的元素
        return index == right && check(postorder, left, mid - 1) && check(postorder, mid, right - 1); // 当有一颗子树不为二叉搜索树返回false后将不断回溯返回false（**逻辑运算符与 && 的短路特性**）
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    private List<List<Integer>> result; // 结果集合
    private List<Integer> cur; // 二叉树前序遍历过程中路径节点的集合

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        this.result = new ArrayList<>(); // 成员变量的初始化
        this.cur = new ArrayList<>();
        path(root, target);
        return result;
    }

    private void path(TreeNode root, int target) {
        if (root == null) return;
        cur.add(root.val);
        if (root.left == null && root.right == null && root.val == target) result.add(new ArrayList<Integer>(cur)); // 当前递归层级访问到叶子节点且路径满足要求：**拷贝**当前遍历路径节点集合 cur 到结果集合中（无需执行return，方法访问两null子节点后，当前层级递归方法回溯前将前序遍历路径节点集合中的此叶子节点移除）
        path(root.left, target - root.val);
        path(root.right, target - root.val);
        cur.remove(cur.size() - 1); // 回溯前：需要在遍历过程中路径节点的集合中移除当前层级访问的节点
    }
}

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {

    private Node pre; // 中序遍历上一节点的指针
    private Node head; // 指针，指向中序遍历的第一个节点：即链表的头节点

    public Node treeToDoublyList(Node root) {
        if (root == null) return root;
        inorder(root); // 中序遍历结束后 pre 指针指向中序遍历的最后一个元素
        pre.right = head; // 使链表产生循环
        head.left = pre;
        return head;
    }

    private void inorder(Node cur) { // cur 即为当前中序遍历节点
        if (cur == null) return; // 递归边界条件
        inorder(cur.left);
        if (pre != null) {
            pre.right = cur;
        } else head = cur; // pre 指针为null则为访问到中序遍历的第一个节点：使用head指针保存头节点
        cur.left = pre;
        pre = cur; // 链表拼接完当前节点后需要将 pre 指针更新为当前遍历节点
        inorder(cur.right);
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        return serialize(root, new StringBuilder()).toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        return deserialize(new LinkedList<String>(Arrays.asList(data.split(",")))); // 将字符串分割转换为字符串数组再将其转换为List集合
    }

    private StringBuilder serialize(TreeNode root, StringBuilder sb) { // 序列化方法的重载，使用StringBuilder加快序列化字符串的拼接：前序遍历
        if (root == null) return sb.append("null").append(","); // 递归边界条件
        sb.append(root.val).append(",");
        serialize(root.left, sb);
        serialize(root.right, sb);
        return sb;
    }

    private TreeNode deserialize(List<String> ser) { // 反序列化方法的重载，使用List便于对序列化字符串进行访问操作：前序遍历（在回溯的过程中拼接节点）
        String cur = ser.remove(0); // 当前节点的值
        if (cur.equals("null")) return null; // 递归边界条件
        TreeNode root = new TreeNode(Integer.parseInt(cur));
        root.left = deserialize(ser);
        root.right = deserialize(ser);
        return root; // **返回当前已拼接好子树的根节点**
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    int count = 0; // 记录中序遍历访问节点的次数
    int result = 0;

    public int kthLargest(TreeNode root, int k) {
        if (root == null || count >= k) return result; // 剪枝（第一次回溯后 count 可能大于 k）
        kthLargest(root.right, k);
        if (++count == k) {
            result = root.val;
        } else kthLargest(root.left, k);
        return result;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0; // 递归的边界条件
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    private boolean flag; // 是否为一高度平衡的二叉树：每个节点的左右两个子树的高度差的绝对值不超过 1

    public boolean isBalanced(TreeNode root) {
        this.flag = true; // 初始化为 true
        countHeight(root);
        return this.flag;
    }

    private int countHeight(TreeNode root) {
        if (root == null) return 0; // 递归的边界条件
        int leftHeight = countHeight(root.left);
        int rightHeight = countHeight(root.right);
        if (Math.abs(leftHeight - rightHeight) > 1) this.flag = false;
        return Math.max(leftHeight, rightHeight) + 1; // 返回左右子树高度中最大的一支作为当前节点二叉树的高度
    }
}