自己做一网站_多做宣传.,如何做直接打开网站的二维码,郑州免费建站,企业网站 个人备案算法系列之滑动窗口
题目 给定一个字符串 s #xff0c;请你找出其中不含有重复字符的 最长 子串 的长度。 示例 1:输入: s abcabcbb
输出: 3
解释: 因为无重复字符的最长子串是 abc#xff0c;所以其长度为 3。
示例 2:输入: s bbbbb请你找出其中不含有重复字符的 最长 子串 的长度。 示例 1:输入: s abcabcbb
输出: 3
解释: 因为无重复字符的最长子串是 abc所以其长度为 3。
示例 2:输入: s bbbbb
输出: 1
解释: 因为无重复字符的最长子串是 b所以其长度为 1。
示例 3:输入: s pwwkew
输出: 3
解释: 因为无重复字符的最长子串是 wke所以其长度为 3。解题思路 使用滑动窗口算法 滑动窗口算法的核心思想是在一个给定的序列如数组或字符串上定义一个窗口该窗口可以根据特定的条件进行动态调整。窗口的大小可以固定也可以根据问题的需求动态变化。在滑动过程中通过不断更新窗口的边界和内部元素的状态我们能够高效地获取所需的信息如最大、最小子序列和满足特定条件的子序列等。 想象一个在序列上滑动的窗口就像一个移动的框它可以从序列的起始位置开始每次移动一个单位或根据具体情况移动多个单位。在每一步移动中窗口会 “吸入” 新的元素同时 “吐出” 离开窗口范围的元素。通过对窗口内元素的实时计算和记录我们可以在不遍历整个序列的情况下快速找到满足特定条件的子序列。 算法原理 初始化设置左右指针left和right通常都指向数据结构的起始位置。窗口滑动 扩展右边界通常先移动right指针来扩展窗口的右边界直到窗口内的元素不再满足特定条件或right指针到达数据结构的末尾。收缩左边界在窗口不满足条件时移动left指针来收缩窗口的左边界直到窗口内的元素重新满足条件。 记录结果在窗口滑动的过程中记录下满足条件的中间结果如最大值、最小值、子串长度等。重复步骤重复步骤2和3直到right指针遍历完整个数据结构。
获取某个字符串中不重复的字符长度如abfhdasdrbch
//abfhdasdrbch//思路// 索引-字符-不重复字符串-重新开始//0-a-a (开始位index0即a)//1-b-ab//2-f-abf//3-h-abfh//4-d-abfhd//5-a-bfhdaa重复了所以需要重新开始新的开始位index1即b//6-s-bfhdas//7-d-asd (又重复了新的开始位index5即a)//8-r-asdr//9-b-asdrbpublic static int getBig(String s){//最大长度int max0;//下一段不重复开始发起始索引号int startIndex0;//字符对应最新的索引号HashMapCharacter, Integer characterHashMap new HashMapCharacter, Integer();int length s.length();for (int i 0; i length; i) {Integer charIndex characterHashMap.get(s.charAt(i));if (charIndex!null){// 如果字符已经存在于哈希表中并且其位置在窗口内则移动左边界startIndexMath.max(charIndex1,startIndex);}characterHashMap.put(s.charAt(i),i);maxMath.max(max,i-startIndex1);}return max;
}
