滑动窗口相关题目

1. 近些年来，我国防沙治沙取得显著成果。某沙漠新种植N棵胡杨（编号1-N），排成一排。一个月后，有M棵胡杨未能成活。现可补种胡杨K棵，请问如何补种（只能补种，不能新种），可以得到最多的连续胡杨树？
   输入描述
   N 总种植数量
   M 未成活胡杨数量
   M 个空格分隔的数，按编号从小到大排列
   K 最多可以补种的数量
   其中：
   1 <= N <= 100000
   1 <= M <= N
   0 <= K <= M
   输出描述
   最多的连续胡杨棵树
   示例1 输入输出 示例仅供调试，后台判题数据一般不包含示例
   输入
   5
   2
   2 4
   1
   输出
   3
   说明
   补种到2或4结果一样，最多的连续胡杨棵树都是3。
   示例2
   输入
   10
   3
   2 4 7
   1
   输出
   6
   说明
   补种第7棵树，最多的连续胡杨棵树为6(5,6,7,8,9,10)

# 补种未成活胡杨 : 数组中元素的索引队列 + 滑动窗口
# 根据窗口中 0 的个数是否大于 k 个滑动 l 的位置
n = int(input())
m = int(input())
death = sorted(list(map(int, input().split(" "))))
k = int(input())trees = [-1] + [1] * n
for i in death:trees[i] = 0l, r, zero_pos, zero_cnt, one_cnt, ans = 1, 1, [], 0, 0, 0
while r < n + 1:if trees[r] == 0:zero_pos.append(r)zero_cnt += 1else:one_cnt += 1if zero_cnt > k:first_zero = zero_pos.pop(0)one_cnt -= sum(trees[l:first_zero])l = first_zero + 1zero_cnt -= 1# 窗口中存在的满足 k 条件的 zero_cnt 个数是可以变为 1 的ans = max(ans, one_cnt + zero_cnt)r += 1print(ans)

2. 一贫如洗的樵夫 阿里巴巴 在去砍柴的路上，无意中发现了强盗集团的藏宝地，藏宝地有编号从0-N的箱子，每个箱子上面贴有一个数字.阿里巴巴念出一个咒语数字k(k<N)，找出连续k个宝箱数字和的 最大值 ，并输出该最大值。
   输入描述
   第一行输入一个数字字串，数字之间使用逗号分隔，例如: 2,10,-3,-8,40,5。
   1≤字串中数字的个数≤100000
   -10000≤每个数字≤10000
   第二行输入咒语数字，例如: 4，咒语数字大小小于宝箱的个数
   输出描述
   连续k个宝箱数字和的最大值，例如: 39
   示例1：
   输入
   2,10,-3,-8,40,5
   4
   输出
   39
   示例2：
   输入
   8
   1
   输出
   8

# 阿里巴巴找黄金宝箱V : 滑动窗口
# 数组中连续 k 个数字 (数组中连续 k 长度的子序列) 的最大和
nums = list(map(int, input().split(",")))
k = int(input())n = len(nums)
l, r, win_sum, ans = 0, 0, 0, float("-inf")
while r < n:win_sum += nums[r]if r - l + 1 == k:ans = max(ans, win_sum)win_sum -= nums[l]l += 1r += 1print(ans)

