题目描述

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

思路

  • 分位计算
  • 按高中低位计算
  • 已121为例，
  • 假设当前位为个位，则高位12，中位1，低位0，
  • 当个位为0时，那么个位为1的个数就是，高位（12）*当前位数（1）
  • 当个位为1时，那么个位为1的个数就是，高位（12）*当前位数（1）+低位（0）+1
  • 当个位为大于1时，那么个位为1的个数就是，高位（12+1）*当前位数（1）
  • 当前位为十位，则高位1，中位2，低位1，
  • 当十位为0时，那么十位为1的个数就是，高位（1）*当前位数（10）
  • 当十位为1时，那么十位为1的个数就是，高位（1）*当前位数（10）+低位（1）+1
  • 当十位为大于1时，那么十位为1的个数就是，高位（1+1）*当前位数（10）
  • 当前位为百位，则高位0，中位1，低位21，
  • 当百位为0时，那么百位为1的个数就是，高位（0）*当前位数（100）
  • 当百位为1时，那么百位为1的个数就是，高位（0）*当前位数（100）+低位（21）+1
  • 当百位为大于1时，那么百位为1的个数就是，高位（0+1）*当前位数（100）
  • 由分析可知，大于1时，需即为所以+8位节点

    Java 1.8

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        int count = 0;
        for (int i = 1; i <= n; i*=10) {
            int a = n/i;
            int b = n%i;
            int c = (a+8)/10*i;
            int d = ((a%10==1)?(b + 1):0);
            count = count + c + d;
        }
        return count;
    }
}