写点什么

2023-08-20:用 go 语言写算法。给定一个由'W'、'A'、'S'、'D'四种字符组成的字符串,长度一定是 4 的倍数, 你可以把任意连续的一段子串,变成'W'、'A'、'S'、'D'组成的随意状

  • 2023-08-20
    北京
  • 本文字数:2647 字

    阅读完需:约 9 分钟

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;}
复制代码



发布于: 刚刚阅读数: 3
用户头像

公众号:福大大架构师每日一题 2021-02-15 加入

公众号:福大大架构师每日一题

评论

发布
暂无评论
2023-08-20:用go语言写算法。给定一个由'W'、'A'、'S'、'D'四种字符组成的字符串,长度一定是4的倍数,  你可以把任意连续的一段子串,变成'W'、'A'、'S'、'D'组成的随意状_福大大架构师每日一题_福大大架构师每日一题_InfoQ写作社区