LeetCode 热题 HOT 100

class Solution {
    public void moveZeroes(int[] nums) {
        int k = 0; // nums数组中[0, ..., k)的元素均为非0元素
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                if (i == k) { // 用于优化数组前几个元素都为非0的情况
                    k++;
                } else {
                    nums[k++] = nums[i];
                    nums[i] = 0;
                }
            }
        }
    }
}

class Solution {
    public int maxArea(int[] height) {
        int ans = 0;
        for (int i = 0, j = height.length - 1; i < j;) {
            ans = Math.max(Math.min(height[i], height[j]) * (j - i), ans);
            if (height[i] < height[j]) {
                i++;
            } else {
                j--;
            }
        }
        return ans;
    }
}

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

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

class Solution {
    public int trap(int[] height) {
        int len = height.length;
        int result = 0;
        if (len == 0) return result;
        int left = 0, right = len - 1;
        int maxL = height[left], maxR = height[right];
        while (left < right) {
            if (maxL < maxR) { // “只取当前有效的leftMax[i]或rightMax[i]的一边更新result”，即较小的最大柱子高度，另一边虽然可能有比当前maxSide更高的柱子，但是当前maxSide已经大于有效边的maxSide，继续遍历下去只会比当前maxSide更大，maxSide同样还是会大于有效边的maxSide，故有效边的left/right更新一定是正确的
                result += maxL - height[left];
                maxL = Math.max(maxL, height[++left]);
            } else {
                result += maxR - height[right];
                maxR = Math.max(maxR, height[--right]);
            }
        } // 退出循环后总有一个单位长度未计算，但是此单位长度一定为数组中的最大值
        return result;
    }
}

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 List<Integer> findAnagrams(String s, String p) {
        int len = p.length();
        List<Integer> list = new ArrayList<>();
        if (len > s.length()) return list;
        int[] pFreq = new int[26];
        int[] sFreq = new int[26];
        int left = 0, right = len - 1;
        boolean flag = true;
        for (int i = 0; i < len; i++) {
            pFreq[p.charAt(i) - 'a']++;
            sFreq[s.charAt(i) - 'a']++;
        }
        while (right < s.length()) {
            for (int i = 0; i < 26; i++) {
                if (pFreq[i] != sFreq[i]) {
                    flag = false;
                    break;
                }
            }
            if (flag) list.add(left);
            sFreq[s.charAt(left++) - 'a']--;
            if (right + 1 < s.length()) {
                sFreq[s.charAt(++right) - 'a']++;
            } else {
                right++;
            }
            flag = true;
        }
        return list;
    }
}

