class Solution {
    public int minOperations(int[] nums, int x) {
        int total = 0, min = Integer.MAX_VALUE;
        for(int num : nums){
            total += num;
        }
        int target = total - x; //将减去两侧元素并寻找和为x的结果的问题转换为用滑动窗口寻找total - x的结果。
        int sum = 0, left = 0, right = 0;
        while(right < nums.length){
            sum += nums[right]; //调整右侧范围，加入新元素到窗口
            right++;
            
            while(left < right && sum > target){ //如果窗口内的和大于目标，则调整左侧范围
                sum -= nums[left];
                left++;
            }
            if(sum == target){   //如果窗口内的和等于目标，则更新最小操作次数
                min = Math.min(min, nums.length - (right - left));
            }
        }
        return min == Integer.MAX_VALUE ? -1 : min;
    }
}

class NumMatrix {
    int[][] dp;
    public NumMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        dp = new int[m+1][n+1];
        
        for(int i = 1; i <= matrix.length; i++){
            for(int j = 1; j <= matrix[0].length; j++){
                dp[i][j] = dp[i][j-1] - dp[i-1][j-1] + dp[i-1][j] + matrix[i-1][j-1];
            }
        };
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return dp[row1][col1] + dp[row2+1][col2+1] - dp[row1][col2+1] - dp[row2+1][col1];
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */

class NumMatrix {
    int[][] mat;
    public NumMatrix(int[][] matrix) {
        mat = matrix;
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = 0;
        for(int i = row1; i <= row2; i++){
            for(int j = col1; j <= col2; j++){
                sum += mat[i][j];
            }
        }
        return sum;
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */

class Solution {
    public boolean hasAllCodes(String s, int k) {
        if(s.length() < k) return false;    //字符串长度不足则返回false
        char[] bin = s.toCharArray();
        int n = s.length(), m = (int) Math.pow(2, k);
        HashSet<Integer> set = new HashSet<>(); //哈希表记录访问过的数字
        
        int num = Integer.parseInt(s.substring(0,k), 2);    //字符串以二进制转换为整数
        int mask = m-1; //掩码等于寻找长度-1
        set.add(num);
        
        for(int i = k; i < s.length(); i++){  //位运算，维护窗口内整数的值
            num <<= 1;  //位运算左移一位
            num &= mask;    //出界的位置被掩码遮盖
            if(bin[i] == '1') num++;
            set.add(num);
            if(set.size() == m) return true;    //如果哈希表长度等于2^k，则已经遍历了所有组合，返回true
        }
        return false;
    }
}

class Solution {
    public int divide(int dividend, int divisor) {
        if(dividend == 0) return 0;
        if(divisor == 1) return dividend;
        if(divisor == -1) return dividend == Integer.MIN_VALUE ? Integer.MAX_VALUE : -dividend; //当dividend为最小整数时，其负数溢出，此时返回Integer.MAX_VALUE
        int a = dividend, b = divisor;
        int sign = a > 0 && b > 0 || a < 0 && b < 0 ? 1 : -1;   //记录除数与被除数是否同号
        if(dividend > 0) a = -a;    //将除数与被除数转换为负数，因为负数能记录的数值比正数大1，防止溢出
        if(divisor > 0) b = -b;
        if(a > b) return 0; //被除数小于除数时返回0
        int res = 1;
        while(a <= b+b && b+b < 0){ //算法核心，快速乘法
            b += b; //除数每次翻倍，直到大于被除数
            res += res; //商的结果翻倍
        }
        res = sign == 1 ? res : -res;   //根据是否同号记录商
        
        divisor = dividend > 0 ? -divisor : divisor;  //当原有被除数是正数时，要将除数取反
        return res + divide(a-b, divisor);
    }
}

class Solution {
    public int maxProduct(String[] words) {
        
        int max = 0;
        int bin[] = new int[words.length];
        
        for(int i = 0; i < words.length; i++){
            int bit = 0;
            for(int j = 0; j < words[i].length(); j++){
                bit |= (1 << (words[i].charAt(j) - 'a'));
            }
            bin[i] = bit;
        }
        
        for(int i = 0; i < words.length; i++){
            for(int j = i+1; j < words.length; j++){
                if((bin[i] & bin[j]) == 0) max = Math.max(max, words[i].length() * words[j].length());
            }
        }
        return max;
    }
}

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][][] dp = new int[strs.length+1][m+1][n+1];
        
