1.问题描述

输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。
示例 1：
输入：n = 12
输出：5
示例 2：
输入：n = 13
输出：6
限制：
1 <= n < 2^31

2.问题分析

我们只需要知道1在每一位出现的次数就行

那么就需要通过找规律来分析。
假设我们对5014这个数字求解。
(1)个位上1出现的个数：记高位为high=501，当前位为cur=4。
那么高位从0~500变化的过程中，每一个变化中1只出现1次，即（高位1）这样的数字；
高位是501时，因为当前位是4，所以1只能出现一次，即5011。
所以总共出现的次数为high * 1+1=502。
(2)十位1出现的个数：记高位high=50，当前位为cur=1，低位为low=4。
那么高位从0~ 49变化的过程中，每一个变化中1出现10次，即（高位10）~（高位19）这样的数字；
高位为50的时候，因为当前位是1，所以我们要看低位来决定出现的次数，因为低位为4，所以此时出现5次，即5010~5014这样的数字。
所以总共出现的次数为high * 10+4=504。
(3)百位1出现的个数：记高位high=5，当前位cur=0，低位为low=14。
那么高位从0~ 4的过程中，每一个变化1出现100次，即（高位100）~（高位199）这样的数字；
高位为5的时候，因为当前位为0，所以不存在出现1的可能性。
所以总共出现的次数为high * 100+0=500。
(4)千位1出现的次数：记高位high=0，当前位cur=5，低位low=014。
那么因为没有高位所以直接看当前位，因为当前位为5，所以1出现的次数为1000，即1000~1999这样的数字。
所以总共出现的次数为high*1000+1000=1000。
综上，最终的结果将每个位置出现1的次数累加即可。

结论:
我们假设高位为high，当前位为cur，低位为low，i代表着需要统计的位置数（1对应个位，10对应十位，100对应百位），则对每一位的个数count有：
cur=0,count = high*i;
cur=1,count=high*i+low+1(多加的这个1是低位全0的情况);
cur>1,count=(high+1)*i
最终累加所有位置上的个数即最终答案。

3.代码实现

3.1.C++代码

int countDigitOne(int n) { int count = 0; long i = 1;//指向遍历的位数，如i=1即个位，i=10即十位，...，因为n可以有31位，所以10^31用long存储 while(n/i!=0){ //n/i控制遍历的次数，将所有的位数都遍历完毕 long high = n/(10*i);//将当前位之前的所有高位都存在high中 long cur = (n/i)%10;//将当前位记录在cur中，即我们每次都需要统计当前位上1出现的次数 long low = n-(n/i)*i; if(cur == 0){             count += high * i; } else if(cur == 1){             count += high * i + low + 1; } else {             count += (high+1) * i; }         i = i * 10;//准备遍历下一位 } return count; } 

3.2.Java代码

public int countDigitOne(int n) { int count = 0; long i = 1;//指向遍历的位数，如i=1即个位，i=10即十位，...，因为n可以有31位，所以10^31用long存储 while(n/i!=0){ //n/i控制遍历的次数，将所有的位数都遍历完毕 long high = n/(10*i);//将当前位之前的所有高位都存在high中 long cur = (n/i)%10;//将当前位记录在cur中，即我们每次都需要统计当前位上1出现的次数 long low = n-(n/i)*i; if(cur == 0){             count += high * i; } else if(cur == 1){             count += high * i + low + 1; } else {             count += (high+1) * i; }         i = i * 10;//准备遍历下一位 } return count; }