力扣395. 至少有 K 个重复字符的最长子串----递归+dfs实现分治
发布日期:2021-06-28 15:43:59
浏览次数:3
分类:技术文章
本文共 1727 字,大约阅读时间需要 5 分钟。
395. 至少有 K 个重复字符的最长子串
给你一个字符串 s 和一个整数 k ,请你找出 s 中的最长子串, 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。
示例 1:输入:s = "aaabb", k = 3输出:3解释:最长子串为 "aaa" ,其中 'a' 重复了 3 次。示例 2:输入:s = "ababbc", k = 2输出:5解释:最长子串为 "ababb" ,其中 'a' 重复了 2 次, 'b' 重复了 3 次。 提示:1 <= s.length <= 104s 仅由小写英文字母组成1 <= k <= 105
题解:
此题可以使用分治法求解。
首先要充分理解题意: 如果字符串s的每个字母都出现k次及以上,那么我们直接返回它的原长度即可。而如果其中能找到一个出现次数少于k的字母类型,那么我们就可以将这类字母当成“断点”处理,即将原字符串s分割成为了若干个小字符串。接着对每个小字符串进行分析,继续完成上述找“断点”的操作,然后再进行分割…
不断分割寻找之后,最后得到字符串一定是每一种字母都出现k次及以上的,那么我们可以根据“如果字符串s的每个字母都出现k次及以上,那么我们直接返回它的原长度即可”可知,此时其可以组成的最长子串长度就是它自己本身,即返回它自己的长度即可。上述操作可以使用递归+dfs思想实现分治,我们最后要做的就是对所有的这些返回的长度进行取最大的操作即可。
切割字符串操作使用c不好操作,因此我们可以通过控制所给字符串的起点和终点来完成所谓的“切割”操作。
代码:
int dfs(char* s, int l, int r, int k) { int hash[26] = { 0}; for(int i=l;i<=r;i++)//每次都要对新子串进行哈希储存一下,注意是从左边界l开始 { hash[s[i]-'a']++; } char temp = 0;//储存找到的第一个断点,刚开始为0,即“\0” for(int i=0;i<26;i++) { if(hash[i]>0&&hash[i]0是必要的,因为断点首先得在s中出现过 { temp = i+'a';//储存此字母,为断点 break;//一次找到一个即可,不用一次分完全,因为按其中一个断点进行分割后可能原先不是断点的字母也变成断点了 } } if(temp==0)//即无断点 { return r-l+1;//返回其长度,也是递归之所以得到长度值的关键所在 } int i = l; int res = 0;//因为最终得到真正的长度都是在上面的return语句实现的 while(i<=r) { while(i<=r&&s[i]==temp)//如果选定的起点直接是断点那么不用看直接往后一个 { i++; } if (i > r) //不能越界,越界直接结束操作即可 { break; } int start = i;//因为后面用i表示下一个的断点了 while(i<=r&&s[i]!=temp) { i++;//找子串的终点,即找下一个断点处 } int length = dfs(s,start,i-1,k); res = fmax(length,res); } return res;}int longestSubstring(char* s, int k) { return dfs(s, 0, strlen(s) - 1, k);}
转载地址:https://blog.csdn.net/xiangguang_fight/article/details/115750348 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
第一次来,支持一个
[***.219.124.196]2024年04月08日 04时02分27秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
2011年网上购书清单
2019-04-29
质量管理专家——戴明的14点说
2019-04-29
软件测试需要思考的问题?
2019-04-29
软件问题的分类与管理
2019-04-29
易用性测试关注点
2019-04-29
人生少走弯路的10条忠告
2019-04-29
测试管理工具TestDirector安装部署及常见问题解决方法
2019-04-29
CMMI中与测试直接相关的两个PA VER VAL
2019-04-29
CMMI标准名词术语
2019-04-29
CMMI L3学习考核基础试题(测试类)
2019-04-29
Windows Server 2003 sp1升级到sp2报错解决办法
2019-04-29
开源数据库性能测试工具HammerOra介绍
2019-04-29
百Google度搜索
2019-04-29
盛开—痛苦的信仰
2019-04-29
apache-jmeter-2.6运行环境配置
2019-04-29
loadrunner 8.1用IE7录制脚本后,生成脚本过程中崩溃解决方法
2019-04-29
Jmeter进行性能测试时多台负载机的配置方法
2019-04-29