您的位置:首页 > 娱乐 > 八卦 > 网页游戏网站7_开发公司总结计划_义乌最好的电商培训学校_2022年适合小学生的新闻

网页游戏网站7_开发公司总结计划_义乌最好的电商培训学校_2022年适合小学生的新闻

2024/12/23 8:39:22 来源:https://blog.csdn.net/2301_80251684/article/details/144273249  浏览:    关键词:网页游戏网站7_开发公司总结计划_义乌最好的电商培训学校_2022年适合小学生的新闻
网页游戏网站7_开发公司总结计划_义乌最好的电商培训学校_2022年适合小学生的新闻

目录

1.长度最小的子数组

2.无重复字符的最长子串

3.最大连续1的个数

4.将X减到0的最小操作数

5.水果成篮

6.找到字符串所有字母异位词

7.串联所有单词的子串

8.最小覆盖子串


滑动窗口

滑动窗口是一种在数据序列(如数组、字符串等)上进行操作的技术。它通过维护一个固定大小(或可变大小)的窗口,在序列上滑动这个窗口来处理数据。这个窗口可以是连续的元素区间,通过不断地移动窗口,对窗口内的数据进行各种操作,比如统计窗口内元素的和、最大值、最小值等。

1.长度最小的子数组

209. 长度最小的子数组 - 力扣(LeetCode)


题目描述

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 

子数组

 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度如果不存在符合条件的子数组,返回 0 。


示例 1:

输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2:

输入:target = 4, nums = [1,4,4]
输出:1

示例 3:

输入:target = 11, nums = [1,1,1,1,1,1,1,1]
输出:0

解法:滑动窗口

算法思路

1.用两个指针left和right来控制窗口大小

2.每次right++后,sum加上right所指向的值(进窗口)

3.循环判断sum的值,如果大于等于target,将len和窗口长度做比较,将较小长度赋给len(判断)

4.在每次判断过程中,符合判断条件(sum>=target)就将left所指元素从sum减去,并left++(出窗口)


JAVA算法代码:

class Solution {public int minSubArrayLen(int target, int[] nums) {int left=0;int right=0;int sum=0;int len=Integer.MAX_VALUE;for(;right<nums.length;right++){
sum+=nums[right];
while(sum>=target){
len=Math.min(len,right-left+1);
sum-=nums[left++];
}}
return len==Integer.MAX_VALUE?0:len;}
}

2.无重复字符的最长子串

3. 无重复字符的最长子串 - 力扣(LeetCode)


题目描述

给定一个字符串 s ,请你找出其中不含有重复字符的最长子串的长度。


示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

解法:滑动窗口

算法思路

1.用数组模拟hash表,每次进窗口,对应hash表的值++

2.判断,进完窗口后,判断right所指的值在hash表中的值是否>1,如果大于1,说明当前这个元素在窗口中出现过

3.出窗口,不停的对left所指值在hash中对应的值++,直到right在hash中对应的值为<=1

4.循环结束,说明窗口里无重复元素,然后让当前窗口长度和之前最大窗口长度比较,得出最大长度

5.right++

6.hash表中的值,是每个字符在窗口中出现的次数


 JAVA算法代码

class Solution {public int lengthOfLongestSubstring(String ss) {int n=ss.length();
char[]s=ss.toCharArray();
int ret=0;
int []hash=new int[128];
int left=0;
int right=0;while(right<n){
hash[s[right]]++;
while(hash[s[right]]>1)
hash[s[left++]]--;
ret=Math.max(ret,right-left+1);
right++;
}
return ret;}
}

3.最大连续1的个数

1004. 最大连续1的个数 III - 力扣(LeetCode)


题目描述

给定一个二进制数组 nums 和一个整数 k,假设最多可以翻转 k 个 0 ,则返回执行操作后 数组中连续 1 的最大个数 。


示例 1:

