当前位置: 首页 > news >正文

滑动窗口(尺取法/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[ik],a[ik+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)

滑动窗口&#xff08;尺取法&#xff09; 算法含义&#xff1a; 在解决关于区间特性的题目时保存搜索区间左右端点&#xff0c;然后根据实际要求不断更新左右端点位置的算法 时间复杂度&#xff1a; O ( n ) O(n) O(n) 空间复杂度&#xff1a; O ( 1 ) O(1) O(1) 在历年真题…...

【打印SQL执行日志】⭐️Mybatis-Plus通过配置在控制台打印执行日志

目录 前言 一、Mybatis-Plus 开启日志的方式 二、测试 三、日志分析 章末 前言 小伙伴们大家好&#xff0c;相信大家平时在处理问题时都有各自的方式&#xff0c;最常用以及最好用的感觉还是断点调试&#xff0c;但是涉及到操作数据库的执行时&#xff0c;默认的话在控制台…...

Vue后台管理系统常用组件的优缺点分析

以下是Vue后台管理系统常用组件的优缺点分析&#xff1a; Element UI 优点&#xff1a; 丰富的组件库&#xff1a;Element UI 提供了大量的组件&#xff0c;包括表单、表格、弹窗、导航等&#xff0c;可以满足各种后台管理系统的需求。易于使用&#xff1a;Element UI 的组件…...

栈的应用——用栈实现算数混合运算表达式的计算

1、单目运算符双目运算符 算数运算符分为单目运算符和双目运算符等 单目运算符只需要一个操作数,双目运算符需要两个操作数 双目运算符最常见:常见的算术运算符:*/,比较运算符:<>=等等以下是一些单目运算符:正号 (+): 用于表示正数或给数值一个正号。例如:+5 仍然…...

动态规划—机器人移动问题(Java)

&#x1f600;前言 机器人移动问题是一个经典的动态规划应用场景&#xff0c;它涉及到在给定范围内的位置上进行移动&#xff0c;并计算到达目标位置的方法数。本文将介绍三种解决这一问题的方法&#xff1a;暴力递归、缓存法和动态规划。通过比较不同方法的优缺点&#xff0c;…...

第十一届蓝桥杯物联网试题(省赛)

对于通信方面&#xff0c;还是终端A、B都保持接收状态&#xff0c;当要发送的数组不为空再发送数据&#xff0c;发送完后立即清除&#xff0c;接收数据的数组不为空则处理&#xff0c;处理完后立即清除&#xff0c;分工明确 继电器不亮一般可能是电压不够 将数据加空格再加\r…...

【Python基础教程】5. 数

&#x1f388;个人主页&#xff1a;豌豆射手^ &#x1f389;欢迎 &#x1f44d;点赞✍评论⭐收藏 &#x1f917;收录专栏&#xff1a;python基础教程 &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff0c;让我们共同学习、…...

Qt中出现中文乱码的原因以及解决方法

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

Linux 文件相关命令

一、查看文件命令 1&#xff09;浏览文件less 默认查看文件的前 10 行。 less /etc/services ##功能说明&#xff1a; #1.默认打开首屏内容 #2.按【回车】按行访问 #3.按【空格】按屏访问 #4.【从上向下】搜索用/111,搜索包含111的内容&#xff0c;此时按n继续向下搜&#x…...

K8S Deployment 简介, 1个简单的Kubernetes Deployment YAML 文件

当谈到 Kubernetes 集群中的应用程序部署和管理时&#xff0c;Deployment、ReplicaSet 和 Pod 是三个重要的概念。它们之间存在一定的关系和层次结构。下面是对 Deployment、ReplicaSet 和 Pod 的详细解释以及它们之间的关系。 Deployment&#xff08;部署&#xff09; Deploy…...

win11安装WSL UbuntuTLS

win11安装WSL WSL 简介WSL 1 VS WSL 2先决要求安装方法一键安装通过「控制面板」安装 WSL 基本命令Linux发行版安装Ubuntu初始化相关设置root用户密码网络工具安装安装1panel面板指导 WSl可视化工具问题总结WSL更新命令错误Ubuntu 启动初始化错误未解决问题 WSL 简介 Windows …...

第十题:金币

题目描述 国王将金币作为工资&#xff0c;发放给忠诚的骑士。第一天&#xff0c;骑士收到一枚金币&#xff1b;之后两天&#xff08;第二天和第三天&#xff09;&#xff0c;每天收到两枚金币&#xff1b;之后三天&#xff08;第四、五、六天&#xff09;&#xff0c;每天收到…...

Windows 11 中Docker的安装教程

选择正确的Docker版本 在Windows上&#xff0c;你可以安装两种类型的Docker&#xff1a;Docker Desktop和Docker Toolbox。Docker Desktop是针对Windows 10 Pro、Enterprise和Education版本的&#xff0c;这些版本内置了Hyper-V虚拟化支持。对于旧版本的Windows&#xff0c;比…...

纯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 入门赛&#xff0c;详细讲解了整个数据处理流程&#xff0c;以及如何从零构建一个模型&#xff0c;适合新手入门。 赛题以新闻数据为赛题数据&#xff0c;数据集报名后可见并可下载。赛题数据为新闻文本&#xff0c;并按照字符级别进行匿名…...

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

Spring声明式事务以及事务传播行为

Spring声明式事务以及事务传播行为 Spring声明式事务1.编程式事务2.使用AOP改造编程式事务3.Spring声明式事务 事务传播行为 如果对数据库事务不太熟悉&#xff0c;可以阅读上一篇博客简单回顾一下&#xff1a;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…...

el-upload上传图片图片、el-load默认图片重新上传、el-upload初始化图片、el-upload编辑时回显图片

问题 我用el-upload上传图片&#xff0c;再上一篇文章已经解决了&#xff0c;el-upload上传图片给SpringBoot后端,但是又发现了新的问题&#xff0c;果然bug是一个个的冒出来的。新的问题是el-upload编辑时回显图片的保存。 问题描述&#xff1a;回显图片需要将默认的 file-lis…...

【拓扑空间】示例及详解1

例1 度量空间的任意两球形邻域的交集是若干球形邻域的并集 Proof&#xff1a; 任取空间的两个球形邻域、&#xff0c;令 任取,令 球形领域 例2 规定X的子集族,证明是X上的一个拓扑 Proof&#xff1a; 1. 2., &#xff08;若干个球形邻域的并集都是的元素&#xff0c;元素…...

linux安装jdk8

上传到某个目录&#xff0c;例如&#xff1a;/usr/local/ tar -xvf jdk-8u144-linux-x64.tar.gz配置环境变量&#xff1a; export JAVA_HOME/usr/local/java export PATH$PATH:$JAVA_HOME/bin设置环境变量&#xff1a; source /etc/profile...

Spring重点知识(个人整理笔记)

目录 1. 为什么要使用 spring&#xff1f; 2. 解释一下什么是 Aop&#xff1f; 3. AOP有哪些实现方式&#xff1f; 4. Spring AOP的实现原理 5. JDK动态代理和CGLIB动态代理的区别&#xff1f; 6. 解释一下什么是 ioc&#xff1f; 7. spring 有哪些主要模块&#xff1f;…...

HTML基础知识详解(上)(如何想知道html的全部基础知识点,那么只看这一篇就足够了!)

前言&#xff1a;在学习前端基础时&#xff0c;必不可少的就是三大件&#xff08;html、css、javascript &#xff09;&#xff0c;而HTML&#xff08;超文本标记语言——HyperText Markup Language&#xff09;是构成 Web 世界的一砖一瓦&#xff0c;它定义了网页内容的含义和…...

如何借助Idea创建多模块的SpringBoot项目

目录 1.1、前言1.2、开发环境1.3、项目多模块结构1.4、新建父工程1.5、创建子模块1.6、编辑父工程的pom.xml文件 1.1、前言 springmvc项目&#xff0c;一般会把项目分成多个包:controler、service、dao、utl等&#xff0c;但是随着项目的复杂性提高&#xff0c;想复用其他一个模…...

爬虫 新闻网站 并存储到CSV文件 以红网为例 V1.0

爬虫&#xff1a;红网网站&#xff0c; 获取当月指定关键词新闻&#xff0c;并存储到CSV文件 V1.0 目标网站&#xff1a;红网 爬取目的&#xff1a;为了获取某一地区更全面的在红网已发布的宣传新闻稿&#xff0c;同时也让自己的工作更便捷 环境&#xff1a;Pycharm2021&#…...

CentOS 使用 Cronie 实现定时任务

CentOS 使用 Cronie 实现定时任务 文章目录 CentOS 使用 Cronie 实现定时任务一、简介二、基本使用1、常用命令2、使用示例第一步&#xff1a;创建脚本/home/create.sh第二步&#xff1a;添加定时任务第三步&#xff1a;重启 cronie 服务额外&#xff1a;查看 cronie 运行状态定…...

java生成word

两种方案 一、poi-tl生成word <dependency><groupId>com.deepoove</groupId><artifactId>poi-tl</artifactId><version>1.12.1</version> </dependency> public static void main(String[] args) throws Exception {String…...

C语言中的结构体:揭秘数据的魔法盒

前言 在C语言的广阔天地中&#xff0c;结构体无疑是一颗璀璨的明珠。它就像是一个魔法盒&#xff0c;能够容纳各种不同类型的数据&#xff0c;并按我们的意愿进行组合和排列。那么&#xff0c;这个魔法盒究竟有何神奇之处呢&#xff1f;让我们一探究竟。 一、结构体的诞生&…...

前端网站模板/推广引流方法有哪些推广方法

1 Region拆分 一个Region代表一个表的一段Rowkey的数据集合&#xff0c;当Region太大&#xff0c;Master会将其拆分。Region太大会导致读取效率太低&#xff0c;遍历时间太长&#xff0c;通过将大数据拆分到不同机器上&#xff0c;分别查询再聚合&#xff0c;Hbase也被人称为“…...

优秀网站 要素/怎么制作网站教程

(Owed by: 春夜喜雨 http://blog.csdn.net/chunyexiyu 转载请标明来源) 一般我们可见的图形RGB三元色。对Alpha通道的话。它不一定会显示到窗口中来。 在Windows窗口中要展示一张透明图相对还是比較困难的&#xff0c; 1. 比如像windows查看器那样&#xff0c;使透明像素显…...

做网站需要下载啥/网络营销出来可以干什么工作

今天突然想到Java反射。然后测试了一下1.8.0_191版本的反射性能&#xff0c;没想到反射竟然比直接调用性能还高。 反射介绍 Java反射是指在程序运行状态中&#xff0c;能检查任意对象的内容并调用任意方法。对于任何一个对象&#xff0c;我们都能够对它的方法和属性进行调用。…...

商业网站定义/seo sem

“秋招“求职季已经过了大半&#xff0c;有的小伙伴已经在这个赛季的前半段成功突围&#xff0c;顺利地找到了心仪的新东家&#xff0c;还有部分小伙伴仍每天苦苦煎熬&#xff0c;不得上岸&#xff0c;辗转在面试之间。 说到求职面试&#xff0c;不得不提的就是那些“招人恨”…...

网站注销流程/seo优化教程下载

年轻的时候&#xff0c;常常以程序员自诩&#xff0c;涓涓代码流于键盘之下&#xff0c;那是何等的满足&#xff01;如今已过而立&#xff0c;随着小儿的出生&#xff0c;青涩自负的青春早已作古&#xff0c;现在的我在做什么呢&#xff1f;该做些什么呢&#xff1f;心里的头绪…...

学校网站建设整改报告/舆情分析系统

三种方法任选一种&#xff1a; 1&#xff1a;用记事本打开对应csproj文件&#xff0c;把里面的" <SignManifests>true</SignManifests> "改成"<SignManifests>false</SignManifests>". 2&#xff1a;用记事本打开项目的.csproj文件…...