电脑手机网站制作/百度网盘官网
文章目录
- 题目
- 方法一:滑窗右端每次+1,左端来回滑动
- 方法二:(最多K种的子串数) - (最多K-1种的子串数) = 恰好K种
题目
1 <= nums.length <= 20000
1 <= nums[i], k <= nums.length
方法一:滑窗右端每次+1,左端来回滑动
这道题初步看上去像滑窗。滑窗解决的问题是“最长”,比如找“无重复字符的最长子串”、“特定排列的子串”。通用方法就是滑窗右侧尽可能向右,直到滑窗内元素的个数不满足要求那么滑窗左侧右移。
本题考虑的不是“最多K个不同整数”,而是“恰好K个不同整数”。
我的办法(方法一)是先用滑窗找到“最多K个不同整数”的每个左右边界,然后对于这其中的每一个右边界,左边界“尝试右移”,找到全部合适的左边界。比如序列12123,对于第二个2来说,“最多2个不同整数”,就是1212,满足条件的左边界有3个,[1]212、[2]12、[1]2.
具体到代码实现,对于每一个右边界(即将加入滑窗)的值来说:
- 如果这个值曾经在滑窗中出现过,则把该值加入滑窗之后,滑窗内仍然是恰好K种数,那么pl“尝试右移”:cnt数组相应减少,直到遇到第一个将cnt的某个非零值减到0位置的位置tmp_pl,那么tmp-pl就是此时右边界对应所有左边界的个数。然后把pl~tmp_pl区间内的数再加回cnt数组(恢复)。
- 如果这个值没有在滑窗中出现,那么把该值加入滑窗之后,滑窗内就有K+1种数了,此时pl必须右移。右移到合适位置后,再进行1中的“尝试右移”操作。
class Solution {int cnt[20010] = {0};int ans = 0;public:int subarraysWithKDistinct(vector<int>& nums, int k) {int pl = 0, pr = 0, k2 = 0;// 先找k个不同的,定下初始滑窗位置 左闭右开for (; pr < nums.size() && k2 < k; pr++)if (++cnt[nums[pr]] == 1) k2++;if (k2 < k) return 0;ans++;// 开始滑动while (pr < nums.size()) {// 先尝试pl右移int tmp_pl = pl;while (cnt[nums[tmp_pl]] > 1) {ans++;cnt[nums[tmp_pl]]--; tmp_pl++;}// 恢复while (tmp_pl > pl) {tmp_pl--;cnt[nums[tmp_pl]]++;}// if 下一个数是旧数,加入if (cnt[nums[pr]] > 0) {cnt[nums[pr]]++; pr++;ans++;}// if 下一个数是新数,pl右移至窗内种类数-1else {cnt[nums[pr]]++; pr++;do {cnt[nums[pl]]--;pl++;} while (cnt[nums[pl - 1]] > 0);ans++;}}// 尝试pl右移int tmp_pl = pl;while (cnt[nums[tmp_pl]] > 1) {ans++;cnt[nums[tmp_pl]]--;tmp_pl++;}return ans;}
};
时间复杂度:最坏是Onn,但是实际还不错。
方法二:(最多K种的子串数) - (最多K-1种的子串数) = 恰好K种
这个方法是官方题解法。
还是12123,且K=2
这个例子,对于1212来说,有3
个左边界可以满足“恰好K种”,这个3
是怎么算出来的呢?最多K-1种的左边界是1个,一共4个潜在的左边界,4-1=3.
(最多K种的子串数) - (最多K-1种的子串数) = 恰好K种
时间复杂度On
相关文章:

Leetcode992-K个不同整数的子数组[两种方法] 关键词 滑窗
文章目录 题目方法一:滑窗右端每次1,左端来回滑动方法二:(最多K种的子串数) - (最多K-1种的子串数) 恰好K种 题目 1 < nums.length < 20000 1 < nums[i], k < nums.length 方法一…...

【闲聊】-后端框架发展史
框架,是为了解决系统复杂性,提升开发效率而产生的工具,主要服务于研发人员。 当然,框架还有更深层的作用,框架的沉淀是一种高级的抽象,会将人类的业务逐步抽象为统一标准又灵活可变的结构,为各行…...

界面控件DevExpress ASP.NET Scheduler - 助力快速交付个人信息管理系统(下)
DevExpress ASP. NET Scheduler组件能完全复制Microsoft Outlook Scheduler的样式和功能,具有日、周、月和时间轴视图,并包括内置的打印支持,因此用户可以在尽可能短的时间内交付全功能的个人信息管理系统。在上文中(点击这里回顾…...

机器学习-04-分类算法-01决策树
总结 本系列是机器学习课程的系列课程,主要介绍机器学习中分类算法,本篇为分类算法开篇与决策树部分。 参考 决策树——ID3和C4.5(理论图解公式推导) 策略产品经理必读系列—第七讲ID3、C4.5和CART算法详解 决策树(…...

探索大数据时代的决策利器:如何有效应对海量数据?
随着信息技术的快速发展,大数据时代已经到来,海量数据成为了我们生活和工作中不可忽视的一部分。这些数据来自各个方面:社交媒体、传感器、网络交易、移动设备等,每天都在以惊人的速度增长。但是,面对如此庞大的数据量,我们该如何有效地应对呢?本文将探索大数据时代的决…...

Linux 学习笔记(16)
十六、 计划任务 在很多时候为了自动化管理系统,我们都会用到计划任务,比如关机,管理,备份之类的操作,我 们都可以使用计划任务来完成,这样可以是管理员的工作量大大降低,而且可靠度更好。 l…...

【C语言】打印闰年
输⼊⼀个年份year,判断year是否是闰年 闰年判断的规则: 1, 能被4整除并且不能被100整除是闰年 2,能被400整除是闰年 结合起来如下: if ((year % 4 0 && year % 100 ! 0) || (year % 400 0)) 代码如下&…...

外贸入门,很残忍但很真实的外贸真相
如果你是小白入行外贸,第一家选择的公司大概率会决定你以后的客户开发模式。 外贸老鸟们可以留言讨论下自己是不是被说中了。 如果新人选择的第一家公司是靠B2B网站,展会或者官网询盘分发,公司每年会花大量的广告费用获客,你会很快…...

【Linux网络编程七】网络序列化和反序列化(网络版本计算器)
【Linux网络编程七】网络序列化和反序列化(网络版本计算器) 一.网络读取问题【解决方案】1.定制协议2.序列化和反序列化3.添加报头①封包②解包 4.框架总结 二.自定义协议:网络计算器协议Ⅰ.客户端发送请求,服务器端接收请求1.构建请求(结构化…...

算法打卡day17|二叉树篇06|Leetcode 654.最大二叉树、617.合并二叉树、700.二叉搜索树中的搜索、98.验证二叉搜索树
算法题 Leetcode 654.最大二叉树 题目链接:654.最大二叉树 大佬视频讲解:最大二叉树视频讲解 个人思路 大概思路就是在数组中 找最大值的节点作为当前节点,用最大值的index切割左右子树的区间,往复循环到数组元素为0; 解法 递…...

C语言之数据在计算机内部的存储
文章目录 一、前言二、类型的基本归类1、整型家族2、浮点数家族3、构造类型4、指针类型 三、整型在内存中的存储1、原码、反码、补码1.1 概念1.2 原码与补码的转换形式1.3 计算机内部的存储编码 2、大小端介绍~~2.1 为什么要有大端和小端之分?2.2 大(小&…...

程序人生——Java中基本类型使用建议
目录 引出Java中基本类型使用建议建议21:用偶判断,不用奇判断建议22:用整数类型处理货币建议23:不要让类型默默转换建议24:边界、边界、还是边界建议25:不要让四舍五入亏了一方 建议26:提防包装…...

Pikachu 靶场搭建
文章目录 环境说明1 Pikachu 简介2 Pikachu 安装 环境说明 操作系统:Windows 10PHPStudy 版本: 8.1.1.3Apache 版本:2.4.39MySQL 版本 5.7.26 1 Pikachu 简介 Pikachu是一个使用“PHP MySQL” 开发、包含常见的Web安全漏洞、适合Web渗透测试学习人员练…...

机器学习-绪论
机器学习致力于研究如何通过计算的手段、利用经验来改善系统自身的性能。在计算机系统中,“经验”通常以“数据”的形式存在,因此,机器学习所研究的主要内容,是关于在计算机上从数据中产生“模型”的算法,即“学习算法…...

mysql 索引(为什么选择B+ Tree?)
索引实现原理 索引:排好序的数据结构 优点:降低I/O成本,CPU的资源消耗(数据持久化在磁盘中,每次查询都得与磁盘交互) 缺点:更新表效率变慢,(更新表数据,还要…...

蓝桥杯-带分数
法一 /* 再每一个a里去找c,他们共用一个st数组,可以解决重复出现数字 通过ac确定b,b不能出现<0 b出现的数不能和ac重复*/import java.util.Scanner;public class Main {static int n,res;static boolean[] st new boolean[15];static boolean[] backup new boolean[15];…...

消息队列面试题
目录 1. 为什么使用消息队列 2. 消息队列的缺点 3. 消息队列如何选型? 4. 如何保证消息队列是高可用的 5. 如何保证消息不被重复消费(见第二条) 6. 如何保证消息的可靠性传输? 7. 如何保证消息的顺序性(即消息幂…...

Android和IOS应用开发-Flutter 应用中实现记录和使用全局状态的几种方法
文章目录 在Flutter中记录和使用全局状态使用 Provider步骤1步骤2步骤3 使用 BLoC步骤1步骤2步骤3 使用 GetX:步骤1步骤2步骤3 在Flutter中记录和使用全局状态 在 Flutter 应用中,您可以使用以下几种方法来实现记录和使用全局状态,并在整个应…...

若依 ruoyi-cloud [网关异常处理]请求路径:/system/user/getInfo,异常信息:404
这里遇到的情况是因为nacos中的配置文件与项目启动时的编码不一样,若配置文件中有中文注释,那么用idea启动项目的时候,在参数中加上 -Dfile.encodingutf-8 ,保持编码一致,(用中文注释的配置文件,…...

自然语言处理里预训练模型——BERT
BERT,全称Bidirectional Encoder Representation from Transformers,是google在2018年提出的一个预训练语言模型,它的推出,一举刷新了当年多项NLP任务值的新高。前期我在零、自然语言处理开篇-CSDN博客 的符号向量化一文中简单介绍…...

2024年信息技术与计算机工程国际学术会议(ICITCEI 2024)
2024年信息技术与计算机工程国际学术会议(ICITCEI 2024) 2024 International Conference on Information Technology and Computer Engineering ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 大会主题: 信息系统和技术…...

渗透测试修复笔记 - 02 Docker Remote API漏洞
需要保持 Docker 服务运行并且不希望影响其他使用 Docker 部署的服务,同时需要禁止外网访问特定的 Docker API 端口(2375):通过一下命令来看漏洞 docker -H tcp://ip地址:2375 images修改Docker配置以限制访问 修改daemon.json配…...

Spring(创建对象的方式3个)
3、Spring IOC创建对象方式一: 01、使用无参构造方法 //id:唯一标识 class:当前创建的对象的全局限定名 <bean id"us1" class"com.msb.pojo.User"/> 02、使用有参构造 <bean id"us2&…...

【GPT-SOVITS-02】GPT模块解析
说明:该系列文章从本人知乎账号迁入,主要原因是知乎图片附件过于模糊。 知乎专栏地址: 语音生成专栏 系列文章地址: 【GPT-SOVITS-01】源码梳理 【GPT-SOVITS-02】GPT模块解析 【GPT-SOVITS-03】SOVITS 模块-生成模型解析 【G…...

6个选品建议,改善你的亚马逊现状。
一、市场热点与需求调研 深入研究当前市场趋势,了解消费者需求的变化。使用亚马逊的销售数据、评价、问答等功能,以及第三方市场研究工具,比如店雷达,分析潜在热销产品的特点。注意季节性需求,提前布局相关选品&#…...

SQL中的SYSDATE函数
前言 在SQL语言中,SYSDATE 是一个非常实用且常见的系统内置函数,尤其在Oracle和MySQL数据库中广泛使用。它主要用来获取服务器当前的日期和时间,这对于进行实时数据记录、审计跟踪、有效期计算等场景特别有用。本文将详细解析SYSDATE函数的使…...

Rust的async和await支持多线程运行吗?
Rust的async和await的异步机制并不是仅在单线程下实现的,它们可以在多线程环境中工作,从而利用多核CPU的并行计算优势。然而,异步编程的主要目标之一是避免不必要的线程切换开销,因此,在单线程上下文中,asy…...

P2676 [USACO07DEC] Bookshelf B
[USACO07DEC] Bookshelf B 题目描述 Farmer John 最近为奶牛们的图书馆添置了一个巨大的书架,尽管它是如此的大,但它还是几乎瞬间就被各种各样的书塞满了。现在,只有书架的顶上还留有一点空间。 所有 N ( 1 ≤ N ≤ 20 , 000 ) N(1 \le N…...

【数学】第十三届蓝桥杯省赛C++ A组/研究生组《爬树的甲壳虫》(C++)
【题目描述】 有一只甲壳虫想要爬上一棵高度为 n 的树,它一开始位于树根,高度为 0,当它尝试从高度 i−1 爬到高度为 i 的位置时有 Pi 的概率会掉回树根,求它从树根爬到树顶时,经过的时间的期望值是多少。 【输入格式…...

Java毕业设计 基于springboot vue招聘网站 招聘系统
Java毕业设计 基于springboot vue招聘网站 招聘系统 springboot vue招聘网站 招聘系统 功能介绍 用户:登录 个人信息 简历信息 查看招聘信息 企业:登录 企业信息管理 发布招聘信息 职位招聘信息管理 简历信息管理 管理员:注册 登录 管理员…...