微信订单网站模版,网页加速器浏览器,网站集约化建设建议,自媒体135编辑器官网Problem: 2719. 统计整数数目 文章目录 题目思路复杂度Code 题目
给你两个数字字符串 num1 和 num2 #xff0c;以及两个整数 max_sum 和 min_sum 。如果一个整数 x 满足以下条件#xff0c;我们称它是一个好整数#xff1a;
num1 x num2 min_sum digit_su… Problem: 2719. 统计整数数目 文章目录 题目思路复杂度Code 题目
给你两个数字字符串 num1 和 num2 以及两个整数 max_sum 和 min_sum 。如果一个整数 x 满足以下条件我们称它是一个好整数
num1 x num2 min_sum digit_sum(x) max_sum. 请你返回好整数的数目。答案可能很大请返回答案对 109 7 取余后的结果。
注意digit_sum(x) 表示 x 各位数字之和。
示例 1
输入num1 “1”, num2 “12”, min_num 1, max_num 8 输出11 解释总共有 11 个整数的数位和在 1 到 8 之间分别是 1,2,3,4,5,6,7,8,10,11 和 12 。所以我们返回 11 。 示例 2
输入num1 “1”, num2 “5”, min_num 1, max_num 5 输出5 解释数位和在 1 到 5 之间的 5 个整数分别为 1,2,3,4 和 5 。所以我们返回 5 。
提示
1 num1 num2 1022 1 min_sum max_sum 400
思路
我们编写一个函数计算所有小于high且满足所有位的和小于max_sum的数的个数 将num1和num2分别带入这个函数得到a和b我们目前的答案就是 b - a
注意此时我们还没有处理num1,这个数我们需要额外计算一下他是否满足好整数
对于计算出现次数的函数我们的最终目的是构造一个满足大于等于min_sum且小于等于max_sum的数s,我们最终统计构造了多少次
我们申明三个参数
i : 构造第i位s:当前构造的数is_limit: 是否受到前一位的制约
在递归过程中当s大于max_sum时说明这个s不可能被取到了返回
当i递归到末尾此时s满足好整数则加1
我们判断下当前要填入的数的最大值有没有受前一位影响如果被影响了就只能填high[i],否则可以填0-9所有数(eg:123,如果第一位我构造为0则第二位只能填012如果第一位构造为0第二位可以填入0-9)
我们开始构造下一位数字
返回结果
复杂度
时间复杂度: 时间复杂度 O ( n m D ) O(nmD) O(nmD) 空间复杂度: O ( m n ) O(mn) O(mn) Code
class Solution:def count(self, num1: str, num2: str, min_sum: int, max_sum: int) - int:def calc(high):cache def dfs(i,s,is_limit):if smax_sum:return 0if ilen(high):return s min_sumres 0up int(high[i]) if is_limit else 9for d in range(up1):res dfs(i1,sd,is_limit and dup)return resreturn dfs(0,0,True)ans ( calc(num2) - calc(num1) ) % 1_000_000_007x 0for i in range(len(num1)):x int(num1[i])if min_sum x max_sum:ans1return ans