# 上述 2 问题的变题
# 1. 给定一个字符串 s, 请你找出其中不含有重复字符的最长子串的长度。（小破站左神）
# https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/ 
class Solution:def lengthOfLongestSubstring(self, s: str) -> int:n = len(s)l, r, prev, ans = 0, 0, [-1] * 256, 0while r < n:# 窗口的左边界 l PK 当前字符上一次出现的位置 + 1 # 淘汰窗口中的重复字符l = max(l, prev[ord(s[r])] + 1)ans = max(ans, r - l + 1)prev[ord(s[r])] = rr += 1 return ans# 2. 给你一个整数数组 nums 和一个整数 k. 请你从 nums 中满足下述条件的全部子数组中找出最大子数组和：
# 子数组的长度是 k，且子数组中的所有元素各不相同。
# 返回满足题面要求的最大子数组和。如果不存在子数组满足这些条件，返回 0。
# 子数组是数组中一段连续非空的元素序列。
# https://leetcode.cn/problems/maximum-sum-of-distinct-subarrays-with-length-k/
class Solution:def maximumSubarraySum(self, nums: List[int], k: int) -> int:# 题目给出的数字范围MAXNUM = 100001   n = len(nums)l, r, win_sum, prev, ans = 0, 0, 0, [-1] * MAXNUM, float("-inf")while r < n:win_sum += nums[r]if prev[nums[r]] + 1 > l:# 窗口的累加和需要减去 （切片索引范围左闭右开）# [窗口的左边界 l, 当前数字 nums[r] 上一次出现的位置] 范围的累加和win_sum -= sum(nums[l:prev[nums[r]]+1])l = prev[nums[r]] + 1     if r - l + 1 == k:ans = max(ans, win_sum)win_sum -= nums[l]l += 1prev[nums[r]] = rr += 1return ans if ans != float("-inf") else 0

3. 给出数字K,请输出所有结果小于K的整数组合到一起的最少交换次数。组合一起是指满足条件的数字相邻，不要求相邻后在数组中的位置。
   数据范围
   -100 <= K <= 100
   -100 <= 数组中数值 <= 100
   输入描述
   第一行输入数组：1 3 1 4 0
   第二行输入K数值：2
   输出描述
   第一行输出最少交换次数：1
   示例1 输入输出示例仅供调试，后台判题数据一般不包含示例
   1 3 1 4 0
   2
   输出
   1
   备注
   小于2的表达式是1 1 0, 共三种可能将所有符合要求数字组合一起，最少交换1次。

# 最少交换次数 : 滑动窗口
# 1. 将数组中所有满足小于 K 条件的数字都看做 1, 不满足的看做 0
# 2. 要将窗口大小维持为数组中的所有 1 的个数 m, 利益最大化
# 3. 窗口中 0 的个数即为当前答案（所要交换的次数）
# 当窗口长度为整个数组中数字满足小于 K 的个数 m 时, 滑动 l 的位置
# 更新答案为 min 当前 m 长度的窗口 - 窗口中所有小于 K 的数字的个数
nums = list(map(int, input().split()))
k = int(input())arr = [1 if i < k else 0 for i in nums]
m = sum(arr)
if m == 0:print(0)exit()n = len(arr)
l, r, ans = 0, 0, float("inf")
while r < n:if r - l + 1 == m:ans = min(ans, m - sum(arr[l:r+1]))l += 1r += 1print(ans)

# 类似题目
# 交换定义为选中一个数组中的两个互不相同的位置并交换二者的值。
# 环形数组是一个数组, 可以认为第一个元素和最后一个元素相邻。
# 给你一个二进制环形数组 nums, 返回在任意位置将数组中的所有 1 聚集在一起需要的最少交换次数。
# https://leetcode.cn/problems/minimum-swaps-to-group-all-1s-together-ii/description/
class Solution:def minSwaps(self, nums: List[int]) -> int:n = len(nums)m = sum(nums)if m == 0:return 0arr = [*nums]for i in nums:arr.append(i)l, r, one_cnts, ans = 0, 0, 0, float("inf")while l < n:if arr[r]:one_cnts += 1if r - l + 1 == m:ans = min(ans, m - one_cnts)if arr[l]:one_cnts -= 1l += 1r += 1return ans if ans != float("inf") else 0    

4. 有N个正整数组成的一个序列。给定整数sum，求长度最长的连续 子序列 ，使他们的和等于sum，返回此子序列的长度如果没有满足要求的序列，返回-1。
   输入描述
   第一行输入是: N个正整数组成的一个序列
   第二行输入是: 给定整数sum
   输出描述
   最长的连续子序列的长度
   备注
   。输入序列仅由数字和英文逗号构成，数字之间采用英文逗号分隔
   。序列长度: 1 <= N <= 200
   。输入序列不考虑 异常情况
   示例1：
   输入
   1,2,3,4,2
   6
   输出
   3
   说明
   1,2,3和4,2两个序列均能满足要求，所以最长的连续序列为1,2,3，因此结果为3.
   示例2：
   输入
   1,2,3,4,2
   20
   输出
   -1
   说明
   没有满足要求的子序列，返回-1

