首页 > 编程语言 >【优选算法 — 滑动窗口】水果成篮 & 找到字符串中所有字母异位词

【优选算法 — 滑动窗口】水果成篮 & 找到字符串中所有字母异位词

时间:2024-11-11 20:50:35浏览次数:5  
标签:count 字符 right 窗口 异位 哈希 滑动 成篮 left

   

 


  水果成篮  


水果成篮


 

  题目描述  

因为只有两个篮子,每个篮子装的水果种类相同,如果从 0 开始摘,则只能摘 0 和 1 两个种类 ;

  • 因为当我们在两个果篮都装有水果的情况下,如果再走到下一颗果树,果树的水果种类不是果篮中的任意一种,则停止采摘;
  • 所以就是要找出一块连续的区域,这个连续的区域最多有两种类型的元素,并且在所有找到的符合条件的区域中,找出长度最长的区域;

通过上述例子,我们可以把题目描述最终简化成一个问题模型:

找出长度最长的子数组,子数组中的元素种类<=2


  解法:滑动窗口  

  • 定义 left 指针固定一个起点,然后定义 right 指针向后枚举;
  • 枚举出所有合适的子数组,然后返回所有子数组中长度最长的数组 ;

  • 模拟一个 hash 表 kinds,来统计水果出现的个数;
  • 每 right 遍历一个元素,就把该元素对应的 kinds[ fruits [ i ] ] ++;
  • 然后每次改变 kinds的元素 kinds[ fruits [ i ] ] ,都要判断 kinds 这个数组的有效元素个数是否小于3 ;

如果想不清楚进窗口和出窗口该怎么操作,就回到暴力枚举的基础上,来模拟出进出窗口的操作:

  1. left = 0 ,right = 0;new kinds[ ];
  2. 进窗口(kinds[fruit [ right ] ]++,right++)
  3. 循环判断 3,4,5(kinds.length 是否 >2)
  4. 出窗口(kinds[fruit [ left ] ]--,left++);
  5. 如果因为 kinds[ fruit [ left ] ]--,导致 kinds[fruit [ left ] ] 变成0,则要移除这个元素
  6. 更新结果(不断更新 ret 直到最后拿到最大值)

Map 官方文档


    编写代码: 

 

  正确写法  

  方法一:使用容器 Map  

  方法二:用数组模拟哈希表  

根据题目给的上述提示,为了降低执行用时,我们可以通过一个数组模拟哈希表


   找到字符串中所有字母异位词   


找到字符串中所有字母异位词


 

  1.先快速判断两个字符数相同的字符串是否是“异位词”  

对于这两个字符数相同的字符串,我们如何判断这两个字符串是一个异位词呢?


我们可以先分别对 这两个字符串 的 所有字符 进行排序,然后使用 双指针 依次比对这两个字符串对应的字符即可;

这个方法虽然可以达到目的,但是因为排序操作,使得时间复杂度太高了;

所以,如果是两个字符数相同的字符串,要比较是不是异位词,我们可以统计每一个字符出现的个数即可,因为异位词是不考虑顺序的。

所以我们可以通过哈希表,快速判断两个词是否是异位词:

   暴力解法   

   总结规律   

所以这个枚举的过程,都是从左到右枚举的,所以可以用滑动窗口的解法来解决:

   解法:滑动窗口 + 哈希表   


  • 之前做的关于滑动窗口的题目,窗口大小是不固定的,这题是第二种滑动窗口的题型,就是窗口大小固定(left 和 right 同时移动);
  • 只要定义的两个指针从始至终都是同向移动的,就是滑动窗口的题型;

  1. left = 0 , right = 0;
  2. 定义 hash1 统计 p 字符串中字符的 key,val
  3. 进窗口(定义 hash2,right++,hash2.get(s[ right ])++)
  4. 判断(right - left + 1 > m)(因为窗口大小固定,left 只需要移动一次,所以判断不用写成循环))
  5. 出窗口(hash2.get(s[ right ])--,left++,)
  6. 更新结果 ( check(hash1,hash2) ,返回 true,子串的首元素下标放入返回的 list 中)
  7. 循环 3 4 5 6

   优化 check()    


因为 s 和 p 都是小写字母,所以我们只需要创建一个大小为 26 的数组模拟哈希表即可,数组下标模拟的是哈希表的 key。

那么每次程序执行到调用 check() 的地方,check()中,仅仅需要比较 26 次每个元素的值是否相同即可。


   时间复杂度    

因此,在上述优化后,时间复杂度 O(26*N) —> O(N)。


因为我们这道题,哈希表存的是一个一个的字符,所以我们可以用字符数组来模拟哈希表,这时候,比较两个字符数组是非常快的;

但是,如果遇到哈希表存的 key,是一个一个的字符串,就不能再用数组模拟哈希表了;


   优化 check() 的判断条件   


我们如果直接调用 check(),来直接比较两个哈希表是否相同 ,是需要比较 26 次才可以出结果的;

如果换难一点的题,可能需要比较更多次,才可以知道两个两个哈希表是否相同,因此我们需要优化 check() 的判断条件;

做法:利用 count 来统计窗口中“有效字符”的个数,一定要注意有效字符的定义

我们要在进窗口的操作过程中,维护 count;

此时,hash1 和 hash2 的 都有一个 c;

  • 所以,在往 hash2 添加了一个字符后,这个字符在 hash1 中也有;
  • 并且这个字符在放入 hash2 后,修改后的个数数字,是小于等于hash1对应字符的个数数字的

满足以上两点,就可以称为是“有效字符”,而 count 就是用来统计这些字符的个数的。

right++,如果遍历到的字符放入 hash2 后,对应的 val 大于 hash1,则说明是无效字符,count不更新