class Solution {
    public String minWindow(String s, String t) {
        if (t.length() > s.length()) return "";
        int left = 0, right = t.length() - 1;
        int len = t.length();
        int[] tFreq = new int[58];
        int[] sFreq = new int[58];
        boolean flag = true;
        String result = s + "a";
        for (int i = 0; i < len; i++) {
            tFreq[t.charAt(i) - 'A']++;
            sFreq[s.charAt(i) - 'A']++;
        }
        while (right < s.length()) {
            for (int i = 0; i < 58; i++) {
                if (tFreq[i] != 0 && tFreq[i] > sFreq[i]) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                while (sFreq[s.charAt(left) - 'A'] > tFreq[s.charAt(left) - 'A']) sFreq[s.charAt(left++) - 'A']--;
                result = result.length() > right - left + 1 ? s.substring(left, right + 1) : result;
                sFreq[s.charAt(left++) - 'A']--;
            }
            flag = true;
            if (right + 1 < s.length()) {
                sFreq[s.charAt(++right) - 'A']++;
            } else {
                right++;
            }
        }
        return result.length() > s.length() ? "" : result;
    }
}

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            freq.put(nums[i], freq.getOrDefault(nums[i], 0) + 1);
        }
        List<Integer>[] bucket = new List[len + 1];
        for (int key : freq.keySet()) {
            int value = freq.get(key);
            if (bucket[value] == null) bucket[value] = new ArrayList();
            bucket[value].add(key);
        }
        int count = 0; // 计数当前为出现频率第k高的元素
        int[] result = new int[k];
        for (int i = len; count < k; i--) {
            if (bucket[i] != null) {
                for (int ele : bucket[i]) {
                    if (count < k) {
                        result[count++] = ele;
                    } else {
                        break;
                    }
                }
            }
        }
        return result;
    }
}

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> resMap = new HashMap<>();
        for (String str : strs) {
            int[] freq = new int[26];
            for (int i = 0; i < str.length(); i++) {
                freq[str.charAt(i) - 'a']++;
            }
            StringBuffer keySb = new StringBuffer();
            for (int i = 0; i < 26; i++) {
                if (freq[i] != 0) {
                    keySb.append((char) (i + 'a')).append(freq[i]);
                }
            }
            String keyStr = keySb.toString();
            List<String> value = resMap.getOrDefault(keyStr, new ArrayList<String>());
            value.add(str);
            resMap.put(keyStr, value);
        }
        return new ArrayList<List<String>>(resMap.values());
    }
}

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

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> eles = new HashSet<>();
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            eles.add(nums[i]);
        }
        for (int num : nums) {
            int len = 1;
            if (!eles.contains(num - 1)) {
                while (eles.contains(++num)) len++;
                result = Math.max(result, len);
            }
        }
        return result;
    }
}

class Solution {
    public void sortColors(int[] nums) {
        int zero = -1; // [0, ..., zero]的元素都为0
        int two = nums.length; // [two, ..., nums.length - 1]的元素都为2
        for (int i = 0; i < two; ) { // 索引i用于遍历
            if (nums[i] == 0) {
                nums[i++] = nums[++zero];
                nums[zero] = 0;
            } else if (nums[i] == 2) { // 这里i不能递增，因为和--two处元素交换，--two处的元素为一不确定的值（未检查的值）
                nums[i] = nums[--two];
                nums[two] = 2;
            } else { // nums[i] == 1
                i++;
            }
        }
    }
}

class Solution {

    Random random = new Random();

    public int findKthLargest(int[] nums, int k) {
        int index = nums.length - k; // 第k大元素的索引
        return randomPartition(nums, 0, nums.length - 1, index);
    }

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

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

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

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> prefixSumCount = new HashMap<>();
        prefixSumCount.put(0, 1); // 前缀和为0的次数为1
        int sum = 0;
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            result += prefixSumCount.getOrDefault(sum - k, 0);
            prefixSumCount.put(sum, prefixSumCount.getOrDefault(sum, 0) + 1);
        }
        return result;
    }
}

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        if (len1 > len2) return findMedianSortedArrays(nums2, nums1);
        int k = (len1 + len2 + 1) / 2; // 需要从两个数组中总共选取的元素的个数
        int left = 0, right = len1; // m1可能取的值的范围
        while (left < right) { // 因为循环内不会出现m1 = len1的情况，所以不会出现m2 = 0的情况
            int m1 = (left + right) / 2;
            int m2 = k - m1;
            if (nums1[m1] < nums2[m2 - 1]) { // 不会有越界的问题
                left = m1 + 1;
            } else {
                right = m1;
            }
        }
        int m1 = left; // 从nums1数组中选取元素的个数，最大为len1
        int m2 = k - m1; // 从nums2数组中选取元素的个数
        int c1 = Math.max(m1 == 0 ? Integer.MIN_VALUE : nums1[m1 - 1], m2 == 0 ? Integer.MIN_VALUE : nums2[m2 - 1]);
        if ((len1 + len2) % 2 == 1) return c1;
        int c2 = Math.min(m1 == len1 ? Integer.MAX_VALUE : nums1[m1], m2 == len2 ? Integer.MAX_VALUE : nums2[m2]);
        return (c1 + c2) * 0.5;
    }
}

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

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] result = {-1, -1};
        int len = nums.length;
        if (len == 0) return result;
        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 result;
        } else { // 已找出target在数组中的开始位置
            result[0] = 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;
                }
            }
            result[1] = left; // 即使target只出现了一次，进入此循环的有效数组范围任包括target开始位置，故可找到其结束位置=开始位置
            return result;
        }
    }
}

