leetcode233.Number of Digit One

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
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.

计算所有小于等于n的正整数中数字1的个数。
比如比13小的正整数中包含1的有1,10,11,12,13，一共有6个1。

思路一：找规律

如果使用暴力循环的话，那么我们只需要遍历所有小于n的正整数，计算该正整数中包含几个1并将返回这些结果的和。但是，这种方法浪费了很多不必要的计算。比如在小于n的正整数中，有很多甚至都一个1都没有。因此，我们需要用更好的方法，减少这种方法的浪费。

我们随意找一个数来入手，假设现在n为52，那么52下含有的1实际上等于50~52 + 1~49中有的1，也就等价于0~2 + 1~49中含有的1。
在这里我们很清楚的知道，当n<10时，只有1个1。因此0~2只有1个1。

我们再来拆解1~49。
1~49其实等价于40~49 + 30~39 + 20~29 + 10~19 + 1~9中的1的个数。我们再分析一下就会发现，40~49, 30~39 , 20~29, 0~9中的1的个数是相同的！而特殊的情况是10~19，它的1的数量其实等于10 + 0~9。

总结一下我们知道countDigitOne(52) = countDigitOne(2) + countDigitOne(9) * 5 + 10。

这里其实还有一个特殊情况，就是当最高位恰好为1的时候，举个例子135。那么100~135等价于36+0~35个1，那么countDigitOne(135) = 36 + countDigitOne(35) + countDigitOne(99)。

整理为代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
public int countDigitOne(int n) {
    if(n <= 0) return 0;
    if(n < 10) return 1;
    int count = 1;
    while(n / count > 9){
        count *= 10;
    }
    if(n / count == 1){
        return n % count + 1 + countDigitOne(n%count) + countDigitOne(count-1);
    }else{
        return countDigitOne(n % count) + count + (n/count) * countDigitOne(count-1);
    }
}