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=" ")