class Solution {
    public int findDuplicate(int[] nums) {
        int len = nums.length;
        int left = 1, right = len - 1;
        while (left < right) {
            int mid = left + right >> 1;
            int count = 0; // 数组中小于mid值元素的个数
            for (int num : nums) {
                if (num <= mid) count++;
            }
            if (count <= mid) {
                left = mid + 1;
            } else {
                right = mid;
            }
        } // 退出循环时left = right
        return left;
    }
}

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] result = new int[nums.length - k + 1];
        Deque<Integer> deque = new LinkedList<Integer>(); // 双端队列
        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 Solution {
    public boolean isValid(String s) {
        int len = s.length();
        if (len % 2 == 1) return false;
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < len; i++) {
            char ch = s.charAt(i);
            if (ch == '(' || ch == '{' || ch == '[') {
                stack.push(ch);
            } else {
                if (ch == ')') {
                    if (stack.empty() || stack.pop() != ch - 1) return false;
                } else {
                    if (stack.empty() || stack.pop() != ch - 2) return false;
                }
            }
        }
        if (!stack.empty()) return false;
        return true;
    }
}

class Solution {
    public int longestValidParentheses(String s) {
        Stack<Integer> stack = new Stack<>();
        stack.push(-1); // 保证栈底永远为上一个未匹配的右括号的索引（即表示新的有效子串开始索引的上一个索引，故需要初始化栈底元素-1）
        int result = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') { // 当前元素为'('则将其索引添加到栈顶
                stack.push(i);
            } else {
                stack.pop(); // 弹出与')'匹配的'('的索引（弹出后栈顶为上一个未匹配的左括号的索引或者上一个未匹配的右括号的索引（即新的有效子串开始索引的上一个索引）），或者当栈中只剩一个元素时弹出需要更新的上一个未匹配的右括号的索引（弹出后栈为空）
                if (stack.empty()) {
                    stack.push(i); // 当栈中只剩一个元素时弹出后为空，更新上一个未匹配的右括号的索引
                } else {
                    result = Math.max(result, i - stack.peek()); // 当前右括号匹配的有效子串长度，即当前右括号的索引减去上一个未匹配的左括号的索引的长度（不能使用当前右括号的索引减去上一个未匹配的右括号的索引，因为这其中可能还会有未匹配的左括号）或者当栈内所有'('全部匹配完毕则减去上一个未匹配的右括号的索引（新的有效子串开始索引的上一个索引）
                }
            }
        }
        return result;
    }
}

class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int result = 0;
        int len = heights.length;
        int[] newHeights = new int[len + 2];
        for (int i = 1; i < len + 1; i++) {
            newHeights[i] = heights[i - 1];
        }
        stack.push(0);
        for (int i = 1; i < len + 2; i++) {
            while (newHeights[i] < newHeights[stack.peek()]) {
                int heightIndex = stack.pop();
                int left = stack.peek();
                int right = i;
                result = Math.max(result, (right - left - 1) * newHeights[heightIndex]);
            }
            stack.push(i);
        }
        return result;
    }
}

class Solution {
    public int maximalRectangle(char[][] matrix) { // 矩阵数组的元素类型为char
        int result = 0;
        int row = matrix.length;
        if (row == 0) return result;
        int col = matrix[0].length;
        int[] heights = new int[col + 2];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++){
                if (matrix[i][j] == '1') {
                    heights[j + 1]++;
                } else {
                    heights[j + 1] = 0;
                }
            }
            Stack<Integer> stack = new Stack<>();
            stack.push(0);
            for (int j = 1; j < col + 2; j++) {
                while (heights[j] < heights[stack.peek()]) {
                    int heightIndex = stack.pop();
                    int left = stack.peek();
                    int right = j;
                    result = Math.max(result, heights[heightIndex] * (right - left - 1));
                }
                stack.push(j);
            }
        }
        return result;
    }
}

