2022-07-07：原本数组中都是大于0、小于等于k的数字，是一个单调不减的数组， 其中可能有相等的数字，总体趋势是递增的。 但是其中有些位置的数被替换成了0，我们需要求出所有的把0替换的方案数量：

2022-07-07：原本数组中都是大于0、小于等于k的数字，是一个单调不减的数组，
其中可能有相等的数字，总体趋势是递增的。
但是其中有些位置的数被替换成了0，我们需要求出所有的把0替换的方案数量：
1）填充的每一个数可以大于等于前一个数，小于等于后一个数；
2）填充的每一个数不能大于k。
来自腾讯音乐。

答案2022-07-07：

方法一：动态规划。
方法二：数学方法。用到组合，C(b-a+m,m)。

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

use rand::Rng;

fn main() {

    let nn: i64 = 20;

    let kk: i64 = 30;

    let test_time: i32 = 10000;

    println!("测试开始");

    for i in 0..test_time {

        let n = rand::thread_rng().gen_range(0, nn) + 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!("出错了!{}", i);

            println!("ans1 = {}", ans1);

            println!("ans2 = {}", ans2);

            break;

        }

    }

    println!("测试结束");

}

// 动态规划

fn ways1(nums: &mut Vec<i64>, k: i64) -> i64 {

    let n = nums.len() as i64;

    // dp[i][j] : 一共i个格子，随意填，但是不能降序，j种数可以选

    let mut dp: Vec<Vec<i64>> = vec![];

    for i in 0..n + 1 {

        dp.push(vec![]);

        for _ in 0..k + 1 {

            dp[i as usize].push(0);

        }

    }

    for i in 1..=n {

        dp[i as usize][1] = 1;

    }

    for i in 1..=k {

        dp[1][i as usize] = i;

    }

    for i in 2..=n {

        for j in 2..=k {

            dp[i as usize][j as usize] =

                dp[(i - 1) as usize][j as usize] + dp[i as usize][(j - 1) as usize];

        }

    }

    let mut res = 1;

    let mut i: i64 = 0;

    let mut j: i64 = 0;

    while i < nums.len() as i64 {

        if nums[i as usize] == 0 {

            j = i + 1;

            while j < nums.len() as i64 && nums[j as usize] == 0 {

                j += 1;

            }

            let left_value = if i - 1 >= 0 {

                nums[(i - 1) as usize]

            } else {

                1

            };

            let right_value = if j < nums.len() as i64 {

                nums[j as usize]

            } else {

                k

            };

            res *= dp[(j - i) as usize][(right_value - left_value + 1) as usize];

            i = j;

        }

        i += 1;

    }

    return res;

}

// 数学方法

// a ~ b范围的数字随便选，可以选重复的数，一共选m个

// 选出有序序列的方案数：C ( m, b - a + m )

fn ways2(nums: &mut Vec<i64>, k: i64) -> i64 {

    let mut res = 1;

    let mut i: i64 = 0;

    let mut j: i64 = 0;

    while i < nums.len() as i64 {

        if nums[i as usize] == 0 {

            j = i + 1;

            while j < nums.len() as i64 && nums[j as usize] == 0 {

                j += 1;

            }

            let left_value = if i - 1 >= 0 {

                nums[(i - 1) as usize]

            } else {

                1

            };

            let right_value = if j < nums.len() as i64 {

                nums[j as usize]

            } else {

                k

            };

            let numbers = j - i;

            res *= c(right_value - left_value + numbers, numbers);

            i = j;

        }

        i += 1;

    }

    return res;

}

// 从一共a个数里，选b个数，方法数是多少

fn c(a: i64, b: i64) -> i64 {

    if a == b {

        return 1;

    }

    let mut x = 1;

    let mut y = 1;

    let mut i = b + 1;

    let mut j = 1;

    while i <= a {

        x *= i;

        y *= j;

        let gcd = gcd(x, y);

        x /= gcd;

        y /= gcd;

        i += 1;

        j += 1;

    }

    return x / y;

}

fn gcd(m: i64, n: i64) -> i64 {

    if n == 0 {

        m

    } else {

        gcd(n, m % n)

    }

}

// 为了测试

fn random_array(n: i64, k: i64) -> Vec<i64> {

    let mut ans: Vec<i64> = vec![];

    for _i in 0..n {

        ans.push(rand::thread_rng().gen_range(0, k) + 1);

    }

    ans.sort();

    for i in 0..n {

        ans[i as usize] = if rand::thread_rng().gen_range(0, 2) == 0 {

            0

        } else {

            ans[i as usize]

        };

    }

    return ans;

}

执行结果如下：

左神java代码

2022-07-07：原本数组中都是大于0、小于等于k的数字，是一个单调不减的数组， 其中可能有相等的数字，总体趋势是递增的。 但是其中有些位置的数被替换成了0，我们需要求出所有的把0替换的方案数量：的相关教程结束。