        for(int i = 1; i <= strs.length; i++){
            int zeros = 0, ones = 0;
            for(char c : strs[i-1].toCharArray()){
                if(c == '0') zeros++;
                else ones++;
            }
            
            for(int j = 0; j <= m; j++){
                for(int k = 0; k <= n; k++){
                    if(j - zeros >= 0 && k - ones >=0) dp[i][j][k] = Math.max(dp[i-1][j][k], dp[i-1][j-zeros][k-ones] + 1);
                    else dp[i][j][k] = dp[i-1][j][k];
                }
            }
        }
        return dp[strs.length][m][n];
    }
}

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m+1][n+1];
        
        for(String s : strs){   //记录每个位置对应的0和1数量
            int zeros = 0, ones = 0;
            for(char c : s.toCharArray()){
                if(c == '0') zeros++;
                else ones++;
            }
            
            for(int i = m; i >= zeros; i--){
                for(int j = n; j >= ones; j--){
                    dp[i][j] = Math.max(dp[i][j], dp[i-zeros][j-ones] + 1);
                }
            }
        }
        return dp[m][n];
    }
}

class Solution {
    String[] s;
    int[] zeros, ones;
    int[][][] memo;
    public int findMaxForm(String[] strs, int m, int n) {
        s = strs;
        zeros = new int[strs.length];
        ones = new int[strs.length];
        memo = new int[strs.length][m+1][n+1];
        
        for(int i = 0; i < strs.length; i++){   //记录每个位置对应的0和1数量
            for(int j = 0; j < strs[i].length(); j++){
                if(s[i].charAt(j) == '0') zeros[i]++;
                else ones[i]++;
            }
        }
        return dfs(0, m, n);
    }
    
    private int dfs(int i, int zero, int one){
        if(i >= s.length){
            return 0;
        }
        if(memo[i][zero][one] != 0) return memo[i][zero][one];
        
        int maxPossibleSubset = 0;
        
        if(zero-zeros[i] >= 0 && one-ones[i] >= 0){
            maxPossibleSubset = 1 + dfs(i+1, zero-zeros[i], one-ones[i]);
        }
        memo[i][zero][one] = Math.max(maxPossibleSubset, dfs(i+1, zero, one));
        return memo[i][zero][one];
        
    }
}

class Solution {
    public int minimumLines(int[][] stockPrices) {
        if(stockPrices.length == 1) return 0;
        
        Arrays.sort(stockPrices, (a,b) -> a[0] - b[0]);
        int count = 1, lastX = 0, lastY = 0;
        
        for(int i = 1; i < stockPrices.length; i++){
            int x = stockPrices[i][0] - stockPrices[i-1][0];
            int y = stockPrices[i][1] - stockPrices[i-1][1];
            
            int k = lastX * y - lastY * x;
            if(k != 0) count++;
            lastX = x;
            lastY = y;
        }
        return count;
    }
}

class Solution {
    public int maximumBags(int[] capacity, int[] rocks, int additionalRocks) {
        int[] diff = new int[capacity.length];
        for(int i = 0 ; i < capacity.length; i++){
            diff[i] = capacity[i] - rocks[i];
        }
        
        Arrays.sort(diff);
        int i = 0;
        while(additionalRocks > 0 && i < diff.length){
            additionalRocks -= diff[i];
            i++;
        }
        return additionalRocks >= 0 ? i : i - 1;
    }
}

class Solution {
    int n;
    int[] p;
    String newString;
    public int countSubstrings(String s) {
        n = s.length();
        StringBuffer sb = new StringBuffer();
        if(n == 0) {   //对字符串进行处理
            sb.append("^$");
        }
        else{
            sb.append("^");
            for(int i = 0; i < s.length(); i++){
                sb.append('#');
                sb.append(s.charAt(i));
            }
            sb.append("#$");
        }
        p = new int[sb.length()];
        newString = sb.toString();
        
        return manacher();
    }
    
    private int manacher(){
        int res = 0, c = 0, r = 0;
        for(int i = 1; i < newString.length()-1; i++){
            int m = 2 * c - i;
            if(i < r) p[i] = Math.min(r-i, p[m]);
            
            while(newString.charAt(i+p[i]+1) == newString.charAt(i-p[i]-1)){    //中心拓展
                p[i]++;
            }
            
            if(i+p[i] > r){ //更新c与r
                c = i;
                r = i + p[i];
            }
            res += (p[i]+1)/2;  //向上取整
        }
        return res;
    }
}