class Solution {
    public int maximalSquare(char[][] matrix) {
        int result = 0;
        int row = matrix.length;
        if (row == 0) return result;
        int col = matrix[0].length;
        int[] heights = new int[col + 2];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] == '1') {
                    heights[j + 1]++;
                } else {
                    heights[j + 1] = 0;
                }
            }
            Stack<Integer> stack = new Stack<>();
            stack.push(0);
            for (int j = 1; j < col + 2; j++) {
                while (heights[j] < heights[stack.peek()]) {
                    int heightIndex = stack.pop();
                    int left = stack.peek();
                    int right = j;
                    int height = heights[heightIndex];
                    int width = right - left - 1;
                    if (width >= height) result = Math.max(result, height * height); // 宽度大于高度才能形成正方形
                }
                stack.push(j);
            }
        }
        return result;
    }
}

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int len = temperatures.length;
        int[] result = new int[len];
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        for (int i = 1; i < len; i++) {
            while (!stack.empty() && temperatures[i] > temperatures[stack.peek()]) { // 需要加上栈不为空的判断
                result[stack.peek()] = i - stack.pop(); // 先执行赋值运算符左边的stack.peek()
            }
            stack.push(i);
        }
        return result;
    }
}

class Solution {
    public String decodeString(String s) {
        StringBuilder res = new StringBuilder();
        int times = 0;
        Stack<String> stackRes = new Stack<>();
        Stack<Integer> stackTimes = new Stack<>();
        for (Character ch : s.toCharArray()) {
            if (ch == '[') {
                stackRes.push(res.toString());
                stackTimes.push(times);
                res = new StringBuilder();
                times = 0;
            } else if (ch == ']') {
                StringBuilder temp = new StringBuilder();
                int mult = stackTimes.pop();
                for (int i = 0; i < mult; i++) temp.append(res);
                res = new StringBuilder(stackRes.pop() + temp);
            } else if (ch >= '0' && ch <= '9') {
                times = times * 10 + Integer.parseInt(ch + ""); // k可能不止一位数
            } else res.append(ch);
        }
        return res.toString();
    }
}

class MinStack {

    private Node head;

    /** initialize your data structure here. */
    public MinStack() {
        
    }
    
    public void push(int val) {
        if (head == null) {
            head = new Node(val, val);
        } else {
            head = new Node(val, Math.min(val, head.minVal), head);
        }
    }
    
    public void pop() {
        head = head.next;
    }
    
    public int top() {
        return head.val;
    }
    
    public int getMin() {
        return head.minVal;
    }

    private class Node {

        int val;
        int minVal;
        Node next;
        
        Node(int val, int minVal) {
            this(val, minVal, null);
        }

        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(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

class LRUCache {

    private int cap;
    private Map<Integer, Node> map;
    private DoubleList list;
    
    public LRUCache(int capacity) {
        this.cap = capacity;
        this.map = new HashMap<>();
        this.list = new DoubleList();
    }
    
    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        int val = map.get(key).val;
        put(key, val); // 需要将此键值对更新到链表的头节点
        return val;
    }
    
    public void put(int key, int value) {
        if (map.containsKey(key)) list.revome(map.get(key));
        Node node = new Node(key, value);
        if (list.size() == cap) {
            Node last = list.removeLast();
            map.remove(last.key);
        }
        list.addFirst(node);
        map.put(key, node);
    }
}

class Node {
    int key, val;
    Node pre, next;

    public Node(int key, int val) {
        this.key = key;
        this.val = val;
    }
}

class DoubleList {
    private Node head, tail;
    private int size;

