# 题目

求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数?

为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。

ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数(从1n1出现的次数)。

# 思路

注意:11算出现了两个1

分别计算数字中每个位置可能出现1的情况,相加。

将数字分为两部分: 当前数字为1,其后面数字可能出现的情况low,当前数字为1,其前面数字可能出现的情况high,所有情况为low * high种情况。

例如,在分析数字8103时:

  • 个位 3: 个位已经是最低位了,所以low只有1中情况。high可以取0 - 810811种情况,所有情况为1 * 811 = 811种情况。

  • 十位 0: low可能为10 - 1910种情况,high可以取0 - 8081种情况,所有情况为81 * 10 = 810种情况。

  • 百位 1: low可能为100 - 199100种情况,high可以取0 - 78种情况;当high8时,low还可以取100 - 104,所有情况为100 * 8 + 4 = 804种情况。

  • 千位 8:low可能为1000 - 19991000种情况,当前已经是最高位了,high只有一种情况,所有情况为1000 * 1 = 1000种情况。

foo

由以上示例:分三种情况考虑,现有数字abcde,分析百位数字c

  • c = 0 : 有 ab*100 种情况
  • c = 1 : 有 ab*100 + de + 1 种情况
  • c > 2 : 有 (ab+1) * 100 种情况

cabcde3位数:

当前的量级:level = 10(3-1)次方

  • ab = abcde / (level*10)
  • c = (abcde / (level)) % 10
  • de = abcde % level

# 代码

    function NumberOf1Between1AndN_Solution(n) {
      let count = 0;
      let i = 1;
      let high = low = current = level = 0;
      let length = n.toString().length;
      while (i <= length) {
        level = Math.pow(10, i - 1); //第i位数位于什么量级 1 10 100 ...
        high = parseInt(n / (level * 10));
        low = n % level;
        current = parseInt(n / level) % 10;
        if (current === 0) {
          count += (high * level);
        } else if (current === 1) {
          count += (high * level + low + 1);
        } else {
          count += ((high + 1) * level);
        }
        i++;
      }
      return count;
    }
ON THIS PAGE