2022-11-03:给定一个数组arr,和一个正数k
如果arr[i] == 0,表示i这里既可以是左括号也可以是右括号,
而且可以涂上1~k每一种颜色
如果arr[i] != 0,表示i这里已经确定是左括号,颜色就是arr[i]的值
那么arr整体就可以变成某个括号字符串,并且每个括号字符都带有颜色。
返回在括号字符串合法的前提下,有多少种不同的染色方案。
不管是排列、还是颜色,括号字符串任何一点不一样,就算不同的染色方案
最后的结果%10001,为了方便,我们不处理mod,就管核心思路。
2 <= arr长度 <= 5000
1 <= k <= 1000
0 <= arr[i] <= k。
2022.8.7笔试第三道。来自猿辅导。
答案2022-11-03:
递归或者动态规划。
代码用rust编写。代码如下:
use std::iter::repeat;
use rand::Rng;
fn main() {
let nn: i32 = 5;
let kk: i32 = 4;
let test_time: i32 = 1000;
println!("测试开始");
for _i in 0..test_time {
let n = (rand::thread_rng().gen_range(0, nn) + 1) << 1;
let k = rand::thread_rng().gen_range(0, kk) + 1;
let mut arr = random_array(n, k);
let ans1 = ways1(&mut arr, k);
let ans2 = ways2(&mut arr, k);
if ans1 != ans2 {
println!("arr = {:?},k = {}", arr, k);
println!("ans1 = {}", ans1);
println!("ans2 = {}", ans2);
println!("出错了!");
break;
}
}
println!("测试结束");
}
// 暴力方法
// 为了验证
fn ways1(arr: &mut Vec<i32>, k: i32) -> i32 {
if arr.len() & 1 != 0 {
return 0;
}
return process1(arr, 0, k);
}
fn process1(arr: &mut Vec<i32>, index: i32, k: i32) -> i32 {
if index == arr.len() as i32 {
let n = arr.len() as i32;
let mut stack: Vec<i32> = repeat(0).take(n as usize).collect();
let mut size = 0;
for i in 0..n {
if arr[i as usize] > 0 {
stack[size as usize] = arr[i as usize];
size += 1;
} else {
if size == 0 {
return 0;
}
size -= 1;
if stack[size as usize] != -arr[i as usize] {
return 0;
}
}
}
return if size == 0 { 1 } else { 0 };
} else if arr[index as usize] != 0 {
return process1(arr, index + 1, k);
} else {
let mut ans = 0;
for color in 1..=k {
arr[index as usize] = color;
ans += process1(arr, index + 1, k);
arr[index as usize] = -color;
ans += process1(arr, index + 1, k);
arr[index as usize] = 0;
}
return ans;
}
}
fn ways2(arr: &mut Vec<i32>, k: i32) -> i32 {
let n = arr.len() as i32;
if n & 1 != 0 {
return 0;
}
let a = combines(arr);
let mut b = 0;
for num in arr.iter() {
if *num != 0 {
b += 1;
}
}
return if ((n - (b << 1)) >> 1) < 0 {
0
} else {
a * k.pow(((n - (b << 1)) >> 1) as u32)
};
}
// 忽略染色这件事,求合法的括号结合数量
fn combines(arr: &mut Vec<i32>) -> i32 {
let n = arr.len() as i32;
let mut dp: Vec<Vec<i32>> = repeat(repeat(-1).take(n as usize).collect())
.take(n as usize)
.collect();
return f(arr, 0, 0, &mut dp);
}
// arr[i....]范围上,去做决定
// j : arr[0..i-1]已经做完决定的部分,左括号比右括号,多几个
// 返回:
// arr[i....]范围上,去做决定,
// 已经做完决定的部分,左括号比右括号多j个
// 这样的情况下,最终合法的括号结合,多少个!
// process(arr, 0, 0)
fn process(arr: &mut Vec<i32>, i: i32, j: i32) -> i32 {
if i == arr.len() as i32 {
return if j == 0 { 1 } else { 0 };
}
if j < 0 {
return 0;
}
// 这个不写也行
// 锦上添花的剪枝条件
if arr.len() as i32 - i < j {
return 0;
}
// arr[i] != 0
if arr[i as usize] != 0 {
// (
return process(arr, i + 1, j + 1);
} else {
// arr[i] 0 ? ( )
let p1 = process(arr, i + 1, j + 1);
let p2 = process(arr, i + 1, j - 1);
return p1 + p2;
}
}
// 在arr[i...]范围上做决定
// 之前在arr[0...i-1]上的决定,使得左括号比右括号多了j个
// 最终合法的括号结合是多少
fn f(arr: &mut Vec<i32>, i: i32, j: i32, dp: &mut Vec<Vec<i32>>) -> i32 {
let n = arr.len() as i32;
if i == n {
return if j == 0 { 1 } else { 0 };
}
if j < 0 {
return 0;
}
if n - i < j {
return 0;
}
// 如果缓存命中,直接返回答案
if dp[i as usize][j as usize] != -1 {
return dp[i as usize][j as usize];
}
let mut ans = 0;
if arr[i as usize] > 0 {
ans = f(arr, i + 1, j + 1, dp);
} else {
ans = f(arr, i + 1, j + 1, dp) + f(arr, i + 1, j - 1, dp);
}
dp[i as usize][j as usize] = ans;
return ans;
}
// 生成长度随机的数组
// 值在0~K之间,但是50%的概率值是0,50%的概率值是1~k中的一个
fn random_array(n: i32, k: i32) -> Vec<i32> {
let mut ans = vec![];
for _ in 0..n {
ans.push(if rand::thread_rng().gen_range(0, 2) == 0 {
0
} else {
rand::thread_rng().gen_range(0, k) + 1
})
}
return ans;
}
执行结果如下:
***
[左神java代码](https://github.com/algorithmzuo/weekly-problems/blob/main/src/class_2022_08_2_week/Code01_ParenthesesDye.java)