    public void addFirst(Node node) {
        if (head == null) {
            head = node;
            tail = node;
        } else {
            Node temp = head;
            head = node;
            head.next = temp;
            temp.pre = head;
        }
        size++;
    }

    public void revome(Node node) {
        if (head == node && tail == node) {
            head = null;
            tail = null;
        } else if (head == node) {
            head = head.next;
            head.pre = null;
        } else if (tail == node) {
            tail = tail.pre;
            tail.next = null;
        } else {
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }
        size--;
    }

    public Node removeLast() {
        Node last = tail;
        revome(tail); // 这里只能使用调用此类中的remove方法，因为tdil可能为链表中唯一节点元素（即是头结点又是未节点）或者仅为尾节点
        return last;
    }

    public int size() {
        return size;
    }
}

/**
 * // 使用LinkedHashMap类的实现，详细实现机制查看JDK API文档及LinkedHashMap类源码
 * class LRUCache {
 * 
 *     private Map<Integer, Integer> cache;
 * 
 *     public LRUCache(int capacity) {
 *         this.cache = new LinkedHashMap<>(capacity, 0.75f, true) {
 *             @Override
 *             protected boolean removeEldestEntry(Map.Entry eldest) {
 *                 return cache.size() > capacity;
 *             }
 *         };
 *     }
 *     
 *     public int get(int key) {
 *         return cache.getOrDefault(key, -1);
 *     }
 *     
 *     public void put(int key, int value) {
 *         cache.put(key, value);
 *     }
 * }
 */
 
/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

class Solution {
    public int[][] merge(int[][] intervals) {
        int len = intervals.length;
        Arrays.sort(intervals, new Comparator<int[]>() { // 泛型为一维数组，第一参数为泛型数组（故最终为二维数组）
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        int[][] result = new int[len][2]; // 初始化为可能的最大长度
        int index = -1;
        result[++index] = intervals[0];
        for (int i = 1; i < len; i++) {
            if (intervals[i][0] > result[index][1]) { // 当前区间的起始位置大于结果数组中最后区间的终止位置则不合并，直接将当前区间加入结果数组
                result[++index] = intervals[i];
            } else { // 将当前区间合并至结果数组的最后区间
                result[index][1] = Math.max(result[index][1], intervals[i][1]);
            }
        }
        return Arrays.copyOf(result, index + 1); // 返回值需要截取有效长度
    }
}

class Solution {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        int equationsSize = equations.size();
        Map<String, Integer> map = new HashMap<>(2 * equationsSize); // 使用传入初始容量的实例化方式，使哈希表无需自动扩容以提高性能
        int index = 0;
        UnionFind unionFind = new UnionFind(2 * equationsSize); // 极端情况下 equations 中的数字变量都不同
        for (int i = 0; i < equationsSize; i++) {
            List<String> equation = equations.get(i);
            String a = equation.get(0);
            String b = equation.get(1);
            if (!map.containsKey(a)) map.put(a, index++); // 将变量与 index 进行映射，使得并查集底层可以使用数组实现
            if (!map.containsKey(b)) map.put(b, index++);
            unionFind.union(map.get(a), map.get(b), values[i]);
        }
        int queriesSize = queries.size();
        double[] result = new double[queriesSize];
        for (int i = 0; i < queriesSize; i++) {
            List<String> query = queries.get(i);
            String c = query.get(0);
            String d = query.get(1);
            if (!map.containsKey(c) || !map.containsKey(d)) {
                result[i] = -1.0;
            } else {
                result[i] = unionFind.isConnected(map.get(c), map.get(d));
            }
        }
        return result;
    }

    private class UnionFind { // 并查集：成员内部类

        private int[] parent;
        private double[] weight;

        public UnionFind(int size) {
            this.parent = new int[size];
            this.weight = new double[size];
            for (int i = 0; i < size; i++) {
                parent[i] = i;
                weight[i] = 1;
            }
        }

        public void union(int index1, int index2, double value) {
            int root1 = find(index1);
            int root2 = find(index2);
            if (root1 == root2) return;
            parent[root1] = root2;
            weight[root1] = value * weight[index2] / weight[index1];
        }

        public int find(int index) {
            if (index != parent[index]) {
                int directRoot = parent[index];
                parent[index] = find(directRoot);
                weight[index] *= weight[directRoot];
            }
            return parent[index];
        }

        public double isConnected(int index1, int index2) {
            int root1 = find(index1);
            int root2 = find(index2);
            if (root1 == root2) {
                return weight[index1] / weight[index2];
            } else {
                return -1.0;
            }
        }
    }
}

class Solution {
    public int[][] reconstructQueue(int[][] people) { // 降序
        Arrays.sort(people, new Comparator<int[]>() { // 泛型为一维数组，第一参数为泛型数组（故最终为二维数组）
            @Override
            public int compare(int[] o1, int[] o2) {
                int res = o2[0] - o1[0];
                if (res == 0) res = o1[1] - o2[1];
                return res;
            }
        });
        List<int[]> list = new ArrayList<>();
        for (int[] ele : people) list.add(ele[1], ele);
        return list.toArray(new int[people.length][2]);
    }
}

/*class Solution {
    public int[][] reconstructQueue(int[][] people) { // 升序
        int[][] result = new int[people.length][2];
        Arrays.sort(people, new Comparator<int[]>() { // 泛型为一维数组，第一参数为泛型数组（故最终为二维数组）
            @Override
            public int compare(int[] o1, int[] o2) {
                int res = o1[0] - o2[0];
                if (res == 0) res = o2[1] - o1[1];
                return res;
            }
        });
        List<Integer> index = new ArrayList<>();
        for (int i = 0; i < people.length; i++) index.add(i);
        for (int[] ele : people) {
            result[index.get(ele[1])] = ele; // 数组可以这样赋值
            index.remove(ele[1]); // 移除的应该为对应的链表中的索引而不是其在结果数组中的索引
        }
        return result;
    }
}*/

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
class Solution {
    public int minMeetingRooms(Interval[] intervals) {
        Arrays.sort(intervals, new Comparator<Interval>() {
            @Override
            public int compare(Interval o1, Interval o2) {
                return o1.start - o2.start;
            }
        });
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int i = 0; i < intervals.length; i++) {
            minHeap.offer(intervals[i].end);
            if (intervals[i].start >= minHeap.peek()) minHeap.poll();
        }
        return minHeap.size();
    }
}

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        Set<String> level = new HashSet<>();
        level.add(s);
        while (!level.isEmpty()) {
            List<String> result = new ArrayList<>(); // 结果集合
            for (String ele : level) if (isVaild(ele)) result.add(ele); // 将此层级合法的字符串添加到结果集合
            if (!result.isEmpty()) return result; // 存在合法字符串直接返回（结束搜索）
            Set<String> nextLevel = new HashSet<>(); // 下一层级的字符串（使用 Set 集合去重）
            for (String ele : level) { // 删除当前层级每个字符串的某一特定位置字符后的所有情况
                for (int i = 0; i < ele.length(); i++) {
                    if (ele.charAt(i) == '(' || ele.charAt(i) == ')') { // 仅删除括号，其它字符跳过
                        StringBuilder sb = new StringBuilder(ele);
                        nextLevel.add(sb.deleteCharAt(i).toString());
                    }
                } 
            }
            level = nextLevel;
        }
        return new ArrayList<String>();
    }

