Leetcode 233. 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.

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

题目分析

1、我们将每个数以位数进行分类，首先计算每一位可以出现多少个一，（一个三位数，我们先计算个位上1出现的次数，然后计算十位上1出现的次数，最后计算百位上1出现的次数）然后进行累加，得到小于n的数出现1的次数之和。

2、将某位上的数字按大小不同进行分类，分析出不同的计算方法。

例子:

以算百位上1为例子:   假设百位上是0, 1, 和 >=2 三种情况: 

    case 1: n=3141092, a= 31410, b=92. 计算百位上1的个数应该为 3141 *100 次.

    case 2: n=3141192, a= 31411, b=92. 计算百位上1的个数应该为 3141 *100 + (92+1) 次. 

    case 3: n=3141592, a= 31415, b=92. 计算百位上1的个数应该为 (3141+1) *100 次. 

以上三种情况可以用 一个公式概括:

(a + 8) / 10 * m + (a % 10 == 1) * (b + 1);

class Solution {
public:
    int countDigitOne(int n) {
        vector<int> nFamily;  
        vector<int> digits;
        int sum = 0;
        while(n/10){
            int temp = n%10;
            digits.push_back(temp);
            n = n/10;
            nFamily.push_back(n);
        }
        digits.push_back(n);
        nFamily.push_back(0);
        for(int i = 0;i<digits.size();i++){
            if(digits[i]==0){
                int addZero = 1;
                for(int j = i-1;j>=0;j--){
                    addZero = addZero*10;
                }
                sum+=nFamily[i]*addZero;
            }
            if(digits[i]==1){
                int addNum = 0;
                int addZero = 1;
                for(int j = i-1;j >= 0;j--){
                    addNum = addNum*10 + digits[j]; 
                    addZero = addZero*10;
                }
                sum+=nFamily[i]*addZero+(addNum+1);
            }
            if(digits[i]>1){
                 int addZero =1;
                 for(int j = i-1;j>=0;j--){
                    addZero = addZero*10;
                }
                sum+=(nFamily[i]+1)*addZero;
            }
        }
        return sum;
    }
};