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

备战蓝桥杯:双指针(滑动窗口)算法之逛花展

P1638 逛画展 - 洛谷 | 计算机科学教育新生态

这道题我们只要用一个kind和一个mp[N]的数组就能解决了

我们的解法1就是暴力枚举,先固定2,从2开始找连续的满足所有种类的最短的子数组,然后固定5,3,1,3,2,分别找出满足所有种类的最短子数组

mp[i]如果是从0到1,kind++,如果是从1到0,kind--

如图,暴力枚举的话j指向的一定是第一次出现的最新的元素种类,如果我们是暴力枚举的话,我们枚举5的时候,j也会回到5

我们对5枚举的时候,j一定会再走到4那个位置,我们何必让j回退呢?

那我们的算法流程就是用left和right指针指向第一个元素,然后让right指针向后走把每个元素进窗口,如果kind种类够了的话,left不断++,再不断更新每个合法的子数组的大小,直到kind不够了再退出去继续right向后走

比如这是一种结果,2出窗口后又是一个结果 

5出窗口后种类不够了,j向后走

不满足要求就不更新结果直到再次符合要求,我们再次让left出窗口

到这里把3出窗口之后再次成为不合法数组

再次合法,继续出left,出了一个就不合法了,right向后走一格,结束

我们来展示一下代码

#include <iostream>
using namespace std;const int N = 1e6+10;
int n,m;
int mp[N];
int a[N];
int main()
{cin >> n  >> m;for(int i = 1;i<=n;i++) cin >> a[i];int kind = 0;int left = 1 , right = 1;int ret = n,begin = 1;while(right<=n){if(mp[a[right]]++ == 0) kind++;while(kind == m){int len = right-left+1;if(len < ret){ret = len;begin = left;}if(mp[a[left]]-- == 1) kind--;left++;}	right++;}cout << begin <<" " << begin+ret-1<< endl;return 0;
}

相关文章:

备战蓝桥杯:双指针(滑动窗口)算法之逛花展

P1638 逛画展 - 洛谷 | 计算机科学教育新生态 这道题我们只要用一个kind和一个mp[N]的数组就能解决了 我们的解法1就是暴力枚举&#xff0c;先固定2&#xff0c;从2开始找连续的满足所有种类的最短的子数组&#xff0c;然后固定5&#xff0c;3&#xff0c;1&#xff0c;3&…...

Linux如何设置软件开机启动呢?

有很多软件&#xff0c;我们安装完之后&#xff0c;服务器一旦重启&#xff0c;软件也需要我们手动再次启动&#xff0c;有很多的软件我们不想手动重启&#xff0c;例如Redis、Mysql、MQ等&#xff0c;那我们怎么配置软件跟着服务器也一起启动呢&#xff0c;今天就给大家带来软…...

Vue(3)

一.生命周期及其四个阶段 Vue生命周期&#xff1a;一个Vue实例从创建到销毁的整个过程 生命周期四个阶段&#xff1a;①创建②挂载③更新④销毁 <body><div id"app"><h3>{{ title }}</h3><div><button click"count--"&…...

11vue3实战-----封装缓存工具

11vue3实战-----封装缓存工具 1.背景2.pinia的持久化思路3.以localStorage为例解决问题4.封装缓存工具 1.背景 在上一章节&#xff0c;实现登录功能时候&#xff0c;当账号密码正确&#xff0c;身份验证成功之后&#xff0c;把用户信息保存起来&#xff0c;是用的pinia。然而p…...

第16章 Single Thread Execution设计模式(Java高并发编程详解:多线程与系统设计)

简单来说&#xff0c; Single Thread Execution就是采用排他式的操作保证在同一时刻只能有一个线程访问共享资源。 1.机场过安检 1.1非线程安全 先模拟一个非线程安全的安检口类&#xff0c;旅客(线程)分别手持登机牌和身份证接受工作人员的检查&#xff0c;示例代码如所示。…...