    private boolean isVaild(String s) { // 判断字符串是否合法
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                count++;
            } else if (s.charAt(i) == ')') count--;
            if (count < 0) return false; // 存在右括号位于左括号前：不合法
        }
        return count == 0; // 是否存在剩余的未匹配左括号
    }
}

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

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

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        int n = nums.length;
        List<Integer> result = new ArrayList<>();
        for (int index : nums) {
            index = (index - 1) % n;
            nums[index] += n;
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] <= n) result.add(i + 1);
        }
        return result;
    }
}

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
        int high = 0, low = 1; // 当high指针更新时low指针在下一次遍历中也一定会更新，不更新则原序列升序应返回0，则需将原始左右指针定义为差值为-1（返回值为 high - low + 1）
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= max) {
                max = nums[i];
            } else high = i;
        }
        for (int i = nums.length - 1; i >= 0; i--) {
            if (nums[i] <= min) {
                min = nums[i];
            } else low = i;
        }
        return high - low + 1;
    }
}

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] freq = new int[26];
        int lastCount = 0; // 最后一个桶中元素的个数
        int size = 0; // 桶的大小
        for (char task : tasks) size = Math.max(size, ++freq[task - 'A']);
        for (int i = 0; i < freq.length; i++) {
            if (freq[i] == size) lastCount++;
        }
        return Math.max(tasks.length, (size - 1) * (n + 1) + lastCount);
    }
}

