Leetcode 233. 数字 1 的个数

Posted on In ,

Question

## Answer 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int countDigitOne(int n) {
        if (n<=9)
            return int(n>=1);
        else
        {
            int len=log10(double(n));
            int high=floor(n/pow(10,len));
            int res=n-high*pow(10,len);
            return (pow(10,len-1)*len*high+(high==1?res+1:pow(10,len))+countDigitOne(res));
        }
    }
};

对于n，将其分为首位high和剩余部分res len为除首位以外剩余部分长度 答案所要的1的个数分为3个部分 0-999...9共len个9 中的1 个数为pow(10,len-1) * len * high 100...0—n 部分首位1 的个数(high==1?res+1:pow(10,len)) 100...0—n 部分其他位1 的个数 直接用递归

Complexity

  • time O(N)
  • space O(lg(N))