LeetCode 第438题 Find All Anagrams in a String【滑动窗口】(Java)

栏目: Java · 发布时间: 4年前

内容简介:原题地址:这道题一开始看起来可能满头雾水,但是仔细想想,跟第76题也蛮像的,无非是这个变位词跟原词是长度相等的。这样就变成了固定宽度的滑动窗口了,不过我们刚才固定和变化的例子都看了,其实除了循环体结构略有不同,其他差异不大。然后就是匹配的条件不同,但是仔细一想,其实也差不多,就是那些我们在p里面的字符出现的频率也要一样。而且如果我们用固定宽度来做的话,我们会发现,我们不用检测有没有多余的字符,宽度一样,且频率一样的话,肯定没有多余的字符,所以这个代码可以轻松地从一个第76题的代码改造出来。

原题地址: https://leetcode.com/problems/find-all-anagrams-in-a-string/

要求

给定一个字符传s和一个非空字符串p,找到所有的p的变位词(anagrams,字符都一样,字符出现的位置不同)在s中的位置。仅包含小写英文单词,而且s和p的长度都不会超过20100。结果顺序不重要。

例 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”的变位词。

这道题一开始看起来可能满头雾水,但是仔细想想,跟第76题也蛮像的,无非是这个变位词跟原词是长度相等的。这样就变成了固定宽度的滑动窗口了,不过我们刚才固定和变化的例子都看了,其实除了循环体结构略有不同,其他差异不大。

然后就是匹配的条件不同,但是仔细一想,其实也差不多,就是那些我们在p里面的字符出现的频率也要一样。而且如果我们用固定宽度来做的话,我们会发现,我们不用检测有没有多余的字符,宽度一样,且频率一样的话,肯定没有多余的字符,所以这个代码可以轻松地从一个第76题的代码改造出来。

我写的比较粗糙,但是基本元素是类似的。首先函数开始和初始化(包括字符数组的初始化,count的初始化):

LeetCode 第438题 Find All Anagrams in a String【滑动窗口】(Java)

循环体(因为是固定宽度的窗口,所以,出入成对,代码很简单。)

LeetCode 第438题 Find All Anagrams in a String【滑动窗口】(Java)

第76题,会做了的话,这道题很简单吧,我的解法耗时6毫秒。

本题代码地址为: https://github.com/tinyfool/leetcode/tree/master/src/p0438

本文假设你对滑动窗口概念有所了解,如果你对滑动窗口的概念不够了解,请参看我介绍 滑动窗口的文章,里面有详细的解释


以上所述就是小编给大家介绍的《LeetCode 第438题 Find All Anagrams in a String【滑动窗口】(Java)》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

奈飞文化手册

奈飞文化手册

[美] 帕蒂·麦考德 / 范珂 / 浙江教育出版社 / 2018-10-1 / 69

一本对奈飞文化进行深入解读的力作。2009年,奈飞公开发布了一份介绍企业文化的PPT文件,在网上累计下载量超过1500万次,被Facebook的CFO谢丽尔·桑德伯格称为“硅谷重要文件”。本书是奈飞前CHO,PPT的主要创作者之一帕蒂·麦考德对这份PPT文件的深度解读。 本书系统介绍奈飞文化准则,全面颠覆20世纪的管人理念。在这本书中,帕蒂·麦考德归纳出8条奈飞文化准则,从多个角度揭示了奈飞......一起来看看 《奈飞文化手册》 这本书的介绍吧!

在线进制转换器
在线进制转换器

各进制数互转换器

MD5 加密
MD5 加密

MD5 加密工具

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具