2405. 子字符串的最优划分-贪心算法
算法 字符串 贪心 划分 最优
2023-09-14 09:06:49 时间
2405. 子字符串的最优划分-贪心算法
给你一个字符串 s ,请你将该字符串划分成一个或多个 子字符串 ,并满足每个子字符串中的字符都是 唯一 的。也就是说,在单个子字符串中,字母的出现次数都不超过 一次 。
满足题目要求的情况下,返回 最少 需要划分多少个子字符串。
注意,划分后,原字符串中的每个字符都应该恰好属于一个子字符串。
示例 1:
输入:s = “abacaba”
输出:4
解释:
两种可行的划分方法分别是 (“a”,“ba”,“cab”,“a”) 和 (“ab”,“a”,“ca”,“ba”) 。
可以证明最少需要划分 4 个子字符串。
示例 2:
输入:s = “ssssss”
输出:6
解释:
只存在一种可行的划分方法 (“s”,“s”,“s”,“s”,“s”,“s”) 。
这一题使用贪心算法其实是符合逻辑的,但是在实现的过程中很多同学可能会使用暴力解法,这个时间应该通过不了,所以最好使用一个字符标记数组,可以大大节省时间开销,解题代码如下:
int partitionString(char * s){
int r[26];
int count=0;
for(int k=0;k<26;k++){
r[k]=0;
}
for(int i=0;s[i]!='\0';i++){
if(r[s[i]-'a']==0){
r[s[i]-'a']++;
}
else{
for(int k=0;k<26;k++){
r[k]=0;
}
count++;
i--;
}
}
return count+1;
}
相关文章
- hdu3068 求一个字符串中最长回文字符串的长度 Manacher算法
- Java实现 蓝桥杯 算法提高 天天向上(DP)
- Java实现蓝桥杯VIP算法训练 预测身高
- Java实现 蓝桥杯 算法训练 字符串合并
- Java实现 蓝桥杯VIP 算法提高 3-2字符串输入输出函数
- Java实现 蓝桥杯VIP 算法提高 3-2字符串输入输出函数
- Java实现 蓝桥杯VIP 算法提高 字符串跳步
- Java实现 蓝桥杯VIP 算法训练 字符串编辑
- Java实现 蓝桥杯VIP 算法训练 比较字符串
- Java实现 蓝桥杯VIP 算法训练 比赛安排
- Java实现 蓝桥杯VIP 算法训练 数的统计
- Java实现 蓝桥杯VIP 算法训练 链表数据求和操作
- Java 蓝桥杯 算法训练 字符串的展开 (JAVA语言实现)
- (算法)判断字符串中是否包含HelloWorld
- (算法)交错的字符串
- KMP算法字符串匹配
- Algorithm:C++语言实现之Hash哈希算法相关(dbj2、sdbm、MurmurHash)
- ML之xgboost:利用xgboost算法(sklearn+7CrVa)训练mushroom蘑菇数据集(22+1,6513+1611)来预测蘑菇是否毒性(二分类预测)
- ML之RS之CF:基于用户的CF算法—利用大量用户的电影及其评分数据集对一个新用户Jason进行推荐电影+(已知Jason曾观看几十部电影及其评分)
- 【ML吴恩达】4 回归模型的分类、应用以及九个回归算法