此时,我们需要判断一下,count 是否等于3(p.length),如果 count 刚好等于3(p.length),说明此时,窗口中的字符全是有效字符;

所以一边通过进窗口操作更新哈希表,一边可以维护 count;当然,上面说的只是入窗口,出窗口也需要维护 count


思考:此时滑动窗口,right 指向新的字符 a,需要更新 count 吗?

是需要的;但是此时的窗口太大了,需要让 left++,并且从 hash2 中移出出窗口的元素;

并且在 left 向后移动的这一步的过程中,第一个 c 变成了多余元素,而第二个 c 变成有效元素;

所以在这一步 left 后挪的过程中,是不改变 count 的值的;

此时的窗口大小等于 p.length,继续向后移动 right,遍历到的字符 e 加到 hash2 中;

每次 right++ 后,需要再次判断窗口的长度,会发现窗口长度大于 p.length,所以又需要调整 left;

在调整 left 之前,我们需要判断此时的  left  是否是一个有效元素

left 指向的元素在 hash2 的 val ,如果小于等于 hash1 中的对应元素的val,则 left 是有效元素;

对于上图的情况,left 向后移动,删除的元素是一个有效元素,因此 count--;

最后,只需要判断 count 是否与 p.length 相等即可,这样就不需要遍历 26 次了;


   总结优化 check() 的判断方法的步骤   

  1. 进窗口:进窗口后,判断 hash2[ input ] <= hash1[ input ]  —> count++
  2. 出窗口:出窗口前,判断  hash2[ input ] <= hash1[ input ] —> count--
  3. 更新结果:只需要判断 count 是否等于 p.length,是则把当前 left 更新到 list 中

   优化后: 

   正确代码: 

   注意:序号一   原因:序号二   


   

 

标签:count,字符,right,窗口,异位,哈希,滑动,成篮,left
From: https://blog.csdn.net/2402_84916296/article/details/143676908

相关文章

  • leetcode刷题笔记--最大滑动窗口
    classSolution{publicintlongestOnes(int[]nums,intk){intl=0,r=0;while(r<nums.length){if(nums[r++]==0){k--;}if(k<0&&nums[l++]==0){......
  • 代码随想录算法训练营第十一天 | 150. 逆波兰表达式求值+ 239. 滑动窗口最大值+347.前
    今天接着补上周末的栈与队列的part2,下午继续完成今天的任务。150.逆波兰表达式求值 给你一个字符串数组 tokens ,表示一个根据 逆波兰表示法 表示的算术表达式。请你计算该表达式。返回一个表示表达式值的整数。注意:有效的算符为 '+'、'-'、'*' 和 '/' 。每个......
  • 滑动窗口最大值
    滑动窗口最大值题目给你一个整数数组nums,有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的k个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。示例示例1:输入:nums=[1,3,-1,-3,5,3,6,7],k=3输出:[3,3,5,5,6......
  • 代码随想录之滑动窗口、Java日期api、集合(11.4-11.11)
    代码1、长度最小的子数组⭐使用滑动窗口的思想,外层循环控制结束位置j,内层循环控制起始位置i,看似是双层循环,但时间复杂度是o(2n)。 2、水果成篮自己想法:使用backet1和backet2表示篮子1和篮子2;使用backet1Account和backet2Account分别表示两个篮子里水果的数量,内层循环将i指针......
  • AnimateDiff:一款强大的制作丝滑动画视频插件,轻松让你的图片动起来
    得益于StableDiffusion的开源,目前很多开发者推出了基于SD生成动画和视频的应用技术和扩展插件,在众多的技术中,AnimateDiff插件以“效果丝滑、稳定、无闪烁”等特性,成为目前Stablediffusion中效果最好的生成动画视频插件之一。今天就给大家详细介绍一下在Stablediffusion中......
  • 找到字符串中所有字母异位词
    找到字符串中所有字母异位词题目给定两个字符串s和p,找到s中所有p的异位词的子串,返回这些子串的起始索引。不考虑答案输出的顺序。示例示例1:输入:s="cbaebabacd",p="abc"输出:[0,6]解释:起始索引等于0的子串是"cba",它是"abc"的异位词。起始索......
  • 这款Chrome 插件,使浏览器页面快速滑动到最底部和最顶部,并且还能...
    前言前几日我在使用谷歌浏览器,也就是chrome的时候,浏览一个内容很长的页面,由于页面上的内容有前后关联,所以我必须不停地切换到上面和下面。这非常不方便。使我非常抓狂。后来,我灵机一动,去谷歌浏览器的插件市场上搜索了一下有没有快速回到底部和顶部的插件,结果,还真有。这下就方便了......
  • vue项目滑动验证组件
    父组件---表单部分:<el-form-itemprop="phone"style="margin-top:6%"><el-inputv-model="ruleForm.phone"placeholder="请输入手机号"clearable:readonly="st......
  • 滑动变阻器有哪些分类?
    滑动变阻器是一种可以改变电阻值的电子元件,广泛应用于各种电子设备中。根据其结构和工作原理的不同,滑动变阻器可以分为以下几类:线性变阻器:线性变阻器的电阻值与滑动触点在固定电阻体上的位置成正比。当滑动触点向一个方向移动时,电阻值逐渐增大;当滑动触点向另一个方向移动时,电阻......
  • h5端IOS滑动不流畅问题怎么解决
    1.CSS动画和过渡避免重排:频繁修改DOM结构、样式或使用会引发重排的属性(如width、height、top等)会导致性能下降。尽量使用transform和opacity进行动画处理。css.smooth{ transition:transform0.3sease,opacity0.3sease;}Note:transition是一种css样......