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.

注意溢出的情况

class Solution {
public:
    int countDigitOne(int n) {
        if(n <= 0)  return 0;
        char str[50];
        sprintf(str, "%d", n);
        return count1(str);
    }
private:
    int count1(char *s){
        if(s == NULL || *s == '\0') return 0;

        int first = *s - '0';
        unsigned int length = static_cast<unsigned int>(strlen(s));

        if(length == 1 && first == 0)
            return 0;

        if(length == 1 && first > 0)
            return 1;

        //num1代表了最高位上是1的数，这些数上总共有num1个高位为1   
        int num1 = 0;
        if(first > 1)   num1 = pow(10, length - 1);
        else if(first == 1) num1 = atoi(s + 1) +1;

        int num2 = first * (length - 1)*pow(10, length - 2);

        int num3 = count1(s + 1);

        return num1 + num2 + num3;
    }
};