高端网站建设创新,上海网站建设联系电,微企点建好网站后要怎么做,南充市建设局网站目录
题目#xff1a;1234. 替换子串得到平衡字符串 - 力扣#xff08;Leetcode#xff09;
题目的接口#xff1a;
解题思路#xff1a;
代码#xff1a;
过啦#xff01;#xff01;#xff01;
写在最后#xff1a; 题目#xff1a;1234. 替换子串得到平衡…目录
题目1234. 替换子串得到平衡字符串 - 力扣Leetcode
题目的接口
解题思路
代码
过啦
写在最后 题目1234. 替换子串得到平衡字符串 - 力扣Leetcode 题目的接口
class Solution {
public:int balancedString(string s) {}
};
解题思路
这个题目就是让我们求出需要替换子串的最小长度
我也想不出什么牛逼的解法
所以就老老实实用哈希和滑动窗口来做
然后控制一下边界
具体思路就是
1. 用一个哈希map存放原字符串以及每个字符的个数
2. 然后实现一个是否需要替换的的函数
3. 最后用滑动窗口的思想
匹配不了 j 就加加
j 遇到对应字符该字符就减减
匹配成功记录下来然后让 i 加加看看还有没有更少的替换次数。
i 遇到对应字符该字符就加加
直到 j 到边界且比配失败将记录的最少的替换次数返回即可。
代码
class Solution {
public://判断字符串是否平衡bool is_balance(int m, unordered_mapchar, int mp){for(const auto it : mp){//如果字符个数大于n/4当然不平衡if(it.second m){return false;}}//字符个数都等于n/4平衡了return true;}int balancedString(string s) {int n s.size();int m n / 4;//建一个哈希mapunordered_mapchar, int mp;//把字符都存进去for(char e : s){mp[e];}//用这个判断函数判断是否已经匹配成功if(is_balance(m, mp)){return 0;}//这里创建ret为一个很大的数用来作为初始的比较数int i 0, j 0, ret INT_MAX, breakcnt 0;//滑动窗口[i, j) while(i n){//如果平衡动i看看还有没有更优解if(is_balance(m, mp)){int tmp j - i;//记录最小替换次数ret min(ret, tmp);//下标i离开了s[i]让该字符数量因为不替换这个字符了mp[s[i]];i;}else{if(j n)//j到边界就停下来{//下标j往后移动让该字符数量--在滑动窗口内的字符是要被替换的mp[s[j]]--;j;}else//j到边界了{breakcnt;//先别直接break让窗口再匹配一次看看还有没有更优解//如果没有第二次到这里就break。if(breakcnt 1){break;}}}}//返回记录的最小替换次数return ret;}
};过啦 写在最后
以上就是本篇文章的内容了感谢你的阅读。
如果喜欢本文的话欢迎点赞和评论写下你的见解。
如果想和我一起学习编程不妨点个关注我们一起学习一同成长。
之后我还会输出更多高质量内容欢迎收看。
