不容易解的题10.15
395.至少有K个重复字符的最长字串
395. 至少有 K 个重复字符的最长子串 - 力扣(LeetCode)https://leetcode.cn/problems/longest-substring-with-at-least-k-repeating-characters/description/?envType=list&envId=ZCa7r67M自认为是不好做的题。尤其是使用滑动窗口解法,思路很难想
一开始的想法很简单,思路也是该ac的思路,但是测试用例太长,超时了
思路是取该字符串上的每一个子串,这里的实现是用双for确定子串的开始和结束位置,将该字串传递进一个自写函数,该函数作用是用一个数组做哈希表来判断每个字符是否出现了k次及以上,如果是返回true,并且判断当前子串长度是否是被记录最长,如果不是更新答案,遍历完之后返回正确的长度即可。
class Solution {
public:int longestSubstring(string s, int k) {int res=0;for(int i=0;i<s.size();i++){for(int j=i;j<s.size();j++){if(fun(s,i,j,k)&&res<j-i+1)res=j-i+1;}}return res;}bool fun(string &s,int left,int right,int k){int arr[26]={0};for(int i=left;i<=right;i++)arr[s[i]-'a']++;for(int i=0;i<26;i++){if(arr[i]!=0&&arr[i]<k)return false;}return true;}
};
做的时候一直以为该思路是可以通过的,然后做了很多次剪枝,发现通不过去。
下面来看正确的滑动窗口实现,是我看一个网友写的,思路十分清晰易懂,后来发现官方题解的滑窗也是这样的思路,但是官方题解一般很难看得懂。
class Solution {
public:int longestSubstring(string s, int k) {int res=0;int arr[26]={0};for(int i=1;i<=26;i++){int left=0,right=0;int diff=0,count=0;memset(arr,0,sizeof(arr));while(right<s.size()){arr[s[right]-'a']++;if(arr[s[right]-'a']==1)diff++;if(arr[s[right]-'a']==k)count++;right++;while(left<right&&diff>i){arr[s[left]-'a']--;if(arr[s[left]-'a']==0)diff--;if(arr[s[left]-'a']==k-1)count--;left++;}if(diff==i&&diff==count)res=max(res,right-left);}}return res;}
};
我们先给出代码,以代码来分析。
循环是以26个不同的字母为限制的,即每次只允许窗口内存在n个不同的字母
设置变量来分别存放当前窗口内不同种类字符的个数、符合该种字符个数等于k的字符有多少个、窗口左边界、窗口右边界
变量设置好后,开始进入第一个while,它是扩张右窗口的
如果当前数组位置为1,diff++,说明有不同的字符第一次加进来
如果当前位置数值为k则count++说明当前字符出现次数第一次达到k,注意这里并不是大于等于k时候count++,这样的话后续加进来该字符会导致重复计数
如果当前窗口出现的字符种类大于i,进入左边界缩小的阶段,进入的是循环而不是if判断语句
循环中如果左边界在右边界左侧,说明该窗口有缩减的必要,并且还要保证此时窗口字符种类大于i
进入之后是和上面类似的判断,不停增大left直到字符种类在允许的范围内
值得注意的有两点:
第一:判断窗口种类个数是否超过i的循环,应该在扩大右边界循环内部,每扩大一次右边界,并完成相应变量增加后,就立即判断此时左边界是否应该缩小
第二:判断完左右边界之后,立即进行的是一句判断
如果当前所允许的字符种类个数等于当前窗口的字符种类个数,并且窗口里任意字符的个数都大于或等于k,则判断是否应该更新答案值
为什么要判断现在最大允许的字符种类个数呢?
因为该循环是由1开始到26结束,每次判断的是最大允许范围这能保证当前窗口前提下,找到的是最大的数值,这样才可能需要更新数据
一定要注意不要把更新数据这条语句不小心写到循环外面了,这样如果在窗口移动时有新数据,就添加不上了
memset每次清理数组很重要,上一次遗留的数据不能作为下一次扩大i限制的哈希表,这会造成不同字母为1时和字母为2时的哈希表累加,这在逻辑上也说不过去
right++可以放在最后,这样使代码更容易理解,当然代码也应该写成right-left+1
注意vector数组的clear不能起到相同的作用
还有就是不要把-‘a’写成-‘0’
还有一种方法是递归:
这种方法,十分巧妙,但是更难想,我一般倾向于能不用递归就不用递归,递归一般思路不好想,而且出bug也不太容易找。
也是先给出代码再看思路
class Solution {
public:int longestSubstring(string s, int k) {unordered_set<char> set(s.begin(),s.end());unordered_map<char,int>map;for(char ch:s)map[ch]++;for(char ch:set){vector<string>path;if(map[ch]<k){split(s,path,ch);int res=0;for(string tn:path){res=max(longestSubstring(tn,k),res);}return res;}}return s.size();}void split(const string&s,vector<string>&path,const char flag=' '){path.clear();istringstream iss(s);string temp;while(getline(iss,temp,flag)){path.push_back(temp);}
}
};
大概的理解:
map记录的是s字符串中每个出现过的字符都有多少个,如果全都大于k那么进不到if循环,直接返回s.size()了,因为整个字符串就符合题解
如果有小于k的说明只要包含该字符的子串都不能满足条件,因为map存储的是s这个字符串中该字符出现的总次数,如果小于那么进行分割,分割出不含该字符的若干字串,将这些子串全部放入一个数组里,然后进行递归,找这些子串中最长的满足条件的长度是多少
如果此时分割出来的子串中含有小于k次频率的字符怎么办?
不用担心,res=max这一行,会再次进入函数,进行分割,直到子串全部满足大于等于k的出现频率
不必深究代码究竟如何进行递归,我们只需要搞清楚分割的条件,以及答案将返回什么即可
怎么样是不是理解起来比滑窗稍难一些,也可能是我个人使用递归很少,所以感觉很难想,用哈希表存每个字符出现频次,然后再把不满足频次的字符分割开,这种思路很巧妙。
都看到这里了如果对您有用的话别忘了一键三连哦,如果是互粉回访我也会做的!
大家有什么想看的题解,或者想看的算法专栏、数据结构专栏,可以去看看往期的文章,有想看的新题目或者专栏也可以评论区写出来,讨论一番,本账号将持续更新。
期待您的关注
相关文章:

不容易解的题10.15
395.至少有K个重复字符的最长字串 395. 至少有 K 个重复字符的最长子串 - 力扣(LeetCode)https://leetcode.cn/problems/longest-substring-with-at-least-k-repeating-characters/description/?envTypelist&envIdZCa7r67M自认为是不好做的题。尤其…...

Megatron-LM GPT 源码分析(二) Sequence Parallel分析
引用 本文基于开源代码 https://github.com/NVIDIA/Megatron-LM ,延续上一篇Megatron-LM GPT 源码分析(一) Tensor Parallel分析 通过对GPT的模型运行示例,从三个维度 - 模型结构、代码运行、代码逻辑说明 对其源码做深入的分析。…...
DNA序列(DNA Consensus String, ACM/ICPC Seoul 2006, UVa1368) rust解法
输入m个长度均为n的DNA序列,求一个DNA序列,到所有序列的总Hamming距离尽量小。两个等长字符串的Hamming距离等于字符不同的位置个数,例如,ACGT和GCGA的Hamming距离为2(左数第1, 4个字符不同)。 输入整数m和…...

如何使用Jmeter进行http接口测试?
前言: 本文主要针对http接口进行测试,使用Jmeter工具实现。 Jmter工具设计之初是用于做性能测试的,它在实现对各种接口的调用方面已经做的比较成熟,因此,本次直接使用Jmeter工具来完成对Http接口的测试。 一、开发接…...

bash一行输入,多行回显demo脚本
效果图: 脚本: #!/bin/bash # 定义一个变量,用来存储输入的内容 input"" # 定义一个变量,用来存储输入的字符 char""# 为了让read能读到空格键 IFS_store$IFS IFS# 提示内容,在while循环中也有&a…...

IDEA spring-boot项目启动,无法加载或找到启动类问题解决
问题描述:找不到或无法加载主类 xxx.xxx.xxx.Classname 解决方案: 1.检查启动设置: 启动类所在包运行环境(一般选择默认即可)设置完成即可进行运行测试 2.如果第一步没有解决问题,试着第二步:…...

【LeetCode刷题(数据结构与算法)】:完全二叉树的节点个数
完全二叉树 的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2h 个节点 输入:r…...

