打开网站代码,学校网站建设工作领导小组,网站开发的工作经验要求,phpcms手机网站怎么做白银挑战-滑动窗口经典问题
1. 最长子串专题
1.1 无重复字符的最长子串
LeetCode3
思路分析
要找最长子串#xff0c;需要直到无重复字符串的首和尾#xff0c;然后再确定最长的那个#xff0c;需要两个指针#xff0c;可利用滑动窗口思想
方法1#xff1a;集合
建…白银挑战-滑动窗口经典问题
1. 最长子串专题
1.1 无重复字符的最长子串
LeetCode3
思路分析
要找最长子串需要直到无重复字符串的首和尾然后再确定最长的那个需要两个指针可利用滑动窗口思想
方法1集合
建立一个集合用于存储无重复的字符建立滑动窗口的起始位置 leftrightright向前滑动 如果遇到相同元素left向前滑动并删除集合中对应的元素直到相同元素被删除然后再将right对应元素保存至集合中 如果遇到不同元素left不变将right对应元素保存至集合中一边滑动一边比较集合长度和已知最大长度最大长度取比较的较大值字符遍历完成输出最大长度
方法2map
定义一个 K-V 形式的mapkey表示字符串value表示其下标索引值定义两个指针left 和 rightleft表示无重复字符串首部索引right为尾部索引遍历字符串每访问一个字符都将更新map将字符串下标索引值更新成最新的 如果遇到重复元素更新对应下标索引同时更新leftleft取原left值和重复元素索引值1二者最大值(特殊情况 abba, b先重复a后重复防止left倒流)一边滑动一边比较right-left长度和已知最大长度最大长度取比较的较大值字符遍历完成输出最大长度
代码实现
方法1集合
class Solution:def lengthOfLongestSubstring(self, s: str) - int:if not s:return 0char_set set()left 0max_len 0for right in range(len(s)):while s[right] in char_set:char_set.remove(s[left])left 1char_set.add(s[right])max_len max(max_len, len(char_set))return max_len方法2map
class Solution:def lengthOfLongestSubstring(self, s: str) - int:if len(s) 0:return 0char_map {}max_len 0left 0for right in range(len(s)):if s[right] in char_map:left max(left, char_map[s[right]] 1)char_map[s[right]] rightmax_len max(max_len, right - left 1)return max_len1.2 至多包含两个不同字符的最长子串
LeetCode159 至多包含两个不同字符的最长子串 给你一个字符串 s 请你找出 至多 包含 两个不同字符 的最长子串并返回该子串的长度。 https://leetcode.cn/problems/longest-substring-with-at-most-two-distinct-characters/
思路分析
仍然使用 left 和 right 来锁定一个窗口然后一边向右移动一边分析
我们接下来需要解决两个问题
怎么判断只有两个元素移除时怎么知道移除谁以及移除之后的left是什么
怎么判断只有两个元素 还是hash好用每一个时刻hashmap包括不超过3个元素
判断移除谁移除后left是什么 设计一下hashmap的key-value的含义key字符value窗口中最右边的字符位置
del_idx min(hashmap.values())
del hashmap[s[del_idx]]
left del_idx 1代码实现
class Solution:def lengthOfLongestSubstringTwoDistinct(self, s: str) - int:if len(s) 3:return len(s)char_map {}max_len 0left 0for right in range(len(s)):if len(char_map) 3:char_map[s[right]] rightif len(char_map) 3:del_idx min(char_map.values())del char_map[s[del_idx]]left del_idx 1max_len max(max_len, right - left 1)return max_len1.3 至多包含K个不同字符的最长子串
LeetCode340 https://leetcode.cn/problems/longest-substring-with-at-most-k-distinct-characters/description/
思路分析 与上一题类似只要把2改为k即可
代码实现
class Solution:def lengthOfLongestSubstringKDistinct(self, s: str, k: int) - int:if len(s) k1:return len(s)char_map {}max_len 0left 0for right in range(len(s)):if len(char_map) k1:char_map[s[right]] rightif len(char_map) k1:del_idx min(char_map.values())del char_map[s[del_idx]]left del_idx 1max_len max(max_len, right - left 1)return max_len2. 长度最小的子数组
LeetCode209 https://leetcode.cn/problems/minimum-size-subarray-sum/
思路分析
本题可以使用双指针来解决也可视为队列法
基本思路如下 先让元素不断入队当入队元素和大于等于target是记录一下此时队列的容量 如果队列元素之和大于等于target则开始出队直到小于target再入队
代码实现
class Solution:def minSubArrayLen(self, target: int, nums: List[int]) - int:left 0min_len len(nums) 1total 0for right in range(len(nums)):total nums[right]while total target:min_len min(min_len, right - left 1)total - nums[left]left 1return min_len if min_len len(nums) else 03. 盛水最多的容器
LeetCode11 https://leetcode.cn/problems/container-with-most-water/
思路分析
盛水的体积的计算短板的高度*长短板之间的宽度 S(left, right) min(h[left], h[right])(right - left)
长短板分列最左边和最右边宽度最大此时长板或短板向中间收窄宽度会变小此时板的高度
若短板向中间收窄短板可能变大水槽面积可能增加若长板向中间收窄短板可能变小或不变水槽面积一定变小
具体执行
初始双指针分列水槽的左右两端循环每轮将短板向内移动一格更新面积的最大值直到两指针相遇时跳出即可获得最大面积
代码实现
class Solution:def maxArea(self, height: List[int]) - int:left, right 0, len(height)-1s 0while left right:s max(s, min(height[left], height[right]) * (right - left))if height[left] height[right]:left 1else:right - 1return s4. 寻找子串异位词排列
异位词排列 如果两个字符串仅仅是字母出现的位置不一样则称两者互为对方的一个排列也称异位词
如何判断
字母的类型一样每个字母出现的个数也是一样的
4.1 字符串的排列
LeetCode 567 https://leetcode.cn/problems/permutation-in-string/
思路分析
字符串的异位词长度 和 字符串的长度是样的所以以字符串的长度作为滑动窗口的大小窗口一边右移一边比较如何判断异位词排序的代价太高了可以创建一个大小为26的数组每个位置存储从a到z的个数 数组索引使用 index s1.charAt(i) - ‘a’ 来表示窗口右移charArray[s2.charAt(right) - ‘a’]窗口左移int left right - s1.length; charArray[s2.charAt(left) - ‘a’]–
代码实现
python中字母与ascii转换 chr() ord()
class Solution:def checkInclusion(self, s1: str, s2: str) - bool:n1, n2 len(s1), len(s2)if n1 n2:return Falsechar_arr1 [0] * 26char_arr2 [0] * 26for i in range(n1):char_arr1[ord(s1[i]) - ord(a)] 1char_arr2[ord(s2[i]) - ord(a)] 1if char_arr1 char_arr2:return Trueleft 0for right in range(n1, n2):char_arr2[ord(s2[right]) - ord(a)] 1char_arr2[ord(s2[left]) - ord(a)] - 1left 1if char_arr1 char_arr2:return Truereturn False4.2 找到字符串中所有字母异位
LeetCode438 https://leetcode.cn/problems/find-all-anagrams-in-a-string/
思路分析 思路分析同上题一致多加了一步进行处理
增加了一个列表记录出现异位词的位置如果出现了将其加到列表中
代码实现
class Solution:def findAnagrams(self, s: str, p: str) - List[int]:n1, n2 len(p), len(s)if n1 n2:return []res []char_arr1 [0] * 26char_arr2 [0] * 26for i in range(n1):char_arr1[ord(p[i]) - ord(a)] 1char_arr2[ord(s[i]) - ord(a)] 1if char_arr1 char_arr2:res.append(0)left 0for right in range(n1, n2):char_arr2[ord(s[right]) - ord(a)] 1char_arr2[ord(s[left]) - ord(a)] - 1left 1if char_arr1 char_arr2:res.append(left)return resclass Solution:def findAnagrams(self, s: str, p: str) - List[int]:p_len, s_len len(p), len(s)if p_len s_len:return []res []p_count [0] * 26s_count [0] * 26for i in range(p_len):p_count[ord(p[i]) - ord(a)] 1s_count[ord(s[i]) - ord(a)] 1if p_count s_count:res.append(0)for i in range(s_len - p_len):s_count[ord(s[i p_len]) - ord(a)] 1s_count[ord(s[i]) - ord(a)] - 1if p_count s_count:res.append(i 1)return res
