【算法专栏】整数中1出现的次数

题目

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

思路

以数字8103为例，分别分析每个位置为1的情况(target)

将数字拆分成 pre-target 考虑

• 个位 3: target为1 可能有 0-1 1-1 ... 810-1 共811种情况
• 十位 0: target为10-19 可能有 0-(10-19) 1-(10-19) ... 80-(10-19) 共81*10=810种情况
• 百位 1: target为100-199 可能有 0-(100-199) 1-(100-199) ... 7-(100-199) + 8-(100-103) = 8*100+4 = 804种情况
• 千为 8: target为1000-1999 可能有 0-(1000-1999) = 1000种情况

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

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

c是abcde第3位数：

当前的量级：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 % Math.pow(10, i - 1);        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;    }