Count Digit One

Posted on | In , |

题目

https://leetcode.com/problems/number-of-digit-one/description/

-w956

想法

这道题的解法有多种，看discussion就会知道花样百出。

一开始想的是，9，99，999…之间的递推关系，但是，这并不好表示一个不整的数，discussion中也有类似的解答，但是一下子也没有看明白。

换了思路之后，参考了 https://leetcode.com/problems/number-of-digit-one/discuss/64382/JavaPython-one-pass-solution-easy-to-understand 这个解法。

计算在某一位1出现的次数，累加起来

而某一位出现1的次数分为3中情况：

对于数AxB，其中A表示x之前的数，B表示x之后的数，例如123456，x为4的话，A = 123，B = 56.
以下假设B有2位：

三种情况

  1. x == 0: A 100
    先看前半部分：Ax，如果递减此数，那么，A每减1，x都会出现0-9中的数，那么也就是说，A减到0，减了A次，x处就出现了A次1.
    然后看后半部分，因为高位减下来的，低位肯定会有00-99，也就是100个，组合以下，就是A    100了
  2. x > 1: A * 100 + 100
    按照上边的情况，还多了不用减A部分，直接减x到1，又有100
  3. x == 1: A * 100 + B + 1
    这种情况比较复杂，除了第一种情况之外，还有当Ax不变的时候，可能的情况。此时，低位可以从0数到B，总共B+1次，所以加上B+1

边界条件

如果x是最低位：
对应的乘的系数是1，B为0，符合条件

如果x为最高位：
A为0，三种情况都符合

实现

实现的代码还是很精巧的，如何计算A和B，都有很好的处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int countDigitOne(int n) {
        if (n == 0)
            return 0;
        int res = 0;
        int x = 1;
        int origin = n;
        do {
            int r = n % 10;
            n /= 10;
            res += n * x;
            if (r == 1) {
                res += origin % x + 1;
            } else if (r > 1) {
                res += x;
            }
            x *= 10;
        } while (n > 0);
        return res;
    }
};