class Solution {
    public void nextPermutation(int[] nums) {
        int len = nums.length;
        if (len <= 1) return;
        for (int i = len - 1; i > 0; i--) {
            if (nums[i] > nums[i - 1]) { // 倒序遍历查找第一对升序的相邻元素
                for (int j = len - 1; j >= i; j--) { // 倒序遍历查找第一个大于nums[i-1]的元素，并且一定能找到
                    if (nums[j] > nums[i - 1]) {
                        int temp = nums[j];
                        nums[j] = nums[i - 1];
                        nums[i - 1] = temp;
                        reverse(nums, i, len - 1);
                        return; // 整个nextPermutation方法结束，将不会执行后续的语句
                    }
                }
            }
        }
        reverse(nums, 0, len - 1); // 未找到升序的相邻元素，则整个数组为降序（不存在下一个更大的排列）
    }

    private void reverse(int[] nums, int left, int right) {
        while (left < right) {
            int temp = nums[right];
            nums[right--] = nums[left];
            nums[left++] = temp;
        }
    }
}

class Solution {
    public boolean canJump(int[] nums) {
        int maxLen = 0; // 可以到达的最大有效距离的索引
        for (int i = 0; i <= maxLen; i++) { // 条件判断语句的边界条件在每次执行循环体的过程中动态更新
            maxLen = Math.max(maxLen, i + nums[i]);
            if (maxLen >= nums.length - 1) return true;
        }
        return false;
    }
}

class Solution {
    public int hammingDistance(int x, int y) { // 调用库函数的形式
        return Integer.bitCount(x ^ y);
    }
}

/*class Solution {
    public int hammingDistance(int x, int y) {
        int z = x ^ y;
        int result = 0;
        for (int i = 0; i < 31; i++) { // 0 ≤ x, y，第32位都为0，只需比较31位
            if (z % 2 == 1) result++;
            z /= 2;
        }
        return result;
    }
}*/

class Solution {
    public void rotate(int[][] matrix) {
        int len = matrix.length;
        for (int i = 0; i < len / 2; i++) { // 将矩阵的所有元素相对中轴横线进行上下翻转
            for (int j = 0; j < len; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[len - 1 - i][j];
                matrix[len - 1 - i][j] = temp;
            }
        }
        for (int i = 0; i < len - 1; i++) { // 将矩阵的所有元素相对斜对角线进行翻转
            for (int j = i + 1; j < len; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
    }
}

class Solution {
    public int uniquePaths(int m, int n) {
        if (m > n) return uniquePaths(n, m);
        long result = 1; // 结果的计算过程中可能超出int类型的范围
        for (int i = n, fac = 1; i <= m + n - 2; i++, fac++) { // 遍历 m-1 次
            result = result * i / fac;
        }
        return (int) result;
    }
}