当前位置:网站首页>2022-07-07:原本数组中都是大于0、小于等于k的数字,是一个单调不减的数组, 其中可能有相等的数字,总体趋势是递增的。 但是其中有些位置的数被替换成了0,我们需要求出所有的把0替换的方案数量:
2022-07-07:原本数组中都是大于0、小于等于k的数字,是一个单调不减的数组, 其中可能有相等的数字,总体趋势是递增的。 但是其中有些位置的数被替换成了0,我们需要求出所有的把0替换的方案数量:
2022-07-07 22:01:00 【福大大架构师每日一题】
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;
}
执行结果如下:
边栏推荐
- 52岁的周鸿祎,还年轻吗?
- Anaconda+pycharm+pyqt5 configuration problem: pyuic5 cannot be found exe
- Codeworks 5 questions per day (average 1500) - day 8
- 【leetcode】day1
- 【编程题】【Scratch二级】2019.12 绘制十个正方形
- Reading notes 004: Wang Yangming's quotations
- Problems faced when connecting to sqlserver after downloading (I)
- Two small problems in creating user registration interface
- [programming questions] [scratch Level 2] March 2019 garbage classification
- Daily question brushing record (16)
猜你喜欢
DataGuard active / standby cleanup archive settings
单机高并发模型设计
95. (cesium chapter) cesium dynamic monomer-3d building (building)
52岁的周鸿祎,还年轻吗?
HB 5469 combustion test method for non-metallic materials in civil aircraft cabin
QT and OpenGL: loading 3D models using the open asset import library (assimp) - Part 2
用语雀写文章了,功能真心强大!
每日刷题记录 (十六)
一鍵免費翻譯300多頁的pdf文檔
Introduction to programming hardware
随机推荐
Kubectl 好用的命令行工具:oh-my-zsh 技巧和窍门
Common selectors are
Aitm3.0005 smoke toxicity test
Chisel tutorial - 05 Sequential logic in chisel (including explicit multi clock, explicit synchronous reset and explicit asynchronous reset)
Go time package common functions
某马旅游网站开发(对servlet的优化)
Teach you to make a custom form label by hand
Codeworks 5 questions per day (average 1500) - day 8
Is it safe for tongdaxin to buy funds?
【编程题】【Scratch二级】2019.09 绘制雪花图案
C - linear table
Chisel tutorial - 03 Combinatorial logic in chisel (chisel3 cheat sheet is attached at the end)
如果在构造函数中抛出异常,最好的做法是防止内存泄漏?
Gorm Association summary
[question de programmation] [scratch niveau 2] oiseaux volants en décembre 2019
Robomaster visual tutorial (11) summary
Automated testing: robot framework is a practical skill that 90% of people want to know
Restricted linear table
Tools for debugging makefiles - tool for debugging makefiles
Uic564-2 Appendix 4 - flame retardant fire test: flame diffusion