首页 > 代码库 > 233. Number of Digit One *HARD* -- 从1到n的整数中数字1出现的次数

233. Number of Digit One *HARD* -- 从1到n的整数中数字1出现的次数

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.

Hint:

  1. Beware of overflow.
class Solution {public:    int countDigitOne(int n) {        if(n <= 0)            return 0;        vector<int> v;        int t = n;        while(t)        {            v.push_back(t%10);            t /= 10;        }        int l = v.size(), rest = n - v[l-1] * pow(10, l-1);        return (v[l-1] > 1 ? pow(10, l-1) : rest + 1) + v[l-1] * (l-1) * pow(10, l-2) + countDigitOne(rest);    }};

 

233. Number of Digit One *HARD* -- 从1到n的整数中数字1出现的次数