教师做爰网站云主机做网站永久保留网站

教师做爰网站,云主机做网站永久保留网站,网站建设开发模式h5,ftp 网站思路#xff1a;滑动窗口。对于主串s和子串p#xff0c;设n是子串p的长度。一、方法一#xff1a;定长滑动窗口。枚举主串s的所有长为n的子串s#xff0c;在滑动的同时维护s’中的每种字母的出现次数。如果s的每种字母的出现次数和p的每种字母的出现次数都相同#xff0c;…思路滑动窗口。对于主串s和子串p设n是子串p的长度。一、方法一定长滑动窗口。枚举主串s的所有长为n的子串s在滑动的同时维护s’中的每种字母的出现次数。如果s的每种字母的出现次数和p的每种字母的出现次数都相同那么s是p的异位词并把s的左端点下标加入答案。附代码class Solution { public ListInteger findAnagrams(String s, String p) { //统计p的每种字母的出现次数 int[] cntp new int[26]; for(char c : p.toCharArray()){ cntp[c - a]; //统计p的字母 } ListInteger res new ArrayList(); int[] cnts new int[26]; //统计s的长度为p.length()的子串s的每种字母的出现次数 for(int right 0;right s.length();right){ cnts[s.charAt(right) - a]; //右端点字母进入窗口 int left right - p.length() 1; if(left 0){ //窗口长度不足p.length() continue; } if(Arrays.equals(cnts,cntp)){ //s和p的每种字母的出现次数都相同 res.add(left); //s的左端点下标加入答案 } cnts[s.charAt(left) - a]--; //左端点字母离开窗口 } return res; } }二、方法二不定长滑动窗口。枚举子串s的右端点如果发现s’其中一种字母的出现次数大于p的这种字母的出现次数则右移s的左端点缩小窗口。如果发现s的长度等于p的长度则说明s的每种字母的出现次数等于p的每种字母的出现次数即s是p的异位词。证明内层循环结束后s的每种字母的出现次数都小于等于p的每种字母的出现次数。如果s’的其中一种字母的出现次数比p的小那么s的长度必然小于p的长度。所以只要s的长度等于p的长度就说明s的每种字母的出现次数和p的每种字母的出现次数都相同就说明s是p的异位词于是把s的左端点下标加入答案。代码实现时可以把cnts和cntp合并成一个cnt1对于p的字母c把cnt[c]加一。2对于s的字母c把cnt[c]减一。3如果cnt[c]小于0则说明窗口中的字母c的个数比p的多右移左端点。附代码class Solution { public ListInteger findAnagrams(String s, String p) { //统计p的每种字母的出现次数 int[] cnt new int[26]; for(char c : p.toCharArray()){ cnt[c - a]; } ListInteger res new ArrayList(); int left 0; for(int right 0;right s.length();right){ int c s.charAt(right) - a; cnt[c]--; //右端点字母进入窗口 while(cnt[c] 0){ //字母c太多了 cnt[s.charAt(left) - a]; //左端点字母离开窗口 left; } if(right - left 1 p.length()){ //s和p的每种字母的出现次数都相同 res.add(left); //s的左端点下标加入答案 } } return res; } }