外围网站做代理,徐州人才网档案查询,山东城乡和住房建设厅网站,做网站推广的工作好吗跟着代码随想录完成了 leetcode 209.长度最小的子数组#xff0c;学习到了滑动窗口的思想。于是做了904题。 题目意思是#xff0c;遍历数组#xff0c;找到包含两种元素的最长子串(字串就包含“连续”之意)#xff0c;返回其长度。因此可以利用滑动数组的思想。
想法过程… 跟着代码随想录完成了 leetcode 209.长度最小的子数组学习到了滑动窗口的思想。于是做了904题。 题目意思是遍历数组找到包含两种元素的最长子串(字串就包含“连续”之意)返回其长度。因此可以利用滑动数组的思想。
想法过程
滑动数组的基本实现为left在左缩小窗口right(i)遍历数组增大窗口。首先left固定不动通过right扩大窗口以达到“刚好”满足要求比如当前字串的和大于target见209题然后right固定不动通过left缩小窗口达到“极限”当窗口达到“刚好”不满足要求的边缘条件就用right扩大窗口。
怎么在滑动左边之后判断当前水果是两个种类还是一个可以通过现有的变量left、right、sum(当前遍历过的元素之和)吗不行。
增加什么变量变量记录两个种类v1 v2、及其数量c1 c2。
情况总结
1最开始c1c20第一个碰到的就算作第一个种类。v1 fruits[0]; c1; 2第二步此时只有一个种类。 fruits[i] 如果与当前水果种类相同c1; 如果不同增加种类v2 fruits[i]; c2; 3第三步如果当前水果种类属于v1,v2对应进行c1,c2 …… 4一直到某个ifruits[i]不属于当前v1,v2。 此时的窗口长度为 c1c2。 res Math.max(res,c1c2);
开始滑动窗口左侧 (left)目的直到窗口内部只剩下一个种类为止。 把此时的新种类 fruits[i] 增加到 v1或者 v2(主要取决于哪个为零)然后回到第二步直到跳出for循环。 唉考虑情况的时候不充分都是在debug过程中又考虑到了新情况。 错误的点
1除去最开始c1和才c2可能同时为零吗不可能窗口左侧极端情况为缩减到只剩一个 然后就需要接着往下判断。 [112]345 11[2]345 2跳出for循环后 res是返回值最初设定为-1。 目标字串可能在数组首部、尾部、中部(情况等价于① 窗口right小于fruit.length ② 窗口right等于fruit.length-1)。
代码
非常的冗余但运行成功。这里只做记录不推荐。
class _Solution904_2 {public int totalFruit(int[] fruits) {int res -1;int sum 0;//滑动窗口要遍历整个数组求出最大的//怎么在滑动左边之后判断当前数组是两个种类还是一个//可以通过现有的变量吗left right?不行是无规则的//增加什么变量两个种类、及其数量int c10,c20; //记录两个种类的数量int v1 -1,v2- 1; //记录两个种类int left0;for(int i 0; i fruits.length; i) {//最开始if(c1 0 c2 0) {v1 fruits[i];c1;continue;}//除去最开始c1和c2可能同时为零吗//不可能假设窗口左侧缩减到只剩一个 然后就需要接着扩大窗口。if(c2 0 || c1 0) { //目前只有一个种类//此时只有一个种类但不知道哪一个为空。//为什么不知道哪一个为空//因为 下文滑动窗口左侧缩减直到窗口只剩下一个种类的时候不知道是v1没了还是v2没了if(c2 0){if(fruits[i] v1) {c1;} else {v2 fruits[i];c2;}} else if(c1 0) {//c2不为空if (fruits[i] v2) {c2;} else {v1 fruits[i];c1;}}} else {//目前已经有两个种类if(fruits[i] v1) {c1;} else if(fruits[i] v2) {c2;} else { //当前的fruits[i]不属于v1 v2需要重新建立窗口res Math.max(res,c1c2);//while去掉一个种类while(c1 ! 0 c2 ! 0){if(fruits[left] v1) {c1--;left;} else if(fruits[left] v2) {c2--;left;}}if(c1 0) {//去掉一个种类之后要加上当前 种类v1 fruits[i];c1;}if(c2 0) {v2 fruits[i];c2;}}}}if(res -1) {//数组中只有两个种类 比如fruits [1,2,1]resc1c2;} else { //目标子串有可能是数组末尾 [0,1,2,2]res Math.max(res,c1c2);}return res;}
}//end class改进
1上述过程的 v1 v2 c1 c2 其实可以用 HashMap 替代 2请品味代码 res Math.max(res, right-left1); 的位置。
class Solution {public int totalFruit(int[] fruits) {MapInteger, Integer cnt new HashMapInteger, Integer();int left 0, res 0;for(int right 0; right fruits.length; right) {cnt.put(fruits[right], cnt.getOrDefault(fruits[right], 0) 1);while(cnt.size() 2) {cnt.put(fruits[left], cnt.get(fruits[left])-1);if(cnt.get(fruits[left]) 0) {cnt.remove(fruits[left]);}left;}res Math.max(res, right-left1);}return res;}
}
