233. 数字 1 的个数

给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。

示例:

输入: 13
输出: 6
解释: 数字 1 出现在以下数字中: 1, 10, 11, 12, 13 。

本题没有用到什么算法，需要挖掘数字的信息。
我的思路是一开始先把位数统计出来，然后从高位开始统计，那么就可以直接得到最高位为1的时候能取多少个数字，取决于是否等于1。
我们来举个例子
1245 和2245两个数字，最高位是千位，前一个数字千位可以取246个从1000-1245,而后一个可以取1000个，从1000-1999，无论最高位是2，是3都是1000个。但是如何求解之后位的数字，就是个问题了，我开始挖掘数字的信息。

如果一个数 xxxdyyy，d是千位，我们如何求千位 1出现的次数呢？
我们来举个例子 345 d 567 这个数字，d是个未确定的数字，我们来求它这一位 1出现的次数。
我们可以发现 345d657这个数字一定比344以及小于344开头的数字大。（后面不变）
那3441000 - 3441999 都是符合答案的，同理还有3331000-3331999，等等，这里一共有1000个，可以取345次，包括0，因为1000也是满足答案的。我们可以发现这个例子就是我之前的思路，那是不是就结束了呢，显然不是，我们只考虑了高位，我们还没有考虑低位，例如3451000 - 3451999这里的数字我们还没考虑，那应该如何考虑呢，显然和d的取值有关系：
如果d是0，那么就显然不满足这个范围。
如果d是1，那低位有多少个，答案就还要加上这个数再加一，比如这个例子当中，3451657，我们可以取3451000-3451657，一共是657+1个。
那如果d>0，显然可以取1000个。

因此我们只需要迭代每一位即可求出答案了！
虽然本题没有用到算法，但是我个人认为难度还是很大的，需要逐一讨论，另外代码中要考虑溢出问题。
代码如下:

class Solution {
    public int countDigitOne(int n) {
        
        long count = 0;
        for (long k = 1; k <= n; k = k * 10){
            
            long t = n / k;
            long higher = t / 10;
            long lower = n % k;
            long digit = t % 10;

            if (digit == 0){
                count += higher * k;
            }
            if (digit == 1){
                count += higher * k + lower + 1;
            }
            if (digit > 1){
                count += higher * k + k;
            } 

        }
        return (int)count;

    }
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-digit-one
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。