当前位置:网站首页>[leetcode]- sliding window

[leetcode]- sliding window

2022-06-13 04:43:00 Pacifica_

Preface

Recording brush LeetCode Sliding window related problems encountered

209. Subarray with the smallest length

Sliding windows are not suitable for arrays with negative values

/** * Inferior   The sliding window  , Because all the special cases considered are if-else Take it out alone , Cause too much if-else Branch , On the one hand, the code is not concise enough , On the one hand, the implementation efficiency is also reduced  * ============= Here are four improvements =============================== * ========== During the improvement process, it can be clearly found that the greatest impact on the time is count function ======================================================== * ==== Because the sliding window is O(n) The algorithm is operated one element at a time , So maintain every sliding window with variable maintenance method ( Subarray ) And are desirable ,======= * ==== There is no need to call the method of loop every time to sum ================================================================= * =================================================================================================== **/
public int minSubArrayLen(int target, int[] nums) {
    
    int length = nums.length;
    /*  Improve one :  First of all, these two if-else It's totally unnecessary  if(length == 0){ return 0; } if(length == 1){ return nums[0] >= target ? 1 : 0; }*/
    int result = length + 1;
    int left = 0;
    int right = 0;
    /* Improvement 2 : *  This section is used to initialize the window , After changing this paragraph , Time has improved significantly , Maybe it's because each time count Method , and count The method itself is a loop , We should use the method of variable maintenance to find  *  The sum of the current subarray instead of the sum of the subarrays calculated every time the transform window  * while (right < length && count(nums, left, right) < target){ * right++; *}*/
    int count1 = 0;
    while (right < length){
    
        count1 += nums[right];
        if(count1 >= target){
    
            break;
        }else {
    
            right++;
        }
    }
    /*  Be careful 1 *  here right May have exceeded the length of the array ·  Special case  : All array elements do not add up to target, in other words  result  It may not have been modified , *  So it should not be returned directly in the end result, It's going back to  result == length + 1 ? 0 : result*/
    while (right < length){
    
        if(count1 >= target){
    
            result = Math.min(right - left + 1, result);
            /* Improve three : Even if the left Add one and right It doesn't matter if they overlap , At this point, the sum of the subarrays is 0, At the next cycle right Will add one , Never mind left Than right Big  if(left + 1 <= right) { count1 -= nums[left]; left++; }else { right++; left++; if(right < length){ count1 = nums[left]; } }*/
            count1 -= nums[left++];
        }else {
    
            right++;
            if(right < length){
    
                count1 += nums[right];
            }
        }
    }
    /*  Be careful 2  When all array elements do not add up to target Should return when 0*/
    return result == length + 1 ? 0 : result;
}
/*public int count(int[] nums, int left, int right){ if(left == right){ return nums[left]; } int count = 0; for(int i = left;i <= right && i < nums.length;i++){ count += nums[i]; } return count; }*/
// After finishing, it is :
public int minSubArrayLen(int target, int[] nums) {
    
    int length = nums.length;
    int result = length + 1;
    int left = 0;
    int right = 0;
    int count1 = 0;
    while (right < length){
    
        count1 += nums[right];
        if(count1 >= target){
    
            break;
        }else {
    
            right++;
        }
    }
    while (right < length){
    
        if(count1 >= target){
    
            result = Math.min(right - left + 1, result);
            count1 -= nums[left++];
        }else {
    
            right++;
            if(right < length){
    
                count1 += nums[right];
            }
        }
    }
    return result == length + 1 ? 0 : result;
}

904. Fruit baskets

public int totalFruit(int[] fruits) {
    
    int length = fruits.length;
    /*  Unnecessary special judgment : if(length == 1){ return 1; } if(length == 2){ return 2; }*/
    int left = 0;
    int right = -1;
    // Find an element different from the first element , Corresponding situation : The previous ones are all the same 
    for(int i = 1;i < length;i++){
    
        if(fruits[i] != fruits[left]){
    
            right = i;
            break;
        }
    }
    // special case  :  All numbers are the same 
    if(right == -1){
    
        return length;
    }
    int record1;
    int record2;
    int maxCount = right - left + 1;
    while (right < length - 1){
    
        // Two numbers of update records  
        record1 = fruits[left];
        record2 = fruits[right];
        while (right < length - 1 && (fruits[right + 1] == record1 || fruits[right + 1] == record2)){
    
            right++;
        }
        maxCount = Math.max(maxCount, (right - left + 1));
        int temp = right;
        while (fruits[temp] == fruits[right]){
    
            temp--;
        }
        left = temp + 1;
        // At this point either right The next one is a different number , or right >= length - 1 Then jump out of the loop , therefore right++ It's totally wrong 
        right++;
    }
    return maxCount;
}

