首页
学习
活动
专区
圈层
工具
发布
社区首页 >专栏 >2022-05-04:比如,str = “ayxbx“, 有以下4种切法 : a | yxbx、ay | xbx、ayx | bx、ayxb | x, 其中第1

2022-05-04:比如,str = “ayxbx“, 有以下4种切法 : a | yxbx、ay | xbx、ayx | bx、ayxb | x, 其中第1

原创
作者头像
福大大架构师每日一题
发布于 2022-05-04 20:30:43
发布于 2022-05-04 20:30:43
2550
举报

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编写。代码如下:

代码语言: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;
}

执行结果如下:

在这里插入图片描述
在这里插入图片描述

左神java代码

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档