[leetcode] Number of Digit One

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

Example:

Input: 13
Output: 6 
Explanation: Digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

分析：要求找1.....n这么多个数字种，1出现的次数。

第一个想法肯定是计算每个数字中1出现的次数，然后求和。最笨的方法，这里计算1出现的次数有个小技巧就是用<<操作。肯定是不行的啦，想都不要想了。

第二个想法，将整数变成字符串，然后求这个长的字符串中1出现的次数。好像能快一点：

 1     public int countDigitOne(int n) {
 2         StringBuffer s = new StringBuffer("");
 3         for ( int i = 1 ; i <= n ; i ++ ){
 4             s.append(""+i);
 5         }
 6         int count = 0;
 7         for ( int i = 0 ; i < s.length() ; i ++ ){
 8             if ( s.charAt(i) == '1' ) count ++;
 9         }
10         return count;
11     }

这里用StringBuffer可以降低内存操作时间，提高效率。不过还是不行，倒数第5个就超时了。

隆重介绍：找规律法。。。。

解题思路

考虑将n的十进制的每一位单独拿出讨论，每一位的值记为weight。

1) 个位

从1到n，每增加1，weight就会加1，当weight加到9时，再加1又会回到0重新开始。那么weight从0-9的这种周期会出现多少次呢？这取决于n的高位是多少，看图：

以534为例，在从1增长到n的过程中，534的个位从0-9变化了53次，记为round。每一轮变化中，1在个位出现一次，所以一共出现了53次。
再来看weight的值。weight为4，大于0，说明第54轮变化是从0-4，1又出现了1次。我们记1出现的次数为count，所以：

count = round+1 = 53 + 1 = 54

如果此时weight为0（n=530），说明第54轮到0就停止了，那么：

count = round = 53

2) 十位

对于10位来说，其0-9周期的出现次数与个位的统计方式是相同的，见图：

不同点在于：从1到n，每增加10，十位的weight才会增加1，所以，一轮0-9周期内，1会出现10次。即rount*10。
再来看weight的值。当此时weight为3，大于1，说明第6轮出现了10次1，则：

count = round*10+10 = 5*10+10 = 60

如果此时weight的值等于0（n=504），说明第6轮到0就停止了，所以：

count = round*10+10 = 5*10 = 50

如果此时weight的值等于1（n=514），那么第6轮中1出现了多少次呢？很明显，这与个位数的值有关，个位数为k，第6轮中1就出现了k+1次(0-k)。我们记个位数为former，则：

count = round*10+former +1= 5*10+4 = 55

3) 更高位

更高位的计算方式其实与十位是一致的，不再阐述。

4) 总结

将n的各个位分为两类：个位与其它位。
对个位来说：

若个位大于0，1出现的次数为round*1+1
若个位等于0，1出现的次数为round*1

对其它位来说，记每一位的权值为base，位值为weight，该位之前的数是former，举例如图：

则：

若weight为0，则1出现次数为round*base
若weight为1，则1出现次数为round*base+former+1
若weight大于1，则1出现次数为rount*base+base

比如：

534 = （个位1出现次数）+（十位1出现次数）+（百位1出现次数）=（53*1+1）+（5*10+10）+（0*100+100）= 214
530 = （53*1）+（5*10+10）+（0*100+100） = 213
504 = （50*1+1）+（5*10）+（0*100+100） = 201
514 = （51*1+1）+（5*10+4+1）+（0*100+100） = 207
10 = (1*1)+(0*10+0+1) = 2

参考：https://blog.csdn.net/yi_afly/article/details/52012593

在这里我总结了一下不需用分个位十位。直接统一看就好了。

 1 class Solution {
 2     public int countDigitOne(int n) {
 3         int round = n;
 4         int count = 0;
 5         int base = 1;
 6         while ( round > 0 ){
 7             int cur = round % 10;
 8             round = round / 10;
 9             count += round * base;
10             if ( cur == 1 ) count += ( n % base ) + 1;
11             else if ( cur > 1 ) count += base;
12             base *= 10;
13         }
14         return count;
15     }
16 }

运行时间0ms。