网站开发 开题报告,濮阳网络改造,网站建设业务元提成,wordpress阅读最多插件209. 长度最小的子数组#xff08;最小滑窗#xff09;
给定一个含有 n 个正整数的数组和一个正整数 s #xff0c;找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组#xff0c;并返回其长度。如果不存在符合条件的子数组#xff0c;返回 0。 示例#xff1a; 输入最小滑窗
给定一个含有 n 个正整数的数组和一个正整数 s 找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组并返回其长度。如果不存在符合条件的子数组返回 0。 示例 输入s 7, nums [2,3,1,2,4,3] 输出2 解释子数组 [4,3] 是该条件下的长度最小的子数组。 注意题目是返回长度即可。
暴力法
class Solution(object):def minSubArrayLen(self, target, nums)::type target: int:type nums: List[int]:rtype: int## 难的问题 可以先考虑暴力解法若没有要求时间复杂度min_len float(inf) # 先定义一个无穷大 min_len 后续再迭代更新for i in range(len(nums)):sum 0for j in range(i, len(nums)):sum nums[j]if sum target:min_len min(min_len, j-i1)break # 使用break 防止再遍历下去return min_len if min_len ! float(inf) else 0时间复杂度O(n^2) 空间复杂度O(1)
滑动窗口法
接下来就开始介绍数组操作中另一个重要的方法滑动窗口。 所谓滑动窗口就是不断的调节子序列的起始位置和终止位置从而得出我们要想的结果。 在暴力解法中是一个for循环滑动窗口的起始位置一个for循环为滑动窗口的终止位置用两个for循环 完成了一个不断搜索区间的过程。 那么滑动窗口如何用一个for循环来完成这个操作呢。 首先要思考 如果用一个for循环那么应该表示 滑动窗口的起始位置还是终止位置。 如果只用一个for循环来表示 滑动窗口的起始位置那么如何遍历剩下的终止位置 此时难免再次陷入 暴力解法的怪圈。 所以 只用一个for循环那么这个循环的索引一定是表示 滑动窗口的终止位置。 那么问题来了 滑动窗口的起始位置如何移动呢 这里还是以题目中的示例来举例s7 数组是 231243来看一下查找的过程 其实从动画中可以发现滑动窗口也可以理解为双指针法的一种只不过这种解法更像是一个窗口的移动所以叫做滑动窗口更适合一些。 在本题中实现滑动窗口主要确定如下三点
窗口内是什么如何移动窗口的起始位置如何移动窗口的结束位置
窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。 窗口的起始位置如何移动如果当前窗口的值大于s了窗口就要向前移动了也就是该缩小了。 窗口的结束位置如何移动窗口的结束位置就是遍历数组的指针也就是for循环里的索引。 解题的关键在于 窗口的起始位置如何移动如图所示 可以发现滑动窗口的精妙之处在于根据当前子序列和大小的情况不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n)。
class Solution(object):def minSubArrayLen(self, target, nums)::type target: int:type nums: List[int]:rtype: intmin_len float(inf) # 同样也是先初始化一个min_leni, sum 0, 0for j in range(len(nums)):sum nums[j]while sum target:min_len min(min_len, j-i1)sum - nums[i]i 1 # 这两行是滑动窗口的巧妙之处return min_len if min_len ! float(inf) else 0
区分时间复杂度 暴力解题法O(n^2) 因为第一个for循环在第一个元素的时候第二个for循环会遍历所有元素第一个for循环在第二个元素的时候也会遍历在第二个for循环的时候遍历所有元素…—— n*nn^2 滑动窗口法不要以为for里放一个while就以为是O(n^2)啊 主要是看每一个元素被操作的次数每个元素在滑动窗后进来操作一次出去操作一次每个元素都是被操作两次所以时间复杂度是 2 × n 也就是O(n)。 子串问题优先滑动窗口。
滑动窗口法模板
一般什么时候会考虑使用 滑动窗口法 ——答当求子串问题最小长度/最大长度对应最小滑窗/最大滑窗时候常常考虑使用滑动窗口法。 若需要种类计数记得定义一个种类计数器以及种类计数 参考 作者HelloPGJC 链接https://leetcode.cn/problems/fruit-into-baskets/solutions/1437444/shen-du-jie-xi-zhe-dao-ti-he-by-linzeyin-6crr/ 来源力扣LeetCode
最小滑窗
最小滑窗模板给定数组 nums定义滑窗的左右边界 i, j求满足某个条件的滑窗的最小长度。
while j len(nums):判断[i, j]是否满足条件如果是简单的 一般不需要判断条件 如上面的题while 满足条件不断更新结果(注意在while内更新所谓结果就是求的长度)i 1 最大程度的压缩i使得滑窗尽可能的小j 1最大滑窗
最大滑窗模板给定数组 nums定义滑窗的左右边界 i, j求满足某个条件的滑窗的最大长度。
while j len(nums):判断[i, j]是否满足条件while 不满足条件i 1 最保守的压缩i一旦满足条件了就退出压缩i的过程使得滑窗尽可能的大不断更新结果注意在while外更新j 1如上面的题
class Solution(object):def minSubArrayLen(self, target, nums)::type target: int:type nums: List[int]:rtype: intmin_len float(inf) # 同样也是先初始化一个min_leni, sum 0, 0for j in range(len(nums)):sum nums[j]while sum target:min_len min(min_len, j-i1)sum - nums[i]i 1 # 这两行是滑动窗口的巧妙之处return min_len if min_len ! float(inf) else 0
76. 最小覆盖子串最小滑窗
题目难度困难 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串则返回空字符串 “” 。 注意
对于 t 中重复字符我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。如果 s 中存在这样的子串我们保证它是唯一的答案。
示例 1 输入s “ADOBECODEBANC”, t “ABC” 输出“BANC” 解释最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、‘B’ 和 ‘C’。 示例 2 输入s “a”, t “a” 输出“a” 解释整个字符串 s 是最小覆盖子串。 示例 3: 输入: s “a”, t “aa” 输出: “” 解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中 因此没有符合条件的子字符串返回空字符串。 求最小子串问题——滑动窗口法 解析题意 最小字串——滑动窗口法 找出的s的子串需要涵盖t中的字符——会使用字典计数器
class Solution(object):def minWindow(self, s, t)::type s: str:type t: str:rtype: stri, j 0, 0needMap defaultdict(int) # 定义一个字典计数器对字符, 初始化都是0needCnt len(t) # 最开始 在s中我需要涵盖的字符数就是t中总的字符数res # 结果 初始化为 for c in t:needMap[c] 1 # 为字符计数器赋值while j len(s):if s[j] in needMap:if needMap[s[j]] 0:needCnt - 1 # 有这个字符 那么我需要的字符数就减1needMap[s[j]] - 1 # 因为t中可能有重复字符 所以这个需要减1while needCnt 0:if not res or j-i1 len(res): # res为空(前面没有结果) 注意是小于len(res) 因为是最小子串res s[i:j1] # 获取# 上面只是更新了结果 needMap和needCnt还没有更新if s[i] in needMap:if needMap[s[i]] 0:needCnt 1 # 因为我下一步要移动i 所以如果现在没有这个字符 我需要的字符数加1needMap[s[i]] 1 # 因为我下一步要移动i 所以如果现在没有这个字符 就要加1 告诉后面我需要i 1 # 更新 ij 1 # 更新jreturn res904. 水果成篮最大字串
你正在探访一家农场农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示其中 fruits[i] 是第 i 棵树的种类 。 你想要尽可能多地收集水果。然而农场的主人设定了一些严格的规矩你必须按照要求采摘水果 你只有 两个 篮子并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。 你可以选择任意一棵树开始采摘你必须从 每棵 树包括开始采摘的树上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次你将会向右移动到下一棵树并继续采摘。 一旦你走到某棵树前但水果不符合篮子的水果类型那么就必须停止采摘。 给你一个整数数组 fruits 返回你可以收集的水果的 最大 数目。 解题 像这种就需要先翻译一下题目意思就是让你从一个整数数组中找出其中最长的子数组然后一个限制条件是这个最长子数组中的整数最多只能有两种。 本题返回的是子数组长度不是子数组注意分清楚 示例 1 输入fruits [1,2,1] 输出3 解释可以采摘全部 3 棵树。 示例 2 输入fruits [0,1,2,2] 输出3 解释可以采摘 [1,2,2] 这三棵树。 如果从第一棵树开始采摘则只能采摘 [0,1] 这两棵树。 示例 3 输入fruits [1,2,3,2,2] 输出4 解释可以采摘 [2,3,2,2] 这四棵树。 如果从第一棵树开始采摘则只能采摘 [1,2] 这两棵树。
class Solution(object):def totalFruit(self, fruits)::type fruits: List[int]:rtype: int# 初始化i, j 0, 0res 0 # 要求最大 我先初始化为0classMap defaultdict(int) # 因为涉及到种类数 所以需要一个种类计数器classCnt 0 # 因为是求最大 我刚开始计数当然为0while j len(fruits):if classMap[fruits[j]] 0:classCnt 1 # 第一个数 种类肯定是加1classMap[fruits[j]] 1while classCnt 2: # 不符合条件 种类数超过2# if classMap[fruits[i]] 0: # 不能用0判断 因为不知道种类数能不能减1if classMap[fruits[i]] 1:classCnt - 1 # 因为下一步我就要移动i了, 当前为1 移动一下肯定为0classMap[fruits[i]] - 1 # 该种类数计数也减1i 1res max(res, j-i1) # 在while外面更新结果j 1return res理解最小滑窗和最大滑窗的更新的不同之处 因为是符合条件才更新结果最小滑动窗口中while的条件是 满足条件 因此在while内更新而最大滑动窗口中while的条件是 不满足条件 因此得等到条件满足也就是退出循环后再更新
1004. 最大连续1的个数 III
给定一个二进制数组 nums 和一个整数 k如果可以翻转最多 k 个 0 则返回 数组中连续 1 的最大个数 。 示例 1 输入nums [1,1,1,0,0,0,1,1,1,1,0], K 2 输出6 解释[1,1,1,0,0,1,1,1,1,1,1] 粗体数字从 0 翻转到 1最长的子数组长度为 6。 示例 2 输入nums [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K 3 输出10 解释[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1] 粗体数字从 0 翻转到 1最长的子数组长度为 10。 注意要理清题意这里未涉及种类计数其中 条件 就是 0的数量 因为翻转0是题目已经设定好的。
class Solution(object):def longestOnes(self, nums, k)::type nums: List[int]:type k: int:rtype: int# 求数组中的子数组 最大个数 —— 最大滑窗# 限制条件是 最大翻转k个0 需要0的个数# 想复杂了 还是要理清题意i, j 0, 0res 0zeroCnt 0while j len(nums):if nums[j] 0:zeroCnt 1while zeroCnt k: # 注意是kif nums[i] 0:zeroCnt - 1 # 因为我下一步要移动ii 1res max(res, j-i1)j 1return res 3. 无重复字符的最长子串
给定一个字符串 s 请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: s “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”所以其长度为 3。 示例 2: 输入: s “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”所以其长度为 1。 示例 3: 输入: s “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”所以其长度为 3。 请注意你的答案必须是 子串 的长度“pwke” 是一个子序列不是子串。
class Solution(object):def lengthOfLongestSubstring(self, s)::type s: str:rtype: int# 子串 最大长度 —— 最大滑窗# 不含重复字符 说明遇到字符计数# 巧妙之处将子串中的字符数 与 字典长度联系起来# 模板不要用的太死板i, j 0, 0res 0char_dict defaultdict(int)while j len(s):char_dict[s[j]] 1while len(char_dict)j-i1: # 不满足条件 这个比较难想char_dict[s[i]] - 1 # 下一步就是移动iif char_dict[s[i]] 0:del char_dict[s[i]]i 1if len(char_dict) j - i 1: # 巧妙之处res max(res, j-i1)j1return res参考https://programmercarl.com/
