如何做网站视频,建设银行网站如何查询开户行,wordpress搞笑网站源码,网站建设叁金手指花总6目录 一、理论
二、例题
1. 最长无重复字符串
2. 长度最小的子数组
3. 字符串的排列
4. 最小覆盖子串
5. 滑动窗口最大值 一、理论
滑动窗口是一类比较重要的解题思路#xff0c;一般来说我们面对的都是非定长窗口#xff0c;所以一般需要定义两个指针 left 和 right一般来说我们面对的都是非定长窗口所以一般需要定义两个指针 left 和 right分别用来限制窗口的左边界和右边界。在解题时一般需要设定两个嵌套的循环外循环不设定条件完全是遍历模式驱动右指针的移动内循环需要设定条件在满足条件的情况下驱动左指针的移动。整体实现滑动窗口的向右移动。外循环虽然没有设定条件但其实存在隐藏的条件就是不满足内循环所设定的条件时运行。在这个框架下我们可以增加对窗口长度和数据的记录进而实现丰富的功能。
def fun():left 0 # 定义左指针right 0 # 定义右指针length 0 # 记录窗口长度# 可以定义数据结构记录窗口元素例如set(), set().add(), set.remove()while right len(s): # 首先移动右指针length 1 # 每移动一次右指针窗口长度加一# 可以做一下数据操作例如set().add()while check(): # 满足某个条件下移动左指针# 可以做一下数据操作例如set().remove()left 1 # 然后移动左指针length - 1 # 每一定一次左指针窗口长度减一right 1 # 真正移动右指针return
二、例题
1. 最长无重复字符串
给定一个字符串 s 请你找出其中不含有重复字符的最长子串的长度。
示例:
输入: s abcabcbb
输出: 3 解释: 因为无重复字符的最长子串是 abc所以其长度为 3。
该问题可以使用动态规划的思想来解具体可以看leetcode动态规划问题总结 Python本题还可以使用变长滑动窗口的思路来解。定义两个指针 left 和 right以及一个集合 lookuplookup 表示以右指针 right 为结尾的最长无重复字符串集合实时更新 left、right 和 lookup。然后向右移动右指针(隐藏条件是 s[right] 不存在于 lookup)直至 s[right] 存在于 lookup然后固定右指针右移左指针直至 s[right] 不存在于 lookup。该双指针移动的结果是完备的当移动右指针时可以保证同步左移左指针一定会造成出现重复字符若同步右移左指针则会造成无重复字符串变短并小于已找到的无重复字符串所以右指针右移过程中并没有错过任何有用的无重复字符串。当右指针固定右移左指针时也是完备的此时如果左移则不会生成新的无重复字符串所以没必要但如果 s[right] 不存在于 lookup 时还继续右移左指针会造成无重复字符串变短并小于已找到的无重复字符串所以也没有必要继续右移。思路确定好了以后就可以通过滑动窗口的两个循环嵌套实现编程外层循环控制右指针递增右移不用设定判断条件(其实存在隐含判断条件就是与内层判断条件相反)内层循环需要设定判断条件内层循环还需要控制左指针的右移。
def lengthOfLongestSubstring(s):if not s: return 0left 0lookup set()n len(s)max_len 0cur_len 0for i in range(n):cur_len 1while s[i] in lookup:lookup.remove(s[left])left 1cur_len - 1if cur_len max_len: max_len cur_lenlookup.add(s[i])return max_len
2. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其总和大于等于 target 的长度最小的连续子数组 [numsl, numsl1, ..., numsr-1, numsr] 并返回其长度。如果不存在符合条件的子数组返回 0 。
示例
输入target 7, nums [2,3,1,2,4,3]
输出2 解释子数组 [4,3] 是该条件下的长度最小的子数组。
该问题属于变长滑动窗口问题定义两个指针 start 和 end。在子串求和小于 target 时end 向右移动直至子串求和大于等于 target然后固定 end右移 start直至子串求和小于 target然后再次移动 start循环往复。该种移动方式的解是完备的只是缩小了解的搜索范围所以时间复杂度更优。在右移 end 时子串求和小于 target如果左移 start虽然有可能得到求和大于 target 的子串但是这些子串的长度一定大于已找到的子串所以并不属于所求解的范围亦或者根本无法左移 start(0)此时如果右移 start那所有子串的和都小于 target所以也不属于求解的范围。在 end 固定时如果左移 start依然不属于求解范围因为窗口长度会增加超过了现有解的长度只能右移 start右移至子串求和小于 target 后就不能再右移了因为继续右移不可能找到子串求和大于 target 的解。编程思路是两层循环嵌套外层循环控制 end 的移动隐藏条件是子串求和小于 target内层循环控制 start 的移动判断条件是子串求和大于等于 target。
def minSubArrayLen(s, nums):if not nums:return 0n len(nums)ans n 1start, end 0, 0total 0while end n:total nums[end]while total s:ans min(ans, end - start 1)total - nums[start]start 1end 1return 0 if ans n 1 else ans
3. 字符串的排列
给你两个字符串 s1 和 s2 写一个函数来判断 s2 是否包含 s1 的排列。如果是返回 true 否则返回 false 。换句话说s1 的排列之一是 s2 的子串 。
示例
输入s1 ab s2 eidbaooo
输出true 解释s2 包含 s1 的排列之一 (ba).
该问题属于定长滑动窗口问题以一个固定长度 len(s1) 进行滑动所以该问题的核心问题在于怎么判断一个长度为 len(s1) 的子集是否为 s1 的排列这里采用的方式是通过字典统计每个字符出现的频率然后比较两个字典是否相等如果相等则两个字符串互为排列。当窗口滑动时只需要将新加入的字符添加到字典中同步将剔除的字符从字典中剔除即可。
def checkInclusion(s1, s2):l1 len(s1)l2 len(s2)if l2 l1: # 若字符串s2的长度小于s1则返回falsereturn Falses abcdefghijklmnopqrstuvwxyzdict1 {}dict2 {}for char in s:dict1[char] 0 # 初始化字典key为字母value为字母出现的次数都初始化为0dict2[char] 0for i in range(l1):dict1[s1[i]] 1 # 首先计算前l1长度的不同字母出现次数dict2[s2[i]] 1if dict1 dict2: # 若两个字典相等则说明字符串的[0:l1]是字符串l1的不同排列return Truefor i in range(l2-l1): # 开始往后查找每次移动一个位置dict2[s2[i]] - 1 # 减去滑动比较得前一个字母出现的次数dict2[s2[il1]] 1 # 加上滑动后加进来的字母出现的次数if dict1 dict2: # 若相等则返回truereturn Truereturn False
4. 最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串则返回空字符串 。注意对于 t 中重复字符我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。如果 s 中存在这样的子串我们保证它是唯一的答案。
示例
输入s ADOBECODEBANC, t ABC
输出BANC 解释最小覆盖子串 BANC 包含来自字符串 t 的 A、B 和 C。
该问题采用滑动窗口的思路来解定义左右两个指针均起于 0 位置右指针在滑动窗口不包含 t 字符串的情况下向右移动当右指针使得滑动窗口包含 t 时固定右指针右移左指针直至滑动窗口不包含 t 字符串然后固定左指针再次右移右指针循环往复直至右指针达到最右侧。该逻辑是完备的当右指针右移时起初如果不左移左指针那滑动窗口并不包含 t 字符串所以没必要检查每个路过的字符以及每个字符对应的所有可能字符串如果左移左指针会造成字符串长度增加也不可能被使用所以右指针右移时并没有错过满足条件的解。当滑动窗口包含 t 字符串时左指针右移也是完备的左指针没必要左移因为左移会增加子集的长度而我们已经有更短的满足条件的解所以左指针只能右移当右移至滑动窗口不包含 t 字符串时停止右移因为继续右移只会得到一堆不满足条件的子集。所以实际右指针针对大部分字符仅仅只是检查了一次针对剩余的小批量字符也只是检查了很少一部分对应字符串整体算下来左右指针的时间复杂度都是O(N)级别如果是暴力法那仅仅获取所有子集的时间复杂度就是O(N^2)。具体编程思路采用嵌套两个循环的方式进行外循环对应右指针内循环对应左指针外循环直接无条件遍历内循环基于判断条件遍历其实外循环存在隐藏条件条件为内循环判断条件的对立面。最后就剩余一个问题如何判断一个字符串是否存在于另一个字符串中这里采用的是字典统计法通过字典统一字符串中每个字符的出现频率通过比较两个字典进行判断。
def minWindow(s, t):def check(dict1, dict2): # 定义一个函数检查dict2是否为dict1的子集for key, value in dict2.items():if dict1[key] value:return Falsereturn Trueif len(s) len(t): return key abcdefghijklmnopqrstuvwxyzABCDEFGHIJGKLMNOPQRSTUVWXYZ # 初始化两个字典分别记录t和s前部分的字符分布dict1 {} # 如果使用collections.Counter()效率关于更高dict2 {}for i in range(len(key)):dict1[key[i]] 0dict2[key[i]] 0for i in range(len(t)):dict1[s[i]] 1 # 得到s前len(t)的字符分布dict2[t[i]] 1 # 得到t的字符分布if check(dict1, dict2): return s[0:len(t)] # 判断右指针为len(t)-1的起始情况min_len len(s) 1min_beign 0min_end 0left 0 # 滑动窗口的左指针for right in range(len(t), len(s)): # 滑动窗口的右指针从len(t)开始隐藏条件在dict2不是dict1子集的情况下移动右指针dict1[s[right]] 1 # 每移动一个右指针必须马上修改其指纹dict1对dict1的修改必须正在check函数之前while check(dict1, dict2): # 条件在dict2是dict1子集的情况下移动左指针if min_len right - left 1: # 此时得到满足条件的子集min_len right - left 1min_beign leftmin_end rightdict1[s[left]] - 1left 1if min_end 0:return else:return s[min_beign:min_end1]
5. 滑动窗口最大值
给你一个整数数组 nums有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值 。
示例
输入nums [1,3,-1,-3,5,3,6,7], k 3
输出[3,3,5,5,6,7]
该问题最朴素的想法就是固定窗口长度向右滑动直接找每个窗口的最大值即可但是这样编程的时间复杂度不满足要求。本题需要借助大根堆这个完全二叉树结构(在 python 中 heapq 包对应的是小根堆所以需要加入负号变大根堆)实现最大值的寻找具体操作为起初用最左侧的的 k 个数值搭建一颗大根堆的完全二叉树然后向右滑动窗口每滑动一次向大根堆增加一个数值但此时的问题是如何删除滑动窗口最左侧剔除的数值或者如何保证大根堆的最大值是在滑动窗口的当前范围内呢其实这里不需要删除滑动窗口最左侧的值只要保证大根堆的最大值永远落在滑动窗口内即可具体操作就是使用 while 循环在大根堆的最大值的索引不在滑动窗口范围内的情况下持续将大根堆的主根剔除在 while 循环终止后大根堆的最大值一定落在滑动窗口的当前范围内此时大根堆的最大值就是当前滑动窗口的最大值。此题的关键是想清楚当滑动窗口右移时没必要把滑动窗口左侧剔除的数据从大根堆中剔除。
import heapqdef maxSlidingWindow(nums, k):n len(nums)# 注意 Python 默认的优先队列是小根堆q [(-nums[i], i) for i in range(k)]heapq.heapify(q)ans [-q[0][0]]for i in range(k, n):heapq.heappush(q, (-nums[i], i)) # 把新的字符放入大根堆while q[0][1] i - k: # 没必要把所有窗口外的数据踢走只需要让找到的最大值在窗口范围内即可heapq.heappop(q)ans.append(-q[0][0])return ans
