Question

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

思路：将一个数字中1出现的次数拆成个、十、百位中1出现次数的和以321为例：

• cnt = 32 + 1，把321拆成高位32和1，固定个位是1，高位的取值可以是0~31共32个数，由于低位为1大于0，所以高位还可以取32（即数字321），则个位上1出现的次数是32+1=33
• cnt = 30 + 10，把321拆成高位3和21，固定十位是1，高位可以取 0 ~ 2 共30个数，由于低位是21-10+1大于0，所以高位还可以取3（即数字310~319），则十位上1出现的次数是30 + 10 = 40
• cnt = 0 + 100，把321拆成高位0和321，固定百位是1，高位可以取 0 个数，由于低位是321-100+1大于0，所以可以取数字100~199），则百位上1出现的次数是0 + 100 = 100

所以321中1出现的次数是173

public class Solution {
  public int NumberOf1Between1AndN_Solution(int n) {
    int cnt = 0, i = 1;
    while(i<=n){
      cnt += n / (i * 10) * i + Math.min(Math.max(n % (i * 10) - i + 1, 0), i);
      i *= 10;
    }
    return cnt;
  }
}