每日一题|2516. 每种字符至少取 K 个|双指针、最长子串、字典

本题需要转化求解目标。

对于一个序列,两头收集的最少数量的时候,剩下的部分(我们称之为子串)就会对应的越长。也就是说,我们只要求解一个满足要求的最长子串,使得两边剩余的字符数量刚好满足要求。

由于题目需要分别记录固定字符的个数,采用字典进行计算。

1.初始化

初始化包含字典、结果值。

首先遍历字符串的全部字符,统计在字典里,也就是子串长度为0。

        cnt_dict = {'a':0, 'b':0, 'c':0}ans = len(s)for ch in s:cnt_dict[ch] += 1if min(cnt_dict.values()) >= k:ans = len(s)else:return -1

这里需要做一个剪枝操作:如果统计的全部个数当中存在一个字符出现的个数小于要求,则可以直接返回-1。其余的情况,ans不变。

2.双指针遍历

两个指针left,right,都同时从左侧出发,先移动right,在right固定的时候,逐渐收紧left,直到刚好存在一个字符的数量等于k

所以是两层循环,外层for循环移动right指针,内层的while循环收紧left指针

每移动一次right指针,所指元素的数量就要-1(子串的长度在变长),每移动一次left指针,所指元素的数量+1(子串在变短)。

        l = 0for r, ch in enumerate(s):cnt_dict[ch] -= 1while l < r and min(cnt_dict.values()) < k:cnt_dict[s[l]] += 1l += 1if min(cnt_dict.values()) >= k:ans = min(ans, len(s) - (r - l + 1))

最后,如果在某一个时刻,所有的数量的最小值达到要求,则更新ans的值为当前“子串外字符长度”和上一次的ans的最小值。

关于语法

1.求字典值的最小值要用.values(),不然默认是键的最小值。

2.存在一个值<k == min < k

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/1548601.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

实时美颜功能技术揭秘:视频美颜SDK与API的技术剖析

当下&#xff0c;用户希望在视频直播中呈现出最佳状态&#xff0c;这推动了视频美颜SDK和API的迅速发展。本文将深入剖析这项技术的核心原理、应用场景以及未来趋势。 一、实时美颜技术的基本原理 在实现这些效果的过程中&#xff0c;视频美颜SDK通常会使用以下几种技术&…

Geekbench6使用指南:Linux系统性能测试,如此简单!

在当今计算机性能日益重要的时代&#xff0c;Geekbench 成为了测试 CPU 性能的热门工具。本文将带你深入了解如何使用 Geekbench&#xff0c;让你的电脑性能一目了然。 1. 什么是 Geekbench&#xff1f; Geekbench 是一款跨平台的基准测试工具&#xff0c;能够评估单核和多核…

Ubuntu Server 20.04 64bit定时备份MySQL8.0.36数据库数据

一、编写sh脚本 常见备份命令介绍 我选用的是mysqldump命令&#xff0c;命令使用简介 [root]> mysqldump -helpUsage: mysqldump [OPTIONS] database_name [tables] OR mysqldump [OPTIONS] --databases [OPTIONS] DB1 [DB2 DB3...] OR mysqldump [OPTIONS] --all…

字节软件测试岗二面:APP测试问题被虐哭了,直到看到这些知识点

APP测试一直是大厂软件测试问到的一个重点细节&#xff0c;下面我来给大家展示一下大厂关于APP测试经常会问到的一些问题&#xff0c;以及解析。想象一下当你遇到面试官问到你这些问题时&#xff0c;你是否也能够对答如流哦&#xff01; 注意&#xff0c;注意啦&#xff01;小编…

对抗攻击方法详解:梯度攻击、转移攻击与模型集成攻击

对抗攻击方法详解&#xff1a;梯度攻击、转移攻击与模型集成攻击 近年来&#xff0c;随着深度学习模型在各个领域取得惊人突破&#xff0c;对抗攻击&#xff08;Adversarial Attack&#xff09; 逐渐成为研究热点。对抗攻击旨在通过在输入数据上施加精心设计的微小扰动&#x…

Meta号称替代程序员的LlamaCoder效果被CodeFlying秒杀,来看实测!

在讲LlamaCoder之前咱先浅聊一下Meta 这两天Meta凭借着Connect 2024大会可谓是风头正盛&#xff0c;刚刚发布的全新开源多模态大模型Llama3.2&#xff0c;热度是一路赶超咱的小草莓啊。 作为一款开源大模型能够和闭源的4o-mini、Claude3 Haiku打的有来有回&#xff0c; 甚至L…

32. Java栈和队列