# 最长连续子序列 : 滑动窗口
nums = list(map(int, input().split(",")))
target = int(input())n = len(nums)
l, r, win_sum, ans = 0, 0, 0, -1
while r < n:win_sum += nums[r]while win_sum - nums[l] >= target:win_sum -= nums[l]l += 1if win_sum == target:ans = max(ans, r - l + 1)r += 1print(ans)

5. 给定两个 字符串 s1 和 s2 和正整数k，其中 s1 长度为 n1，s2 长度为 n2，
   在s2中选一个子串，满足:
   1：该子串长度为n1+k
   2：该子串中包含s1中全部字母，
   3：该子串每个字母出现次数不小于s1中对应的字母，
   我们称s2以长度k 冗余 覆盖s1，
   给定s1，s2，k,
   求最左侧的s2以长度k冗余覆盖s1的子串的首个元素的下标，
   如果没有返回-1。
   输入描述：
   输入为三行
   第一行为 s1
   第二行为 s1
   第三行为 k
   s1和s2都只包含小写字母
   输出描述：
   最左侧的 s2 以长度 k 冗余覆盖 s1 的子串的首个元素下标，若不存在，则返回-1.
   示例1：
   输入：
   ab
   aabcd
   1
   输出：
   0
   示例2：
   输入：
   abc
   dfs
   10
   输出：
   -1

# 最左侧冗余覆盖子串 : 负债模型 + 滑动窗口
s1 = input().strip()
s2 = input().strip()
k = int(input().strip())n1, n2 = len(s1), len(s2)
if n1 + k > n2:print(-1)exit()cnt = [0] * 256
for i in s1:cnt[ord(i)] -= 1l, r, debt, ans = 0, 0, n1, -1
while r < n2:if cnt[ord(s2[r])] < 0:debt -= 1cnt[ord(s2[r])] += 1if debt == 0:while r - l + 1 > n1 + k:if cnt[ord(s2[l])] > 0:cnt[ord(s2[l])] -= 1l += 1if r - l + 1 == n1 + k:ans = lbreakr += 1print(ans)

6. 给定一个矩阵，包含N*M个整数，和一个包含K个整数的数组现在要求在这个矩阵中找一个宽度最小的子矩阵，要求子矩阵包含数组中所有的整数。
   输入描述
   第一行输入两个正整数N，M，表示矩阵大小。
   接下来N行M列表示矩阵内容。下一行包含一个正整数K。下一行包含K个整数，表示所需包含的数组，K个整数可能存在重复数字。
   所有输入数据小于1000。
   输出描述
   输出包含一个整数，表示满足要求子矩阵的最小宽度，若找不到，输出-1
   示例1
   输入
   2 5
   1 2 2 3 1
   2 3 2 3 2
   3
   1 2 3
   输出
   2
   说明
   矩阵第0、3列包含了1、2、3，矩阵第3、4列包含了1、2、3
   示例2
   输入
   2 5
   1 2 2 3 1
   1 3 2 3 4
   3
   1 1 4
   输出
   5
   说明
   矩阵第1,2,3,4,5列包含了1,1,4

# 宽度最小的子矩阵 : 负债模型 + 滑动窗口
n, m = list(map(int, input().split(" ")))
nums = []
for i in range(n):nums.append(list(map(int, input().split(" "))))
k = int(input())
target = list(map(int, input().split(" ")))MAXNUM = 1001
cnt = [0] * MAXNUM
for i in target:cnt[i] -= 1l, r, debt, width = 0, 0, k, float("inf")
while r < m:for i in range(n):if cnt[nums[i][r]] < 0:debt -= 1cnt[nums[i][r]] += 1if debt == 0:count = sum([1 if cnt[nums[i][l]] > 0 else 0 for i in range(n)])while count == n:count = sum([1 if cnt[nums[i][l]] > 0 else 0 for i in range(n)])if count == n:judge_all_duplicate = Falsefor i in range(n):cnt[nums[i][l]] -= 1for i in cnt:if i < 0:judge_all_duplicate = Truebreakif judge_all_duplicate:for i in range(n):cnt[nums[i][l]] += 1breakelse:l += 1width = min(width, r - l + 1)r += 1print(width if width != float("inf") else -1)

