网站备案 教程,短视频seo营销,上海突发新闻,设计软件ai不会算法的小白不是好小白#xff0c;可恶还有什么可以难倒我这个美女的#xff0c;不做花瓶第一天#xff01;
一、长度最小的子数组
209. 长度最小的子数组 - 力扣#xff08;LeetCode#xff09;
1.思路
滑动窗口法#xff1a;把数组的区间#xff0c;假设成为两…不会算法的小白不是好小白可恶还有什么可以难倒我这个美女的不做花瓶第一天
一、长度最小的子数组
209. 长度最小的子数组 - 力扣LeetCode
1.思路
滑动窗口法把数组的区间假设成为两个指针先后移动两个指针
我们先读懂题目这个很重要不过我现在读的不是很懂没事美女有弱点可以理解
2.辅助理解的例子没办法罗思路不过脑子只能解析一下
let transactions [1, 2, 3, 4, 5];目标是找到一个连续的子数组其元素总和至少为 9
let target 9;
let result minSubArrayLen(target, transactions);1.初始设置
transactions [1, 2, 3, 4, 5]
target 9
start 0, end 0
sum 0
ans Infinity
2.迭代过程 第一轮迭代: end 0 sum 1 (1)sum target (9)所以 end。 第二轮迭代: end 1 sum 3 (1 2)sum target所以 end。 第三轮迭代: end 2 sum 6 (1 2 3)sum target所以 end。 第四轮迭代: end 3 sum 10 (1 2 3 4)sum target: Math.min(ans, end - start 1) - Math.min(Infinity, 4 - 0 1) - ans 4sum - nums[start]start - sum 9 (2 3 4), start 1 第五轮迭代: end 3 sum 9 (2 3 4)sum target: Math.min(ans, end - start 1) - Math.min(4, 4 - 1 1) - ans 3sum - nums[start]start - sum 7 (3 4), start 2 接下来的迭代 end 继续增加但不再找到总和大于等于 target 的更短子数组。
3结果
最终ans 的值为 3。函数返回 3表示最短的满足条件的子数组长度是 3即 [2, 3, 4]。
很好这个滑动窗口是这样理解了但是不会活学活用那么下面继续
二.水果成篮
904. 水果成篮 - 力扣LeetCode
很抽象我读不懂题目找了一个外援理解了一下题目
人话我们的目标是找到一个窗口其中只包含两种类型的水果并且这个窗口尽可能大
步骤 初始化: 定义两个变量来跟踪窗口的开始和结束位置。同时使用一个数据结构如哈希表来跟踪窗口内不同水果的数量。 扩大窗口: 从左向右移动窗口的右边界即不断添加新的水果到窗口中同时更新哈希表。 满足条件的窗口: 当窗口中包含超过两种水果时移动窗口的左边界以排除一种水果直到窗口重新只包含两种水果。 记录结果: 在每次更新窗口时如果窗口只包含两种水果更新最大收集水果的数量。 重复直到结束: 继续扩大和缩小窗口直到覆盖了整个数组。
例子
假设 fruits [1, 2, 1, 2, 3]我们可以按以下步骤使用滑动窗口法
开始: 窗口为空最大数量为 0。窗口扩大: 添加 1窗口为 [1]最大数量为 1。窗口扩大: 添加 2窗口为 [1, 2]最大数量为 2。窗口扩大: 添加 1窗口为 [1, 2, 1]最大数量为 3。窗口扩大: 添加 2窗口为 [1, 2, 1, 2]最大数量为 4。窗口扩大: 添加 3窗口为 [1, 2, 1, 2, 3]。现在窗口中有三种水果需要缩小窗口。缩小窗口: 移除窗口左边的 1窗口变为 [2, 1, 2, 3]。依然有三种水果继续缩小。缩小窗口: 移除窗口左边的 2窗口变为 [1, 2, 3]。现在窗口中有两种水果最大数量更新为 3。
最终最大收集的水果数量为 4在添加第四个水果之前。
初始设置
basket {}: 用来存储水果的类型和数量。start 0: 窗口的开始位置。maxFruits 0: 可以收集的最大水果数。fruits [1, 2, 1, 2, 3]: 待处理的水果数组。
迭代过程 第一次迭代 (end 0): fruit fruits[0] 1basket {1: 1}maxFruits Math.max(0, 0 - 0 1) 1 第二次迭代 (end 1): fruit fruits[1] 2basket {1: 1, 2: 1}maxFruits Math.max(1, 1 - 0 1) 2 第三次迭代 (end 2): fruit fruits[2] 1basket {1: 2, 2: 1}maxFruits Math.max(2, 2 - 0 1) 3 第四次迭代 (end 3): fruit fruits[3] 2basket {1: 2, 2: 2}maxFruits Math.max(3, 3 - 0 1) 4 第五次迭代 (end 4): fruit fruits[4] 3basket {1: 2, 2: 2, 3: 1}现在 basket 中有三种水果。需要移动 start 来删除一种水果。移动 startbasket {1: 1, 2: 2, 3: 1}继续移动 startbasket {2: 2, 3: 1}maxFruits Math.max(4, 4 - 1 1) 4
结果
函数最终返回 maxFruits 4。这意味着最长的符合规则的连续子数组是 [1, 2, 1, 2]其长度为 4。
三、最小覆盖子串
76. 最小覆盖子串 - 力扣LeetCode
辅助笨蛋美女理解的例子
初始设置
s ADOBECODEBANCt ABC初始化窗口的左右指针l 0, r 0窗口中符合条件的字符数量formed 0记录 t 中字符出现频率的哈希表 tFreq记录窗口中字符出现频率的哈希表 windowCounts最小子串的长度minLength Infinity最小子串的起始索引minLeft 0
迭代过程 初始化 tFreq: tFreq {A: 1, B: 1, C: 1} 第一次迭代 (r 0): 当前字符 s[r] AwindowCounts {A: 1}formed 1因为 A 是 t 的一部分r 第二次迭代 (r 1): 当前字符 s[r] DwindowCounts {A: 1, D: 1}formed 保持不变r 第三次迭代 (r 2): 当前字符 s[r] OwindowCounts {A: 1, D: 1, O: 1}formed 保持不变r 第四次迭代 (r 3): 当前字符 s[r] BwindowCounts {A: 1, D: 1, O: 1, B: 1}formed 2因为 B 是 t 的一部分r 第五次迭代 (r 4): 当前字符 s[r] EwindowCounts {A: 1, D: 1, O: 1, B: 1, E: 1}formed 保持不变r 第六次迭代 (r 5): 当前字符 s[r] CwindowCounts {A: 1, D: 1, O: 1, B: 1, E: 1, C: 1}formed 3C 是 t 的一部分现在窗口包含所有 t 的字符开始尝试缩小窗口 (l 开始移动) 移动 l 直到 formed 减少l 停在 3B 处此时窗口是 ADOBEC长度为 6minLength 6, minLeft 0 继续迭代: 继续移动 r 和 l寻找更小的覆盖子串每当 formed 达到 3 时尝试缩小窗口并更新 minLength 和 minLeft
结果
经过迭代找到最小覆盖子串 BANC长度为 4起始索引为 9函数返回 BANC
每次迭代都会检查当前窗口是否包含了 t 中的所有字符。
美女不懂的地方反思理解到了
缩小窗口的具体步骤
假设我们有字符串 s ADOBECODEBANC 和 t ABC并且我们已经通过向右移动右指针 r 扩展了窗口直到它包含了 t 中的所有字符。目前的窗口是 ADOBEC从索引 0 到 5。 缩小窗口: 我们现在尝试通过向右移动左指针 l 来缩小窗口。每移动一次 l窗口中包含的字符数量就会相应减少。 维护 formed 条件: formed 变量用来跟踪窗口中是否包含了 t 中的所有字符。在这个例子中当窗口包含 A, B, C 各至少一次时formed 条件为满足状态。 移动 l 直到 formed 减少: 开始逐个移除窗口左侧的字符并检查每次移除后窗口是否仍然满足 formed 条件。在这个例子中当左指针 l 移到 3 的位置时即字符 B窗口为 BEC去掉了 ADO。这时窗口不再包含 t 中的所有字符A 被移除了所以 formed 条件不再满足。 更新最小子串信息: 在移动 l 之前如果当前窗口满足条件我们检查它是否比之前记录的最小窗口更小。在这个例子中窗口 ADOBEC 的长度为 6这是目前找到的满足条件的最小窗口。因此minLength 更新为 6minLeft 更新为窗口的起始索引 0。
通过以上步骤我们找到了一个满足条件的子串 ADOBEC。但算法不会停止它会继续尝试找到可能存在的更小的满足条件的子串直到遍历完整个字符串 s。最终的答案在这个例子中是 BANC。