1. 前言 栈和队列相关的题目是校招中出现频率一般,但是是属于相对基础的题型。我们要关注两类问题,栈和队列的添加和删除操作,以及栈和队列之间的区别和联系。 2. 栈和队列 2.1 数据结构 首先我们给出栈和队列的数据结构定义: (1)栈(Stack):允许在某一端插入元素(…

Ubuntu下Kafka安装及使用

Kafka是由Apache软件基金会开发的一个开源流处理平台&#xff0c;同时也是一个高吞吐量的分布式发布订阅消息系统。它由Scala和Java编写&#xff0c;具有多种特性和广泛的应用场景。 Kafka是一个分布式消息系统&#xff0c;它允许生产者&#xff08;Producer&#xff09;发布消…

CUDA error: no kernel image is available for execution on the device

记录一下出现上述问题的一个原因&#xff1a; pytorch所依赖的cuda版本不满足显卡(GPU)的算力要求&#xff01; 举例来说&#xff0c;显卡是3090&#xff0c;并按照以下命令安装Pytorch: conda install pytorch1.7.0 torchvision0.8.0 torchaudio0.7.0 cudatoolkit10.1 -c p…

另外知识与网络总结

一、重谈NAT&#xff08;工作在网络层&#xff09; 为什么会有NAT 为了解决ipv4地址太少问题&#xff0c;到了公网的末端就会有运营商路由器来构建私网&#xff0c;在不同私网中私有IP可以重复&#xff0c;这就可以缓解IP地址太少问题&#xff0c;但是这就导致私有IP是重复的…

2024最新gewechat开发微信机器人教程说明

简介&#xff1a;本文将指导你如何搭建一个微信机器人&#xff0c;通过接入gewe框架实现智能回复与聊天功能。我们将从基础设置开始&#xff0c;逐步讲解如何配置机器人&#xff0c;并通过实例展示其实际应用。 随着人工智能技术的不断发展&#xff0c;智能机器人已经成为我们…

南沙csp-j/s一对一家教 解一本通题: 1937:【06NOIP普及组】数列

【题目描述】 给定一个正整数k(3≤k≤15),把所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递增的序列&#xff0c;例如&#xff0c;当k3时&#xff0c;这个序列是&#xff1a; 1&#xff0c;3&#xff0c;4&#xff0c;9&#xff0c;10&#xff0c;12&#xff0c;13&a…

8,STM32CubeMX配置SPI工程(读取norflash的ID)

1&#xff0c;前言 单片机型号&#xff1a;STM32F407 编程环境 &#xff1a;STM32CubeMX Keil v5 硬件连接 &#xff1a;SPI1&#xff0c;CS/SS--->PB14 注&#xff1a;本工程在1&#xff0c;STM32CubeMX工程基础&#xff08;配置Debug、时钟树&#xff09;基础上完…

echarts饼图legend纵向分页

效果图 legend: {orient: vertical,type: scroll,bottom: 0,left: 10,icon: circle,height: 100, // 设置高度即可实现pageIconColor: #1b9aee, //翻页下一页的三角按钮颜色pageIconInactiveColor: #7f7f7f, //翻页&#xff08;即翻页到头时&#xff09;textStyle: {lineHei…

永辉超市自救三部曲:靠名创优品复制胖东来?如何避免另一个苏宁易购?

《港湾商业观察》施子夫 王璐 从潮流产品新锐向大型商超迈入&#xff0c;没有人想到名创优品(09896.HK&#xff1b;MNSO.US)会成为永辉超市&#xff08;601933.SH&#xff09;的第一大股东。 近63亿元的收购价让两家本就知名度颇高的企业在2024年的商业江湖中更加瞩目。然而…

C语言VS实用调试技巧

文章目录 一、什么是bug?二、什么是调试&#xff1f;三、Debug和Release四、VS调试快捷键4.1环境准备4.2调试快捷键 五、监视和内存观察5.1监视5.2内存 六、调试举例七、编程常见错误归类7.1编译型错误7.2链接型错误7.3运行时错误 一、什么是bug? &#x1f34e;bug本意是 “…

TypeScript 设计模式之【状态模式】

文章目录 状态模式&#xff1a;优雅切换的交通信号灯状态模式的奥秘状态模式有什么利与弊?如何使用状态模式来优化你的系统代码实现案例状态模式的主要优点状态模式的主要缺点状态模式的适用场景总结 状态模式&#xff1a;优雅切换的交通信号灯 当你站在繁忙的十字路口&#…

Vatee万腾平台:企业智能化生态的领航者

在科技日新月异的今天&#xff0c;企业的智能化转型已成为不可逆转的趋势。Vatee万腾平台&#xff0c;凭借其前瞻性的技术视野和不懈的创新精神&#xff0c;正逐步构建起一个以智能化为核心的新型商业生态&#xff0c;成为推动企业智能化升级的核心力量。 Vatee万腾平台深谙技…

大数据毕业设计选题推荐-程序员招聘数据分析系统-Hive-Hadoop-Spark

✨作者主页&#xff1a;IT研究室✨ 个人简介&#xff1a;曾从事计算机专业培训教学&#xff0c;擅长Java、Python、微信小程序、Golang、安卓Android等项目实战。接项目定制开发、代码讲解、答辩教学、文档编写、降重等。 ☑文末获取源码☑ 精彩专栏推荐⬇⬇⬇ Java项目 Python…

【中级通信工程师】终端与业务(六):市场环境与购买行为

【零基础3天通关中级通信工程师】 终端与业务(六)&#xff1a;市场环境与购买行为 本文是中级通信工程师考试《终端与业务》科目第六章《市场环境与购买行为》的复习资料和真题汇总。本章的核心内容涵盖了通信市场环境、消费者市场的特点和动机、集团客户市场的采购过程等内容…