LeetCode-Number of Digit One（编程之美-1的数目）

ゝ一纸荒年。 2022-08-04 13:39 199阅读 0赞

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.

题不难但是很难分析，首先我们想到的就是分解问题，找规律，把大问题小问题化，然后在编程解决。

很明显这里有一个比较好想的办法就是从1~n遍历，每次都去判断每个i中1的个数，显然比较慢。

肯定有别的办法，就是在给定n的时候直接分析。这个时候分析问题就可以从n=1开始尝试，用归纳法，找出什么规律出来。

很显然，我们可以按照位一个一个找，即在个位、十位、百位。。。出现过的1。

现在直接给出N的一般规律，比如N=abced五位数字的时候，我们分析百位c，有三种情况：

1）c == 0的时候，比如12013，此时百位出现1的是：00 100 ~ 00 199， 01 100~01 199，……，11 100~ 11 199，共1200个，显然这个有高位数字决定，并且受当前位数影响；

2）c == 1的时候，比如12113，此时百位出现1的肯定包括c=0的情况，另外还需要考虑低位的情况即：00100 ~ 00113共114个，

3）c >= 2的时候，比如12213，此时百位出现1的是：00 100 ~ 00 199， 01 100~01 199，……，11 100~ 11 199，12 100 ~ 12 199，共1300个，这个有高位数字决定，其实是加一，并且乘以当前位数

所以就可以写出如下代码：

public int countDigitOne(int n) {
            long count = 0;
            long factor = 1;
            
            while (n / factor != 0) {
                long lower = n % factor;
                long cur = (n / factor) % 10;
                long higher = n / (factor * 10);
                
                if (cur < 2) {
                    count += higher * factor;
                    if (cur == 1) count += lower+1;
                } else {
                    count += (higher+1) * factor;
                }
                factor *= 10;
            }
            return (int) count;
        }

分析这种问题确实比较费劲！