题目描述 输入一个整数 例如,输入12,1~12这些整数中包含1 的数字有1、10、11和12,1一共出现了5次。 示例 1: 输入:n = 1 输出:5 (分别是1 10 11 12) 示例 2: 输入:n = 13 输出:6 (分别是1 10 11 12 13) 思路 首先我们知道,肯定可以用求模取余的方法来获取1~n这n个数每个数位上的数,如果是1的话则ans+1,但我们有更巧妙的方法。 根据题目要求,我们需要统计 1~n 范围内所有整数中,数字 1 出现的个数。由于 n 的范围最大为 ,它是一个 10 位整数,因此我们可以考虑枚举每一个数位(个位,十位,百位等),分别统计该数位上数字 1 出现的次数,最后将所有数位统计出的次数进行累加即可得到答案。 为了直观地叙述我们的算法,下面我们以百位进行举例,对于几个不同的 n 手动计算出答案,随后扩展到任意数位。 以 n = 1234567 为例,我们需要统计百位上数字 1 出现的次数。我们知道,对于从 0 开始的 1000 个数(即000~999),百位上的数字 1 会出现 100 次,即数的最后三位每 1000个数都呈现 [000, 999] 的循环,其中的 [100, 199] 在「百位」上的数字为 1,共有 100 个。 而 n 拥有 1234 个这样的循环,每个循环百位上都出现了 100 次 1,这样就一共出现了 1234 ×100 次 1。如果使用公式表示,那么这部分出现的 1 的次数为:
而对于剩余不在完整的循环中的部分,即n的最后三位数567(即n%1000),这三位数的范围为000~567。我们记 ,这一部分在百位上出现1的次数可以通过分类讨论得出:
可以发现,当 , 的值小于等于 0,而我们希望得到 0 的答案; 时, 的值大于 100,而我们希望得到 100 的答案,因此我们可以总结归纳出这一部分在百位上 1 的出现次数为: 此时,我们就得到了 1~n 中百位上数字 1 出现的次数为:
我们用类似的方法可以计算出在其它数位上数字 11 出现的次数。如果该数位可以表示为(例如 k=0, 1, 2 分别表示个位,十位,百位),那么数字 1 出现的次数为:
Demo
|
|
来自: 520jefferson > 《数据结构与算法》