免费企业推广网站,wordpress运行环境要求,河北邢台贴吧,yangdesign工业设计公司3、无重复字符的最长子串#xff08;中等#xff09;
题目描述
给定一个字符串 s #xff0c;请你找出其中不含有重复字符的 最长子串 的长度。
示例 1: 输入: s “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”#xff0c;所以其长度为 3。 示例 2: 输…3、无重复字符的最长子串中等
题目描述
给定一个字符串 s 请你找出其中不含有重复字符的 最长子串 的长度。
示例 1: 输入: s “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”所以其长度为 3。 示例 2: 输入: s “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”所以其长度为 1。 示例 3: 输入: s “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”所以其长度为 3。 请注意你的答案必须是 子串 的长度“pwke” 是一个子序列不是子串。 提示
0 s.length 5 * 104s 由英文字母、数字、符号和空格组成
题目思路
对于这道题要求是找到最长连续的、不包含重复字符的字符子串。
经过观察思考我们可以得知可以通过滑动窗口的方法来寻找这样的答案。
这里子串的条件是不能包含重复的字符因此首先在遍历时我们可以定义一个哈希表来保存对应字符所处位置方便查看当前字符是否在子串中。
同时定义left与right指针分别作为滑动窗口的左右两端因此子串长度就是right - left。
在right从左到右遍历时对于s[right]
如果该字符未曾出现、或出现的位置在当前子串左边那么该字符可以作为否则就对left指针进行更新——即更新到对应已重复字符的下一个位置将重复排除掉最后每轮循环都需要记录或刷新当前字符的位置
算法代码
class Solution:def lengthOfLongestSubstring(self, s: str) - int:letter_index_map {}left, right 0, 0max_length 0while right len(s):curr_letter_index letter_index_map.get(s[right])# 说明当前字符要么从未出现、要么在当前子序列之前出现if curr_letter_index is None or curr_letter_index left:max_length max(max_length, right - left 1)else:left curr_letter_index 1# 记录/刷新当前字符所在位置letter_index_map[s[right]] rightright 1return max_length438、找到字符串中所有字母异位词中等
题目描述
给定两个字符串 s 和 p找到 s 中所有 p 的 异位词 的子串返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串包括相同的字符串。
示例 1: 输入: s “cbaebabacd”, p “abc” 输出: [0,6] 解释: 起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。 起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。 示例 2: 输入: s “abab”, p “ab” 输出: [0,1,2] 解释: 起始索引等于 0 的子串是 “ab”, 它是 “ab” 的异位词。 起始索引等于 1 的子串是 “ba”, 它是 “ab” 的异位词。 起始索引等于 2 的子串是 “ab”, 它是 “ab” 的异位词。 提示:
1 s.length, p.length 3 * 104s 和 p 仅包含小写字母
题目思路
所谓的异位词在哈希问题中已有说明 49、字母异位词分组 在该问题中既可以直接对单词进行排序来判断。
在这道题中这里如果直接去排序的话需要排序的次数就太多了例如如果s长度是10p长度是3那么至少要排序71次更不用说s和p的长度可能会非常大。
因此另一种方法则是字母计数只需要使用ASCII码作为索引构造哈希表然后统计字母出现次数最后对比两个哈希表是否相同就可以知道两个单词是否是字母异位词了。
在这道题中本质上就是以p的长度划定一个滑动窗口每向右移动一位时
窗口最左侧字符去掉因此该字符的计数-1窗口最右侧字符新增因此该字符的计数1如果此时的s_counter和p_counter是否相同就将对应索引加入结果中
需要注意的是在滑动前我们自然是要有已经构造好的窗口因此定义两个字母哈希表s_counter和p_counter
s_counter记录滑动过程中s字符子串字符出现次数p_counter不变量记录p的字符出现次数相当于模板
同时因为所谓遍历本质上就是开始滑动窗口因此构造完s_counter和p_counter后需要首先做一下判断看下第一个滑动区间是否满足条件。
算法代码
class Solution:def findAnagrams(self, s: str, p: str) - List[int]:s_len, p_len len(s), len(p)if s_len p_len:return []s_counter [0] * 26p_counter [0] * 26total_anagrams_idx []for i in range(p_len):s_counter[ord(s[i]) - ord(a)] 1p_counter[ord(p[i]) - ord(a)] 1# 第一个滑动区间单独判断if s_counter p_counter:total_anagrams_idx.append(0)for i in range(s_len - p_len):# 滑动一位去掉左侧字符新增右侧字符s_counter[ord(s[i]) - ord(a)] - 1s_counter[ord(s[i p_len]) - ord(a)] 1if s_counter p_counter:total_anagrams_idx.append(i 1)return total_anagrams_idx补充说明
所谓滑动窗口法又称为“寸取法”一般用来解决查找满足依一定条件的连续区间的特殊性质长度等 等一类问题。
由于区间是连续的因此当整个区间发生变化时可以通过对旧有的计算结果对搜索空间的剪枝一般就是滑动窗口最左侧滑出的部分从而减少了重复计算、降低了时间复杂度、避免了暴力的搜索。
往往类似于“请找到满足xx条件的最x区间/子串/子数组”这一类问题都可以使用滑动窗口法来进行解决。
