当前位置: 首页 > news >正文

经典算法 统计数字问题(常数时间解决)

统计数字问题

一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排,每个页码都不含多余的前导数字0。例如,第6 页用数字6 表示,而不是06 或006 等。数字计数问题要求对给定书的总页码n,计算出书的全部页码中分别用到多少次数字0,1, 2,…,9。
给定表示书的总页码的10 进制整数n (1≤n≤10^9 ) 。编程计算书的全部页码中分别用到多少次数字0,1,2,…,9。

输入示例

11

输出示例

1
4
1
1
1
1
1
1
1
1

输入示例

99999974

输出示例

68888887
79999998
79999998
79999998
79999998
79999997
79999997
79999992
79999987
79999837

c++代码

算法时间复杂度o(1)

#include<bits/stdc++.h>using namespace std;void countDigits(int num, vector<int>& digitCount) {int factor = 1;while (factor <= num) {int lower = num - (num / factor) * factor;int current = (num / factor) % 10;int higher = num / (factor * 10);for (int i = 0; i < 10; ++i) {digitCount[i] += higher * factor;if (i < current) digitCount[i] += factor;else if (i == current) digitCount[i] += lower + 1;}digitCount[0] -= factor;factor *= 10;}
}int main() {int n;cout << "请输入书的总页码 n: ";cin >> n;vector<int> digitCount(10, 0);countDigits(n, digitCount);for (int i = 0; i < 10; ++i) {cout << digitCount[i] << endl;}return 0;
}//by wqs

题目解析

这个题目的暴力方法很容易想到,从0开始遍历一直到n,然后不断余10除10得到各位上的数字(这个操作常数时间可以解决),

所以时间复杂度o(n),可惜1≤n≤10^9,当n = 10^9会超时。

我的办法可以在常数时间内解决这个问题。

算法讲解

vector<int> digitCount(10, 0);//记录答案

我的办法就是一位数一位数的来,统计个位数出现多少次,然后统计十位数出现多少次,然后统计百位数出现多少次。

把他们加起来就是最终答案,那么怎么求呢。

int factor = 1;
while (factor <= num) {//...factor *= 10;
}

举两个例子

从0-135687、从0-175687789

例如求0-135687千位数上每个数字出现的次数(也就是n = 135687)

再来一个验证用例例如求0-175687789千万位数上每个数字出现的次数(也就是n = 175687789)

我会分三部分计算,对于任意一个数都可以分成三部分

cur、low、high、factor

n = 135687,求千位数

cur指当前千位数上的数也就是5

low指cur后面的数也就是687

high指cur前面的数也就是13

factor指当前的位数也就是1000

n = 175687789,求千万位数

cur指当前千万位数上的数也就是7

low指cur后面的数也就是5687789

high指cur前面的数也就是1

factor指当前的位数也就是10000000

int lower = num - (num / factor) * factor;
int current = (num / factor) % 10;
int higher = num / (factor * 10);
第一部分 从000000-129999、从000000000-099999999

为了方便计算我们引入前导0,当然根据题目要求我们最后要减去前导0。例如2表示为000002,0表示为000000,长度和n的长度一样。

先求从000000-129999千位数上每个数字出现的次数

000000

000001

…省略1000行左右,千位上0已经出现了1000次

001000

001001

…省略1000行左右,千位上1已经出现了1000次

002000

…省略8000行左右,这个时候0-9都已经出现了1 * 1000次

009999

…省略10000行左右这个时候0-9都已经出现了2 * 1000次

019999

129999

这个时候0-9都已经出现了13 * 1000次

事实上,这个值就是higher * factor.

000000-129999千位数上每个数字出现的次数 = higher * factor

再比如辅助例子里面000000000-099999999千万位数上每个数字出现的次数 = higher * factor = 1 * 10000000

这说明0-9都有一部分是 higher * factor

for (int i = 0; i < 10; ++i) {digitCount[i] += higher * factor;
}
第二部分 从130000-134999,从100000000-169999999

现在求从130000-134999千位数上每个数字出现的次数

130000

130001

…0已经出现了1000次

130999

131000

131001

…1已经出现了1000次

131999

134999

从0-4已经出现了1000次

这个值就是factor.

从130000-134999千位数上0-current - 1数字出现的次数 += factor.

for (int i = 0; i < 10; ++i) {if (i < current) digitCount[i] += factor;
}
第三部分 从135000到135687,从170000000-175687789