76. Minimum cover substring (hard)

class Solution {
    
    private Map<Character,Integer> tMap = new HashMap<>();
    private Map<Character,Integer> resMap = new HashMap<>();
    public String minWindow(String s, String t) {
    
        if(s.length() == 0){
    
            return "";
        }
        int tLength = t.length();
        int sLength = s.length();
        for (int i = 0; i < tLength; i++) {
    
            char c = t.charAt(i);
            tMap.put(c,tMap.getOrDefault(c,0) + 1);
        }
        int l = 0;
        while (l < sLength && !tMap.containsKey(s.charAt(l))){
    
            l++;
        }
        int r = sLength - 1;
        while (r > l && !tMap.containsKey(s.charAt(r))){
    
            r--;
        }
        if(l > r){
    
            return "";
        }
        // The above code is putting s Both ends are not t All characters appearing in are eliminated , And then in the rest of the string newS To find the matching string in the 
        String newS = s.substring(l,r + 1);
        //len Record the length of the smallest window currently recorded during the operation 
        int len = 1000000000;
        int resl = 0;
        int resr = -1;
        //p1 Is the left border of the window , shrink windows ;p2 Is the right border of the window , enlarge a window 
        int p1 = 0;
        //p2 Starting from the negative is to deal with newS The case of a length of one , For example s:"a",t:"a"
        int p2 = -1;
        //p2<newS.length() - 1 It's easy to understand , When the right edge of the window reaches the end of the string, it is the termination condition of sliding 
        // But there may be p2 When the end of the string is reached ,p1 You can also continue to narrow the window to the right , So add another one p1<p2 Conditions 
        while (p1 < p2 || p2 < newS.length() - 1){
    
            // As long as the current window does not meet the conditions p2 Always shift to the right 
            while (p2 < newS.length() - 1 && !check()){
    
                p2++;
                char c = newS.charAt(p2);
                resMap.put(c,resMap.getOrDefault(c,0) + 1);
            }
            // The current window meets the conditions , It's about to be updated len as well as resl,resr, Ensure that at this time len The smallest is the smallest ,resl and resr Is the corresponding string subscript 
            if(check() && p2 - p1 +  1 < len){
    
                len = p2 - p1 +  1;
                resl = p1;
                resr = p2;
            }
            // The obtained window is qualified , So you can start to narrow the window and traverse to the right to find a better solution 
            if(p1<p2){
    
            char c = newS.charAt(p1++);
            //p1 At first, it must point to t Some characters in , The idea of contraction is to find the next t Some characters in 
            resMap.put(c,resMap.get(c) - 1);
            while (!tMap.containsKey(newS.charAt(p1))){
    
                p1++;
            }}
        }
        return (resr == -1) ? "" : newS.substring(resl,resr + 1);
    }
    public boolean check(){
    
        for (Map.Entry<Character, Integer> entry : tMap.entrySet()) {
    
            Character key = entry.getKey();
            Integer val = entry.getValue();
            if (resMap.getOrDefault(key, 0) < val) {
    
                return false;
            }
        }
        return true;
    }
}

674. The longest continuous increasing sequence ( Online processing / The sliding window )

The subsequence must be continuous . Variable l Maintain the length of the continuous sequence of the number currently traversed , that , When traversal to nums[i] when , If nums[i] > nums[i - 1],l Plus one , otherwise nums[i] It should be recalculated as the beginning of the new increment sequence , l Set as 1

public int findLengthOfLCIS(int[] nums) {
    
    int len = nums.length;
    int l = 1,maxL = 1; //maxL Maintain maximum length .l Initialize to 1, Corresponding  nums[0] 
    for(int i = 1;i < len;i++){
    
        if(nums[i] > nums[i - 1]){
    
            l++;
            maxL = Math.max(l,maxL);
        }
        else l = 1;
    }
    return maxL;
}

53. Maximum subarray and ( Online processing / The sliding window )

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

Traversing arrays from scratch , use sum Record the elements and... Of the subsequence traversed at this time , If sum Less than 0, That is, the sum of the subsequences traversed is less than 0, Because the topic is required to be a subsequence . So the sum of this element is 0 The subsequence of is a burden to the subsequence that follows , Because no matter what the sum of the following sequences is , If you want to sum this paragraph into 0 The subsequence of plus , The sum of the whole sequence becomes smaller , So if at the moment sum Less than 0, It is necessary to discard the currently traversed subsequence

Interview questions 17.24. Maximum submatrix

Problem solving ideas come from Solution to the problem
Is probably , For each line i, Will be the first i Go to the first place j That's ok (j = i,i + 1,…,row - 1) All the lines between “ Squeeze ” For a number , And then the one-dimensional array [ Maximum subarray and ] solve