class Solution {
    String word;
    public int countSubstrings(String s) {
        word = s;
        int ret = 0;
        for(int i = 0; i < s.length(); i++){
            ret+=count(i);
        }
        return ret;
    }
    
    private int count(int i){
        int count = 1, left = i-1, right = i+1;

        while(left >= 0 && right < word.length() && word.charAt(left) == word.charAt(right)){
            count++;
            left--;
            right++;
        }
        
        left = i;
        right = i+1;
        
        while(left >= 0 && right < word.length() && word.charAt(left) == word.charAt(right)){
            count++;
            left--;
            right++;
        }
        return count;
    }
}

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        
        int[][] dp = new int[m+1][n+1];
        dp[0][1] = 1;
        
        for(int x = 1; x < m+1; x++){
            for(int y = 1; y < n+1; y++){
                if(obstacleGrid[x-1][y-1] == 0){
                    dp[x][y] = dp[x][y-1] + dp[x-1][y];
                }
            }
        }
        return dp[m][n];
    }
}

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

class Solution {
    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        if(original == null) return null;
        if(original.equals(target)) return cloned;
        
        TreeNode left = getTargetCopy(original.left, cloned.left, target);
        if(left != null) return left;
        else return getTargetCopy(original.right, cloned.right, target);
    }
}

class Solution {
    public int largestCombination(int[] candidates) {
        int[] bin = new int[31];
        int res = 0;
        for(int candidate : candidates){
            int count = 0;
            while(count < 31){
                if((candidate & 1) == 1){
                    bin[count]++;
                }
                candidate = candidate >> 1; 
                count++;
            }
        }
        for(int time : bin){
            res = Math.max(res, time);
        }
        return res;
    }
}

class Solution {
    public int maxConsecutive(int bottom, int top, int[] special) {
        int res = 0;
        int lastRoom = bottom-1;
        Arrays.sort(special);
        
        for(int room : special){
            int temp = room - lastRoom - 1;
            res = Math.max(res, temp);
            lastRoom = room;
            
        }
        int temp = top - lastRoom;
        res = Math.max(res, temp);
        
        return res;
    }
}

/**
 * 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 {
    public int deepestLeavesSum(TreeNode root) {
        Deque<TreeNode> q = new LinkedList<>();
        int res = 0;
        
        q.offer(root);
        
        int level = q.size();
        
        while(!q.isEmpty()){
            int sum = 0;
            for(int i = 0; i < level; i++){
                TreeNode curr = q.poll();
                sum += curr.val;
                if(curr.left != null) q.offer(curr.left);
                if(curr.right != null) q.offer(curr.right);
            }
            res = sum;
            level = q.size();
        }
        return res;
    }
}

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        HashMap<Integer, List<int[]>> edges = new HashMap<>(); 
        
        for(int[] time : times){    //建立有向边
            int source = time[0] - 1, kid = time[1] - 1, cost = time[2];    //注意index需要-1
            List<int[]> list = edges.getOrDefault(source, new ArrayList<>());
            list.add(new int[]{kid, cost});    //建立起点——终点映射
            edges.put(source, list);
        }
        
        int[] visited = new int[n];
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> a[1] - b[1]);    //优先级队列，最小堆每次访问距离最近的节点
        
        int start = k-1;
        dist[start] = 0;
        pq.offer(new int[]{start, 0});  //start为初始节点，后面的距离为了实现优先级队列
        
        while(!pq.isEmpty()){
            int[] curr = pq.poll();
            int source = curr[0];

            if(visited[source] == 1) continue;
            visited[source] = 1;
            
            List<int[]> children = edges.getOrDefault(source, new ArrayList<>());   //获取当前起点的所有边
            for(int[] child : children){
                int kid = child[0], cost = child[1];
                
                if(cost + dist[source] < dist[kid]){    //如果新的距离小于之前的最小距离，则更新距离并将新的起点加入优先级队列
                    dist[kid] = cost + dist[source];
                    pq.offer(new int[]{kid, dist[kid]});    //更新的距离是从出发节点到当前节点的距离，每次优先访问最近的节点
                }
            }
        }
        
        int res = 0;
        
        for(int d : dist){  //最后遍历，距离的最大值就是结果
            res = Math.max(res, d);
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}