粮食门户网站建设方案,对购物网站建设的建议,长沙企业网站推广服务公司,响应式网站页面设计第一题 无重复字符串的最长子串
思路
其实就是在字符串S中 找到没有重复的最长子串的长度 这道题的难点就是在于如何判断最长并且无重复
首先 最长长度 可以使用变量max记录保存
再者 判断有无重复 最简单的方法就是 暴力遍历法 即对于每次找的子串都再次寻找遍历…第一题 无重复字符串的最长子串
思路
其实就是在字符串S中 找到没有重复的最长子串的长度 这道题的难点就是在于如何判断最长并且无重复
首先 最长长度 可以使用变量max记录保存
再者 判断有无重复 最简单的方法就是 暴力遍历法 即对于每次找的子串都再次寻找遍历一次 判断是否已有字符 自然 这种方法判断的话 时间复杂度会不是一般的高
当然 算法优化我们慢慢再讨论 最直接的思路就是如此
解法一暴力法
我们的暴力当然和上述思路不太一样 我们对于是否重复 可以直接利用Map集合key不能重复的特点 然后使用containKey()方法直接进行判断
class Solution {public static int lengthOfLongestSubstring(String s) {
// 对于S的特殊情况直接返回0if(snull || s.length()0) return 0;
//将S转化为char数组[] 遍历该数组 然后进行判断char[] charArray s.toCharArray();int max1;MapCharacter,Integer mapnew HashMap();
//遍历 每次遍历开始就是认定为子串的起始字符for(int i0;i charArray.length;i){
//每次记录完一次后 需要把map清空map.clear();map.put(charArray[i],i); //将第一个字符放入for(int ji1;j charArray.length;j){if(map.containsKey(charArray[j])){ // 利用containKey方法直接判断if(map.size()max) maxmap.size(); // 判断当前map长度和max进行比较break;}else{map.put(charArray[j],j);}}if(map.size()max) maxmap.size();}return max;}
} 解法二滑动窗口法
所谓滑动窗口其实就是在字符串中先选定一段把这段作为一个可以滑动的窗口这个窗口类似于队列每次判断队列中字符是否满足题目条件不满足即向左滑动这是整体情况下 一般是向左 自然 也可以只会滑动右边界滑动窗口的时候自然左边会少一位右边会多一位。
class Solution {public int lengthOfLongestSubstring(String s) {if (s.length()0) return 0;HashMapCharacter, Integer map new HashMapCharacter, Integer();int max 0;int left 0;for(int i 0; i s.length(); i ){if(map.containsKey(s.charAt(i))){ //判断是否存在已有队列中
//有的话 找到map中该重复的元素的索引位置 判断两者索引大小 通过对索引的判断 不断向右滑动变化起点left Math.max(left,map.get(s.charAt(i)) 1); }map.put(s.charAt(i),i);//不存在则添加到map中max Math.max(max,i-left1); // 更新最大长度}return max;}
}
第二题 找到字符串中所有字母异位词 思路
和第一题类似 也是遍历找子串 只是这个题目判断依据 不是重复 而是找异位词 异位词的定义我们之前也遇到过 简单来说 就是字母组成一样 如果是异位词 那么排序后的字符串两者一定是一样的 所以我们对其的判断方式就是排序后是否一样 那么这道题的解题思路就很明确
需要注意字符串长度 判null等特殊情况
解法一暴力法
同样的 直接暴力遍历 然后判断是否为异位词就行即可
class Solution {public ListInteger findAnagrams(String s, String p) {if(snull||p.length()s.length()) return new ArrayList();char[] pArray p.toCharArray();Arrays.sort(pArray);ArrayListInteger list new ArrayList();int i0;int lp.length();// abvdef abfor(i0;is.length()-l;i){char[] sArray s.substring(i, i l).toCharArray();Arrays.sort(sArray);if(String.valueOf(pArray).equals(String.valueOf(sArray))){list.add(i);}}return list;}
}
我们是采用排序的方式进行判断异位词 当然也可以采用哈希表映射 统计字母次数的方式 代码如下
class Solution {public ListInteger findAnagrams(String s, String p) {int sLen s.length(), pLen p.length();if (sLen pLen) {return new ArrayListInteger();}ListInteger ans new ArrayListInteger();int[] sCount new int[26];int[] pCount new int[26];for (int i 0; i pLen; i) {sCount[s.charAt(i) - a];pCount[p.charAt(i) - a];}if (Arrays.equals(sCount, pCount)) {ans.add(0);}for (int i 0; i sLen - pLen; i) {--sCount[s.charAt(i) - a];sCount[s.charAt(i pLen) - a];if (Arrays.equals(sCount, pCount)) {ans.add(i 1);}}return ans;}
} 解法二滑动窗口法
我们不再分别统计滑动窗口和字符串 p 中每种字母的数量而是统计滑动窗口和字符串 p 中每种字母数量的差并引入变量 differ来记录当前窗口与字符串 p 中数量不同的字母的个数并在滑动窗口的过程中维护它。
在判断滑动窗口中每种字母的数量与字符串 ppp 中每种字母的数量是否相同时只需要判断 differ是否为零即可
class Solution {public ListInteger findAnagrams(String s, String p) {ListInteger res new ArrayListInteger();int sLen s.length();int pLen p.length();if(sLen pLen) {return res;}//表示字母出现次数差距//count[x] 0 表示 s与p中字母x出现次数相同 都出现了n次(n0)//count[x] n 表示 在s中字母x出现次数比p多 多出现了n次(n0)//count[x] -n 表示 在s中字母x出现次数比p少 少出现了n次(n0)int[] count new int[26];for(int i 0; i pLen; i){count[s.charAt(i)-a];--count[p.charAt(i)-a];}//表示字母差异个数int differ 0;for(int j 0; j 26; j){if(count[j]!0)differ;}if(differ0){res.add(0);}//向右滑动for(int i 0; i sLen - pLen; i){//缩减时只考虑count[x]1与count[x]0的情况//因为缩减时字母x减少count[x]会减去1//(1)count[x]1时(次数差距1次不相同) //count[x]0 - 次数相同 - 不相同变相同字母差异个数减少1 - differ--//(2)count[x]0时(次数相同) //count[x]-1 - 次数差距变为1次-相同变不相同 字母差异个数增加1 - differ//(3)count[x]-1时(次数不相同) - count[x]-2 次数还是不相同- 字母差异数不变//(4)count[x]2时(次数不相同) - count[x]1 次数还是不相同- 字母差异数不变//左缩减一位iif (count[s.charAt(i) - a] 1) { //窗口中s子串左边减少一个s[i]的数量(把原来多出来的1个s[i]去掉变得相同)//两个字符串字母差距缩小--differ;} else if (count[s.charAt(i) - a] 0) { //窗口中s子串左边减少一个s[i]的数量(把原来相同数量的s[i]的减少了1个数量变得不相同)//两个字符串字母差距增大differ;}//窗口中s子串左边减少一个字母s[i]--count[s.charAt(i) - a];//添加时只考虑count[x]-1与count[x]0的情况原因分析与缩减时类似//右添加一位ipLenif (count[s.charAt(i pLen) - a] -1) { //窗口中s子串右边增加一个s[ipLen]的数量(把原来缺少的1个s[i]加上数量变得相同)//两个字符串字母差距缩小--differ;} else if (count[s.charAt(i pLen) - a] 0) { //窗口中s子串右边增加一个s[ipLen]的数量(把原来相同数量的s[i]多加了1个变得不相同)//两个字符串字母差距增大differ;}//窗口中s子串右边增加一个字母s[ipLen]count[s.charAt(i pLen) - a];//两个字符串字母差距为0if (differ 0) {res.add(i 1);}}return res; }
}
