【滑动窗口】长度最小的子数组|无重复字符的最长子串|最大连续1的个数 III|将 x 减到 0 的最小操作数

本文主要是介绍【滑动窗口】长度最小的子数组|无重复字符的最长子串|最大连续1的个数 III|将 x 减到 0 的最小操作数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

1.题目解析:

2.算法原理

(1)方法一:暴力列举出所有的子数组的和

时间复杂度:O(n**2):枚举所有子数组O(n**2)

(2)方法二:

利用单调性(两个指针都不回退),使用"同向双指针"(其实就是滑动窗口)来优化

那么滑动窗口过程是怎么样的?

<1>left  = 0,rght  = 0

<2>进窗口

<3>判断 并决定什么时候出窗口

(其中二三步是循环的)

还有一步更新结果:这一步可能在<2>,也可能在<3>

以【2,3,1,2,4,3】为例模拟这个过程

开始left和right都指向2(第一个元素),

然后开始进窗口(right++),right指向3,sum从0变为2,

然后进行判断,如果sum>target,更新结果并出窗口(也就是left++);如果sum<=target,继续进窗口(也就是right++)

正确性验证:

利用单调性,规避了很多没有必要的枚举行为(也就是当 sum>target时,right不用继续++)

 时间复杂度:O(N)

最坏情况:left和right都走到数组的最后,也就是N+N=2N

3.代码实现

class Solution {public int minSubArrayLen(int target, int[] nums) {int sum = 0;int ret = Integer.MAX_VALUE;for(int left=0,right=0;right<nums.length;right++) {sum+=nums[right];//进窗口while(sum>=target) {//判断ret = Math.min(right-left+1,ret);//更新结果sum-=nums[left];left++;}}//要考虑特殊情况:不存在return ret==Integer.MAX_VALUE ? 0:ret;}
}

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

1.题目解析:

2.算法原理

方法一:暴力枚举 + 哈希表(判断字符是否重复出现) 

时间复杂度:O(N**2)

方法二:利用规律,使用滑动窗口来解决问题

<1>left  = 0,rght  = 0

<2>进窗口(right++)—>让字符进入哈希表

<3>判断(窗口内是否出现重复字符)

有重复字符就出窗口(left++),从哈希表中删除该字符,这个过程需要一直重复,直到left找到重复的字符

<4>更新结果:在出完窗口到没有重复字符后就统计结果

3.代码实现

class Solution {public int lengthOfLongestSubstring(String s) {char[] ss = s.toCharArray();//字符串转为字符数组int[] hash = new int[128]; //用数组模拟哈希表int len = 0;for(int left=0,right=0;right<s.length();right++) {//进窗口hash[ss[right]]++;while(hash[ss[right]]>1) {//有重复字符//删除hash[ss[left]]--;//出窗口left++;}//更新结果len = Math.max(len,right-left+1);}return len;}
}

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

1.题目解析:

2.算法原理:

问题转化:找出最长的子数组,0的个数不超过k个

方法一:暴力枚举+zero计数器

方法二:在暴力的情况下不让right回退—>滑动窗口

<1>left  = 0,rght  = 0

<2>进窗口:right++,如果是1,无视;如果是0,计数器+1

<3>判断(zero>k) 并决定什么时候出窗口(left++,计数器-1)

<4>更新结果:出窗口结束

3.代码实现:

class Solution {public int longestOnes(int[] nums, int k) {int count=0;int zero=0;for(int left=0,right=0;right<nums.length;right++) {//进窗口if(nums[right]==0){zero++;}while(zero>k) {//判断:0的个数超过k个//出窗口if(nums[left]==0) {zero--;}left++;}count=Math.max(count,right-left+1);}return count;}
}

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

1.题目解析:

2.算法原理:

正难则反:找出最长的子数组的长度(len),所有元素的和正好等于sum-x(target),那么最后求的就是n-len的最小值

<1>left  = 0,rght  = 0

<2>进窗口—>Sum+=nums[right]

<3>判断 Sum>target(此处不应该有==,因为要等于不能出窗口)

并决定什么时候出窗口—>sum-=nums[left]

<4>更新结果:这个时候需要加上判断sum==target

3.代码实现:

class Solution {public int minOperations(int[] nums, int x) {int Sum=0;for(int a:nums) Sum+=a;int sum=0;int target = Sum-x;//处理细节if(target<0) {return -1;}int ret=-1;for(int left=0,right=0;right<nums.length;right++) {//进窗口sum+=nums[right];//判断while(sum>target) {//出窗口sum-=nums[left++];}//更新结果if(sum==target) {ret=Math.max(right-left+1,ret);}}return (ret==-1)?(-1):(nums.length-ret);}
}

这篇关于【滑动窗口】长度最小的子数组|无重复字符的最长子串|最大连续1的个数 III|将 x 减到 0 的最小操作数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/828821

相关文章

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

poj2406(连续重复子串)

题意:判断串s是不是str^n,求str的最大长度。 解题思路:kmp可解,后缀数组的倍增算法超时。next[i]表示在第i位匹配失败后,自动跳转到next[i],所以1到next[n]这个串 等于 n-next[n]+1到n这个串。 代码如下; #include<iostream>#include<algorithm>#include<stdio.h>#include<math.

poj3261(可重复k次的最长子串)

题意:可重复k次的最长子串 解题思路:求所有区间[x,x+k-1]中的最小值的最大值。求sa时间复杂度Nlog(N),求最值时间复杂度N*N,但实际复杂度很低。题目数据也比较水,不然估计过不了。 代码入下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring

spoj705( 求不相同的子串个数)

题意:求串s的不同子串的个数 解题思路:任何子串都是某个后缀的前缀,对n个后缀排序,求某个后缀的前缀的个数,减去height[i](第i个后缀与第i-1 个后缀有相同的height[i]个前缀)。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstrin

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

poj 1287 Networking(prim or kruscal最小生成树)

题意给你点与点间距离,求最小生成树。 注意点是,两点之间可能有不同的路,输入的时候选择最小的,和之前有道最短路WA的题目类似。 prim代码: #include<stdio.h>const int MaxN = 51;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int P;int prim(){bool vis[MaxN];

poj 2349 Arctic Network uva 10369(prim or kruscal最小生成树)

题目很麻烦,因为不熟悉最小生成树的算法调试了好久。 感觉网上的题目解释都没说得很清楚,不适合新手。自己写一个。 题意:给你点的坐标,然后两点间可以有两种方式来通信:第一种是卫星通信,第二种是无线电通信。 卫星通信:任何两个有卫星频道的点间都可以直接建立连接,与点间的距离无关; 无线电通信:两个点之间的距离不能超过D,无线电收发器的功率越大,D越大,越昂贵。 计算无线电收发器D

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

poj 1734 (floyd求最小环并打印路径)

题意: 求图中的一个最小环,并打印路径。 解析: ans 保存最小环长度。 一直wa,最后终于找到原因,inf开太大爆掉了。。。 虽然0x3f3f3f3f用memset好用,但是还是有局限性。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#incl