题目描述：
求出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;
}
大佬的代码是写的真的很简洁，继续加油！
