青少年编程知识记录

2025年02月28日

【算法】滑动窗口2—窗口大小可变

对于滑动窗口第二类：窗口大小可变类型

图解如下，类似双指针算法。

【解题思想】

1、字符串 S 中使用双指针的左右指针技巧，初始化 left = right = 0，把索引的左闭右开区间 [left,right) 称为一个「窗口」。
2、先不断增加 right 指针扩大窗口[left, right)（也就是 right++），直到窗口中的字符串符合要求：包含 T 中所有字符。
3、停止增加 right ，转而不断增加 left 指针缩小窗口[left, right)（也就是 left++），直到窗口中的字符串不再符合要求：不包含 T 中所有字符。
4、同时，每增加 left，都要更新一轮结果。
5、重复 2 & 3 步骤，直到 right 到达字符串 S 的尽头。
6、第 2 步骤寻找「可行解」（符合要求），第 3 步骤优化「可行解」（找最短），最终找到「最优解」（最短的覆盖子串）。
7、左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动，这就是「滑动窗口」名字的来历。

2025年02月22日

【算法】滑动窗口1—窗口大小固定

一、定义

滑动窗口算法（Sliding Window Algorithm）是一种用于解决数组或字符串中子数组或子串问题的优化技术。它通过维护一个窗口（通常是数组或字符串的一个连续子区间），在遍历过程中动态调整窗口的起始和结束位置，从而高效地解决问题。

滑动窗口的核心思想是：

窗口大小固定：窗口的大小在滑动过程中保持不变。
窗口大小可变：窗口的大小根据条件动态调整。

二、使用场景

滑动窗口算法通常用于以下场景：

1.子数组/子串问题：

求满足条件的最大或最小子数组/子串。
例如：最大子数组和、最小覆盖子串、最长无重复字符子串等。

2.固定窗口大小问题：

例如：计算大小为 k 的子数组的平均值。

3.优化暴力解法：

将时间复杂度从 O(n²) 优化到 O(n)。

三、示例

1.例题1：固定窗口大小

【题目描述】给定一个数组和一个整数 k，计算所有大小为 k 的子数组的平均值。

【题目分析】

（1）什么是子数组？

子数组是数组中连续的一段元素。
例如，数组 [1, 3, 2, 6, -1] 的子数组包括 [1, 3, 2]、[3, 2, 6] 等。

（2）什么是大小为 `k` 的子数组？

大小为 k 的子数组是指长度为 k 的连续子数组。
例如，如果 k = 3，那么子数组的长度必须是 3。

（3）什么是子数组的平均值？

子数组的平均值是指子数组中所有元素的和除以子数组的长度。
例如，子数组 [1, 3, 2] 的平均值是 (1 + 3 + 2) / 3 = 2。

（4）问题的目标

对于数组中的每一个大小为 k 的子数组，计算其平均值，并返回所有平均值的集合。

【解题思路】

（1）暴力解法

遍历数组，对于每一个起始位置 i，计算从 i 到 i + k - 1 的子数组的和，然后除以 k 得到平均值。
时间复杂度：O(n * k)，其中 n 是数组的长度。

（2）滑动窗口优化

使用滑动窗口技术，避免重复计算子数组的和。
初始化第一个窗口的和，然后在滑动窗口时，加上新元素，减去旧元素。
时间复杂度：O(n)。

#include <iostream>  using namespace std;  void sw(int nums[], int n, int k) {      if (n < k) return; // 如果数组长度小于k，直接返回      double windowSum = 0;      // 初始化窗口      for (int i = 0; i < k; i++) {          windowSum += nums[i];      }      cout << windowSum / k << " ";      // 滑动窗口      for (int i = k; i < n; i++) {          windowSum += nums[i] - nums[i - k]; // 加上新元素，减去旧元素          cout << windowSum / k << " ";      }      cout << endl;  }    int main() {      int nums[] = {1, 3, 2, 6, -1, 4, 1, 8, 2};      int n = sizeof(nums) / sizeof(nums[0]);      int k = 5;      sw(nums, n, k);      return 0;  }

【过程解释】

初始化窗口：

计算第一个窗口的和 windowSum，即 nums[0] 到 nums[k-1] 的和。
输出第一个窗口的平均值 windowSum / k。

滑动窗口：

从第 k 个元素开始，滑动窗口。
每次滑动时，加上新元素 nums[i]，减去旧元素 nums[i - k]。
输出当前窗口的平均值 windowSum / k。

图示：

第一次：（1+3+2）/3

第二次：(3+2+6)/3 ，对比上一次，少了第一个数1，多了后一个数6

第二次：(2+6-1)/3 ，对比上一次，少了上一个数2，多了后一个数-1

2025年02月22日

【题解】摘花生问题

【题目描述】

Hello Kitty想摘点花生送给她喜欢的米老鼠。

她来到一片有网格状道路的矩形花生地(如下图)，从西北角进去，东南角出来。

地里每个道路的交叉点上都有种着一株花生苗，上面有若干颗花生，经过一株花生苗就能摘走该它上面所有的花生。

Hello Kitty只能向东或向南走，不能向西或向北走。

问Hello Kitty最多能够摘到多少颗花生。

【输入描述】

第一行是一个整数T，代表一共有多少组数据。

接下来是T组数据。

每组数据的第一行是两个整数，分别代表花生苗的行数R和列数 C。

每组数据的接下来R行数据，从北向南依次描述每行花生苗的情况。每行数据有C个整数，按从西向东的顺序描述了该行每株花生苗上的花生数目M。

【输出描述】

对每组输入数据，输出一行，内容为Hello Kitty能摘到得最多的花生颗数。

【样例输入】

2  2 2  1 1  3 4  2 3  2 3 4  1 6 5

【样例输出】

8  16

【数据范围】

1 ≤ T ≤ 100,

1 ≤ R, C ≤ 100,

0 ≤ M ≤ 1000

2025年02月06日

小S新买了一个掌上游戏机，这个游戏机由两节5号电池供电。为了保证能够长时间玩游戏，他买了很多5号电池，这些电池的生产商不同，质量也有差异，因而使用寿命也有所不同，有的能使用5个小时，有的可能就只能使用3个小时。显然如果他只有两个电池一个能用5小时一个能用3小时，那么他只能玩3个小时的游戏，有一个电池剩下的电量无法使用，但是如果他有更多的电池，就可以更加充分地利用它们，比如他有三个电池分别能用3、3、5小时，他可以先使用两节能用3个小时的电池，使用半个小时后再把其中一个换成能使用5个小时的电池，两个半小时后再把剩下的一节电池换成刚才换下的电池（那个电池还能用2.5个小时），这样总共就可以使用5.5个小时，没有一点浪费。

现在已知电池的数量和电池能够使用的时间，请你找一种方案使得使用时间尽可能的长。

【输入描述】

输入包含多组数据。每组数据包括两行，第一行是一个整数N(2≤N≤1000)，表示电池的数目，接下来一行是N个正整数表示电池能使用的时间。

【输出描述】

对每组数据输出一行，表示电池能使用的时间，保留到小数点后1位。

【样例输入】

2  3 5  3  3 3 5

【样例输出】

3.0  5.5