MySQL 8.0.41 终端修改root密码

1.在 MySQL 命令行中&#xff0c;运行以下命令修改密码 ALTER USER rootlocalhost IDENTIFIED BY new_password; 其中&#xff0c;new_password替换为你想要设置的新密码 2.退出 MySQL终端&#xff0c;重新打开&#xff0c;使用新密码进入&#xff0c;修改成功...

微信小程序案例2——天气微信小程序(学会绑定数据)

文章目录 一、项目步骤1 创建一个weather项目2 进入index.wxml、index.js、index.wxss文件,清空所有内容,进入App.json,修改导航栏标题为“中国天气网”。3进入index.wxml,进行当天天气情况的界面布局,包括温度、最低温、最高温、天气情况、城市、星期、风行情况,代码如下…...

android的Compose 简介

Jetpack Compose 简介 Jetpack Compose 是 Android 官方推出的声明式 UI 工具包&#xff0c;用于替代传统 XML 布局&#xff0c;简化界面开发流程。它基于 Kotlin 语言&#xff0c;通过函数式编程实现高效、灵活的 UI 构建&#xff0c;支持实时预览和更直观的状态管理。 优势…...

缓存实战:Redis 与本地缓存

引言 在现代互联网应用中&#xff0c;缓存是提升系统性能和用户体验的关键技术之一。通过将频繁访问的数据存储在快速访问的存储介质中&#xff0c;可以显著减少对数据库的直接访问压力&#xff0c;从而提高系统的响应速度和吞吐量。 本文将从实战的角度出发&#xff0c;详细…...

apisix的real-ip插件使用说明

k8s集群入口一般都需要过负载均衡&#xff0c;然后再到apisix。 这时候如果后台业务需要获取客户端ip&#xff0c;可能拿到的是lb或者网关的内网ip。 这里一般要获取真实ip需要做几个处理。 1. 负载均衡上&#xff0c;一般支持配置获取真实ip参数&#xff0c;需要配置上。然…...

音视频协议

1. 多媒体信息 1.1 多媒体信息的两个主要特点&#xff1a; 信息量很大 标准语音&#xff1a;64Kbits(8KHz采样&#xff0c;8位编码)高质量音频&#xff1a;3Mbps(100KHz采样&#xff0c;12位编码) 在传输多媒体数据时&#xff0c;对时延和时延抖动均有较高要求 1.2 处理时延…...

第一财经对话东土科技 | 探索工业科技新边界

当前以ChatGPT、Sora等为代表的生成式人工智能快速发展&#xff0c;越来越多面向垂直场景的行业大模型涌现出来&#xff0c;并成为推动制造业智能化改造与数字化转型、加快推进新型工业化&#xff0c;进而培育发展新质生产力的新引擎。 在垂类场景的应用落地&#xff0c;是AI发…...

Maven 与企业项目的集成

1. Maven 在企业级项目中的作用 Maven 是 Java 生态中最流行的构建和依赖管理工具&#xff0c;广泛用于企业级项目的构建、依赖管理、测试、打包、部署和 CI/CD 集成。对于大型企业项目&#xff0c;Maven 提供了一整套标准化的构建流程&#xff0c;并支持 多模块&#xff08;M…...

激活函数篇 01 —— 激活函数在神经网络的作用

欢迎来到我的主页&#xff1a;【Echo-Nie】 本篇文章收录于专栏【机器学习】 以下是激活函数系列的相关的所有内容: 激活函数篇 01 —— 一文搞懂激活函数在神经网络中的作用 逻辑回归&#xff1a;Sigmoid函数在分类问题中的应用 1 激活函数的作用 1.1 引入非线性 激活函数…...

22.2、Apache安全分析与增强

目录 Apache Web安全分析与增强 - Apache Web概述Apache Web安全分析与增强 - Apache Web安全威胁Apache Web安全机制Apache Web安全增强 Apache Web安全分析与增强 - Apache Web概述 阿帕奇是一个用于搭建WEB服务器的应用程序&#xff0c;它是开源的&#xff0c;它的配置文件…...

