当前位置:网站首页>Sliding window problem review
Sliding window problem review
2022-07-06 05:01:00 【Xiaozhi re0】
List of articles
Of course, it can be in B Stand and find some teaching videos to learn
Simply speaking ; The idea of sliding windows is
(1) When the current conditions are not met , Expand to the right , When the conditions are met , Shrink the left border to the right , Get a solution and save it temporarily ,
(2) The first step of the cycle , Get another solution , Compare it with the first solution , Get the optimal solution and store it temporarily , And so on , Stop until the window reaches the right boundary .
1. Start with the basic problem
1.1 Power button [3]: Longest substring without repeating characters
Original link : Longest substring without repeating characters
Given a string s , Please find out that there are no duplicate characters in it Longest substrings The length of .
Example 1:
Input : s = "abcabcbb"
Output : 3
explain : Because the longest substring without repeating characters is "abc", So its length is 3.
Example 2:
Input : s = "bbbbb"
Output : 1
explain : Because the longest substring without repeating characters is "b", So its length is 1.
Example 3:
Input : s = "pwwkew"
Output : 3
explain : Because the longest substring without repeating characters is "wke", So its length is 3.
Please note that , Your answer must be Substring The length of ,"pwke" Is a subsequence , Not substring .
Example 4:
Input : s = ""
Output : 0
Tips :
0 <= s.length <= 5 * 104
s By the English letters 、 Numbers 、 Symbols and spaces
source : Power button (LeetCode)
link :https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
Use sliding window to solve
class Solution {
public int lengthOfLongestSubstring(String s) {
// Slide window idea ;
// Step right in the string ; If there is repetition, the left boundary shrinks ;
int n = s.length();
if(n<2)
return n;
// Here, we can use character array to mark char character ;
// Use int[] Array to count the frequency of characters ;
char[] cArr = s.toCharArray();
//s By the English letters 、 Numbers 、 Symbols and spaces ;
int[] nums = new int[128];
// Two pointers to the window ;
int left = 0;
int right = 0;
// The result is at least 1;
int res = 1;
// As long as the window does not exceed the bounds of the string ; Can operate ;
while(right<n){
// Record the frequency of the current character ;
nums[cArr[right]]++;
// Note that if the sliding is repeated, the left pointer boundary will be contracted ;
while(nums[cArr[right]]==2){
nums[cArr[left]]--;
left++;
}
// Calculated length ;
res = Math.max(res,right-left+1);
right++;
}
return res;
}
}
Also available set Non repetition of sets , Solve with pointer
class Solution {
public int lengthOfLongestSubstring(String s) {
// String matching process ;
if(s==null || s.length()==0)
return 0;
// Pointer solution ;
Set<Character> set = new HashSet<>();
int zhen = -1; int res =0;
for(int i =0;i<s.length();++i){
if(i!=0){
set.remove(s.charAt(i-1));
}
// Move without repetition ;
while(zhen+1<s.length() && !set.contains(s.charAt(zhen+1))){
set.add(s.charAt(zhen+1));
++zhen;
}
// The length of the non repeating characters in this segment ;
res = Math.max(res,zhen-i+1);
}
return res;
}
}
1.2 Power button [209]: Subarray with the smallest length
Original position : Subarray with the smallest length
Given a containing n An array of positive integers and a positive integer target .
Find the sum of the array ≥ target The smallest length of
Continuous subarray [numsl, numsl+1, ..., numsr-1, numsr] , And return its length .
If there is no sub array that meets the conditions , return 0 .
Example 1:
Input :target = 7, nums = [2,3,1,2,4,3]
Output :2
explain : Subarray [4,3] Is the smallest subarray in this condition .
Example 2:
Input :target = 4, nums = [1,4,4]
Output :1
Example 3:
Input :target = 11, nums = [1,1,1,1,1,1,1,1]
Output :0
Tips :
1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105
source : Power button (LeetCode)
link :https://leetcode-cn.com/problems/minimum-size-subarray-sum
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
The sliding window
class Solution {
public int minSubArrayLen(int target, int[] nums) {
// Slide window idea ;
int left = 0;
int right = 0;
int n = nums.length;
int sum = 0;
// Set a default length ;
int len = Integer.MAX_VALUE;
while(right < n){
// First move the right pointer , Add data ;
sum+=nums[right];
// if >= The target ; Because we need to satisfy the shortest subarray , Then shrink the left boundary ;
while(sum>=target){
len = Math.min(len,right - left +1);
// Shrink the left border ;
sum -= nums[left];
left++;
}
right ++;
}
// because len Initialized to the maximum ; Here we need to exclude ;
if(len == Integer.MAX_VALUE){
return 0;
}
return len;
}
}
2. Other questions
Basically, the idea of sliding window is used ; Additional requirements need to be considered ;
2.1 Power button [424] : The longest repeated character after replacement
Original link : The longest repeated character after replacement
Given a string s And an integer k .
You can select any character in the string , And change it to any other uppercase English characters . This operation can be performed up to k Time .
After doing this , return The length of the longest substring containing the same letter .
Example 1:
Input :s = "ABAB", k = 2
Output :4
explain : With two 'A' Replace with two 'B', vice versa .
Example 2:
Input :s = "AABABBA", k = 1
Output :4
explain :
Will the middle one 'A' Replace with 'B', The string changes to "AABBBBA".
Substring "BBBB" There is the longest repeating letter , The answer for 4.
Tips :
1 <= s.length <= 105
s It's made up of lowercase letters
0 <= k <= s.length
source : Power button (LeetCode)
link :https://leetcode-cn.com/problems/longest-repeating-character-replacement
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
Using the slide window , Match gradually to the right , At the same time, record the number of repeated characters in the current window ; If in Replace k Time
after , Approximate to the length of the window ; Then the length of the current window meets the conditions , Return to ;
class Solution {
public int characterReplacement(String s, int k) {
int len = s.length();
if(len < 2) return len;
// String to array ;
char[] Arr = s.toCharArray();
// An array that records character frequencies ;
int[] temp = new int[128];
// When the window slides , The current number of characters in the window at this time ;
int tempCount =0;
// final result ;
int res = 0;
// Sliding pointer ;
int left = 0;
int right = 0;
while(right < len){
temp[Arr[right]]++;
// Record the number ;
tempCount = Math.max(tempCount,temp[Arr[right]]);
right ++;
// If the current character cannot fill the window , You need to shrink the left window ;
if(tempCount+k < right - left){
temp[Arr[left]]--;
left++;
}
// Record the length at this time ;
res = Math.max(res,right - left);
}
return res;
}
}
2.2 Power button [76] : Minimum cover substring
Original position : Minimum cover substring
- Give you a string s 、 A string t .
- return s Covered by t The smallest string of all characters .
- If s There is no coverage in t Substring of all characters , Returns an empty string "" .
Be careful :
about t Duplicate characters in , The number of characters in the substring we are looking for must not be less than t The number of characters in the .
If s There is such a substring in , We guarantee that it is the only answer .
Example 1:
Input :s = "ADOBECODEBANC", t = "ABC"
Output :"BANC"
Example 2:
Input :s = "a", t = "a"
Output :"a"
Example 3:
Input : s = "a", t = "aa"
Output : ""
explain : t Two characters in 'a' Shall be included in s In the string of ,
Therefore, there is no qualified substring , Returns an empty string .
Tips :
1 <= s.length, t.length <= 105
s and t It's made up of English letters
source : Power button (LeetCode)
link :https://leetcode-cn.com/problems/minimum-window-substring
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
Parent string matching child string problem , Use the window to find the starting position of the matching character ;
How to ensure that matching characters are equal ?
- Use the character statistics array to count the number of occurrences of the current character , If it is consistent, it means it matches ;
class Solution {
public String minWindow(String s, String t) {
//.... at that time Didn't pay attention to , hold faLen and sonLen All the lengths are used s Of , Wrong shooting for a long time ;
//s: Parent string , t: Substring ;
int faLen = s.length();
int sonLen = t.length();
// Special circumstances exclude ;
if(faLen < sonLen){
return "";
}
// Here, first change the two strings into character arrays ;
char[] FaArr = s.toCharArray();
char[] SonArr = t.toCharArray();
// An array used to count the number of character frequencies ;
int[] FaCount = new int[128];
int[] SonCount = new int[128];
// The substring is fixed , Then give it directly ;
for(char c:SonArr){
SonCount[c]++;
}
// Record the current row in the window The number of substring character types included ;
int FaDistance = 0;
// The sliding window ;
int left = 0;
int right = 0;
// The length of the string that satisfies the condition in the parent string ;
int goodLen = Integer.MAX_VALUE;
// The qualified index starting point in the parent string ;
int begin = 0;
while(right < faLen){
// The current number of characters is the same ; Then increase the number of types of parent string ;
if(FaCount[FaArr[right]] < SonCount[FaArr[right]]){
FaDistance ++;
}
// Record the number of times the current character appears ;
FaCount[FaArr[right]]++;
// The parent string moves to the right first ;
right++;
// Be careful ; If you have completely found the child string in the parent string ; Consider starting optimization ;
while(FaDistance == sonLen){
// Here is the length , At the same time, record the starting point of the left window ;
if(goodLen > right-left){
goodLen = right-left;
begin = left;
}
// If the number of characters corresponding to the left pointer has matched the number of substrings ; Then the number of types of strings decreases ;
if(FaCount[FaArr[left]] == SonCount[FaArr[left]]){
FaDistance --;
}
FaCount[FaArr[left]]--;
// The left window is indented ;
left++;
}
}
// Here, we need to judge the length of the satisfied substring ;
if(goodLen ==Integer.MAX_VALUE ){
return "";
}
// Intercept the matching string ;
return s.substring(begin,begin+goodLen);
}
}
2.3 Power button [438] : Find all alphabetic words in the string
Original position : Find all alphabetic words in the string
Given two strings s and p, find s All in p Of Heterotopic words The string of ,
Returns the starting index of these substrings . Regardless of the order of the answer output .
Heterotopic words A string formed by rearrangement of the same letters ( Include the same string ).
Example 1:
Input : s = "cbaebabacd", p = "abc"
Output : [0,6]
explain :
Start index equals 0 The substring is "cba", It is "abc" The heterotopic words of .
Start index equals 6 The substring is "bac", It is "abc" The heterotopic words of .
Example 2:
Input : s = "abab", p = "ab"
Output : [0,1,2]
explain :
Start index equals 0 The substring is "ab", It is "ab" The heterotopic words of .
Start index equals 1 The substring is "ba", It is "ab" The heterotopic words of .
Start index equals 2 The substring is "ab", It is "ab" The heterotopic words of .
Tips :
1 <= s.length, p.length <= 3 * 104
s and p Only lowercase letters
source : Power button (LeetCode)
link :https://leetcode-cn.com/problems/find-all-anagrams-in-a-string
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
This question , stay 76 Based on the question , Minor changes ,
Which exactly matches the substring Length and character ;
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> list = new ArrayList<>();
// Sliding window problem ;
int FaLen = s.length();
int SonLen = p.length();
if(FaLen<SonLen){
return list;
}
// First convert the substring into an array ;
char[] SonArr = p.toCharArray();
// An array that counts the number of string frequencies ;
int[] FaCount = new int[128];
int[] SonCount= new int[128];
// Count the number of character occurrences of the substring ;
for(char c : SonArr){
SonCount[c]++;
}
// The number of character types matched in the parent string ;
int FaDistance =0;
// The current number of character types of the substring ;
int SonDistance = 0;
for(int i =0;i<SonCount.length;i++){
if(SonCount[i]>0){
SonDistance+=1;
}
}
int left =0;
int right =0;
while(right < FaLen){
// Slide the window to the right first ;
char rightChar = s.charAt(right);
// If the current substring has this character, then act ;
if(SonCount[rightChar]>0){
FaCount[rightChar]++;
if(FaCount[rightChar] == SonCount[rightChar]){
FaDistance++;
}
}
right++;
// When the substring length is matched ;
while(FaDistance == SonDistance){
// Mark the appropriate starting point ;
if(SonLen == right-left){
list.add(left);
}
char leftChar = s.charAt(left);
// The left window shrinks ;
if(SonCount[leftChar]>0){
FaCount[leftChar]--;
if(FaCount[leftChar]<SonCount[leftChar]){
FaDistance--;
}
}
left++;
}
}
return list;
}
}
2.4 Power button [ 567] Arrangement of strings
Original position : Arrangement of strings
Here are two strings s1 and s2 ,
Write a function to judge s2 Does it include s1 Permutation .
If it is , return true ; otherwise , return false .
let me put it another way ,s1 One of the permutations is s2 Of Substring .
Example 1:
Input :s1 = "ab" s2 = "eidbaooo"
Output :true
explain :s2 contain s1 One of the permutations of ("ba").
Example 2:
Input :s1= "ab" s2 = "eidboaoo"
Output :false
Tips :
1 <= s1.length, s2.length <= 104
s1 and s2 Only lowercase letters
source : Power button (LeetCode)
link :https://leetcode-cn.com/problems/permutation-in-string
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
and 438 The solution of the problem is consistent ;
class Solution {
public boolean checkInclusion(String s1, String s2) {
// Actually sum 438 Same question ;
//s1: Substring ; s2: Parent string ;
int SonLen = s1.length();
int FaLen = s2.length();
if(FaLen < SonLen){
return false;
}
// String to array ;
char[] SonArr = s1.toCharArray();
// An array of statistical character ratings ;
int[] SonCount = new int[128];
int[] FaCount = new int[128];
// Number of types of parent string ;
int FaDistance =0;
// The number of types of substrings ;
int SonDistance =0;
// First give the substring ;
for(char c:SonArr){
SonCount[c]++;
}
for(int i =0;i<SonCount.length;i++){
if(SonCount[i]>0){
SonDistance+=1;
}
}
// Sliding pointer ;
int left = 0;
int right = 0;
while(right<FaLen){
// If there are characters in the substring, operate again ;
char rightChar = s2.charAt(right);
if(SonCount[rightChar]>0){
FaCount[rightChar]++;
if(FaCount[rightChar]==SonCount[rightChar]){
FaDistance++;
}
}
right++;
// When the number of types of parent string matches enough ;
while(FaDistance == SonDistance){
// If it matches the sequence ; Go straight back to ;
if(right - left == SonLen){
return true;
}
// The left border is ready to shrink ;
char leftChar = s2.charAt(left);
if(SonCount[leftChar]>0){
FaCount[leftChar]--;
if(FaCount[leftChar] < SonCount[leftChar]){
FaDistance --;
}
}
left++;
}
}
return false;
}
}
边栏推荐
- Idea one key guide package
- [detailed steps of FreeRTOS shift value for the first time]
- [noip2008 improvement group] stupid monkey
- 集合详解之 Map + 面试题
- 关于es8316的音频爆破音的解决
- Weng Kai C language third week 3.1 punch in
- [NOIP2008 提高组] 笨小猴
- Postman管理测试用例
- Oracle query table index, unique constraint, field
- 从0到1建设智能灰度数据体系:以vivo游戏中心为例
猜你喜欢
行业专网对比公网,优势在哪儿?能满足什么特定要求?
F12 solve the problem that web pages cannot be copied
Leetcode dynamic planning day 16
Codeforces Round #804 (Div. 2)
Rce code and Command Execution Vulnerability
Postman关联
DMA use of stm32
ORM aggregate query and native database operation
Fuzzy -- basic application method of AFL
Idea one key guide package
随机推荐
Biscuits (examination version)
[NOIP2009 普及组] 分数线划定
Scala function advanced
ISP learning (2)
nacos-高可用seata之TC搭建(02)
Postman assertion
Codeforces Round #804 (Div. 2)
TCP three handshakes you need to know
Mongodb basic knowledge summary
2021 RoboCom 世界机器人开发者大赛-本科组(复赛)
GAMES202-WebGL中shader的編譯和連接(了解向)
[05-1, 05-02, 05-03] network protocol
Introduction of several RS485 isolated communication schemes
Fuzzy -- basic application method of AFL
idea一键导包
8. Static file
MPLS experiment
你需要知道的 TCP 三次握手
也算是學習中的小總結
Ora-01779: the column corresponding to the non key value saving table cannot be modified