当前位置：网站首页>[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;
}
}
边栏推荐
- Createanonymousthreadx passes parameters to anonymous threads
- Express scaffold creation
- 正态分布（高斯分布）
- [sword finger offer] interview question 25 Merge two ordered linked lists
- PHP security development 15 user password modification module
- [sword finger offer] interview question 24 Reverse linked list
- 2022 ICML | Pocket2Mol: Efficient Molecular Sampling Based on 3D Protein Pockets
- Implementation of homepage header function in PHP development blog system
- Collection of some compatibility issues
- 利用Javeswingjdbc基于mvc设计系统
猜你喜欢
SQL notes
Record a troubleshooting process - video call cannot be picked up
A simple understanding of consistent hash
Express framework knowledge - Art template template, cookie, session
约瑟夫问题
剑指 Offer 56 - I. 数组中数字出现的次数
![[try to hack] upload labs (temporarily write to 12)](/img/df/dbb78121f7428e25ffb73cfc43ce1b.png)
[try to hack] upload labs (temporarily write to 12)
Ultra quicksort reverse sequence pair
Collection of wrong questions in soft test -- morning questions in the first half of 2010
2022 ICLR | CONTRASTIVE LEARNING OF IMAGE- AND STRUCTURE BASED REPRESENTATIONS IN DRUG DISCOVERY
随机推荐
Vercel uses HTTP caching
Small program imitating Taobao Jiugong grid sliding effect
你的一对一会议效率低下，你可以这么做！
Powershell 加域 Add-Computer模块
A simple understanding of consistent hash
Set properties \ classes
Ultra quicksort reverse sequence pair
SEO specification
是“凯撒密码”呀。(*‘▽‘*)*
How to implement a custom jdbc driver in only four steps?
Vercel 使用 HTTP 缓存
Ctfshow common postures (821-830)
Sword finger offer 56 - I. number of occurrences in the array
CTFSHOW SQL注入篇（211-230）
Latex operation
Conception d'un système basé sur MVC avec javaswing JDBC
2022 ICLR | CONTRASTIVE LEARNING OF IMAGE- AND STRUCTURE BASED REPRESENTATIONS IN DRUG DISCOVERY
Win8.1和Win10各自的优势
The differences between the four startup modes of activity and the applicable scenarios and the setting methods of the two startup modes
Redis