2023-08-20:用go语言写算法。给定一个由'W'、'A'、'S'、'D'四种字符组成的字符串,长度一定是4的倍数, 你

举报
福大大架构师每日一题 发表于 2023/08/20 20:23:53 2023/08/20
【摘要】 2023-08-20:用go语言写算法。给定一个由’W’、‘A’、‘S’、'D’四种字符组成的字符串,长度一定是4的倍数,你可以把任意连续的一段子串,变成’W’、‘A’、‘S’、'D’组成的随意状态,目的是让4种字符词频一样。返回需要修改的最短子串长度。完美走位问题。输入:s = “QQQW”。输出:2。解释:我们可以把前面的 “QQ” 替换成 “ER”。来自华为OD。来自左程云。答案202...

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;
}

在这里插入图片描述

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。