【代码随想录】算法训练营 第一天 第一章 数组 Part 1
目录 数组基础知识补充 704. 二分查找 题目 左闭右闭方法 思路 代码 左闭右开方法 思路 代码 27. 移除元素 题目 暴力解法 思路 代码 双指针法 思路 代码 数组基础知识补充 1. 在leecode中,数组一般是以vector容器的形式出现的,虽然ve…...
286_C++_定时器的其中一个操作,定时重载接口—startTimer循环执行回调(未完全)
1、启动一个定时器,允许在一定时间间隔内执行回调函数startTimer 1、接口函数参数详解 /*** @brief startTimer 定时重载接口* @param interval 定时器触发间隔,单位毫秒 (ms)* @param notify 定时时间到后需要触发的回调* @param type 回调驱动方…...

自动驾驶学习笔记(四)——变道绕行仿真
#Apollo开发者# 学习课程的传送门如下,当您也准备学习自动驾驶时,可以和我一同前往: 《自动驾驶新人之旅》免费课程—> 传送门 《2023星火培训【感知专项营】》免费课程—>传送门 文章目录 前言 仿真内容 启动Dreamview 开启Sim…...

C++位图,布隆过滤器
本期我们来学习位图,布隆过滤器等相关知识,以及模拟实现,需求前置知识 C-哈希Hash-CSDN博客 C-封装unordered_KLZUQ的博客-CSDN博客 目录 位图 布隆过滤器 海量数据面试题 全部代码 位图 我们先来看一道面试题 给 40 亿个不重复的无符号…...
Python多种方法实现九九乘法表
你好,我是悦创。 九九乘法表是一种常见的算术学习工具,通常用于帮助学生记住乘法的基本运算。以下是使用Python实现九九乘法表的几种方法: 1. 使用两个嵌套循环 for i in range(1, 10):for j in range(1, i 1):print(f"{j}x{i}{i * …...

【力扣1876】长度为三且各字符不同的子字符串
👑专栏内容:力扣刷题⛪个人主页:子夜的星的主页💕座右铭:前路未远,步履不停 目录 一、题目描述二、题目分析 一、题目描述 题目链接:长度为三且各字符不同的子字符串 如果一个字符串不含有任何…...

HSN:微调预训练ViT用于目标检测和语义分割,华南理工和阿里巴巴联合提出
今天跟大家分享华南理工大学和阿里巴巴联合提出的将ViT模型用于下游任务的高效微调方法HSN,该方法在迁移学习、目标检测、实例分割、语义分割等多个下游任务中表现优秀,性能接近甚至在某些任务上超越全参数微调。 论文标题:Hierarchical Side…...

机器学习的原理是什么?
训过小狗没? 没训过的话总见过吧? 你要能理解怎么训狗,就能非常轻易的理解机器学习的原理. 比如你想教小狗学习动作“坐下”一开始小狗根本不知道你在说什么。但是如果你每次都说坐下”然后帮助它坐下,并给它一块小零食作为奖励,经过多次…...
Java集合框架之ArrayList源码分析
文章目录 简介ArrayList底层数据结构初始化集合操作追加元素插入数据删除数据修改数据查找 扩容操作总结 简介 ArrayList是Java提供的线性集合,本篇笔记将从源码(java SE 17)的角度学习ArrayList: 什么是ArrayList?ArrayList底层数据结构是…...

TensorFlow入门(二十、损失函数)
损失函数 损失函数用真实值与预测值的距离指导模型的收敛方向,是网络学习质量的关键。不管是什么样的网络结构,如果使用的损失函数不正确,最终训练出的模型一定是不正确的。常见的两类损失函数为:①均值平方差②交叉熵 均值平方差 均值平方差(Mean Squared Error,MSE),也称&qu…...
MySQL中死锁
数据库的死锁是指不同的事务在获取资源时相互等待,导致无法继续执行的一种情况。当发生死锁时,数据库会自动中断其中一个事务,以解除死锁。在数据库中,事务可以分为读事务和写事务。读事务只需要获取读锁,而写事务需要…...

【LeetCode刷题(数据结构)】:给定一个链表 每个节点包含一个额外增加的随机指针 该指针可以指向链表中的任何节点或空节点 要求返回这个链表的深度拷贝
给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next…...

uniapp封装loading 的动画动态加载
实现效果 html代码 <view class"loadBox" v-if"loading"><img :src"logo" class"logo"> </view> css代码 .loadBox {width: 180rpx;min-height: 180rpx;border-radius: 50%;display: flex;align-items: center;j…...

SpringBoot-17-MyBatis动态SQL标签之常用标签
文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...
将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?
Otsu 是一种自动阈值化方法,用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理,能够自动确定一个阈值,将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

企业如何增强终端安全?
在数字化转型加速的今天,企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机,到工厂里的物联网设备、智能传感器,这些终端构成了企业与外部世界连接的 “神经末梢”。然而,随着远程办公的常态化和设备接入的爆炸式…...
鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南
1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发,使用DevEco Studio作为开发工具,采用Java语言实现,包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...

[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.
ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #:…...

Ubuntu系统复制(U盘-电脑硬盘)
所需环境 电脑自带硬盘:1块 (1T) U盘1:Ubuntu系统引导盘(用于“U盘2”复制到“电脑自带硬盘”) U盘2:Ubuntu系统盘(1T,用于被复制) !!!建议“电脑…...

图解JavaScript原型:原型链及其分析 | JavaScript图解
忽略该图的细节(如内存地址值没有用二进制) 以下是对该图进一步的理解和总结 1. JS 对象概念的辨析 对象是什么:保存在堆中一块区域,同时在栈中有一块区域保存其在堆中的地址(也就是我们通常说的该变量指向谁&…...

AxureRP-Pro-Beta-Setup_114413.exe (6.0.0.2887)
Name:3ddown Serial:FiCGEezgdGoYILo8U/2MFyCWj0jZoJc/sziRRj2/ENvtEq7w1RH97k5MWctqVHA 注册用户名:Axure 序列号:8t3Yk/zu4cX601/seX6wBZgYRVj/lkC2PICCdO4sFKCCLx8mcCnccoylVb40lP...

针对药品仓库的效期管理问题,如何利用WMS系统“破局”
案例: 某医药分销企业,主要经营各类药品的批发与零售。由于药品的特殊性,效期管理至关重要,但该企业一直面临效期问题的困扰。在未使用WMS系统之前,其药品入库、存储、出库等环节的效期管理主要依赖人工记录与检查。库…...