题目描述
输入一个整数 n,求从 1 到 n 这 n 个整数的十进制表示中 1 出现的次数。
例如输入 12,从 1 到 12 这些整数中包含 “1” 的数字有 1,10,11 和 12,其中 “1” 一共出现了 5 次。
数据范围
1≤n≤109
样例
输入: 12 输出: 5
方法一:数位DP O(logn)
如果按照暴力的做法,我们从 1~n 每个数都去算一遍 1 的个数,这个时间复杂度肯定会很高的,要是在面试的时候这么做估计就是出门右转的事情了 doge ~
所以这道题需要对上述操作进行优化,我们用到的方法是数位 DP ,先来看一个例子方便大家理解,假设 n = 13015 ,这时候就需要分情况进行讨论:
- 【万位的1】
1 _ _ _ _
中第一位取1
,则此时已经封顶,后四位只能取0000 ~ 3015
,故一共出现了1 * 3016 = 3016
次。
- 【千位的1】
_ 1 _ _ _
中第一位取0
时,后三位可以取000 ~ 999
,故一共出现1 * 1000
次。1 1 _ _ _
中第一位封顶,则后三位可以取000 ~ 999
,故一共出现1 * 1000 = 1000
次。
- 【百位的1】
_ _ 1 _ _
中前两位范围是00 ~ 12
,则后两位可以取00 ~ 99
,故一共出现13 * 100 = 1300
次。1 3 0 _ _
中前两位封顶,则第三位最高只能取0
且后两位范围是00 ~ 15
,故一共出现16
次。
- 【十位的1】
_ _ _ 1 _
中前三位范围是000 ~ 129
,则最后一位可以取0 ~ 9
,故一共出现130 * 10 = 1300
次。1 3 0 1 _
中前三位封顶且第四位发现可以取到1
,则最后一位可以取0 ~ 5
共6
次。
【个位的1】
_ _ _ _ 1 中前四位范围是 0000 ~ 1301 ,故一共出现 1 * 1302 = 1302 次。
通过上面这个例子,我们就可以得到下面这个结论:
假设给定 n = a b c d e f ,我们这里计算一下 c 这一位 1 出现的次数(其它位同理)。
(1)当前两位的范围是 00 ~ ab-1 时,后面三位可以取 000 ~ 999 ,故一共出现 ab * 1000 次。
(2)如果前两位封顶即取的就是 ab ,那么又要分三种情况,要看看给定的 n 的 c 的值是多少:
当 c = 0 时,一共出现 0 次。
当 c = 1 时,后三位可以取 000 ~ def ,故一共出现 def + 1 次。
当 c > 1 时,后三位可以取 000 ~ 999 ,故一共出现 1000 次。
综上所述,我们只用去拿到该位左边的所有数已经右边的所有数,然后根据上面的情况进行计算,每一位都是这样计算。
class Solution { public: int numberOf1Between1AndN_Solution(int n) { if (!n) return 0; vector<int> number; //用来存储每一位 while (n) number.push_back(n % 10), n /= 10; int ans = 0; //从最高位开始计算 for (int i = number.size() - 1; i >= 0; i--) { int left = 0, right = 0, t = 1; //获得第i位左边的数 for (int j = number.size() - 1; j > i; j--) left = left * 10 + number[j]; //获取第i为右边的数 for (int j = i - 1; j >= 0; j--) right = right * 10 + number[j], t *= 10; //计算左边的数在0~ab-1的那种情况 ans += left * t; //计算左边的数等于ab的那种情况 if (number[i] == 1) ans += right + 1; else if (number[i] > 1) ans += t; } return ans; } };
欢迎大家在评论区交流~