2022-05-04：比如，str = "ayxbx"，有以下4种切法 : a | yxbx、ay | xbx、ayx | bx

福大大架构师每日一题

发布于 2022-06-04 10:44:55

2220

发布于 2022-06-04 10:44:55

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2022-05-04：比如，str = "ayxbx"，

有以下4种切法 : a | yxbx、ay | xbx、ayx | bx、ayxb | x，

其中第1、3、4种切法符合：x和y的个数，至少在左右两块中的一块里有相同的数量，

所以返回3。

给定一个字符串str，长度为N，

你有N-1种划分方法，把str切成左右两半，返回有几种切法满足：

x和y的个数，至少在左右两块中的一块里有相同的数量。

来自微软。

答案2022-05-04：

遍历统计x和y的个数。再次遍历做判断。

时间复杂度：O(N)。

代码用rust编写。代码如下：

fn main() {
    let answer = split_same_number_ways("ayxbx");
    println!("answer = {}", answer);
}

fn split_same_number_ways(str: &str) -> isize {
    if str.len() == 0 {
        return 0;
    }
    let mut x_all: isize = 0;
    let mut y_all: isize = 0;
    for c in str.chars() {
        x_all += if c == 'x' { 1 } else { 0 };
        y_all += if c == 'y' { 1 } else { 0 };
    }
    let mut left_x: isize = if str.chars().nth(0).unwrap() == 'x' {
        1
    } else {
        0
    };
    let mut left_y: isize = if str.chars().nth(0).unwrap() == 'y' {
        1
    } else {
        0
    };
    let mut ans: isize = 0;
    for i in 1..str.len() {
        if left_x == left_y || (x_all - left_x) == (y_all - left_y) {
            ans += 1;
        }
        left_x += if str.chars().nth(i as usize).unwrap() == 'x' {
            1
        } else {
            0
        };
        left_y += if str.chars().nth(i as usize).unwrap() == 'y' {
            1
        } else {
            0
        };
    }
    return ans;
}

执行结果如下：