旅游网站模板免费下载,做鲜花配送网站需要准备什么,企业互联网,昆明电子商务网站建设滑动窗口篇 1. 长度最小的子数组Python3 2. 无重复字符的最长子串3. 串联所有单词的子串3.1 *(本题前导题)* 找到字符串中所有字母异位词本题 4. 最小覆盖子串官方解法优化解法(我写的不太成功#xff0c;并未加速) 滑动窗口就像一只蠕动的蚯蚓#xff0c;头部前进#xff0… 滑动窗口篇 1. 长度最小的子数组Python3 2. 无重复字符的最长子串3. 串联所有单词的子串3.1 *(本题前导题)* 找到字符串中所有字母异位词本题 4. 最小覆盖子串官方解法优化解法(我写的不太成功并未加速) 滑动窗口就像一只蠕动的蚯蚓头部前进尾部蓄力和双指针天生一对。 1. 长度最小的子数组 题目链接长度最小的子数组 - leetcode 题目描述 给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [ n u m s l nums_l numsl, n u m s l 1 nums_{l1} numsl1, …, n u m s r − 1 nums_{r-1} numsr−1, n u m s r nums_r numsr] 并返回其长度。如果不存在符合条件的子数组返回 0 。 题目归纳 (1)子数组总和 target (2)子数组要连续 [nums_l, nums_(l1), … , nums_(r-1), nums_r] (3)长度为r-(l-1)值要最小 (4)数组的值均为正整数所以只管考虑相加 解题思路 (1) 解法 见代码。 Python3
class Solution:def minSubArrayLen(self, target: int, nums: List[int]) - int:# (1)子数组总和 target# (2)子数组要连续 [nums_l, nums_(l1), ... , nums_(r-1), nums_r]# (3)长度为r-(l-1)值要最小# (4)数组的值均为正整数所以只管考虑相加# sum[i] sum (nums[0] ... nums[i])# 那么子数组[nums_l, nums_(l1), ... , nums_(r-1), nums_r]的和就会等于 sum[r] - sum[l-1]# 与 盛最多水容器 一题类似移动值更小的边界指针n len(nums)if(n 0):return 0l, r 0, 0ans_len 1e9sums 0while r n:sums nums[r]while sums target: # 这里的l1移动值得玩味ans_len min(ans_len, r-(l-1))sums - nums[l]l 1r 1if ans_len 1e9: # 说明所有数组元素加起来都小于targetreturn 0else:return ans_len2. 无重复字符的最长子串 题目链接无重复字符的最长子串 - leetcode 题目描述 给定一个字符串 s 请你找出其中不含有重复字符的 最长子串 的长度。 题目归纳 (1)如果依次递增地枚举子串的起始位置那么子串的结束位置也是递增的 解题思路 (1) 解法 见代码。 class Solution:def lengthOfLongestSubstring(self, s: str) - int:hash_set set()n len(s)right, ans -1, 0for i in range(n):if i 0:hash_set.remove(s[i-1]) # 移除起始处前一个位置的元素while right 1 n and s[right1] not in hash_set: # 下一个元素不重复循环这个过程hash_set.add(s[right1])right 1 # 真正右移ans max(ans, right-i1)return ans
3. 串联所有单词的子串
3.1 (本题前导题) 找到字符串中所有字母异位词 题目链接找到字符串中所有字母异位词 - leetcode 题目描述 给定两个字符串 s 和 p找到 s 中所有 p 的 异位词 的子串返回这些子串的起始索引。不考虑答案输出的顺序。异位词 指由相同字母重排列形成的字符串包括相同的字符串。 输入: s cbaebabacd, p abc 输出: [0,6] 解释: 起始索引等于 0 的子串是 cba, 它是 abc 的异位词。 起始索引等于 6 的子串是 bac, 它是 abc 的异位词。 s 和 p 仅包含小写字母 题目归纳 题意不难理解。第一步如果给你两个字符串长度一致各字符数量一致这两个字符串即互为异位词。第二步滑动窗口寻找。建一个和 p p p串长度相同的滑动窗口在 s s s中滑动那么只要这个窗口字符数量与 p p p一致即为异位词。 解题思路 (1) 解法 找到字符串中所有字母异位词 - leetcode官方题解 # (1)python原生写法数组统计词频
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 []ans []s_count [0]*26p_count [0]*26for i in range(p_len):p_count[ord(p[i]) - 97] 1 # ord()返回对应的unicode编码97是a的ASCII码值s_count[ord(s[i]) - 97] 1 if (s_count p_count): # 词频数组相等ans.append(0) # 开头位置就是答案之一for i in range(1,s_len - p_len1) : # 滑动窗口的起始位置最多不会超过s_len - p_lens_count[ord(s[i-1]) - 97] - 1 # 滑动窗口向右滑动中s_count[ord(s[ip_len-1]) - 97] 1 # 滑动窗口向右滑动下一个要包括的字符词频1if s_count p_count:ans.append(i) return ans# (2)python中的collections写法Counter()类统计词频
from collections import Counter # leetcode刷题时最好把引用也写上避免到时引用类没有自动提示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 []ans []s_count Counter() # Counter()类统计词频十分好用p_count Counter()for i in range(p_len):p_count[p[i]] 1s_count[s[i]] 1if (s_count p_count): # 词频数组相等ans.append(0) # 开头位置就是答案之一for i in range(1,s_len - p_len1) : # 滑动窗口的起始位置最多不会超过s_len - p_lens_count[s[i-1]] - 1s_count[s[ip_len-1]] 1if s_count p_count:ans.append(i) return ans本题 题目链接串联所有单词的子串 - leetcode 题目描述 给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。 s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。例如如果 words [ab,cd,ef] 那么 abcdef abefcdcdabef cdefabefabcd 和 efcdab 都是串联子串。 acdbef 不是串联子串因为他不是任何 words 排列的连接。返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。 题目归纳 在有了前导题的基础上乍一看可以用全排列先将数组中的子串组合情况全部列出来然后放入字符串s中进行s.find(sub_str)进行查找但是这种方式的时间复杂度太高达到了 O ( n ! ) O(n!) O(n!) n n n是数组长度。 解题思路 (1) 解法 串联所有单词的子串 - leetcode官方题解 from collections import Counter # leetcode刷题时最好把引用也写上避免到时引用类没有自动提示class Solution:def findSubstring(self, s: str, words: List[str]) - List[int]:# 第438题的元素是字母此题的元素是单词。438题是求异位词而这里是求异位字符串res []m len(words)n len(words[0]) # 每个单词长度一致s_len len(s)window_len m*nfor i in range(n):if i window_len s_len: # i偏移量若s_len则越界这里偏移量为words长度即窗口长度m*nbreak# Counter()类用法: # (1)https://blog.csdn.net/weixin_67683316/article/details/127079849 # (2)https://docs.python.org/3/library/collections.html#collections.Counter# 这道题中Counter()也可以理解为hash表只是更便于调用用dict()实现也是一样的differ Counter() # 一、对s进行切片每个切片长度为n这样才是类似于字母异位词的搜寻。# 划分方法为先删去前i个字母再对剩余字母进行切片长度为n的划分若划分至末尾字母长度不足n也删去for j in range(m):word s[i j*n : i (j1)*n]# 初始化differ时出现在窗口中的单词每出现一次相应的值1differ[word] 1for w in words: # 这里遍历循环最好不要写成for word in words, 避免与上面产生阅读歧义# 出现在words中的单词每出现一次相应的值-1differ[w] - 1if differ[w] 0: # 词频不能低于0必须删除要么做减法时加限制条件del differ[w]# [i, in, i2n,...,s_len - window_len]for start in range(i, s_len-window_len 1, n): if start ! i:# 窗口右移右侧加入新词左侧移出旧词对differ做相应的更新new_word s[start window_len - n : start window_len]differ[new_word] 1if differ[new_word] 0:del differ[new_word]old_word s[start-n: start]differ[old_word] - 1if differ[old_word] 0:del differ[old_word]if len(differ) 0: # 词频完全一致则为串联子串可以append此时索引res.append(start)return res
4. 最小覆盖子串 题目链接最小覆盖子串 - leetcode 题目描述 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串则返回空字符串 “” 。 输入s ADOBECODEBANC, t ABC 输出BANC 解释最小覆盖子串 “BANC” 包含来自字符串 t 的 A、B 和 C。 题目归纳 测试用例保证答案唯一。 解题思路 (1) 解法 最小覆盖子串 - leetcode官方题解 官方解法
from collections import Counter # leetcode刷题时最好把引用也写上避免到时引用类没有自动提示class Solution:def check(self, window_counter: Counter, t_counter: Counter):# 如果window中的词频数量t则是符合条件的if window_counter t_counter:return Trueelse:return Falsedef minWindow(self, s: str, t: str) - str:# 查找s中涵盖t所有字符的最小子串像《找到字符串中所有字母异位词》的扩展# 《找到字符串中所有字母异位词》是目标长度必须相同且字符频数也必须相同# 这道题只需要字符频数相同长度可以也就是说这题的滑动窗口window_len是不固定的# 解题思路# (1)称包含t的全部字母窗口为可行窗口# (2)双指针l与r。窗口包含t串左指针l右移窗口不包含t串右指针r右移。任意时刻只有一个指针运动。# (3)此时要比较ans_len长度若ans_len比之前更小那么更新ans_len与ans。ans_len r-(l-1)# (4)用Counter计算字符频率# (5)优化版本官解未实现。精简无关字符串就是扔掉一些无关子串如sXXABXXC, tABC那么可以扔掉开头的两个XXs_len len(s)t_len len(t)if s_len t_len:return window_counter Counter() # 窗口字频词典t_counter Counter() # t字频词典# (1)计算t中字符频率for ch in t:t_counter[ch] 1# (2)双指针l, r 0, 0ans_len 1e9ans while r s_len:s_r s[r]if r s_len and t_counter[s_r] 0: # r指针未越界且当前字符在t_counter字频词典中window_counter[s_r] 1 # 窗口中该字频1while self.check(window_counter,t_counter) and l r: # 在s中找到了包含t的字符串window_len r-l1if window_len ans_len: # 找到了更小的窗口长度ans_len window_lenans s[l: lwindow_len]s_l s[l]if t_counter[s_l] 0: # 只在window_counter中减去与t串相关的字符词频。window_counter[s_l] - 1 # 左指针向右移动if window_counter[s_l] 0: # 有无这行判断对求解无影响为了严谨del window_counter[s_l]l 1 # 窗口包含t串左指针l右移r 1 # 窗口不包含t串右指针r右移return ans优化解法(我写的不太成功并未加速)
from collections import Counter # leetcode刷题时最好把引用也写上避免到时引用类没有自动提示class Solution:def check(self, window_counter: Counter, t_counter: Counter):# 如果window中的词频数量t则是符合条件的if window_counter t_counter:return Trueelse:return Falsedef minWindow(self, s: str, t: str) - str:# 查找s中涵盖t所有字符的最小子串像《找到字符串中所有字母异位词》的扩展# 《找到字符串中所有字母异位词》是目标长度必须相同且字符频数也必须相同# 这道题只需要字符频数相同长度可以也就是说这题的滑动窗口window_len是不固定的# 解题思路# (1)称包含t的全部字母窗口为可行窗口# (2)双指针l与r。窗口包含t串左指针l右移窗口不包含t串右指针r右移。任意时刻只有一个指针运动。# (3)此时要比较ans_len长度若ans_len比之前更小那么更新ans_len与ans。ans_len r-(l-1)# (4)用Counter计算字符频率# (5)优化版本官解未实现。精简无关字符串就是扔掉一些无关子串如sXXABXXC, tABC那么可以扔掉开头的两个XXs_len len(s)t_len len(t)if s_len t_len:return window_counter Counter() # 窗口字频词典t_counter Counter() # t字频词典# (1)计算t中字符频率for ch in t:t_counter[ch] 1# ()优化部分可选。 faster_start 0 # 更快速的起点位置faster_end s_len - 1 # 更快速的终点位置# 优化解法扔掉s中前面与后面未在t中出现的字符串部分while faster_start s_len:if t_counter[s[faster_start]] 0: # s中的该字符未在t中出现,faster_start可以前进faster_start 1else:break # 找到了第一个出现的位置就跳出不再前进while faster_end 0:if t_counter[s[faster_end]] 0:faster_end - 1else:break# (2)双指针l, r faster_start, 0ans_len 1e9ans while r faster_end1:s_r s[r]if r s_len and t_counter[s_r] 0: # r指针未越界且当前字符在t_counter字频词典中window_counter[s_r] 1 # 窗口中该字频1while self.check(window_counter,t_counter) and l r: # 在s中找到了包含t的字符串window_len r-l1if window_len ans_len: # 找到了更小的窗口长度ans_len window_lenans s[l: lwindow_len]s_l s[l]if t_counter[s_l] 0: # 只在window_counter中减去与t串相关的字符词频。window_counter[s_l] - 1 # 左指针向右移动if window_counter[s_l] 0: # 有无这行判断对求解无影响为了严谨del window_counter[s_l]l 1 # 窗口包含t串左指针l右移r 1 # 窗口不包含t串右指针r右移return ans
