Python-算法编程100例-滑动窗口（入门级）

题目1：最大连续1的个数（简单）

给定一个二进制数组 nums ， 计算其中最大连续 1 的个数。

解答：前缀和+双指针

# 给定一个二进制数组 nums ， 计算其中最大连续 1 的个数。
from typing import Listclass Solution:def findMaxConsecutiveOnes(self, nums: List[int]) -> int:idx_1 = []count_0 = [0] * len(nums)for i in range(len(nums)):if nums[i] == 1:idx_1.append(i)count_0[i] = i - len(idx_1) + 1left = 0right = 0max_len_1 = 0while right < len(idx_1):flaw_0 = count_0[idx_1[right]] - count_0[idx_1[left]]if flaw_0 == 0:max_len_1 = max(max_len_1, right-left+1)right += 1else:left += 1print(max_len_1)

题目2：最大连续1的个数（中等）

给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。

解答：滑动窗口-贪吃蛇-右边无脑滑动、坐边看情况收缩

from typing import List
# 贪吃蛇-右边无脑滑动、坐边看情况收缩
class Solution:def longestOnes(self, nums: List[int], k: int) -> int:s = len(nums)left = 0count = 0max_len = 0for right in range(s):if nums[right] == 0:count += 1while count > k:# 结算max_len = max(max_len, right - left)if nums[left] == 0:count -= 1left += 1max_len = max(max_len, right - left + 1)print(max_len)

题目3：最长空闲内存

某系统中有一空间连续的内存，被划分成多个大小相同的内存块。内存的使用状态记录在字符串memory中，每个内存块状态用x或者.表示，
# 其中x表示内存被使用，.表示内存空闲
现在最多可以释放其中cnt个内存块（即将字符串中的x变成.）,以获得一块空间连续的且最长的空闲内存，请计算并返回该最长空闲内存的内存块数量

解答：动窗口-贪吃蛇-右边无脑滑动、坐边看情况收缩

class Solution:def max_free_memory(self, memory, cnt):s = len(memory)left = 0count = 0max_len = 0for right in range(s):if memory[right] == "x":count += 1while count > cnt:# 结算max_len = max(max_len, right - left)if memory[left] == "x":count -= 1left += 1max_len = max(max_len, right - left + 1)print(max_len)