当前位置:   article > 正文

力扣刷题第438题(1)

力扣刷题第438题(1)

起始索引等于 2 的子串是 “ab”, 它是 “ab” 的异位词。

提示:

  • 1 <= s.length, p.length <= 3 * 104

  • s 和 p 仅包含小写字母


经验总结:

1:技巧方法方面

通过本题,在比较二十六个英文字母时候 开辟计数数组count是比较方便的,给出一个字符串统计其中的字符出现个数,其实是比较好操作的,因为数字 0 - 9 十个 ,大小写 各自26个,这些全部加起来,也还是常数级内进行操作。。。用到的时间和空间复杂度都为O(1)

但是有时候数字他不给出限制 大小,自己做数组,用下标存储,浪费太大了

本题考察的思想,关于哈希表方面的,其实无非就是 用数组做个哈希表,存放小写字母出现的个数,这些在考察字母异位词,赎金信问题中,打的一拳开,免得百拳来。

2:其次,关于滑动窗口,以前对滑动窗口的理解还是不够深,如本题为什么人家的方法能比我的快,用时10ms以内,而我的虽然用暴力安慰奖超过百分之五,用时两千毫秒,再用“滑动数组”依然是百分之十,用时一千毫秒呢?仔细分析,原因莫不是我的“滑动窗口” 是真假美猴王。

我没有掌握理解滑动窗口的思想。 仔细分析大佬的题解,每次滑动窗口 大佬的·题解是:

最核心的一点,大佬的思想是:

因为cntS这个计数数组本质上就是记录一定长度内子串的每个字符对应的小写字母出现的个数。

所以每次就通过左边的字母出现的次数 减一

右边窗口新增进来的字母的次数 加一 进行重复利用的操作 。一旦P字符串长度数十万,S字符串只用读取一次十万 统计出现个数,之后每次加一减一。

滑动窗口真可谓是YYDS了!

至此才算是初窥门径,略懂皮毛。算法思想博大精深!

而我的所谓“双指针”“滑动数组”,其实无非就是,位置的加一减一,变更位置后,还是对符合条件的数组重新读取,再次操作,存入cntS这个统计S字符串中 长度等于P字符串的子串中的各个字符出现的个数。实在是粗陋浅薄,不堪入目~~~

真&滑动窗口


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

提交记录

61 / 61 个通过测试用例

状态:通过

执行用时: 10 ms

内存消耗: 39.1 MB

邀请好友来挑战 找到字符串中所有字母异位词

语言: java

添加备注

class Solution

{

public List findAnagrams(String s, String p)

{

//首先变量命名不要给自己找麻烦 这种Oj题目大小写容易分辨不出来

//其次三种情况

int slen = s.length();

int plen = p.length();

List list = new ArrayList ();

if(slen < plen)

{

return list;

}

int [] scnt = new int[26];

int [] pcnt = new int [26];

for(int i = 0; i < plen ; i++)

{

scnt[s.charAt(i)-‘a’]++;

pcnt[p.charAt(i)-‘a’]++;

}

if(Arrays.equals(scnt,pcnt))

list.add(0);

for(int i = plen;i< slen ; i++)

{

scnt[s.charAt(i-plen)-‘a’]–;

scnt[s.charAt(i)-‘a’]++;

if(Arrays.equals(scnt,pcnt))

{

list.add(i-plen+1);

}

}

return list;

}

}


假&滑动窗口

class Solution

{

public List findAnagrams(String s, String p)

{

int sLen = s.length();

int pLen = p.length();

List list = new ArrayList ();

int left = 0;

int right = 0;

if(sLen<pLen)

{

return list;

}

while(right < sLen)

{

if(right-left+1 == pLen)

{

int[] cntP = new int[26];

int[] cntS = new int[26];

for(int i=0;i<pLen;i++)

{

cntP[p.charAt(i)-‘a’]++;

}

for(int i=left;i<left+pLen;i++)

{

cntS[s.charAt(i)-‘a’]++;

}

if(Arrays.equals(cntP,cntS))

{

list.add(left);

}

left++;

}

right++;

}

return list;

}

}


上述仅为针对本题的 滑动窗口 思想

下面补充 滑动窗口的相关

细节知识点

首先:滑动窗口,窗口根据右边的动,我在编程过程中,考虑过 如 p字符串长度为3,而s字符串长度为7时候,则在右边right滑动到  下标为6,第七位的时候就结束,但是如果

s=abcdefabc

p=abc,那就直接漏了一种情况。直接破防 这是右边的一种。

滑动窗口,本质上是双指针,还有快慢指针,这种双指针的情况其实盯着快慢指针中的快指针,

滑动窗口中的右边栏,切记滑动窗口右边栏一定要滑动到底~!

自我介绍一下,小编13年上海交大毕业,曾经在小公司待过,也去过华为、OPPO等大厂,18年进入阿里一直到现在。

深知大多数前端工程师,想要提升技能,往往是自己摸索成长或者是报班学习,但对于培训机构动则几千的学费,着实压力不小。自己不成体系的自学效果低效又漫长,而且极易碰到天花板技术停滞不前!

因此收集整理了一份《2024年Web前端开发全套学习资料》,初衷也很简单,就是希望能够帮助到想自学提升又不知道该从何学起的朋友,同时减轻大家的负担。

img

既有适合小白学习的零基础资料,也有适合3年以上经验的小伙伴深入学习提升的进阶课程,基本涵盖了95%以上前端开发知识点,真正体系化!

由于文件比较大,这里只是将部分目录截图出来,每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频,并且会持续更新!

如果你觉得这些内容对你有帮助,可以扫码获取!!(备注:前端)

最后

技术是没有终点的,也是学不完的,最重要的是活着、不秃。零基础入门的时候看书还是看视频,我觉得成年人,何必做选择题呢,两个都要。喜欢看书就看书,喜欢看视频就看视频。最重要的是在自学的过程中,一定不要眼高手低,要实战,把学到的技术投入到项目当中,解决问题,之后进一步锤炼自己的技术。

技术学到手后,就要开始准备面试了,找工作的时候一定要好好准备简历,毕竟简历是找工作的敲门砖,还有就是要多做面试题,复习巩固。有需要面试题资料的朋友点击这里可以领取


2.imgtp.com/2024/03/13/H4lCoPEF.jpg" />

最后

技术是没有终点的,也是学不完的,最重要的是活着、不秃。零基础入门的时候看书还是看视频,我觉得成年人,何必做选择题呢,两个都要。喜欢看书就看书,喜欢看视频就看视频。最重要的是在自学的过程中,一定不要眼高手低,要实战,把学到的技术投入到项目当中,解决问题,之后进一步锤炼自己的技术。

技术学到手后,就要开始准备面试了,找工作的时候一定要好好准备简历,毕竟简历是找工作的敲门砖,还有就是要多做面试题,复习巩固。有需要面试题资料的朋友点击这里可以领取

[外链图片转存中…(img-k4KbkXUr-1713202180543)]

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/木道寻08/article/detail/860566
推荐阅读
相关标签
  

闽ICP备14008679号