洛阳建站洛阳市网站建设,wordpress 调用作者,wordpress百度分享代码,智联招聘网站建设情况学习目标
了解滑动窗口的基本原理#xff1b;学会用使用python语言解答滑动窗口经典题目#xff1b;了解双指针的基本原理#xff1b;学会使用python语言解答双指针经典题目#xff1b;
滑动窗口
209. 长度最小的子数组
https://leetcode.cn/problems/minimum-size-sub…学习目标
了解滑动窗口的基本原理学会用使用python语言解答滑动窗口经典题目了解双指针的基本原理学会使用python语言解答双指针经典题目
滑动窗口
209. 长度最小的子数组
https://leetcode.cn/problems/minimum-size-subarray-sum/description/
暴力解法 目标是找子数组暴力遍历所有的子数组 枚举子数组的下标i对于每个开始下标i 枚举子数组的结束下标jij使得nums[i]到nums[j]的元素和大于等于s更新子数组的最小长度j-i1 优化点 前提nums数组中全是正整数枚举子数组的结束下标时如果nums[i]到nums[j]的元素和大于等于s时中断对结束下标的枚举
class Solution:def minSubArrayLen(self, target: int, nums: List[int]) - int:if not nums:return 0n len(nums)ans n 1# 枚举子数组的开始下标ifor i in range(n):total 0# 枚举子数组的结束下标jfor j in range(i, n):total nums[j]# 更新子数组的最小长度j-i1if total target:ans min(ans, j - i 1)breakif ans n 1:return 0else:return ans
滑动窗口
定义两个指针start和end分别表示子数组滑动窗口的开始位置和结束位置初始状态下都指向下标0维护变量total存储子数组中的元素和即从nums[start]到nums[end]的元素和迭代 滑动窗口终止位置移动在每一轮迭代的最后将end右移将nums[end]加到total滑动窗口起始位置移动若totals则更新子数组最小长度end-start1然后将nums[start]从total中减去并将start右移直到totals同时不断更新子数组的最小长度
class Solution:def minSubArrayLen(self, target: int, nums: List[int]) - int:if not nums:return 0n len(nums)ans n 1# 滑动窗口的开始位置和结束位置start, end 0, 0total 0 while end n:total nums[end]while total target:ans min(ans, end - start 1)total - nums[start]# 滑动窗口起始位置移动start 1# 滑动窗口终止位置移动end 1if ans n 1:return 0else:return ans滑动窗口图解 扩张窗口为了找到一个可行解找到了就不再扩张因为扩张不再有意义收缩窗口在长度上优化该可行解直到条件被破坏继续寻找下一个可行解然后再优化到不能优化
567. 字符串的排列
https://leetcode.cn/problems/permutation-in-string/description/ 题目建模
无需全排列排列不会改变字符串中每个字符的个数所以只有两个字符串每个字符的个数均相等时一个字符串才是另一个字符串的排列建模s1的每个字符出现的次数与s2某个子串的每种字符出现次数相同。
滑动窗口解法
维护两个数组dic1和dic2其中dic1用于统计s1中各个字符的个数dic2用于统计当前遍历子串中的各个字符的个数由于需要遍历的子串长度均为m1我们可以使用一个固定长度为m1的滑动窗口来维护dic2滑动窗口每向右滑动一次就多统计一次进入窗口的字符少统计一次离开窗口的字符。然后判断dic1是否与dic2相等若相等则意味着当前窗口内的子串是s1的排列之一。
class Solution:def checkInclusion(self, s1: str, s2: str) - bool:m1 len(s1)m2 len(s2)if m1 m2:return False# 采用有序字典来比较由于只包含小写字母采用数组来模拟有序字典dic1 [0] * 26dic2 [0] * 26# 滑动窗口长度固定为m1for i in range(m1):dic1[ord(s1[i]) - ord(a)] 1dic2[ord(s2[i]) - ord(a)] 1if dic1 dic2:return True# 滑动窗口每向右滑动一次就多统计一次进入窗口的字符少统计一次离开窗口的字符for i in range(m1, m2):dic2[ord(s2[i-m1]) - ord(a)] - 1dic2[ord(s2[i]) - ord(a)] 1if dic1 dic2:return Truereturn False
双指针
滑动窗口有本质上是双指针窗口的开始位置和结束位置便是两个指针窗口的滑动对应指针的移动双指针有时也叫快慢指针在数组里是用两个整型代表下标在链表里面是两个指针一般能将O(N^2)的时间复杂度降为O(N);两个指针的位置一般在第一个元素和第二个元素或者第一个元素和最后一个元素快指针在前“探路”当符合某种条件快慢指针向前挪动。同向双指针在同向双指针套路中两个指针朝相同方向移动但是快慢不同。反向双指针 反向双指针中的两个指针反向而行。
11. 盛最多水的容器
https://leetcode.cn/problems/container-with-most-water/description/
双指针解法
指针每一次移动都意味着排除掉一根柱子如何确定排除哪一根柱子。
class Solution:def maxArea(self, height: List[int]) - int:#双指针1、设置两个指针一个指向起始位置一个指向末尾则s min(h[i],h[j])*(j-i);2、指针向内移动移动高板则面积肯定减少3、移动矮板面积可能增加4、直至指针相遇返回面积最大值#coding i, j 0, len(height)-1area 0ans 0while i j:area min(height[i],height[j]) * (j-i)ans max(area,ans)if height[i] height[j]:i 1else:j - 1return ans
