滑动窗口(尺取法/Python)
滑动窗口(尺取法)
算法含义:
在解决关于区间特性的题目时保存搜索区间左右端点,然后根据实际要求不断更新左右端点位置的算法
时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( 1 ) O(1) O(1)
在历年真题中,滑动窗口主要有求追偿不重复子串和模拟优先队列求区间最值两个作用
一、求最长不重复字串
不重复子串:字符串的字串中不包含重复字符的字串
from collections import defaultdicts = input()
n = len(s)
# 建立一个字典存储各个元素在窗口中出现的次数
d = defaultdict(int)
ans = 0
# 确定窗口左端
left = 0
for right in range(n):# 如果发现窗口中已经有s[right],将left右移直到窗口中不存在s[right]while d[s[right]] > 0:# 更新字典d[s[left]] -= 1left += 1ans = max(ans, right-left+1)print(ans)
二、模拟优先队列求区间最值
滑动窗口研究区间的性质,可以用于模拟优先队列从而高效求出区间内的最大值和最小值
例题 1: 附近最小(蓝桥杯第14届省模拟赛)
问题描述:
小蓝有一个序列 a [ 1 ] , a [ 2 ] , . . . , a [ n ] a[1],a[2],...,a[n] a[1],a[2],...,a[n]。给定一个正整数 k,请问对于每一个 1 到 n 之间的正整数i, a [ i − k ] , a [ i − k + 1 ] , . . . , a [ i + k ] a[i−k],a[i−k+1],...,a[i+k] a[i−k],a[i−k+1],...,a[i+k] 这 2k+1 个数中的最小值是多少?
当某个下标超过 1 到 n 的范围时,数不存在,求最小值时只取存在的那些值。
输入格式:
输入的第一行包含一整数 n,第二行包含 n 个整数,分别表示 a [ 1 ] , a [ 2 ] , . . . , a [ n ] a[1],a[2],...,a[n] a[1],a[2],...,a[n]。第三行包含一个整数 k
输出格式
输出一行,包含 n 个整数,分别表示对于每个序号求得的最小值。
代码示例:
# 滑动窗口 + 优先队列
n = int(input())
a = [int(i) for i in input().split()]
k = int(input())
# 在数组右边补k个一定不是最小值的数以免分类讨论
a = a + [a[n-1]+1]*k
d = k*2+1 # 窗口宽度
ans = []
q = [] # 递增的优先队列
# 注意i是滑动窗口的右端点
for i in range(n+k):# 如果队列不为空,将所有大于当前元素的队尾元素出队while q and a[q[-1]] > a[i]:q.pop()# 将新元素的下标入队q.append(i)# 检查队头元素是否在新区间范围内if i - q[0] > d-1:q.pop(0)# 将队头元素记录下来if i >= k:ans.append(a[q[0]])# print answer
print(' '.join(list(map(str, ans))))
例题 2: 子矩阵(蓝桥杯第14届省赛真题)
问题描述:
给定一个n x m(n行m列)的矩阵。设一个矩阵的价值为其所有数中的最大值和最小值的乘积。求给定矩阵的所有大小为 a x b (a行b列)的子矩阵的价值的和。答案可能很大,你只需要输出答案对 998244353 取模后的结果。
输入格式:
输入的第一行包含四个整数分别表示n,m,a,b,相邻整数之间使用一个空格分隔。接下来
n行每行包含m个整数,相邻整数之间使用一个空格分隔,表示矩阵中的每个数 A i j A_{ij} Aij。
输出格式
输出一行包含一个整数表示答案。
# 利用滑动窗口模拟优先队列,从而将搜索每一个区间中最值的时间复杂度从O(n*n)优化为O(n)
MOD = 998244353
def get_max(nums,step):# the variable called step store the size of intervalq = []max_list = []for i in range(len(nums)):while q and nums[q[-1]] < nums[i]:# when the end element of prior-quee is small than the new element# pop out the end elementq.pop(-1)# the list store the index of every number because it is more convenient to find # out whether the index is out of the interval or not q.append(i)# when the first element is out of the range of interval, pop it outif q[0] <= i-step:q.pop(0)# when the queue has been built, add the first element into the answer listif i >= step-1:max_list.append(nums[q[0]])return max_list
# using the same theory,we can find out the minist number
def get_min(nums,step):q = []min_list = []for i in range(len(nums)):while q and nums[q[-1]] > nums[i]:q.pop(-1)q.append(i)if q[0] <= i-step:q.pop(0)if i >= step-1:min_list.append(nums[q[0]])return min_list
# similarly,we can calculate out the sum of all the numbers in the interval
def get_sum(nums,step):sum_list = []temp = 0# the pointer called i is actually the right pointer# the left pointer's value is i-step+1for i in range(len(nums)):if i < step - 1:temp += nums[i]elif i == step-1:temp += nums[i]sum_list.append(temp)else:temp -= nums[i-step]temp += nums[i]sum_list.append(temp)return sum_list# the main part of the algorithm
# firstly,use the function to find out all the line's extremum
n,m,a,b = map(int,input().split())
matrix = []
for i in range(n):matrix.append([int(j) for j in input().split()])
# zip the row
m_max_one = []
m_min_one = []
for i in range(n):m_max_one.append(get_max(matrix[i], b))m_min_one.append(get_min(matrix[i], b))
# transpose the temporary matrix and zip again
# the result is the collection of extremum matrix
m_max_two = [[0]*n for i in range(len(m_max_one[0]))]
m_min_two = [[0]*n for i in range(len(m_min_one[0]))]
for i in range(len(m_max_one[0])):for j in range(len(m_max_one)):m_max_two[i][j] = m_max_one[j][i]m_min_two[i][j] = m_min_one[j][i]
# zip the col
m_max = []
m_min = []
for i in range(len(m_max_two)):m_max.append(get_max(m_max_two[i], a))m_min.append(get_min(m_min_two[i], a))
# calculate the sum of all the sub_matrixs' value
res = 0
for i in range(len(m_max)):for j in range(len(m_max[0])):res += m_max[i][j]*m_min[i][j]res %= MOD
print(res)
相关文章:
滑动窗口(尺取法/Python)
滑动窗口(尺取法) 算法含义: 在解决关于区间特性的题目时保存搜索区间左右端点,然后根据实际要求不断更新左右端点位置的算法 时间复杂度: O ( n ) O(n) O(n) 空间复杂度: O ( 1 ) O(1) O(1) 在历年真题…...

