2023-04-10:给定两个正整数x、y,都是int整型(java里) 返回0 ~ x以内,每位数字加起

2023-04-10:给定两个正整数x、y,都是int整型(java里)
返回0 ~ x以内,每位数字加起来是y的数字个数。
比如,x = 20、y = 5,返回2,
因为0 ~ x以内,每位数字加起来是5的数字有:5、14,
x、y范围是java里正整数的范围,
x <= 2 * 10^9,
y <= 90。
输入:1000,4。
输出:15。
输入:2000,6。
输出:49。
来自CISCO。

答案2023-04-10:

本文介绍了两种解决给定 x 和 y,求 0x 中每位数字之和为 y 的数字个数的方法。第一种方法使用暴力枚举的方式,遍历 0x 中的每一个数字,计算其每位数字之和是否等于 y,并统计符合条件的数字数量。第二种方法使用动态规划的思想,通过数位 DP 的方式快速计算符合条件的数字数量。

  1. 暴力枚举法

暴力枚举法是一种朴素的解题思路,对于每个数字,我们可以循环计算其每位数字之和,然后判断是否等于 y,如果是,则计数器加 1。这种方法看似简单,但由于需要遍历 x 个数,时间复杂度为 O(x * log(x)),不能满足本题要求的时间复杂度。

  1. 数位 DP

数位 DP 是一种常见的动态规划思想,主要用于解决与数字相关的问题。其基本思路是将数字按照位数拆分,然后根据各位数字的限制条件(如数字大小、数字和等)进行状态转移,最终得到答案。

本题中,我们可以使用数位 DP 来计算符合条件的数字数量。具体来说,假设当前处理到数字 x 的第 i 位,已经确定前 i-1 位的数字为 num,则当前的状态可以表示为 (i, num, sum),其中 sum 表示前 i 位数字之和。根据此状态定义,我们可以设计转移方程如下:

如果 i == 0,则返回 sum 是否等于 y 的结果,即 count(x, i, num, sum) = if sum == y {1} else {0}。

否则,设当前处理到的数字为 cur,则有两种情况:

当 cur <= sum 时,对答案的贡献为 get_form(i-1, sum-cur),即在第 i-1 位上选择符合条件的数字,然后将其放在当前位置上。

当 cur == x / offset % 10 时,需要递归计算下一位数字的方案总数,即 count(x, i-1, num+cur*offset, sum-cur)。

最终的答案为 count(x, len, 0, y),其中 len 表示数字 x 的位数,offset 表示当前处理到的位数所代表的权值。

为了提高效率,我们可以使用记忆化搜索来避免重复计算。具体来说,我们可以使用一个二维数组 dp 来记录已经计算过的状态,如果当前状态已经被计算过,则直接返回其对应的结果。

同时,由于在转移方程中需要频繁地查询 get_form(i, sum) 函数,这会导致函数调用次数过多,降低程序效率。因此,我们可以在程序运行前先预处理出所有可能的状态下的方案数,然后使用静态数组保存结果,在程序运行时直接查询即可。

综上所述,本题的数位 DP 解法时间复杂度为 O(log(x) * y),空间复杂度为 O(log(x) * y)。相比于暴力枚举法,数位 DP 基于动态规划的思想,通过状态转移方程快速计算答案,具有更高的效率和更好的可拓展性。

rust代码如下:

fn num1(x: i32, y: i32) -> i32 {
    let mut ans = 0;
    for i in 0..=x {
        if check1(i, y) {
            ans += 1;
        }
    }
    ans
}

fn check1(num: i32, y: i32) -> bool {
    let mut sum = 0;
    let mut n = num;
    while n != 0 {
        sum += n % 10;
        n /= 10;
    }
    sum == y
}

fn num2(x: i32, y: i32) -> i32 {
    if x < 0 || y > 90 {
        return 0;
    }
    if x == 0 {
        return if y == 0 { 1 } else { 0 };
    }
    let mut offset = 1;
    let mut len = 1;
    while offset <= x / 10 {
        offset *= 10;
        len += 1;
    }
    let mut dp = vec![vec![-1; (y + 1) as usize]; (len + 1) as usize];
    count(x, offset, len, y, &mut dp)
}

fn count(x: i32, offset: i32, len: i32, rest: i32, dp: &mut Vec<Vec<i32>>) -> i32 {
    if len == 0 {
        return if rest == 0 { 1 } else { 0 };
    }
    if dp[len as usize][rest as usize] != -1 {
        return dp[len as usize][rest as usize];
    }
    let mut ans = 0;
    let cur = (x / offset) % 10;
    for i in 0..cur.min(rest + 1) {
        ans += get_form((len - 1) as usize, (rest - i) as usize);
    }
    if cur <= rest {
        ans += count(x, offset / 10, len - 1, rest - cur, dp);
    }
    dp[len as usize][rest as usize] = ans;
    ans
}

// 打表
const FORM_SIZE: usize = 11;
const FORM_SUM: usize = 91;

static mut FORM: [[i32; FORM_SUM]; FORM_SIZE] = [[0; FORM_SUM]; FORM_SIZE];

fn init_form() {
    unsafe {
        FORM[0][0] = 1;
        for len in 1..=10 {
            for sum in 0..=len * 9 {
                for cur in 0..=9.min(sum as i32) {
                    FORM[len as usize][sum as usize] +=
                        FORM[(len - 1) as usize][(sum - cur) as usize];
                }
            }
        }
    }
}

fn get_form(len: usize, sum: usize) -> i32 {
    unsafe { FORM[len][sum] }
}

fn main() {
    println!("{}", i32::MAX);
    init_form();
    println!("{}", num1(88739128, 37));
    println!("{}", num2(88739128, 37));

    println!("{}", num1(1000, 4));
    println!("{}", num2(1000, 4));

    println!("{}", num1(2000, 6));
    println!("{}", num2(2000, 6));
}

在这里插入图片描述

本作品采用《CC 协议》,转载必须注明作者和本文链接
微信公众号:福大大架构师每日一题。最新面试题,涉及golang,rust,mysql,redis,云原生,算法,分布式,网络,操作系统。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!
未填写
文章
464
粉丝
21
喜欢
37
收藏
22
排名:461
访问:1.9 万
私信
所有博文
社区赞助商