柚子网站建设,线上商城是什么软件,宁波正规seo推广公司,wordpress导入采集文章找到字符串中所有的字母异位词 .题目链接题目详情题目解析算法原理滑动窗口流程图定义指针及变量进窗口判断出窗口更新结果 我的答案 . 题目链接
找到字符串中所有的字母异位词
题目详情 题目解析
所谓的异位词,就是一个单词中的字母,打乱顺序,重新排列得到的单词 如:abc-bca 那么题目的目的就很明显了,就是要求在s字符串中找到p的异位词(相同组成,不同排列) 我们来模拟找一下 首先,定义两个指针,维护满足异位词的左右边界 使right往右移动
如图,在left与right之间,长度刚好符合p的异位词,此时,就需要对这个字符串进行校验,很,很明显,cba就属于p的异位词,校验成功,将当前异位词的首元素下标记录一下,然后使right继续往右移,但是此时子串的长度就不满足p的异位词了,因此,需要将left也往右移动一位 移动完成之后,此时子串的长度又满足条件了,进行校验,并不是p的异位词,继续移动,直到遍历完整个数组 很明显,整个过程通过两个指针,同向进行遍历来解决问题,而left与right之间,往右移动的过程,与窗口类似,因此我们考虑使用滑动窗口来实现这个过程
算法原理
滑动窗口流程图 定义指针及变量
定义两个指针:left和right,初始值都为0 创建hash表1,用数组模拟,记录p的每个字母出现的个数 创建hash表2,用数组模拟,用来记录子串(窗口)中各个字母出现的个数 定义变量count,来记录窗口中的有效字母的个数 创建链表来存储满足条件的异位词的下标
进窗口
将right所在的字母添加到hash2中,t添加完成之后 如果hash2[s[right]-‘a’]hash1[s[right]-‘a’] 说明当前字母是有效字母,就将count加一
判断
判断子串长度是否大于p的异位词的长度
出窗口
当窗口内子串长度大于p的异位词的长度的时候,需要将left所在的字母从hash2中减去1,在减去之前,需要再进行一层判断,判断hash2[s[left]-‘a’]hash1[s[left]-‘a’],如果满足,说明减去的是有效字母,因此需要将count进行减一
更新结果
如果有效字母个数count等于p的字母个数,就说明满足p的异位词,将当前子串的下标存进链表中
我的答案
class Solution {public ListInteger findAnagrams(String ss, String pp) {//定义返回值ListInteger list new ArrayList();//将ss和pp转换为数组,方便遍历char[]s ss.toCharArray();char[]p pp.toCharArray();//创建hash1,统计pint[]hash1 new int[26];for(char tmp:p){hash1[tmp-a];}//创建hash2,用于统计sint[]hash2 new int[26];//定义变量int count 0;//记录有效字母个数for(int left 0,right 0;rights.length;right){//进窗口hash2[s[right]-a];//维护有效字母个数if(hash2[s[right]-a]hash1[s[right]-a]) count;//判断if(right-left1p.length){//出窗口//维护有效字母个数if(hash2[s[left]-a]hash1[s[left]-a]) count--;hash2[s[left]-a]--;left;}//更新结果if(countp.length){list.add(left);}}return list;}
}