【打印SQL执行日志】⭐️Mybatis-Plus通过配置在控制台打印执行日志
目录 前言 一、Mybatis-Plus 开启日志的方式 二、测试 三、日志分析 章末 前言 小伙伴们大家好,相信大家平时在处理问题时都有各自的方式,最常用以及最好用的感觉还是断点调试,但是涉及到操作数据库的执行时,默认的话在控制台…...
Vue后台管理系统常用组件的优缺点分析
以下是Vue后台管理系统常用组件的优缺点分析: Element UI 优点: 丰富的组件库:Element UI 提供了大量的组件,包括表单、表格、弹窗、导航等,可以满足各种后台管理系统的需求。易于使用:Element UI 的组件…...

栈的应用——用栈实现算数混合运算表达式的计算
1、单目运算符双目运算符 算数运算符分为单目运算符和双目运算符等 单目运算符只需要一个操作数,双目运算符需要两个操作数 双目运算符最常见:常见的算术运算符:*/,比较运算符:<>=等等以下是一些单目运算符:正号 (+): 用于表示正数或给数值一个正号。例如:+5 仍然…...
动态规划—机器人移动问题(Java)
😀前言 机器人移动问题是一个经典的动态规划应用场景,它涉及到在给定范围内的位置上进行移动,并计算到达目标位置的方法数。本文将介绍三种解决这一问题的方法:暴力递归、缓存法和动态规划。通过比较不同方法的优缺点,…...

