[leetcode~数位动态规划] 2719. 统计整数数目 hard

news/2024/2/27 20:54:44

给你两个数字字符串 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

class Solution {static final int N = 23;static final int M = 401;static final int MOD = 1000000007;int[][] d;String num;int min_sum;int max_sum;public int count(String num1, String num2, int min_sum, int max_sum) {d = new int[N][M];for (int i = 0; i < N; i++) {Arrays.fill(d[i], -1);}this.min_sum = min_sum;this.max_sum = max_sum;return (get(num2) - get(sub(num1)) + MOD) % MOD;}public int get(String num) {this.num = new StringBuffer(num).reverse().toString();return dfs(num.length() - 1, 0, true);}// 求解 num - 1,先把最后一个非 0 字符减去 1,再把后面的 0 字符变为 9public String sub(String num) {char[] arr = num.toCharArray();int i = arr.length - 1;while (arr[i] == '0') {i--;}arr[i]--;i++;while (i < arr.length) {arr[i] = '9';i++;}return new String(arr);}public int dfs(int i, int j, boolean limit) {if (j > max_sum) {return 0;}if (i == -1) {return j >= min_sum ? 1 : 0;}if (!limit && d[i][j] != -1) {return d[i][j];}int res = 0;int up = limit ? num.charAt(i) - '0' : 9;for (int x = 0; x <= up; x++) {res = (res + dfs(i - 1, j + x, limit && x == up)) % MOD;}if (!limit) {d[i][j] = res;}return res;}
}

http://www.ppmy.cn/news/1325624.html

相关文章

统计学-R语言-5.3

文章目录 前言分位数统计量的标准误总结 前言 本篇文章即为概率与分布的最后一篇文章。 分位数 分位数函数是累积分布函数的反函数。 p-分位数是具有这样性质的一个值&#xff1a;小于或等于它的概率为p。 根据定义&#xff0c;中位数即50%分位数。 分位数通常用于置信区间的…

kylin集群负载均衡(kylin3,hbaseRIF问题)

hbase历险记 目录 hbase历险记 寻找问题 分析原因 解决方案 方案1&#xff08;资源问题、失败&#xff09; 方案2&#xff08;成功&#xff09; 寻找问题 不知道你是不是有这样的疑惑。我kylin是个单机&#xff0c;我使用的hbase是个集群&#xff0c;但内存全在某一台机…

c# 自定义 滑块TrackBar

辛苦半天做出来的&#xff0c;如果觉得好用&#xff0c;记得点赞 效果图如下&#xff1a; 具体操作&#xff1a; 1 、添加代码&#xff08;代码在下面&#xff09;&#xff0c;重新生成下整个工程&#xff0c;在工具栏中就出现控件&#xff0c;将控件拖到窗体中 2、只需要调整…

leedcode刷题笔记day1

题目大意&#xff1a; 暴力解法 两个for循环&#xff08;也是我一看到题目想到的方法&#xff09; 枚举在数组中所有的不同的两个下标的组合逐个检查它们所对应的数的和是否等于 target 复杂度分析 时间复杂度:O(n2)&#xff0c;这里 n 为数组的长度 空间复杂度:O(1)&#x…

STM32F103标准外设库——SysTick系统定时器(八)

个人名片&#xff1a; &#x1f981;作者简介&#xff1a;一名喜欢分享和记录学习的在校大学生 &#x1f42f;个人主页&#xff1a;妄北y &#x1f427;个人QQ&#xff1a;2061314755 &#x1f43b;个人邮箱&#xff1a;2061314755qq.com &#x1f989;个人WeChat&#xff1a;V…

容器技术1-容器与镜像简介

目录 1、容器与虚拟化 2、容器发展历程 3、镜像简介 4、镜像原理 &#xff08;1&#xff09;分层存储 &#xff08;2&#xff09;写时复制 &#xff08;3&#xff09;内容寻址 &#xff08;4&#xff09;联合挂载 1、容器与虚拟化 容器技术在操作系统层面实现了对计算机…

无法定位程序输入点~于动态链接库上

无法定位程序输入点~于动态链接库上 拷贝库文件的时候拷错了 可以看到对于相同名字的文件&#xff0c;不同编译器对于的文件是不同的

Git 在 SSH 协议下使用代理

关于 Git 使用 Proxy , 网上很多教程讲的都是 如何设置 Http 下 Git 使用 Proxy , 但是并没有提到 SSH 下如何使用 Proxy . 即便有些文章讲到了, 也有不少是 Windows 平台下的, Linux 平台下的很少提及, 所以这里就记录一下, 如何在 Ubuntu 中, 使用 Git 在 SSH 协议下应用代理…

“一键中日文件夹名转换 - 批量修改,轻松实现中文到日语的名称翻译“

