蓝桥杯每日一题-----数位dp练习

题目

在这里插入图片描述
链接

参考代码

写了两个,一个是很久以前写的,一个是最近刚写的,很久以前写的时候还不会数位dp所以写了比较详细的注释,这两个代码主要是设置了不同的记忆数组,通过这两个代码可以理解记忆数组设置的灵活性。


import java.util.Scanner;public class Main {// 给定两个正整数a和b,求在[a,b]中的所有整数中,每个数码(digit)各出现了多少次。static int[] b = new int[15];static long[][][] f = new long[15][10][15];public static void main(String[] args) {Scanner scanner = new Scanner(System.in);long n = scanner.nextLong();long m = scanner.nextLong();for (int i = 0; i < 15; i++) {for (int j = 0; j < 10; j++) {for (int j2 = 0; j2 < 15; j2++) {f[i][j][j2] = -1;}}}for (int i = 0; i <= 9; i++) {System.out.print((get(m, i) - get(n - 1, i)) + " ");}}private static long get(long x, int target) {// TODO Auto-generated method stublong t = x;int i = 0;while (t > 0) {b[i++] = (int) (t % 10);t = t / 10;}return dfs(target, true, true, i - 1, 0);}//	target  表示要计算的值
//	e  是否贴上界
//当要判断的数的位数小于原数的位数时,就没有上界了,如果位数和原数一样,每一位的上界就是对应的原数
//	first  是否是数的第一个位
//	k  数的第几位 now
//  t  出现的次数private static long dfs(int target, boolean e, boolean first, int k, int t) {// TODO Auto-generated method stub//long res = 0;if (k == -1)return t;// 如果数位考虑完,返回出现的次数// f[k][target][t]时公用的,找这个x的时候可以用,找下一个x的时候也可以用,所以他应该具有普遍性,// 但是当我的位数和x一样时,他有不同的边界if ((!e) && (!first) && f[k][target][t] != -1)return f[k][target][t];// 判断这一位我可以最大填到哪个数int u = e ? b[k] : 9;// 如果是要填写首位数,那么这个数等于0的时候其实位数是减一,要单独考虑。if (first) {res += dfs(target, false, true, k - 1, t);}// 注意我已经判断了如果要给首位填数,首位数为0的情况,所以当要给首位填数时,我要从1开始,如果不是首位,那么从0开始即可for (int i = first ? 1 : 0; i <= u; i++) {// 贴上界是指此时的位数的上界是受此位的数的限制,最大数可能到达不了9// 只有本位是贴上界的下一位才有贴上界的可能,比如54321,只要是第五位他的上界就是5,也就是此位最大取到5,// 这也就是为什么在get中一开始遍历的时候e = true// 当确定了这个数是5位的时候,如果第五位小于5,那他后面的数是不贴上界的最大值可以写到9,但如果第五位等于5// 那下一位也是贴上界的,最大值只能取到4// (i == u) & e 这也是它的来源res += dfs(target, (i == u) & e, false, k - 1, (i == target) ? t + 1 : t);}// f[k][target][t]时公用的,找这个x的时候可以用,找下一个x的时候也可以用,所以他应该具有普遍性,// 但是当我的位数和x一样时,他有不同的边界限制,此时他得出的值具有个性,不能给其他的x用,所以不能存在f数组中// 这是为什么要判断是否贴上界的原因// 当该位数为一个数的首位时,因为此时该数的实际位数是不确定的,首位为0时实际位数会减少,但我依然记录在res中,这样此时的// (f[k][target][t] 就有两种情况一是k是首位的时候,二是k不是首位的时候,所以我们应该舍去k时首位的时候if (!e && !first) {f[k][target][t] = res;}return res;}
}
import java.util.Arrays;
import java.util.Scanner;public class 数字计数 {static long dp[][][][] = new long[15][10][15][2];
public static void main(String[] args) {Scanner scanner = new Scanner(System.in);long a = scanner.nextLong();long b = scanner.nextLong();for(int i = 0;i < 15;i++)for(int j = 0;j < 10;j++)for(int k = 0;k < 15;k++)Arrays.fill(dp[i][j][k], -1);for(int i = 0;i < 10;i++)System.out.print(solve(b,i)-solve(a-1,i)+" ");//20 21 2 12 22 32 42 52 62 72 82 92 23 24 25 26 27 28 29
//	System.out.println(solve(b, 2));//2 12 20-29(10) 32 42 52 62 72 82 92 22
}
static int nums[] = new int[15];
static int temp[] = new int[15];
static int tot = 0;
private static long solve(long n,int k) {// TODO Auto-generated method stubtot=0;while(n > 0) {nums[++tot] = (int) (n % 10);n /= 10;}return dfs(tot,1,1,k,0);
}
private static long dfs(int cnt, int limit, int zeros, int k, int num) {// TODO Auto-generated method stubif (cnt==0) {
//		for(int i = 1;i <= 2;i++) System.out.print(temp[i]);
//		System.out.println( " "+ num);return num;}if(limit==0&&dp[cnt][k][num][zeros]!=-1) return dp[cnt][k][num][zeros];int up = limit==1?nums[cnt]:9;int st = zeros==1?1:0;long res = 0;if(zeros==1)  res+=dfs(cnt-1, (0==up?1:0)&limit, 1, k, num);//该位填0for(int i = st;i <= up;i++) {
//		temp[cnt]=i;res+=dfs(cnt-1, (i==up?1:0)&limit, 0, k, i==k?num+1:num);}if(limit==0) dp[cnt][k][num][zeros]=res;return res;
}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/251839.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

npm ERR! code CERT_HAS_EXPIRED

执行npm i报错&#xff1a; npm ERR! code ETIMEDOUT npm ERR! syscall connect npm ERR! errno ETIMEDOUT npm ERR! network request to https://registry.npmjs.org/react-redux failed, reason: connect ETIMEDOUT 104.16.2.35:443 npm ERR! network This is a problem rel…

python常用pandas函数nlargest / nsmallest及其手动实现

目录 pandas库 Series和DataFrame nlargest和nsmallest 用法示例 代替方法 手动实现 模拟代码 pandas库 是Python中一个非常强大的数据处理库&#xff0c;提供了高效的数据分析方法和数据结构。它特别适用于处理具有关系型数据或带标签数据的情况&#xff0c;同时在时间…

十分钟学会用springboot制作微信小程序富文本编辑器

1.1 富文本模型设计 在构建富文本编辑器系统时&#xff0c;首先需要设计一个合适的富文本模型。 CREATE TABLE IF NOT EXISTS rich_texts (id INT PRIMARY KEY AUTO_INCREMENT,title VARCHAR(255),content TEXT,created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP );这个表包括…

【算法与数据结构】647、516、LeetCode回文子串+最长回文子序列

文章目录 一、647、回文子串二、516、最长回文子序列三、完整代码 所有的LeetCode题解索引&#xff0c;可以看这篇文章——【算法和数据结构】LeetCode题解。 一、647、回文子串 思路分析&#xff1a;判断一个字符串是否为回文串那么必须确定回文串的所在区间&#xff0c;而一维…

(2)(2.13) Rockblock Satellite Modem

文章目录 前言 1 支持的MAVLink命令信息 2 设置 3 使用方法 4 数据成本 5 参数 前言 &#xff01;Note 该功能仅适用于 ArduPilot 4.4 或更高版本&#xff0c;并且要求飞行控制器支持 LUA 脚本(LUA Scripts)。 RockBLOCK 卫星调制解调器可实现与 ArduPilot 飞行器的全球…

如何将pdf转换成ppt?掌握这个方法就简单多了

有时候&#xff0c;PDF文件的布局和设计可能需要进行微调或重新排版&#xff0c;以适应PPT的特定格式和风格。那么怎么pdf怎么转ppt呢&#xff1f;为了更方便地对布局、字体、图像和其他元素进行编辑和调整&#xff0c;以符合PPT的需求&#xff0c;我们可以直接通过pdf在线转pp…

SQL Server之DML触发器

一、如何创建一个触发器呢 触发器的定义语言如下&#xff1a; CREATE [ OR ALTER ] TRIGGER trigger_nameon {table_name | view_name}{for | After | Instead of }[ insert, update,delete ]assql_statement从这个定义语言我们可以知道如下信息&#xff1a; trigger_name&…

Linux项目自动化构建工具之make/Makefile演示gcc编译

文章目录 一、背景二、如何使用&#xff1f;三、原理四、关于make的问题五、再次理解/编写makefile依赖关系依赖方法 六、原理讲解项目清理makefile是支持变量的取消执行make后显示命令依赖方法可以多行 一、背景 会不会写makefile&#xff0c;从一个侧面说明了一个人是否具备…

nop-entropy可逆计算入门(1)

第1步&#xff1a;从大佬的gitee&#xff1a;https://gitee.com/canonical-entropy/nop-entropy下载源码&#xff0c;进行本地编译&#xff0c;具体编译看项目下的readme,想偷懒的可以下载我编译后的jar&#xff0c;放到自己的maven仓库 https://pan.baidu.com/s/1p9MOh40MJ2m…

mac如何实现升级node版本、切换node版本

一、 查看node所有版本&#xff08;前提:安装了nodejs&#xff09; npm view node versions二、安装指定node版本 sudo n 版本号三、检查目前安装了哪些版本的node&#xff0c;会出现已安装的node版本 n四、切换已安装的node版本 sudo n 版本号其他命令 1、sudo npm cache…

Centos 内存和硬盘占用情况以及top作用

目录 只查看内存使用情况&#xff1a; 内存使用排序取前5个&#xff1a; 硬盘占用情况 定位占用空间最大目录 top查看cpu及内存使用信息 前言-与正文无关 生活远不止眼前的苦劳与奔波&#xff0c;它还充满了无数值得我们去体验和珍惜的美好事物。在这个快节奏的世界中&…

Matlab数字图像处理——图像复原与滤波算法应用方法

图像处理领域一直以来都是计算机科学和工程学的一个重要方向&#xff0c;图像复原则是其中一个重要的研究方向之一。图像复原旨在通过运用各种滤波算法&#xff0c;对图像进行去噪、恢复和改善&#xff0c;以提高图像的质量和可视化效果。在本文中&#xff0c;我们将介绍如下内…

python Flask 写一个简易的 web 端程序(附demo)

python Flask 写一个简易的 web 端程序 &#xff08;附demo&#xff09; 介绍简单介绍装饰器 app.route("/") 进阶增加接口设置端口 静态网页核心代码完整代码 介绍 Flask 是一个用于构建 Web 应用程序的轻量级 Python Web 框架。它设计简单、易于学习和使用&#x…

ReactNative实现宽度变化实现的动画效果

效果如上图所示&#xff0c;通过修改设备宽度实现动画效果 import React, {useRef, useEffect, useState} from react; import {Animated, Text, View, Image} from react-native;const FadeInView props > {const fadeAnim useRef(new Animated.Value(0)).current;React…

list基本使用

list基本使用 构造迭代器容量访问修改 list容器底层是带头双向链表结构&#xff0c;可以在常数范围内在任意位置进行输入和删除&#xff0c;但不支持任意位置的随机访问&#xff08;如不支持[ ]下标访问&#xff09;&#xff0c;下面介绍list容器的基本使用接口。 template <…

k8s学习-Kubernetes的网络

Kubernetes作为编排引擎管理着分布在不同节点上的容器和Pod。Pod、Service、外部组件之间需要⼀种可靠的方找到彼此并进行通信&#xff0c;Kubernetes网络则负责提供这个保障。 1.1 Kubernetes网络模型 Container-to-Container的网络 当Pod被调度到某个节点&#xff0c;Pod中…

ARM PAC指针认证的侧信道攻击——PACMAN安全漏洞

目录 Q1. PACMAN论文的内容是什么&#xff1f; Q2. Arm处理器是否存在漏洞&#xff1f; Q3. 受Arm合作伙伴架构许可设计的处理器实现是否受到影响&#xff1f; Q4. Cortex-M85受到影响吗&#xff1f; Q5. Cortex-R82受到影响吗&#xff1f; Q6. 指针认证如何保护软件&…

Python 实现 五子棋小游戏【附源码】

引言 五子棋是一种古老而深受欢迎的策略游戏&#xff0c;它具有简单的规则和无穷的变化。作为一种传统的中国棋类游戏&#xff0c;五子棋已经在世界范围内流行起来&#xff0c;并成为智力挑战和休闲娱乐的优秀选择。 规则和玩法&#xff1a; 五子棋使用一个15x15的棋盘&#x…

MIMIC数据库, 使用Python研究万古霉素的剂量 (一)

一、万古霉素 是一种杀菌型 抗生素&#xff0c;抑制细菌细胞壁的合成 万古霉素对以下细菌有效&#xff1a; 大多数革兰阳性球菌和杆菌有抗菌活性&#xff0c;包括几乎所有耐青霉素和头孢菌素的 Staphylococcus aureus 和凝固酶阴性葡萄球菌株 许多菌株 肠球菌 &#xff08;…

【Java报错】显示错误“Error:java: 程序包org.springframework.boot不存在“

使用idea运行项目&#xff0c;显示错误信息如下&#xff1a; 原因是&#xff1a;idea配置的maven加载不到autoconfigure。 解决方案一&#xff1a; 第6步绕过证书语句如下&#xff1a; -Dmaven.wagon.http.ssl.insecuretrue -Dmaven.wagon.http.ssl.allowalltrue 打开终端&am…