leetcode 233. Number of Digit One

233. Number of Digit One

Total Accepted: 20083 Total Submissions: 79485 Difficulty: Hard

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

For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

思路：累加各个数位为1时的情况总数。注意int的最大值：4294967296

对于特定的数n，设1出现的总次数为ones。从右向左的第i位（个位第1位）n_i有

(1) n_i==0,ones+=n/10ⁱ⁺¹*10ⁱ;

(2) n_i==1,ones+=n/10ⁱ⁺¹*10ⁱ+n%10ⁱ+1;

(3) n_i>1,ones+=(n/10ⁱ⁺¹+1)*10ⁱ;

代码：

基本的代码应该这样：

 1 class Solution {
 2 public:
 3     int countDigitOne(int n) {
 4         int a,b;
 5         long long ones=0;
 6         for(long long m=1;m<=n;m*=10){
 7             a=n/m;
 8             b=n%m;
 9             if(a%10==0){
10                 ones+=a/10*m;
11                 continue;
12             }
13             if(a%10==1){
14                 ones+=a/10*m+(b+1);
15                 continue;
16             }
17             ones+=(a/10+1)*m;
18         }
19         return ones;
20     }
21 };

下面用了一个技巧：ones+=(a+8)/10*m+(a%10==1)*(b+1)

 1 /*
 2 为什么m的类型为long long：因为m在最后1个循环后可能会超出int的范围。
 3 例如n=1410065408，如果m的类型是int，那么m=1000000000后，经过m*=10后，m溢出，m会仍然满足条件m<=n而继续循环。但这是不对的。所以m的类型要是long long。
 4 */
 5 class Solution {
 6 public:
 7     int countDigitOne(int n) {
 8         int a,b;
 9         long long ones=0;//显然，1的总和值可能会超过int的范围
10         for(long long m=1;m<=n;m*=10){
11             a=n/m;
12             b=n%m;
13             ones+=(a+8)/10*m+(a%10==1)*(b+1);
14         }
15         return ones;
16     }
17 };