7. 一个 DNA 序列由 A/C/G/T 四个字母的 排列组合 组成。 G 和 C 的比例（定义为 GC-Ratio ）是序列中 G 和 C 两个字母的总的出现次数除以总的字母数目（也就是序列长度）。在基因工程中，这个比例非常重要。因为高的 GC-Ratio 可能是基因的起始点。给定一个很长的 DNA 序列，以及限定的子串长度 N ，请帮助研究人员在给出的 DNA 序列中从左往右找出 GC-Ratio 最高且长度为 N 的第一个子串。
   DNA序列为 ACGT 的子串有: ACG , CG , CGT 等等，但是没有 AGT ， CT 等等（这行内容毫无关系？）
   数据范围： 字符串长度 满足 1≤n≤1000，输入的字符串只包含 A/C/G/T 字母
   输入描述：
   输入一个string型基因序列，和int型子串的长度
   输出描述：
   找出GC比例最高的子串,如果有多个则输出第一个的子串
   示例1：
   输入
   ACGT
   2
   输出
   CG
   说明
   ACGT长度为2的子串有AC,CG,GT3个，其中AC和GT2个的GC-Ratio都为0.5，CG为1，故输出CG
   示例2：
   输入
   AACTGTGCACGACCTGA
   5
   输出
   GCACG
   说明
   虽然CGACC的GC-Ratio也是最高，但它是从左往右找到的GC-Ratio最高的第2个子串，所以只能输出GCACG。

# DNA序列 : 滑动窗口
s = input().strip()
k = int(input().strip())n = len(s)
l, r, max_ratio, start = 0, 0, float("-inf"), 0
while r < n:if r - l + 1 == k:cur = s[l:r+1]ratio = (cur.count("C") + cur.count("G")) / len(cur)if ratio > max_ratio:max_ratio = ratiostart = ll += 1r += 1print(s[start:start+k] if max_ratio != float("-inf") else "")

8. 公司用一个字符串来表示员工的出勤信息
   absent：缺勤
   late：迟到
   leaveearly：早退
   present：正常上班
   现需根据员工出勤信息，判断本次是否能获得出勤奖，能获得出勤奖的条件如下：
   缺勤不超过一次；
   没有连续的迟到/早退；
   任意连续7次考勤，缺勤/迟到/早退不超过3次。
   输入描述
   用户的考勤数据字符串，记录条数 >= 1；
   输入字符串长度 < 10000；
   不存在非法输入
   如：
   2
   present
   present absent present present leaveearly present absent
   输出描述
   根据考勤数据字符串，如果能得到考勤奖，输出”true”；否则输出”false”，
   对于输入示例的结果应为：
   true false
   示例1 输入输出示例仅供调试，后台判题数据一般不包含示例
   输入
   2
   present
   present present
   输出
   true true
   示例2 输入输出示例仅供调试，后台判题数据一般不包含示例
   输入
   2
   present
   present absent present present leaveearly present absent
   输出
   true false

# 考勤信息 : 字符串处理 + 滑动窗口
n = int(input())
records = []
for i in range(n):records.append(list(map(str, input().split(" "))))for kao_qin in records:m = len(kao_qin)nums = [0] * mabsent, present = 0, 0for i in range(m):if kao_qin[i] == "absent":nums[i] = -1absent += 1if kao_qin[i] == "present":nums[i] = 1present += 1if absent > 1:print("false", end=" ")continueif present == m:print("true", end=" ")continuel, r, prev_zero_pos, cnt, ans = 0, 0, -2, 0, Truewhile r < m:if nums[r] <= 0:if nums[r] == 0:prev_zero_pos = rcnt += 1if prev_zero_pos + 1 == r:ans = ans and Falsebreakif r - l + 1 == 7:ans = ans and cnt <= 3if not ans:breakif nums[l] <= 0:if nums[l] == 0:prev_zero_pos = -2 if prev_zero_pos == l else prev_zero_poscnt -= 1l += 1r += 1print("true" if ans else "false", end=" ")