整数中1出现的次数（java）

题目描述：

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

分析：

看到题目，首先想到的就是：遍历1到n，把每个整数转为为string，然后转化做char[],判断每一位上的1的个数。

解答：

public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
     if(n<=0) return 0;
        int sum  =0;
        for(int i=1;i<=n;i++) {
            char[] cs = String.valueOf(i).toCharArray();
            for (char c : cs) {
                if (c - '1' == 0) {
                    sum++;
                }
            }
        }
        return sum;
    }
}

运行成功

改进：

如上做法其实感觉有点蠢。因为用到了额外的数组空间来保存每个数字的字符数组，后来看到可以直接用数字除十来求值和取余即可。

public int NumberOf1Between1AndN_Solution(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);
    }
    return cnt;
}

大佬的代码是写的真的很简洁，继续加油！