Python-算法编程100例-滑动窗口(入门级)

发布于:2024-06-29 ⋅ 阅读:(46) ⋅ 点赞:(0)

题目1:最大连续1的个数(简单)

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

解答:前缀和+双指针

# 给定一个二进制数组 nums , 计算其中最大连续 1 的个数。
from typing import List

class 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) + 1

        left = 0
        right = 0
        max_len_1 = 0
        while 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 += 1
            else:
                left += 1

        print(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 = 0
        count = 0
        max_len = 0
        for right in range(s):
            if nums[right] == 0:
                count += 1
            while count > k:
                # 结算
                max_len = max(max_len, right - left)
                if nums[left] == 0:
                    count -= 1
                left += 1
            max_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 = 0
        count = 0
        max_len = 0
        for right in range(s):
            if memory[right] == "x":
                count += 1
            while count > cnt:
                # 结算
                max_len = max(max_len, right - left)
                if memory[left] == "x":
                    count -= 1
                left += 1
            max_len = max(max_len, right - left + 1)

        print(max_len)

 

 


网站公告

今日签到

点亮在社区的每一天
去签到