2022-07-11：给定n位长的数字字符串和正数k，求该子符串能被k整除的子串个数。
(n<=1000，k<=100)。
来自微众。4.11笔试。
答案2022-07-11：
动态规划。假设abcdef%k=0，abc000%k=0，那么def%k=0。
代码用rust编写。代码如下：
代码语言：go复制use rand::Rng;
fn main() {
let nn: i64 = 18;
let kk: i64 = 20;
let test_time: i32 = 3000;
println!("测试开始");
for i in 0..test_time {
let str = random_number(rand::thread_rng().gen_range(0, nn) 1);
let k = rand::thread_rng().gen_range(0, kk) 1;
let ans1 = mod_ways1(&str, k);
let ans2 = mod_ways2(&str, k);
if ans1 != ans2 {
println!("出错了!{}", i);
println!("ans1 = {}", ans1);
println!("ans2 = {}", ans2);
break;
}
}
println!("测试结束");
}
// 暴力方法
// 为了验证
fn mod_ways1(s: &str, k: i64) -> i64 {
let n = s.len() as i64;
let mut ans = 0;
for i in 0..n {
for j in i..n {
if (&s[i as usize..(j 1) as usize]).parse::<i64>().unwrap() % k == 0 {
ans = 1;
}
}
}
return ans;
}
// 正式方法
// 时间复杂度O(N * k)
fn mod_ways2(s: &str, k: i64) -> i64 {
let mut cur: Vec<i64> = vec![];
for _ in 0..k {
cur.push(0);
}
// 帮忙迁移
let mut next: Vec<i64> = vec![];
for _ in 0..k {
next.push(0);
}
// 0...i 整体余几？
let mut mod0: i64 = 0;
// 答案：统计有多少子串的值%k == 0
let mut ans = 0;
for cha in s.bytes() {
for i in 0..k {
// i -> 10个
// (i * 10) % k
next[((i * 10) % k) as usize] = cur[i as usize];
cur[i as usize] = 0;
}
let mut tmp = cur.clone();
cur = next.clone();
next = tmp.clone();
mod0 = (mod0 * 10 (cha - '0' as u8) as i64) % k;
ans = if mod0 == 0 { 1 } else { 0 } cur[mod0 as usize];
cur[mod0 as usize] = 1;
}
return ans;
}
// 为了测试
fn random_number(n: i64) -> String {
let mut ans: Vec<u8> = vec![];
for _i in 0..n {
ans.push('0' as u8 rand::thread_rng().gen_range(0, 10));
}
return String::from_utf8(ans).unwrap();
}执行结果如下：
在这里插入图片描述
