求出1-13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1-13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。

解法一：暴力破解

public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        int ans=0;
        int i=1;
        while(i<=n){
            int j=i;
            while(j!=0){
                if(j%10==1) ans++;
                j/=10;
            }
            i++;
        }
        return ans;
    }
}

解法二：数位数

非原创， thanks to

• https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/solution/mian-shi-ti-43-1n-zheng-shu-zhong-1-chu-xian-de-2/
• https://leetcode-cn.com/problems/number-of-digit-one/solution/shu-zi-1-de-ge-shu-by-leetcode/

public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        int digit=1;
        int low=0;
        int curr=n%10;
        int high=n/10;
        int ans=0;
        while(high!=0||curr!=0){
            if(curr<1){
                ans+=high*digit;
            }else if(curr==1){
                ans+=high*digit+low+1;
            }else{
                ans+=(high+1)*digit;
            }
            low+=curr*digit;
            curr=high%10;
            high/=10;
            digit*=10;
        }
        return ans;
    }
}

注意第8行的循环退出条件，不能修改成digit<=n。
否则针对比较大的n，digit会溢出。
所以以下这个代码（digit对应这里的m）

class Solution {
    public int countDigitOne(int n) {
        int cnt = 0;
        for (int m = 1; m <= n; m *= 10) {
            int a = n / m, b = n % m;
            cnt += (a + 8) / 10 * m + (a % 10 == 1 ? b + 1 : 0);
            System.out.println(m);
        }
        return cnt;
    }
}

如果我们打印一下m，就会得到

1
10
100
1000
10000
100000
1000000
10000000
100000000
1000000000
1410065408
1215752192
-727379968
1316134912
276447232
-1530494976

你看，溢出了。
所以，循环条件不能设置成digit<=n。