长春网长春网站设计站建设,如何免费制作一个网页,网络营销产品的五个层次,交互设计师目录 1 找到字符串中所有字母异位词
分析#xff1a;
代码展示#xff1a;
代码展示#xff1a;
2 串联所有单词的子串
分析#xff1a;
代码展示#xff1a;
3 串联所有单词的子串
分析#xff1a;
代码展示#xff1a;
4 水果成篮
分析#xff1a;
代码展…目录 1 找到字符串中所有字母异位词
分析
代码展示
代码展示
2 串联所有单词的子串
分析
代码展示
3 串联所有单词的子串
分析
代码展示
4 水果成篮
分析
代码展示 1 找到字符串中所有字母异位词 分析
这道题我们首先想到的暴力解法就是枚举出所有的可能字串然后进行判断就行。而最大的难点在于判断是否相同。
我们先来讲该暴力解法的优解滑动窗口。经过前几题的练习应该很容易想到这种字串问题用滑动窗口。滑动窗口就不多赘述我们来介绍这道题的细节和难点
1 遍历详细过程我们首先要定义两个MapCharacter,Interger,分表存储p和遍历过的s。定义两个指针left 和 right。right向右遍历当遇到一个字符就存入map。假设p的字符数为3直到right和left之间存入三个字符时进行判断成立的话则存入list然后leftright。直到right遍历到s最后一个字符。
2 判断相同的两种方式
1 创建两个map一个存储字符串p,另一个存储遍历过s的并且用一个for遍历字符串p,如果两个map.getOrDefault(key,0)返回的值均相同那么就符合要求
2 创建两个map,mapS和mapP。我们创建一个变量count。来记录right遍历的时候存入的有效字符。什么是有效字符比如p的字符个数为2那么我们用滑动窗口遍历字符串s的时候如果这个字符在mapP中并且mapS的该字符个数小于等于mapP时我们就count如果遇到的字符不在mapP中count就不。最后判断count是否等于p.length()即可。
后面会多次用到整个方法请理解记住。 代码展示
class Solution {public ListInteger findAnagrams(String s, String p) {int left 0;int right 0;MapCharacter,Integer mapS new HashMap();MapCharacter,Integer mapP new HashMap();int count 0;ListInteger list new ArrayList();for (int i 0; i p.length(); i) {int total mapP.getOrDefault(p.charAt(i) , 0) 1;mapP.put(p.charAt(i) , total);}while( right s.length()) {int total mapS.getOrDefault(s.charAt(right) , 0) 1;mapS.put(s.charAt(right) , total);if(mapS.getOrDefault(s.charAt(right) , 0) mapP.getOrDefault(s.charAt(right),0) ) {count;}right;if(count p.length()) {list.add(left);}if(right - left p.length()) {if(mapS.getOrDefault(s.charAt(left) , 0) mapP.getOrDefault(s.charAt(left),0) ) {count--;}int out mapS.getOrDefault(s.charAt(left) , 0) - 1;mapS.put(s.charAt(left) , out);left;}}return list;}
}这个运行结果时间不是最优的是因为hashMap我们将map换成计数数组即可。即创建int[] c new int[26],字符a的存储下标a - a 。不过map的通用性较强。
代码展示
class Solution {public ListInteger findAnagrams(String s, String p) {int left 0;int right 0;int[] mapS new int[26];int[] mapP new int[26];int count 0;ListInteger list new ArrayList();for (int i 0; i p.length(); i) {mapP[p.charAt(i) - a];}while( right s.length()) {if(mapS[s.charAt(right) - a] mapP[s.charAt(right) - a]) {count;}if(count p.length()) {list.add(left);}if(right - left p.length()) {if(mapS[s.charAt(left) - a]-- mapP[s.charAt(left) - a]) {count--;}left;}}return list;}
}我们看出这个代码简化了很多。
2 串联所有单词的子串
分析 这道题和上一题如出一辙只是上一题是字符这道题是字符串核心解法是不变的。假设word每个元素长度是3 ,我们遍历s的时候每次以3为一组进行遍历即可。
这道题有两个难点
demo: s cabcd words [ab,cd].; len words[0].length();
1 示例中未给出所有可能情况
这个示例的返回结果应该是[1]但是当我们以0开始遍历的时候每次遍历程度为2此时是无法得出结果的。因此我们要让left和right从0开始完整遍历一次从1开始完整遍历。当我们再2开始遍历的时候可以发现和从0开始遍历是相同的因此到2的时候就无需再遍历一次了。这时候得到的才是完整答案
2 条件。
当我们从0开始遍历的时候如果整个遍历的循环条件是right s.length()。那么由于right每次遍历两个元素就会越界因此我们的条件应该是right len s.length();
代码展示
class Solution {public ListInteger findSubstring(String s, String[] words) {ListInteger list new ArrayList();int len words[0].length();int totalL len * words.length;int sum 0;while(sum len) {int left sum;int right sum;MapString, Integer map1 new HashMap();MapString, Integer map2 new HashMap();int count 0;for (int i 0; i words.length; i) {int tmp map2.getOrDefault(words[i], 0) 1;map2.put(words[i], tmp);}while (right len s.length()) {
// int k right;
// char[] c new char[len];
// while (k s.length() k len right) {
// c[k - right] s.charAt(k);
// k;
// }
// String s1 new String(c);String s1 s.substring(right,right len);int tmp map1.getOrDefault(s1, 0) 1;map1.put(s1, tmp);right right len;if (map1.getOrDefault(s1, 0) map2.getOrDefault(s1, 0)) {count;}if (right - left totalL) {if (count words.length) {list.add(left);}//int index left;
// char[] c2 new char[len];
// while (index s.length() index len left) {
// c2[index - left] s.charAt(index);
// index;
// }s1 s.substring(left,left len);if (map1.getOrDefault(s1, 0) map2.getOrDefault(s1, 0)) {count--;}tmp map1.get(s1) - 1;map1.put(s1, tmp);left left len;}}sum;}return list;}
}
3 串联所有单词的子串 分析
这道题仍然是不管先后顺序只要包含t中的字串就行。因此我们判断字串是否包含t的全部元素并相同的时候我们仍然可以使用count去标记。
首先看到这样的题目描述以及求字串那么我们想到的解法一定是滑动窗口那么我们就要想一下进窗口出窗口和更新结果的时机以及条件。
我们先是定义两个指针,left和right。right向后依次遍历。每次遍历过的字符都放入集合里。并且判段该元素是否在t中存在并且数量小于t中对应字符的数量如果是那么count; 接下来我们需要判断当前的right和left之间的字符串是否满足条件即count是否等于t.length。相等话如果长度小于之前满足要求的字符串则更新结果。之后再对left进行。
以上就是大体思路
优化点
我们可以将map或作数组方法和题一一样将string转为字符然后-a存入数组。这样时间可以减短很多
代码展示 public static String minWindow(String s, String t) {MapString ,Integer map1 new HashMap();MapString ,Integer map2 new HashMap();String result ;for (int i 0; i t.length(); i) {map2.put(t.substring(i,i1),map2.getOrDefault(t.substring(i,i1),0) 1);}int right 0;int left 0;int count 0;int min s.length();while(right s.length()) {String tmp s.substring(right,right 1);map1.put(tmp,map1.getOrDefault(tmp,0) 1);if(map1.get(tmp) map2.getOrDefault(tmp , 0)) {count;}right;if(map1.containsKey(tmp)) {while(count t.length()) {if(min (right - left)) {min right - left;result s.substring(left , right);}tmp s.substring(left,left 1);if(map1.get(tmp) map2.getOrDefault(tmp , 0)) {count--;}map1.put(tmp,map1.getOrDefault(tmp,0) - 1);left;}}}return result;}4 水果成篮 分析
遇到这种连续数组求字串或者长度之类的用滑动窗口。这道题的思考点在于如何直到是否有两种以上的不同数字我们可以用map如果map.size没有超过2那么继续往里面加如果超过2那么就左移left。然后每次移动的时候更新最大值即可。
代码展示
class Solution {public int totalFruit(int[] fruits) {MapInteger , Integer map new HashMap();int right 0;int left 0;int max 0;while(right fruits.length) {int tmp map.getOrDefault(fruits[right] , 0) 1;map.put(fruits[right] , tmp);right;while (map.size() 2) {tmp map.getOrDefault(fruits[left] , 0) - 1;map.put(fruits[left] , tmp);if (map.get(fruits[left]) 0) {map.remove(fruits[left]);}left;}if(right - left max) {max right - left ;}}return max;}
}
下一章节我们开始讲二分法。