Day.23

leetcode 413.等差数列划分 问题&#xff1a;如果一个数列 至少有三个元素 &#xff0c;并且任意两个相邻元素之差相同&#xff0c;则称该数列为等差数列。给你一个整数数组 nums &#xff0c;返回数组 nums 中所有为等差数组的 子数组 个数。 子数组 是数组中的一个连续序列…...

CentOS虚机在线扩容系统盘数据盘

最近在制作Openstack下的镜像&#xff0c;用户需要CentOS6以及CentOS7的虚机镜像&#xff0c;遇到了些关于系统盘以及数据盘在线扩容的问题&#xff0c;故此整理一下。 ​ 传统我们想对磁盘在线热扩容&#xff0c;必然会想到LVM逻辑卷。如果没有LVM逻辑卷的情况下&#xff0c;…...

动手写ORM框架 - GeeORM第一天 database/sql 基础

文章目录 1 初识 SQLite2 database/sql 标准库3 实现一个简单的 log 库4 核心结构 Session本文是7天用Go从零实现ORM框架GeeORM的第一篇。介绍了 SQLite 的基础操作(连接数据库,创建表、增删记录等)。使用 Go 语言标准库 database/sql 连接并操作 SQLite 数据库,并简单封装…...

绘制中国平安股价的交互式 K 线图

在本文中,探索如何使用 Python 的强大库进行股市数据分析与可视化。我们将以中国平安(股票代码:sh601318)为例,展示如何获取其股票数据,并绘制一张交互式 K 线图。 K 线图是股市分析中不可或缺的工具,它能够直观地显示股票的波动情况,包括开盘价、收盘价、最高价和最低…...

[渗透测试]热门搜索引擎推荐— — shodan篇

[渗透测试]热门搜索引擎推荐— — shodan篇 免责声明&#xff1a;本文仅用于分享渗透测试工具&#xff0c;大家使用时&#xff0c;一定需要遵守相关法律法规。 除了shodan&#xff0c;还有很多其他热门的&#xff0c;比如&#xff1a;fofa、奇安信的鹰图、钟馗之眼等&#xff0…...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

智慧医疗能源事业线深度画像分析(上)

引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

CSS设置元素的宽度根据其内容自动调整

width: fit-content 是 CSS 中的一个属性值&#xff0c;用于设置元素的宽度根据其内容自动调整&#xff0c;确保宽度刚好容纳内容而不会超出。 效果对比 默认情况&#xff08;width: auto&#xff09;&#xff1a; 块级元素&#xff08;如 <div>&#xff09;会占满父容器…...

Spring是如何解决Bean的循环依赖:三级缓存机制

1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间‌互相持有对方引用‌,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...

【Linux】Linux 系统默认的目录及作用说明

博主介绍&#xff1a;✌全网粉丝23W&#xff0c;CSDN博客专家、Java领域优质创作者&#xff0c;掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围&#xff1a;SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...

并发编程 - go版

1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程&#xff0c;系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能

1. 开发环境准备 ​​安装DevEco Studio 3.1​​&#xff1a; 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK ​​项目配置​​&#xff1a; // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...

手机平板能效生态设计指令EU 2023/1670标准解读

手机平板能效生态设计指令EU 2023/1670标准解读 以下是针对欧盟《手机和平板电脑生态设计法规》(EU) 2023/1670 的核心解读&#xff0c;综合法规核心要求、最新修正及企业合规要点&#xff1a; 一、法规背景与目标 生效与强制时间 发布于2023年8月31日&#xff08;OJ公报&…...

Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成

一个面向 Java 开发者的 Sring-Ai 示例工程项目&#xff0c;该项目是一个 Spring AI 快速入门的样例工程项目&#xff0c;旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计&#xff0c;每个模块都专注于特定的功能领域&#xff0c;便于学习和…...