public int[] getMaxMatrix(int[][] matrix) {
    
    int row = matrix.length;
    int column = matrix[0].length;
    int maxSum = Integer.MIN_VALUE,r1 = 0,c1 = 0,r2 = 0,c2 = 0,sum,r1Tmp = 0,c1Tmp = 0;
    int[] rowSum = new int[column]; // Currently being “ Squeeze ” The sum of each column in all rows of 
    for(int i = 0;i < row;i++){
      // For each line  i
        Arrays.fill(rowSum,0);
        for(int j = i;j < row;j++){
      // enumeration  j
            sum = 0;
            for(int k = 0;k < column;k++){
     
                rowSum[k] += matrix[j][k];  // seek i  To  j  The sum of each column in all rows 
                if(sum > 0) sum += rowSum[k]; 
                else{
        // The preceding sum is less than 0, Then discard , Make the sum of the current column as the new  sum, At the same time, update the row and column coordinates in the upper left corner 
                    sum = rowSum[k];
                    r1Tmp = i;
                    c1Tmp = k;
                }
                if(sum > maxSum){
      // If we get a sum larger than the maximum sum of the maintained submatrix , Update the four coordinates of the maintenance answer and maxSum
                    maxSum = sum;
                    r1 = r1Tmp;
                    c1 = c1Tmp;
                    r2 = j;
                    c2 = k;
                }
            }
        }
    }
    return new int[]{
    r1,c1,r2,c2};
}

363. The rectangular area does not exceed K And

The solution to this problem is not really like a sliding window , But the idea is very similar to the above two questions , So I put it together . It is suggested to compare the three questions together
First , Some rectangular regions in the original matrix are enumerated , That is, submatrix , So similar to the above [ Maximum submatrix ] subject , When enumerating a submatrix, each row of it “ Compress ” For a number , Get a one-dimensional array , Each number in this one-dimensional array represents the sum of elements in a row , Then calculate the matrix that these rows can form , The sum with the largest element sum can be , Of course, the maximum sum should not be greater than k

class Solution {
    
    public int maxSumSubmatrix(int[][] matrix, int k) {
    
        int rows = matrix.length, cols = matrix[0].length, max = Integer.MIN_VALUE;
        for (int l = 0; l < cols; l++) {
     //  Enumerate the left boundary 
            int[] rowSum = new int[rows]; 
            for (int r = l; r < cols; r++) {
     //  Enumerate right borders 
                for (int i = 0; i < rows; i++) {
    
                    rowSum[i] += matrix[i][r]; // Sum up the elements of each row between the left and right boundaries 
                }
                max = Math.max(max, findMax(rowSum, k)); // Find the matrix that can be composed of these rows between the left and right boundaries , The sum of the largest elements 
                if(max == k) return k; // Find something equal to k The answer of returns directly to , Save subsequent operations , It's also a pruning 
            }
        }
        return max;
    }
    private int findMax(int[] arr, int k) {
    
        int max = Integer.MIN_VALUE,sum;
        for (int i = 0;i < arr.length;i++) {
     // The first i Line can be the same as i+1,..., The first arr.length-1 Successive rows between rows form a matrix 
            sum = 0;
            for (int j = i; j < arr.length; j++) {
    
                sum += arr[j];
                if (sum > max && sum <= k) max = sum;
                if(max == k) return k;
            }
        }
        return max;

    }
}

You can see it , Actually findMax() Function is to find arr The largest subarray of an array and , It only requires that the sum of the largest subarray should not exceed k, So it's similar to [ Maximum subarray and ], The following optimizations can be made :

class Solution {
    
    public int maxSumSubmatrix(int[][] matrix, int k) {
    
    	//...
        int[] rowSum = new int[rows];  // take rowSum New new Change the operation to full fill to 0
        for (int l = 0; l < cols; l++) {
     //  Enumerate the left boundary 
            Arrays.fill(rowSum,0);
            //...
        }
        return max;
    }
    private int findMax(int[] arr, int k) {
    
        int sum = 0,max = Integer.MIN_VALUE;
        for(int i : arr){
    
            if(sum < 0) sum = 0;
            sum += i;
            max = Math.max(max,sum);
        }
        if(max <= k) return max; // The maximum subarray sum does not exceed k Just be satisfied , Can return directly , Otherwise, it will be calculated as before 
        max = Integer.MIN_VALUE;
        sum = 0;
        for (int i = 0;i < arr.length;i++) {
    
            //...
        }
        return max;
    }
}
原网站

版权声明
本文为[Pacifica_]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/164/202206130438414277.html