第十一届蓝桥杯物联网试题(省赛)
对于通信方面,还是终端A、B都保持接收状态,当要发送的数组不为空再发送数据,发送完后立即清除,接收数据的数组不为空则处理,处理完后立即清除,分工明确 继电器不亮一般可能是电压不够 将数据加空格再加\r…...

【Python基础教程】5. 数
🎈个人主页:豌豆射手^ 🎉欢迎 👍点赞✍评论⭐收藏 🤗收录专栏:python基础教程 🤝希望本文对您有所裨益,如有不足之处,欢迎在评论区提出指正,让我们共同学习、…...

Qt中出现中文乱码的原因以及解决方法
Qt专栏:http://t.csdnimg.cn/C2SDN 目录 1.引言 2.原因分析 3.源文件的编码格式修改方法 4.程序内部使用的默认编码格式修改方法 5.QString转std::string的方法 6.总结 1.引言 在编写Qt程序的时候,或多或少都可能遇到用QString时候,明明…...

Linux 文件相关命令
一、查看文件命令 1)浏览文件less 默认查看文件的前 10 行。 less /etc/services ##功能说明: #1.默认打开首屏内容 #2.按【回车】按行访问 #3.按【空格】按屏访问 #4.【从上向下】搜索用/111,搜索包含111的内容,此时按n继续向下搜&#x…...
K8S Deployment 简介, 1个简单的Kubernetes Deployment YAML 文件
当谈到 Kubernetes 集群中的应用程序部署和管理时,Deployment、ReplicaSet 和 Pod 是三个重要的概念。它们之间存在一定的关系和层次结构。下面是对 Deployment、ReplicaSet 和 Pod 的详细解释以及它们之间的关系。 Deployment(部署) Deploy…...

win11安装WSL UbuntuTLS
win11安装WSL WSL 简介WSL 1 VS WSL 2先决要求安装方法一键安装通过「控制面板」安装 WSL 基本命令Linux发行版安装Ubuntu初始化相关设置root用户密码网络工具安装安装1panel面板指导 WSl可视化工具问题总结WSL更新命令错误Ubuntu 启动初始化错误未解决问题 WSL 简介 Windows …...
第十题:金币
题目描述 国王将金币作为工资,发放给忠诚的骑士。第一天,骑士收到一枚金币;之后两天(第二天和第三天),每天收到两枚金币;之后三天(第四、五、六天),每天收到…...
Windows 11 中Docker的安装教程
选择正确的Docker版本 在Windows上,你可以安装两种类型的Docker:Docker Desktop和Docker Toolbox。Docker Desktop是针对Windows 10 Pro、Enterprise和Education版本的,这些版本内置了Hyper-V虚拟化支持。对于旧版本的Windows,比…...

