建设银行 钓鱼网站,国内免费注册二级域名的网站,做外贸一般总浏览的网站,网站的宣传方法有哪些目录链接#xff1a;
力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目#xff1a;
https://github.com/September26/java-algorithms 原题链接#xff1a;力扣 描述#xff1a;
有一个只含有 Q, W, E, R 四种字符#xff0c;且长度为 n 的字符串。
假如在该… 目录链接
力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目
https://github.com/September26/java-algorithms 原题链接力扣 描述
有一个只含有 Q, W, E, R 四种字符且长度为 n 的字符串。
假如在该字符串中这四个字符都恰好出现 n/4 次那么它就是一个「平衡字符串」。 给你一个这样的字符串 s请通过「替换一个子串」的方式使原字符串 s 变成一个「平衡字符串」。
你可以用和「待替换子串」长度相同的 任何 其他字符串来完成替换。
请返回待替换子串的最小可能长度。
如果原字符串自身就是一个平衡字符串则返回 0。 示例 1
输入s QWER
输出0
解释s 已经是平衡的了。
示例 2
输入s QQWE
输出1
解释我们需要把一个 Q 替换成 R这样得到的 RQWE (或 QRWE) 是平衡的。示例 3
输入s QQQW
输出2
解释我们可以把前面的 QQ 替换成 ER。 示例 4
输入s QQQQ
输出3
解释我们可以替换后 3 个 Q使 s QWER。提示
1 s.length 10^5s.length 是 4 的倍数s 中只含有 Q, W, E, R 四种字符解题思路
* 解题思路
* 统计四个字符的数量使用数组保存看看哪些是多余的并且统计多出了几个记录到map中value为多出的次数。
* 使用双指针然后遍历字符串如果满足所有value0则leftIndex,并且value相应的增加。
* 否则rightIndex,value相应的减少
代码
public class Solution1234 {public int balancedString(String s) {int[] counts new int[4];char[] chars s.toCharArray();for (char c : chars) {if (c Q) {counts[0];} else if (c E) {counts[1];} else if (c W) {counts[2];} else {counts[3];}}MapCharacter, Integer map new HashMap();for (int i 0; i counts.length; i) {int count counts[i];int diffCount count - s.length() / 4;if (diffCount 0) {if (i 0) {map.put(Q, diffCount);} else if (i 1) {map.put(E, diffCount);} else if (i 2) {map.put(W, diffCount);} else {map.put(R, diffCount);}}}if (map.size() 0) {return 0;}//双指针llint minLength Integer.MAX_VALUE;int leftIndex 0;int rightIndex 0;while (rightIndex chars.length) {if (allZero(map)) {minLength Math.min(minLength, rightIndex - leftIndex);char leftChar chars[leftIndex];Integer integer map.getOrDefault(leftChar, 0);map.put(leftChar, integer 1);leftIndex;continue;}char rightChar chars[rightIndex];Integer integer map.getOrDefault(rightChar, 0);map.put(rightChar, integer - 1);rightIndex;}while (leftIndex chars.length) {if (allZero(map)) {minLength Math.min(minLength, rightIndex - leftIndex);char leftChar chars[leftIndex];Integer integer map.getOrDefault(leftChar, 0);map.put(leftChar, integer 1);leftIndex;continue;}break;}return minLength;}private boolean allZero(MapCharacter, Integer map) {CollectionInteger values map.values();IteratorInteger iterator values.iterator();while (iterator.hasNext()) {if (iterator.next() 0) {return false;}}return true;}}