现在求从135000-135687千位数上每个数字出现的次数

135000

135001

.

.

.

135687

5出现的次数就是行数

一共688行也就是low + 1

for (int i = 0; i < 10; ++i) {if (i == current) digitCount[i] += lower + 1;
}
去除前导0

000000

000001

…省略大概1000行

000999

001000

前导0的个数就是factor的大小

digitCount[0] -= factor;

相关文章:

经典算法 统计数字问题(常数时间解决)

统计数字问题 一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排&#xff0c;每个页码都不含多余的前导数字0。例如&#xff0c;第6 页用数字6 表示&#xff0c;而不是06 或006 等。数字计数问题要求对给定书的总页码n&#xff0c;计算出书的全部页…...

基于yolov8的糖尿病视网膜病变严重程度检测系统python源码+pytorch模型+评估指标曲线+精美GUI界面

【算法介绍】 基于YOLOv8的糖尿病视网膜病变严重程度检测系统 基于YOLOv8的糖尿病视网膜病变严重程度检测系统是一款利用深度学习技术&#xff0c;专为糖尿病视网膜病变早期诊断设计的智能辅助工具。该系统采用YOLOv8目标检测模型&#xff0c;结合经过标注和处理的医学影像数…...

AcWing 5933:爬楼梯 ← 递归 / 递推 / 高精度

【题目来源】 https://www.acwing.com/problem/content/5936/ 【题目描述】 树老师爬楼梯&#xff0c;他可以每次走 1 级或者 2 级&#xff0c;输入楼梯的级数&#xff0c;求不同的走法数。 例如&#xff1a;楼梯一共有 3 级&#xff0c;他可以每次都走一级&#xff0c;或者第…...

c++ 中的容器 vector 与数组 array

当初自学 c 与 c 语言时&#xff0c;一直被指针弄的云里雾里。后来 c 中引入了容器&#xff0c;避免了指针。但是&#xff0c;一些教材把容器的章节放在书本中后面的章节&#xff0c;太不合理。应该把这种方便的功能放到前面&#xff0c;这样一些初学者就不会遇到太多生硬难懂的…...

我的世界1.20.1forge模组开发进阶物品(7)——具有动画、3D立体效果的物品

基础的物品大家都会做了对吧?包括武器的释放技能,这次来点难度,让物品的贴图呈现动画效果和扔出后显示3D立体效果,这个3D立体效果需要先学习blockbench,学习如何制作贴图。 Blockbench Blockbench是一个用于创建和编辑三维模型的免费软件,特别适用于Minecraft模型的设计…...

ubuntu22.04安装docker engine

在Ubuntu 22.04上安装Docker Engine可以通过以下步骤完成&#xff1a; 更新系统包索引&#xff1a; sudo apt update安装必要的依赖包&#xff1a; 这些包允许apt通过HTTPS使用仓库。 sudo apt install -y apt-transport-https ca-certificates curl software-properties-commo…...

性能测试测试策略制定|知名软件测评机构经验分享

随着互联网产品的普及&#xff0c;产品面对的用户量级也越来越大&#xff0c;能抗住指数级增长的瞬间访问量以及交易量是保障购物体验是否顺畅的至关重要的一环&#xff0c;而我们的性能测试恰恰也是为此而存在的。 性能测试是什么呢&#xff1f;性能测试要怎么测呢&#xff1f…...

Let‘s Encrypt免费证书的应用示例

文章目录 前言证书申请证书介绍cert.pemchain.pemfullchain.pemprivkey.pem 使用步骤搭建简易demo应用新建nginx配置文件测试SSL是否生效 总结 前言 最近在搞苹果应用上架的问题&#xff0c;据说用HTTP会被拒&#xff0c;但貌似不绝对&#xff0c;2017年苹果曾发公告说必须要求…...

threeJS——安装以及三要素

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、安装二、三要素1.场景1.1创建场景1.2向场景添加元素1.3场景属性 2.相机2.1相机特点2.2正交相机2.3空间布局2.4小姐操作 3.渲染器 总结 前言 本章简单介绍前…...

【Electron入门】进程环境和隔离

目录 一、主进程和渲染进程 1、主进程&#xff08;main&#xff09; 2、渲染进程&#xff08;renderer&#xff09; 二、预加载脚本 三、沙盒化 为单个进程禁用沙盒 全局启用沙盒 四、环境访问权限控制&#xff1a;contextIsolation和nodeIntegration 1、contextIsola…...

