【12.22】转行小白历险记-算法01

2023-12-22 22:44:10

不会算法的小白不是好小白,可恶还有什么可以难倒我这个美女的,不做花瓶第一天

一、长度最小的子数组

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.迭代过程

  1. 第一轮迭代: end = 0

    • sum = 1 (1)
    • sum < target (9),所以 end++
  2. 第二轮迭代: end = 1

    • sum = 3 (1 + 2)
    • sum < target,所以 end++
  3. 第三轮迭代: end = 2

    • sum = 6 (1 + 2 + 3)
    • sum < target,所以 end++
  4. 第四轮迭代: end = 3

    • sum = 10 (1 + 2 + 3 + 4)
    • sum >= target:
      • Math.min(ans, end - start + 1) -> Math.min(Infinity, 4 - 0 + 1) -> ans = 4
      • sum -= nums[start]start++ -> sum = 9 (2 + 3 + 4), start = 1
  5. 第五轮迭代: end = 3

    • sum = 9 (2 + 3 + 4)
    • sum >= target:
      • Math.min(ans, end - start + 1) -> Math.min(4, 4 - 1 + 1) -> ans = 3
      • sum -= nums[start]start++ -> sum = 7 (3 + 4), start = 2
  6. 接下来的迭代

    • end 继续增加,但不再找到总和大于等于 target 的更短子数组。

3结果

  • 最终,ans 的值为 3
  • 函数返回 3,表示最短的满足条件的子数组长度是 3(即 [2, 3, 4])。

很好这个滑动窗口是这样理解了,但是不会活学活用,那么下面继续

二.水果成篮

904. 水果成篮 - 力扣(LeetCode)

很抽象我读不懂题目:找了一个外援理解了一下题目

人话:我们的目标是找到一个窗口,其中只包含两种类型的水果,并且这个窗口尽可能大

步骤

  1. 初始化: 定义两个变量来跟踪窗口的开始和结束位置。同时,使用一个数据结构(如哈希表)来跟踪窗口内不同水果的数量。

  2. 扩大窗口: 从左向右移动窗口的右边界,即不断添加新的水果到窗口中,同时更新哈希表。

  3. 满足条件的窗口: 当窗口中包含超过两种水果时,移动窗口的左边界以排除一种水果,直到窗口重新只包含两种水果。

  4. 记录结果: 在每次更新窗口时,如果窗口只包含两种水果,更新最大收集水果的数量。

  5. 重复直到结束: 继续扩大和缩小窗口,直到覆盖了整个数组。

例子

假设 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]: 待处理的水果数组。

迭代过程

  1. 第一次迭代 (end = 0):

    • fruit = fruits[0] = 1
    • basket = {1: 1}
    • maxFruits = Math.max(0, 0 - 0 + 1) = 1
  2. 第二次迭代 (end = 1):

    • fruit = fruits[1] = 2
    • basket = {1: 1, 2: 1}
    • maxFruits = Math.max(1, 1 - 0 + 1) = 2
  3. 第三次迭代 (end = 2):

    • fruit = fruits[2] = 1
    • basket = {1: 2, 2: 1}
    • maxFruits = Math.max(2, 2 - 0 + 1) = 3
  4. 第四次迭代 (end = 3):

    • fruit = fruits[3] = 2
    • basket = {1: 2, 2: 2}
    • maxFruits = Math.max(3, 3 - 0 + 1) = 4
  5. 第五次迭代 (end = 4):

    • fruit = fruits[4] = 3
    • basket = {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。

文章来源:https://blog.csdn.net/TTTT2222111/article/details/135152603
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。