【算法】【算法杂谈】从1到n的自然数组中，1出现的次数如何计算？

前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识！

问题介绍

原问题
从1到n的自然数组中，1出现的次数如何计算？
如 [1…11] 中有1的有 1,10,11，结果为4

解决方案

原问题：
首先给一个示例：n = 114时，求[1…114]之间1的个数
首先我们求15 - 114之间1的个数，然后再求[1…14]之间1的个数，为什么这么来，可以看下面的感 ¹
15-114之间1的个数如何求？
1、首先百位是1时的数一共有14个，如果百位是2时，则百位是1的个数就是100-199，也就是 10^2个
2、其次求10位是1的个数，百位首先范围只能是1，如果百位是2，那么范围就是[1…2]，按照除了十位和百位以外，其他的可以随便取，所以就是10^1个，如果百位是2就是 2 * 10^1个，
3、接下来算个位时同十位相同，那么这个时候你可能会问，个位时1时，十位难道不限制吗？哎，就是不用限制，为什么？看下面¹
先看下代码怎么写，然后咱们讨论一下巧妙之处~

代码编写

java语言版本

原问题：
方法一：

  /*** 二轮测试： 给定整数num，求1-num中1出现的次数* @param num* @return*/public static int oneNumCp1(int num) {if (num < 1) {return 0;}if (num < 10) {// 10以内的数只有一个1return 1;}// 计算位数int len = 0;int tem = num;while (tem != 0) {len ++;tem /= 10;}// 求起点tem = num;// 最高位int height = (int)(tem / Math.pow(10, len-1));// 当前轮的起点int start = (int)(tem - (height) * Math.pow(10, len-1)) + 1;// 计算当前层的1的个数int oneNum = 0;// 先计算最高位是1的情况if (height == 1) {// 最高位是1oneNum += start;}else {oneNum += Math.pow(10, len-1);}// 剩余的自由组合oneNum += Math.pow(10, len-2) * height * (len-1);return oneNum + oneNumCp1(start-1);}public static void main(String[] args) {System.out.println(oneNumCp1(114));}

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

写在最后

方案和代码仅提供学习和思考使用，切勿随意滥用！如有错误和不合理的地方，务必批评指正~
如果需要git源码可邮件给[e-mail]
再次感谢左大神对我算法的指点迷津！

---

1. 首先这个答案可以解释上面两个疑惑：
   为什么偏偏计算15-114呢？就是因为我们在计算个位（后面可能是低位）的时候，以为十位可能会被限制为1，不能为2，这样计算起来很麻烦，所以这里取巧了，将15-99的数字全部加载114的后面，这样就凑齐了100-199，这样计算个位就不会被10位限制，很显然后续的计算直接计算1-15，也不会再计算15-99了。
   2、现在114并不典型，我们需要注意一下214的情况：
   214的解法仍然是求15 - 214先，我们发现15-99能够填充214到299，首先算十位是没有变化的（注意十位是1时百位是2时，219等价于 019 ）虽然219不存在，但是019能够作为代替，这也解释了为什么百位不能为1，只能是1-2的范围。
   3、还有一个容易误会的地方就是刚开始我会觉得当十位是1的时候，个位会有1的时候，那么计算个位1的时候十位也会有1的时候，是否会有重复？
   这里是一个理解误区，我们在计算1的个数时，如果有一个数是111，那么这个数应该被计数三次才对，很显然我们在排列组合的时候会计算三次，完全没有问题！ ↩︎ ↩︎