2023-08-20：用go语言写算法。给定一个由'W'、'A'、'S'、'D'四种字符组成的字符串，长度一定是4的倍数，
你可以把任意连续的一段子串，变成'W'、'A'、'S'、'D'组成的随意状态，
目的是让4种字符词频一样。
返回需要修改的最短子串长度。
完美走位问题。
输入：s = "QQQW"。
输出：2。
解释：我们可以把前面的 "QQ" 替换成 "ER"。
来自华为OD。
来自左程云。
答案2023-08-20：
算法步骤：
1.定义辅助函数ok()，用于判断当前字符词频是否能使四种字符的词频相同。
2.初始化数组arr保存每个字符的对应值（'Q': 0, 'W': 1, 'E': 2, 'R': 3）和数组cnts记录每个字符的词频。
3.使用双指针来搜索每个可能的子串。外层循环控制左指针，内层循环控制右指针。
4.当当前子串不满足要求时，右指针向右移动并更新词频数组cnts，直到子串满足要求。
5.当子串满足要求时，更新当前最短子串长度。
6.左指针向右移动并更新词频数组，继续搜索可能的子串。
7.返回最短子串长度。
总的时间复杂度为O(n)，其中n是字符串的长度。
总的额外空间复杂度为O(1)，因为只使用了固定大小的数组和常数个变量。
go完整代码如下：
package main
import "fmt"
func balancedString(s string) int {
n := len(s)
arr := make([]int, n)
cnts := make([]int, 4)
for i := 0; i < n; i++ {
switch s[i] {
case 'Q':
arr[i] = 0
case 'W':
arr[i] = 1
case 'E':
arr[i] = 2
case 'R':
arr[i] = 3
}
cnts[arr[i]]++
}
ans := n
for l, r := 0, 0; l < n; l++ {
for !ok(cnts, l, r) && r < n {
cnts[arr[r]]--
r++
}
if ok(cnts, l, r) {
ans = min(ans, r-l)
} else {
break
}
cnts[arr[l]]++
}
return ans
}
func ok(cnts []int, l int, r int) bool {
maxCnt := max(max(max(cnts[0], cnts[1]), cnts[2]), cnts[3])
changes := maxCnt*4 - cnts[0] - cnts[1] - cnts[2] - cnts[3]
rest := r - l - changes
return rest >= 0 && rest%4 == 0
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func main() {
s := "QQQW"
result := balancedString(s)
fmt.Println(result)
}
rust完整代码如下：
fn balanced_string(s: &str) -> i32 {
let n = s.len() as i32;
let mut arr = Vec::with_capacity(n as usize);
let mut cnts = vec![0; 4];
for c in s.chars() {
let val = match c {
'W' => 1,
'E' => 2,
'R' => 3,
_ => 0,
};
arr.push(val);
cnts[val] += 1;
}
let mut ans = n;
for l in 0..n {
let mut r = l;
while !ok(&cnts, l, r) && r < n {
cnts[arr[r as usize] as usize] -= 1;
r += 1;
}
if ok(&cnts, l, r) {
ans = ans.min(r - l);
} else {
break;
}
cnts[arr[l as usize] as usize] += 1;
}
ans
}
fn ok(cnts: &[i32], l: i32, r: i32) -> bool {
let max_cnt = cnts.iter().max().copied().unwrap_or(0);
let changes = max_cnt * 4 - cnts[0] - cnts[1] - cnts[2] - cnts[3];
let rest = r - l - changes;
rest >= 0 && rest % 4 == 0
}
fn main() {
let s = "QQQW";
let result = balanced_string(s);
println!("{}", result);
}
c++完整代码如下：
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
bool ok(const std::vector<int>& cnts, int l, int r);
int balancedString(const std::string& str) {
int n = str.size();
std::vector<int> arr(n);
std::vector<int> cnts(4);
for (int i = 0; i < n; i++) {
char c = str[i];
arr[i] = (c == 'W' ? 1 : (c == 'E' ? 2 : (c == 'R' ? 3 : 0)));
cnts[arr[i]]++;
}
int ans = n;
for (int l = 0, r = 0; l < n; l++) {
while (!ok(cnts, l, r) && r < n) {
cnts[arr[r++]]--;
}
if (ok(cnts, l, r)) {
ans = std::min(ans, r - l);
}
else {
break;
}
cnts[arr[l]]++;
}
return ans;
}
bool ok(const std::vector<int>& cnts, int l, int r) {
int maxCnt = std::max(std::max(cnts[0], cnts[1]), std::max(cnts[2], cnts[3]));
int changes = maxCnt * 4 - cnts[0] - cnts[1] - cnts[2] - cnts[3];
int rest = r - l - changes;
return rest >= 0 && rest % 4 == 0;
}
int main() {
std::string s = "QQQW";
int result = balancedString(s);
std::cout << "Result: " << result << std::endl;
return 0;
}
c完整代码如下：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int balancedString(char* s) {
int n = strlen(s);
int* arr = (int*)malloc(sizeof(int) * n);
int cnts[4] = { 0 };
for (int i = 0; i < n; i++) {
char c = s[i];
arr[i] = c == 'W' ? 1 : (c == 'E' ? 2 : (c == 'R' ? 3 : 0));
cnts[arr[i]]++;
}
int ans = n;
for (int l = 0, r = 0; l < n; l++) {
while (!ok(cnts, l, r) && r < n) {
cnts[arr[r++]]--;
}
if (ok(cnts, l, r)) {
ans = ans < r - l ? ans : r - l;
}
else {
break;
}
cnts[arr[l]]++;
}
free(arr);
return ans;
}
int ok(int* cnts, int l, int r) {
int maxCnt = cnts[0];
for (int i = 1; i < 4; i++) {
if (cnts[i] > maxCnt) {
maxCnt = cnts[i];
}
}
int changes = maxCnt * 4 - cnts[0] - cnts[1] - cnts[2] - cnts[3];
int rest = r - l - changes;
return rest >= 0 && rest % 4 == 0;
}
int main() {
char s[] = "QQQW";
int result = balancedString(s);
printf("%d\n", result);
return 0;
}