提示词框架介绍和使用场景

框架介绍 CO-STAR 框架 定义 CO-STAR是六个关键要素的缩写,每个字母代表一个特定的部分: Context(上下文) :提供任务的背景信息或环境 当前任务是为一家科技公司撰写一篇关于人工智能发展趋势的文章/ 需要为一场面向高中生的科普讲座准备内容Objective(目标) :明确任…...

牛客NC288803 和+和

​import java.util.Comparator;import java.util.PriorityQueue;import java.util.Scanner;​public class Main {public static void main(String[] args) {// 创建Scanner对象用于读取输入Scanner sc new Scanner(System.in);// 读取两个整数n和m&#xff0c;分别表示数组的…...

AI学习第七天

数组&#xff1a;基础概念、存储特性及力扣实战应用 在计算机科学与数学的广袤领域中&#xff0c;数组作为一种极为重要的数据结构&#xff0c;发挥着不可或缺的作用。它就像一个有序的 “数据仓库”&#xff0c;能高效地存储和管理大量数据。接下来&#xff0c;让我们深入了解…...

【uniapp原生】实时记录接口请求延迟,并生成写入文件到安卓设备

在开发实时数据监控应用时&#xff0c;记录接口请求的延迟对于性能分析和用户体验优化至关重要。本文将基于 UniApp 框架&#xff0c;介绍如何实现一个实时记录接口请求延迟的功能&#xff0c;并深入解析相关代码的实现细节。 前期准备&必要的理解 1. 功能概述 该功能的…...

XR应用测试:探索虚拟与现实的边界

引言 随着XR&#xff08;扩展现实&#xff0c;Extended Reality&#xff09;技术的快速发展&#xff0c;VR&#xff08;虚拟现实&#xff09;、AR&#xff08;增强现实&#xff09;和MR&#xff08;混合现实&#xff09;应用逐渐渗透到游戏、教育、医疗、工业等多个领域。对于…...

算法之算法思想

算法思想 ♥算法思想知识体系详解♥ | Java 全栈知识体系 经典算法思想总结 经典算法思想总结&#xff08;含LeetCode题目推荐&#xff09; | JavaGuide...

mac电脑中使用无线诊断.app查看连接的Wi-Fi带宽

问题 需要检查连接到的Wi-Fi的AP硬件支持的带宽。 步骤 1.按住 Option 键&#xff0c;然后点击屏幕顶部的Wi-Fi图标&#xff1b;2.从下拉菜单中选择 “打开无线诊断”&#xff08;Open Wireless Diagnostics&#xff09;&#xff1b;3.你可能会看到一个提示窗口&#xff0c;…...

物理竞赛中的线性代数

线性代数 1 行列式 1.1 n n n 阶行列式 定义 1.1.1&#xff1a;称以下的式子为一个 n n n 阶行列式&#xff1a; ∣ A ∣ ∣ a 11 a 12 ⋯ a 1 n a 21 a 22 ⋯ a 2 n ⋮ ⋮ ⋱ ⋮ a n 1 a n 2 ⋯ a n n ∣ \begin{vmatrix}\mathbf A\end{vmatrix} \begin{vmatrix} a_{11…...

FFmpeg-chapter3-读取视频流(原理篇)

ffmpeg网站&#xff1a;About FFmpeg 1 库介绍 &#xff08;1&#xff09;libavutil是一个包含简化编程函数的库&#xff0c;包括随机数生成器、数据结构、数学例程、核心多媒体实用程序等等。 &#xff08;2&#xff09;libavcodec是一个包含音频/视频编解码器的解码器和编…...

机器视觉线阵相机分时频闪选型/机器视觉线阵相机分时频闪选型

在机器视觉系统中,线阵相机的分时频闪技术通过单次扫描切换不同光源或亮度,实现在一幅图像中捕捉多角度光照效果,从而提升缺陷检测效率并降低成本。以下是分时频闪线阵相机的选型要点及关键考量因素: 一、分时频闪技术的核心需求 多光源同步控制 分时频闪需相机支持多路光源…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

Admin.Net中的消息通信SignalR解释

定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

ffmpeg(四):滤镜命令

FFmpeg 的滤镜命令是用于音视频处理中的强大工具&#xff0c;可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下&#xff1a; ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜&#xff1a; ffmpeg…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

多模态大语言模型arxiv论文略读(108)

CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题&#xff1a;CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者&#xff1a;Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...