校园网站建设论文,网站备案中商城服务性质是什么,欢迎访问中国建设银行官方网站,wordpress 文章过滤Halo#xff0c;这里是Ppeua。平时主要更新C语言#xff0c;C#xff0c;数据结构算法......感兴趣就关注我吧#xff01;你定不会失望。 #x1f308;个人主页#xff1a;主页链接 #x1f308;算法专栏#xff1a;专栏链接 我会一直往里填充内容哒#xff01; … Halo这里是Ppeua。平时主要更新C语言C数据结构算法......感兴趣就关注我吧你定不会失望。 个人主页主页链接 算法专栏专栏链接 我会一直往里填充内容哒 LeetCode专栏专栏链接 目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目也会当天做完发出 代码仓库Gitee链接 点击关注收获更多优质内容 目录
题目
白话讲解
题例:
题解: 代码实现:
完结撒花 本题的核心思想为滑动窗口滑动窗口
忘掉的友友们可以回顾之前的内容进行复习一下 滑动窗口
题目 有一个只含有 Q, W, E, R 四种字符且长度为 n 的字符串。 假如在该字符串中这四个字符都恰好出现 n/4 次那么它就是一个「平衡字符串」。 给你一个这样的字符串 s请通过「替换一个子串」的方式使原字符串 s 变成一个「平衡字符串」。 你可以用和「待替换子串」长度相同的 任何 其他字符串来完成替换。 请返回待替换子串的最小可能长度。 如果原字符串自身就是一个平衡字符串则返回 0。 白话讲解
有一个长度为4的倍数的字符串其中出现四类字符QWER若这四类字符出现的次数为n/4则认为这是一个平衡字符串,返回0
若不为平衡字符串,则需要替换其中连续的子字符串,返回替换最短子字符串的长度.
题例: 输入s QWER
输出0
解释s 已经是平衡的了。 输入s QQWE
输出1
解释我们需要把一个 Q 替换成 R这样得到的 RQWE (或 QRWE) 是平衡的。 输入s QQQW
输出2
解释我们可以把前面的 QQ 替换成 ER。 输入s QQQQ
输出3
解释我们可以替换后 3 个 Q使 s QWER。 题解:
观察题意可知,以滑动窗口为分界点,若 窗口外的字母每类字母n/4 则将窗口内的字母全部替换就满足题意了.
举个例子:WQWRQQW 当区间内为WQWRQ时,窗口外的字母数如图所示,这时将窗口内的字母全部替换成所缺项,即可符合题意 如图,蓝线是变化的字母,绿线是没有变化的字母(先按下不表) ,这时我们就可以发现,这个子字符串是满足题意的.这个长度为5
我们可以把这个作为答案嘛?显然是不可以的,因为这不是最优解.最简单来看,
当区间内容为QWRQ的时候,也就是左移一个单位,将没有变化的字符串移出去,此时要变化的就是QWRQ
这就体现出了滑动窗口的核心思想:先向右遍历到满足条件的区间,左区间再收缩寻找最优解 代码实现:
#include algorithm
#includeiostream
#includestring
using namespace std;
class Solution {
public:int balancedString(string s) {int cnt[26]{0};int ns.size();for(char c:s)cnt[c-A];int ansINT_MAX;if(cnt[Q-A]n/4cnt[W-A]n/4cnt[E-A]n/4cnt[R-A]n/4)return 0;//已经排完序for(int i0,j0;jn;j)//遍历右端点{cnt[s[j]-A]--;//更新刚刚新加入窗口的元素while(ijcnt[Q-A]n/4cnt[W-A]n/4cnt[E-A]n/4cnt[R-A]n/4)//窗口外的所有元素数量都小于等于要求答案{ansmin(ans,j-i1);//说明当前区间内的所有元素都变换即可满足题意更新区间cnt[s[i]-A];//寻找最小的情况i;}}return ans;}
};
完结撒花 本篇博客的内容【Leetcode 每日一题 1234. 替换子串得到平衡字符串】已经结束。 若对你有些许帮助可以点赞、关注、评论支持下博主你的支持将是我前进路上最大的动力。 若以上内容有任何问题欢迎在评论区指出。若对以上内容有任何不解都可私信评论询问。 诸君山顶见