纯C代码模板
一、快排 void QuickSort(int *a,int left,int right){if(left>right) return;else{int low left,high right;int pivot a[low];while(low<high){while(a[high] > pivot && low < high){high--;}a[low] a[high]; //必须先动a[low]while(a[low] < …...

二、GitLab相关操作
GitLab相关操作 一、组、用户、项目管理1.创建组2.创建项目3.创建用户并分配组3.1 创建用户3.2 设置密码3.3 给用户分配组 二、拉取/推送代码1.配置ssh(第一次需要)1.1 创建一个空文件夹1.2 配置本地仓账号和邮箱1.3 生成ssh公钥密钥1.4 gitlab配置公钥 2.拉取代码3.推送代码3.…...
【详细注释+流程讲解】基于深度学习的文本分类 TextCNN
前言 这篇文章用于记录阿里天池 NLP 入门赛,详细讲解了整个数据处理流程,以及如何从零构建一个模型,适合新手入门。 赛题以新闻数据为赛题数据,数据集报名后可见并可下载。赛题数据为新闻文本,并按照字符级别进行匿名…...
Day.21
interface MyInterface{public final static int PI 3;void show();public default void printX(){System.out.println("接口默认方法");}public static void printY(){System.out.println("接口静态方法");}}class MyClass implements MyInterface{publi…...

Spring-IoC 基于注解
基于xml方法见:http://t.csdnimg.cn/dir8j 注解是代码中的一种特殊标记,可以在编译、类加载和运行时被读取,执行相应的处理,简化 Spring的 XML配置。 格式:注解(属性1"属性值1",...) 可以加在类上…...

Spring声明式事务以及事务传播行为
Spring声明式事务以及事务传播行为 Spring声明式事务1.编程式事务2.使用AOP改造编程式事务3.Spring声明式事务 事务传播行为 如果对数据库事务不太熟悉,可以阅读上一篇博客简单回顾一下:MySQL事务以及并发访问隔离级别 Spring声明式事务 事务一般添加到…...
【C语言数据库】Sqlite3基础介绍
1. SQLite简介 SQLite is a C-language library that implements a small, fast, self-contained, high-reliability, full-featured, SQL database engine. SQLite is the most used database engine in the world. SQLite is built into all mobile phones and most computer…...
ES6从入门到精通:前言
ES6简介 ES6(ECMAScript 2015)是JavaScript语言的重大更新,引入了许多新特性,包括语法糖、新数据类型、模块化支持等,显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var…...

无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...
Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?
Redis 的发布订阅(Pub/Sub)模式与专业的 MQ(Message Queue)如 Kafka、RabbitMQ 进行比较,核心的权衡点在于:简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化
缓存架构 代码结构 代码详情 功能点: 多级缓存,先查本地缓存,再查Redis,最后才查数据库热点数据重建逻辑使用分布式锁,二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...
Linux系统部署KES
1、安装准备 1.版本说明V008R006C009B0014 V008:是version产品的大版本。 R006:是release产品特性版本。 C009:是通用版 B0014:是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存:1GB 以上 硬盘…...

Appium下载安装配置保姆教程(图文详解)
目录 一、Appium软件介绍 1.特点 2.工作原理 3.应用场景 二、环境准备 安装 Node.js 安装 Appium 安装 JDK 安装 Android SDK 安装Python及依赖包 三、安装教程 1.Node.js安装 1.1.下载Node 1.2.安装程序 1.3.配置npm仓储和缓存 1.4. 配置环境 1.5.测试Node.j…...

河北对口计算机高考MySQL笔记(完结版)(2026高考)持续更新~~~~
MySQL 基础概念 数据(Data):文本,数字,图片,视频,音频等多种表现形式,能够被计算机存储和处理。 **数据库(Data Base—简称DB):**存储数据的仓库…...
SE(Secure Element)加密芯片与MCU协同工作的典型流程
以下是SE(Secure Element)加密芯片与MCU协同工作的典型流程,综合安全认证、数据保护及防篡改机制: 一、基础认证流程(参数保护方案) 密钥预置 SE芯片与MCU分别预置相同的3DES密钥(Key1、Key2…...

短视频时长预估算法调研
weighted LR o d d s T p 1 − p ( 1 − p ) o d d s T p ( T p o d d s ∗ p ) o d d s p o d d s T o d d s odds \frac{Tp}{1-p} \newline (1-p)odds Tp \newline (Tp odds * p) odds \newline p \frac{odds}{T odds} \newline odds1−pTp(1−p)oddsTp(Tpodds…...
Steam爬取相关游戏评测
## 因为是第一次爬取Steam。所以作为一次记录发出;有所错误欢迎指出。 无时间指定爬取 import requests import time import csv import osappid "553850" # 这里你也可以改成 #appid int(input()) max_reviews 10000 # 想爬多少条 # max_reviews…...