输入:nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出:6
解释:[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1,最长的子数组长度为 6。

示例 2:

输入:nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出:10
解释:[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1,最长的子数组长度为 10。

解法:滑动窗口

算法思路

1.不要想怎么翻转0,我们可以让一个区间的0的个数不超过k个就行,然后求这个区间的最大长度

2.right控制窗口的右,left控制窗口的左

3.进窗口,判断right所指元素是不是0,如果是zero就++(进窗口)

4.判断区间内0元素的个数是否超过k,超过需要进行出窗口操作(判断)

5.看left所指元素是不是为0,是的话,zero--,继续判断zero的值是否超过k(出窗口)

6.只要zero的值不超过k,每一次都需要获取新的窗口大小和之前最大窗口大小作比较,然后给最大窗口赋值


JAVA算法代码

class Solution {public int longestOnes(int[] nums, int k) {int ret=0;int left=0;int right=0;
int zero=0;
while(right<nums.length){
if(nums[right]==0)zero++;while(zero>k){
if(nums[left++]==0)zero--;
}
ret=Math.max(ret,right-left+1);
right++;
}
return ret;}
}

4.将X减到0的最小操作数

1658. 将 x 减到 0 的最小操作数 - 力扣(LeetCode)


题目描述

给你一个整数数组 nums 和一个整数 x 。每一次操作时,你应当移除数组 nums 最左边或最右边的元素,然后从 x 中减去该元素的值。请注意,需要 修改 数组以供接下来的操作使用。

如果可以将 x 恰好 减到 0 ,返回 最小操作数 ;否则,返回 -1 。


示例 1:

输入:nums = [1,1,4,2,3], x = 5
输出:2
解释:最佳解决方案是移除后两个元素,将 x 减到 0 。

示例 2:

输入:nums = [5,6,7,8,9], x = 4
输出:-1

示例 3:

输入:nums = [3,2,20,1,1,3], x = 10
输出:5
解释:最佳解决方案是移除后三个元素和前两个元素(总共 5 次操作),将 x 减到 0 。

解法:滑动窗口

算法思路:

1.由题目可以知道,我们只能从数组的两边进行操作,要使两边的数的和等于x,并使数的个数最小

2.将这个问题转化为求中间数组的最大长度,使其和等于整个数组的和减去x的值

3.定义两个指针,使用滑动窗口,每次循环进入窗口,然后循环判断窗口内的元素和是否大于target,大于就将最左边的元素减去(出窗口),更新窗口的最大长度

4.如果ret(记录窗口长度的)仍然是初始的-1,那么整个数组没有符合的数组,否则返回数组长度减去ret,即为需要删除的最小元素个数


JAVA算法代码

class Solution {public int minOperations(int[] nums, int x) {int sum=0;for(int a:nums)sum+=a;int target=sum-x;if(target<0)return -1;int ret=-1;int tmp=0;
for(int left=0,right=0;right<nums.length;right++){
tmp+=nums[right];
while(tmp>target){tmp-=nums[left++];
}
if(tmp==target)ret=Math.max(ret,right-left+1);
}
if(ret==-1)return -1;
else return nums.length-ret;}
}

5.水果成篮

904. 水果成篮 - 力扣(LeetCode)


题目描述

你正在探访一家农场,农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示,其中 fruits[i] 是第 i 棵树上的水果 种类 。

你想要尽可能多地收集水果。然而,农场的主人设定了一些严格的规矩,你必须按照要求采摘水果:

  • 你只有 两个 篮子,并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
  • 你可以选择任意一棵树开始采摘,你必须从 每棵 树(包括开始采摘的树)上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次,你将会向右移动到下一棵树,并继续采摘。
  • 一旦你走到某棵树前,但水果不符合篮子的水果类型,那么就必须停止采摘。

给你一个整数数组 fruits ,返回你可以收集的水果的 最大 数目。


示例 1:

输入:fruits = [1,2,1]
输出:3
解释:可以采摘全部 3 棵树。

示例 2:

输入:fruits = [0,1,2,2]
输出:3
解释:可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘,则只能采摘 [0,1] 这两棵树。

示例 3:

输入:fruits = [1,2,3,2,2]
输出:4
解释:可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘,则只能采摘 [1,2] 这两棵树。

示例 4:

输入:fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出:5
解释:可以采摘 [1,2,1,1,2] 这五棵树。

解法:滑动窗口

算法思路:

1.使用数组充当hash表

2.进窗口,先记录水果的种类,判断水果是否在篮中,没在kinds++,篮中对应水果个数++,即水果对应的hash表中的位置++

3.循环判断水果种类是否大于2,不断地减去最左边的水果,当某个水果的个数减为0时,kinds--

4.更新水果篮中水果的最大个数


JAVA算法代码

class Solution {public int totalFruit(int[] fruits) {int n=fruits.length;int []hash=new int[n+1];
int kinds=0;
int ret=0;
for(int left=0,right=0;right<fruits.length;right++){
int in=fruits[right];
if(hash[in]==0)kinds++;
hash[in]++;while(kinds>2){
int out=fruits[left++];
hash[out]--;
if(hash[out]==0)kinds--;
}ret=Math.max(ret,right-left+1);
}
return ret;}
}

6.找到字符串所有字母异位词

438. 找到字符串中所有字母异位词 - 力扣(LeetCode)


题目描述

给定两个字符串 s 和 p,找到 s 中所有 p 的 异位词的子串,返回这些子串的起始索引。不考虑答案输出的顺序。


示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

 示例 2:

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

解法:滑动窗口

算法思路:

1.自定义一个hash表1,用于存储pp字符串中各个字符的个数

2.使用滑动窗口,控制窗口内的元素个数和pp字符串的字符个数相等,用count记录有效字符的个数

3.常规的进窗口,判断,出窗口

4.每次将窗口大小控制和pp字符数相等时,判断有效字符的个数是否和pp字符数相等,如果相等,将窗口的左下标添加到要返回的顺序表中


JAVA算法代码:

class Solution {public List<Integer> findAnagrams(String ss, String pp) {List<Integer>ret=new ArrayList<>();
char[]s=ss.toCharArray();
char[]p=pp.toCharArray();
int []hash1=new int[26];
for(char a:p)hash1[a-'a']++;
int []hash2=new int[26];
int m=p.length;
for(int left=0,right=0,count=0;right<s.length;right++){
char in=s[right];
if(++hash2[in-'a']<=hash1[in-'a'])count++;
while(right-left+1>m){
char out=s[left++];
if(hash2[out-'a']--<=hash1[out-'a'])count--;
}if(count==m)ret.add(left);
}
return ret;}
}

7.串联所有单词的子串

30. 串联所有单词的子串 - 力扣(LeetCode)


题目描述

给定一个字符串 s 和一个字符串数组 words words 中所有字符串 长度相同

 s 中的 串联子串 是指一个包含  words 中所有字符串以任意顺序排列连接起来的子串。

  • 例如,如果 words = ["ab","cd","ef"], 那么 "abcdef", "abefcd""cdabef", "cdefab""efabcd", 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串,因为他不是任何 words 排列的连接。

返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。


示例 1:

输入:s = "barfoothefoobarman", words = ["foo","bar"]
输出:[0,9]
解释:因为 words.length == 2 同时 words[i].length == 3,连接的子字符串的长度必须为 6。
子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。

示例 2:

输入:s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出:[]
解释:因为 words.length == 4 并且 words[i].length == 4,所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。

示例 3:

输入:s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出:[6,9,12]
解释:因为 words.length == 3 并且 words[i].length == 3,所以串联子串的长度必须为 9。
子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。
子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。
子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。

解法:滑动窗口

算法思路:

1.和上一题找到字符串所有的字母异位词方法类似,不同的是将字符换成了字符串

2.创建一个hash表存储words中字符串出现的次数

3.循环一个字符串长度的次数,因为每个字符串的长度相同,并且不知道子串是从哪个字符开始的

4.将left和right指向开始位置,每次向后走时,走len的长度,代表每次向后走一个单词

5.进窗口和,判断,出窗口均是以单词的长度为单位

6.如果窗口的长度和words总单词长度相等,并且有效单词的个数和words中的单词个数相等,那么,left所指位置的子串就是符合要求的,将其索引添加到ret顺序表中

7.查询完毕返回ret


JAVA算法代码

class Solution {public List<Integer> findSubstring(String s, String[] words) {List<Integer>ret=new ArrayList<>();Map<String,Integer>hash1=new HashMap<>();for(String str:words)hash1.put(str,hash1.getOrDefault(str,0)+1);int len=words[0].length();int m=words.length;for(int i=0;i<len;i++){
Map<String,Integer>hash2=new HashMap<>();
for(int left=i,right=i, count=0;right+len<=s.length();right+=len){String in=s.substring(right,right+len);
hash2.put(in,hash2.getOrDefault(in,0)+1);
if(hash2.get(in)<=hash1.getOrDefault(in,0))count++;
while(right-left+1>len*m){
String out=s.substring(left,left+len);
if(hash2.get(out)<=hash1.getOrDefault(out,0))count--;
hash2.put(out,hash2.get(out)-1);
left+=len;
}
if(count==m)ret.add(left);
}
}return ret;   }
}

8.最小覆盖子串

76. 最小覆盖子串 - 力扣(LeetCode)


题目描述

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 "" 。


示例 1:

输入:s = "ADOBECODEBANC", t = "ABC"
输出:"BANC"
解释:最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2:

输入:s = "a", t = "a"
输出:"a"
解释:整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中,
因此没有符合条件的子字符串,返回空字符串。

解法:滑动窗口+hash表

算法思路:

1.定义一个变量,统计tt字符串中字符的种类

2.创建一个hash表,记录tt字符串中每个字符的个数

3.创建一个hash表,记录滑动窗口中字符的个数,min记录符合条件子串的最小长度,begin记录最小子串的起始位置

4.进窗口,判断,出窗口

5.如果hash2中进窗口字符的个数和hash1中的一样多,那么count++,count用于记录hash2中符合条件的字符种类的数目

6.如果count和kinds相等,进行更新操作和出窗口操作

7.返回找到的最小子串,没有就返回空串


JAVA算法代码

class Solution {public String minWindow(String ss, String tt) {char[]s=ss.toCharArray();char[]t=tt.toCharArray();
char []hash1=new char[128]; 
int kinds=0;
for(char ch:t){if(hash1[ch]++==0)kinds++;
}
char []hash2=new char[128]; int min=Integer.MAX_VALUE,begin=-1;
for(int left=0,right=0,count=0;right<s.length;right++){
char in=s[right];
if(++hash2[in]==hash1[in])count++;
while(count==kinds){
if(right-left+1<min){
min=right-left+1;
begin=left;
}
char out=s[left++];
if(hash2[out]--==hash1[out])count--;
}
}
if(begin==-1)return new String();
else return ss.substring(begin,begin+min);}
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com