当前位置：首页 > news >正文

【LeetCode】每日一题（3）

news 2025/7/7 12:36:05

题目：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_map<char, 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_map<char, 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;}
};