2022-11-03：给定一个数组arr，和一个正数k 如果arr[i] == 0，表示i这里既可以是左括号

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代码

本作品采用《CC 协议》，转载必须注明作者和本文链接