国外家装设计网站,如何做软件开发,微信 网站界面 模板,传奇是网页游戏吗题目链接#xff1a;https://leetcode.cn/problems/replace-the-substring-for-balanced-string/description/
思路
题目意思
这题意思是一个只含有[Q, W, E, R] 四个字符的字符串s且长度一定是 4的倍数#xff0c; 需要你通过替换子串#xff0c;使他变成一个「平衡字符… 题目链接https://leetcode.cn/problems/replace-the-substring-for-balanced-string/description/
思路
题目意思
这题意思是一个只含有[Q, W, E, R] 四个字符的字符串s且长度一定是 4的倍数 需要你通过替换子串使他变成一个「平衡字符串」也就是字符串s内四个字符的数量都相等。
首先要仔细审题我刚开始是以为计算需要替换的字符的数量秒wa仔细阅读发现是替换连续子串需要找到一个最小长度的替换连续子串第一反应就是滑动窗口或者双指针。 算法小课堂 滑动窗口滑动窗口是双指针的一种特例可以称为左右指针在任意时刻只有一个指针运动而另一个保持静止。滑动窗口路一般用于解决特定的序列中符合条件的连续的子序列的问题。 滑动窗口的时间复杂度是线性的时间复杂度一般为O(n)滑动窗口的左右边界都不会向左滑动向左滑动等于走回头路是一种回溯的算法很可能会陷入死循环。滑动窗口是一种全遍历问题一定会遍历到末尾的。 方法滑动窗口 哈希表
刚开始我们用哈希表统计出四个字符的数量我们需要满足「平衡字符串」所以定义一个 check函数 判断四个字符数量小于等于 n / 4。
如果原始的 s 就是 「平衡字符串」则返回 0。如果不是接下来就是用滑动窗口来遍历字符串找到待替换子串来维护区间 [l,r) : 当前 l 指针不动 通过内循环移动 r 指针循环条件 r 指针需小于字符串s长度并且check函数满足直到找到待替换子串。如果找到了使得条件被满足的 r我们用 r−l 来更新答案 ans当前 r 指针不动并使得 l向右移动一个单位进行下一次枚举通过外循环移动 l 指针 循环条件 l 指针需小于字符串s长度使当前代替换子串合法并且最小。直到 r 指针移动到大于等于字符串s长度的位置且check函数不满足退出循环。
代码示例
func balancedString(s string) int {n : len(s)mp : make(map[byte]int)for _, v : range s {mp[byte(v)]}// 判断当前字符串是否是平衡字符串check : func() bool {if mp[Q] n / 4 || mp[W] n / 4 ||mp[E] n / 4 || mp[R] n / 4 {return false}return true}if check() {return 0}r, ans : 0, len(s)// 滑动窗口for l, c : range s {for r n !check() {mp[s[r]]--r}// 如果上面循环是 r n 条件退出// 表示现在的连续子串是不满足替换条件的可以直接退出避免影响正确答案if !check() {break}ans min(ans, r - l)mp[byte(c)]}return ans
}func min(a, b int) int {if a b {return b}return a
}复杂度分析
时间复杂度O(n)其中n表示字符串s的长度记录四个字符的数量需要遍历字符串s所需时间为O(n)滑动窗口时间是线性的所以所需时间也为O(n)。空间复杂度O(1)不需要额外申请空间。
