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

电脑手机网站制作/百度网盘官网

电脑手机网站制作,百度网盘官网,猎头网招聘,广东新闻联播主持人名单文章目录 题目方法一&#xff1a;滑窗右端每次1&#xff0c;左端来回滑动方法二&#xff1a;&#xff08;最多K种的子串数&#xff09; - &#xff08;最多K-1种的子串数&#xff09; 恰好K种 题目 1 < nums.length < 20000 1 < nums[i], k < nums.length 方法一…

文章目录

  • 题目
  • 方法一:滑窗右端每次+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.

具体到代码实现,对于每一个右边界(即将加入滑窗)的值来说:

  1. 如果这个值曾经在滑窗中出现过,则把该值加入滑窗之后,滑窗内仍然是恰好K种数,那么pl“尝试右移”:cnt数组相应减少,直到遇到第一个将cnt的某个非零值减到0位置的位置tmp_pl,那么tmp-pl就是此时右边界对应所有左边界的个数。然后把pl~tmp_pl区间内的数再加回cnt数组(恢复)。
  2. 如果这个值没有在滑窗中出现,那么把该值加入滑窗之后,滑窗内就有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个不同整数的子数组[两种方法] 关键词 滑窗

文章目录 题目方法一&#xff1a;滑窗右端每次1&#xff0c;左端来回滑动方法二&#xff1a;&#xff08;最多K种的子串数&#xff09; - &#xff08;最多K-1种的子串数&#xff09; 恰好K种 题目 1 < nums.length < 20000 1 < nums[i], k < nums.length 方法一…...

【闲聊】-后端框架发展史

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

界面控件DevExpress ASP.NET Scheduler - 助力快速交付个人信息管理系统(下)

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

机器学习-04-分类算法-01决策树

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

探索大数据时代的决策利器:如何有效应对海量数据?

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

Linux 学习笔记(16)

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

【C语言】打印闰年

输⼊⼀个年份year&#xff0c;判断year是否是闰年 闰年判断的规则&#xff1a; 1&#xff0c; 能被4整除并且不能被100整除是闰年 2&#xff0c;能被400整除是闰年 结合起来如下&#xff1a; if ((year % 4 0 && year % 100 ! 0) || (year % 400 0)) 代码如下&…...

外贸入门,很残忍但很真实的外贸真相

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

【Linux网络编程七】网络序列化和反序列化(网络版本计算器)

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

算法打卡day17|二叉树篇06|Leetcode 654.最大二叉树、617.合并二叉树、700.二叉搜索树中的搜索、98.验证二叉搜索树

算法题 Leetcode 654.最大二叉树 题目链接:654.最大二叉树 大佬视频讲解&#xff1a;最大二叉树视频讲解 个人思路 大概思路就是在数组中 找最大值的节点作为当前节点&#xff0c;用最大值的index切割左右子树的区间&#xff0c;往复循环到数组元素为0&#xff1b; 解法 递…...

C语言之数据在计算机内部的存储

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

程序人生——Java中基本类型使用建议

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

Pikachu 靶场搭建

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

机器学习-绪论

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

mysql 索引(为什么选择B+ Tree?)

索引实现原理 索引&#xff1a;排好序的数据结构 优点&#xff1a;降低I/O成本&#xff0c;CPU的资源消耗&#xff08;数据持久化在磁盘中&#xff0c;每次查询都得与磁盘交互&#xff09; 缺点&#xff1a;更新表效率变慢&#xff0c;&#xff08;更新表数据&#xff0c;还要…...

蓝桥杯-带分数

法一 /* 再每一个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. 消息队列如何选型&#xff1f; 4. 如何保证消息队列是高可用的 5. 如何保证消息不被重复消费&#xff08;见第二条&#xff09; 6. 如何保证消息的可靠性传输&#xff1f; 7. 如何保证消息的顺序性&#xff08;即消息幂…...

Android和IOS应用开发-Flutter 应用中实现记录和使用全局状态的几种方法

文章目录 在Flutter中记录和使用全局状态使用 Provider步骤1步骤2步骤3 使用 BLoC步骤1步骤2步骤3 使用 GetX&#xff1a;步骤1步骤2步骤3 在Flutter中记录和使用全局状态 在 Flutter 应用中&#xff0c;您可以使用以下几种方法来实现记录和使用全局状态&#xff0c;并在整个应…...

若依 ruoyi-cloud [网关异常处理]请求路径:/system/user/getInfo,异常信息:404

这里遇到的情况是因为nacos中的配置文件与项目启动时的编码不一样&#xff0c;若配置文件中有中文注释&#xff0c;那么用idea启动项目的时候&#xff0c;在参数中加上 -Dfile.encodingutf-8 &#xff0c;保持编码一致&#xff0c;&#xff08;用中文注释的配置文件&#xff0c…...

自然语言处理里预训练模型——BERT

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

2024年信息技术与计算机工程国际学术会议(ICITCEI 2024)

2024年信息技术与计算机工程国际学术会议&#xff08;ICITCEI 2024&#xff09; 2024 International Conference on Information Technology and Computer Engineering ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 大会主题&#xff1a; 信息系统和技术…...

渗透测试修复笔记 - 02 Docker Remote API漏洞

需要保持 Docker 服务运行并且不希望影响其他使用 Docker 部署的服务&#xff0c;同时需要禁止外网访问特定的 Docker API 端口&#xff08;2375&#xff09;&#xff1a;通过一下命令来看漏洞 docker -H tcp://ip地址:2375 images修改Docker配置以限制访问 修改daemon.json配…...

Spring(创建对象的方式3个)

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

【GPT-SOVITS-02】GPT模块解析

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

6个选品建议,改善你的亚马逊现状。

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

SQL中的SYSDATE函数

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

Rust的async和await支持多线程运行吗?

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

P2676 [USACO07DEC] Bookshelf B

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

【数学】第十三届蓝桥杯省赛C++ A组/研究生组《爬树的甲壳虫》(C++)

【题目描述】 有一只甲壳虫想要爬上一棵高度为 n 的树&#xff0c;它一开始位于树根&#xff0c;高度为 0&#xff0c;当它尝试从高度 i−1 爬到高度为 i 的位置时有 Pi 的概率会掉回树根&#xff0c;求它从树根爬到树顶时&#xff0c;经过的时间的期望值是多少。 【输入格式…...

Java毕业设计 基于springboot vue招聘网站 招聘系统

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