剑指offer第二版|剑指offer 44. 从1到n整数中1出现的次数动态规划|c++|剑指offer|算法

?个人博客：https://blog.csdn.net/Newin2020?spm=1011.2415.3001.5343
专栏地址：剑指offer系列题解
原题地址：题目地址
专栏定位：为找工作的小伙伴整理常考算法题解，祝大家都能成功上岸！
??如果有收获的话，欢迎点赞收藏，您的支持就是我创作的最大动力

题目描述

输入一个整数 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 次。

【剑指offer第二版|剑指offer 44. 从1到n整数中1出现的次数】综上所述，我们只用去拿到该位左边的所有数已经右边的所有数，然后根据上面的情况进行计算，每一位都是这样计算。

class Solution { public: int numberOf1Between1AndN_Solution(int n) { if (!n)return 0; vector 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; } };

欢迎大家在评论区交流~