在处理大量文件夹时&#xff0c;你是否曾为中日文件夹名称的转换而感到困扰&#xff1f;现在&#xff0c;有了我们的批量修改工具&#xff0c;这些烦恼全部消失&#xff01;只需简单几步&#xff0c;就能将中文名的文件夹名称翻译成日语&#xff0c;让你的文件管理更加高效。 …

使用 Kali Linux Hydra 工具进行攻击测试和警报生成

一、Hydra 工具和 Kali Linux 简介 在网络安全领域中&#xff0c;渗透测试是评估系统密码强度的重要组成部分。Hydra 是一款由黑客组织“The Hackers Choice”开发的开源登录破解工具&#xff0c;支持50多种协议。本教程将探索如何将 Hydra 与 Kali Linux 结合使用&#xff0c…

【论文阅读】Relation-Aware Graph Transformer for SQL-to-Text Generation

Relation-Aware Graph Transformer for SQL-to-Text Generation Abstract SQL2Text 是一项将 SQL 查询映射到相应的自然语言问题的任务。之前的工作将 SQL 表示为稀疏图&#xff0c;并利用 graph-to-sequence 模型来生成问题&#xff0c;其中每个节点只能与 k 跳节点通信。由…

MySQL 8.0中已过时的选项和变量

以下系统变量、状态变量和选项在 MySQL 8.0 版本中已过时&#xff1a; 以下系统变量、状态变量和选项在 MySQL 8.0 版本中已被废弃。 • Compression&#xff1a;客户端连接是否使用压缩的客户端/服务器协议。在 MySQL 8.0.18 版本中废弃。 • Slave_open_temp_tables&#x…

Python实战:多进程知识

一 传统编程的缺陷 传统编程的弊端&#xff1a; # 必须按照顺序执行&#xff0c;多个任务无法同时在还行 import timedef sing():for i in range(5):print("sing: hero")time.sleep(1) # 每唱一次&#xff0c;等1秒再唱def dance():for i in range(5):print(…

Git 远程仓库

以 GitHub/Gitee 为例&#xff0c;作为简述 Git 中的远程仓库&#xff0c;以及常用命令。 配置 SSH 本地 Git 仓库和 GitHub/Gitee 仓库之间的传输是通过 SSH 加密的&#xff1a; 创建 SSH Key。 # 检查本地主机是否已存在 ssh key $ cd ~/.ssh $ ls # 若没有文件 id_rsa 和 i…

JavaScript从入门到精通系列第三十一篇:详解JavaScript中的字符串和正则表达式相关的方法

文章目录 知识回顾 1&#xff1a;概念回顾 2&#xff1a;正则表达式字面量 一&#xff1a;字符串中正则表达式方法 1&#xff1a;split 2&#xff1a;search 3&#xff1a;match 4&#xff1a;replace 知识回顾 1&#xff1a;概念回顾 正则表达式用于定义一些字符串的…

windows安装mysql5.7

看了如何学习mysql后&#xff0c;就开始本地安装mysql&#xff0c;开始学习了。 1.官网下载 官网地址&#xff1a; https://dev.mysql.com/downloads/mysql/ 选择5.7版本 点击 “No thanks, just start my download”开始下载 下载64位的压缩包版 解压下载好的.zip文件&#xf…

PBR材质背光面太暗优化

图形学中漫反射光照遵循兰伯特光照模型&#xff0c;它的公式如下 其中&#xff1a; &#xff1a;漫反射光颜色 &#xff1a;入射光颜色 &#xff1a;材质的漫反射系数 &#xff1a;法线方向 &#xff1a;光源方向 由于背光面的法线方向和光源方向的点积为负数&#xff0c;因此…

c语言-库函数memcpy()、memmove()、memcmp()、memset()介绍

文章目录 前言一、库函数memcpy()1.1 memcpy()介绍1.2 memcpy()模拟实现 二、库函数memmove()2.1 memmove()介绍2.2 memmove()模拟实现 三、库函数memcmp()3.1 memcmp()介绍 四、库函数memset()4.1 memset()介绍 总结 前言 本篇文章介绍c语言库函数memcpy()、memmove()、memcm…

用 Python 制作可视化 GUI 界面,一键实现证件照背景颜色的替换

今天&#xff0c;我们来分享一下如何通过Python的十来行代码来替换证件照的背景颜色&#xff0c;那么在最后&#xff0c;小编也会将上述的流程制作成一个GUI界面来方便大家使用。关于界面的大致模样其实和先前的相差不大&#xff0c;大家应该都看过上一篇的内容 界面大体的样子…

网络原理--http

目录 一、 DNS&#xff08;应用层协议&#xff09; 1、域名概念 2、维护ip地址和域名之间的映射&#xff08;域名解析系统&#xff09; 3、DNS系统&#xff08;服务器&#xff09; 4、如何解决DNS服务器高并发问题 二、HTTP&#xff08;应用层协议&#xff09; 1、htt…
最新文章