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;
}
执行结果如下：
左神java代码
