题目

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

方法

参考：https://blog.csdn.net/yi_afly/article/details/52012593
时间复杂度：O(logn) 以10为底

思路

从个位、十位、百位一一分析1出现的次数

个位：拿到一个数n。从1~n中，数字1出现的次数，在个位上，就是1，11，21等等 —— 这边只讨论个位。就相当于每10个数，个位会出现1次1，那么就可以通过判断1~n有多少个10，来计算个位会出现几次1。
以534为例：534有53个10，和4。53个10，相当于个位轮换53次，每轮换一次，个位就会出现一次1。加上531，
所以count = 53 + 1 = 54 。如果n为530，就只有53次了。所以个位本身，还需要做判断是否小于1

十位：其实和个位类似，十位出现1的次数，也可以用十位数轮换次数来计算。区别在于，当1~n过程中，十位一旦为1，会有连续10个数，十位为1，比如110~119。与个位不同，个位出现1，下一个数个位就不是1了。那么我们计算出十位轮换次数后，就需要乘以10，这是的10就是十位的权重，才能得出十位出现1的次数。十位轮换的次数，就从百位或者更高位去计算。
以534为例，十位轮换的次数就是5次。所以是5 * 10 = 50次。仍然要对十位本身进行判断。因为，通过十位的轮换次数，只考虑了1~, 11~, 21~, 31~, 41~的情况，百位为5开头，实际上还未考虑，需要判断十位本身是否会轮换到1来判断。这里534，3大于0，会轮换到1，所以还需要加上510~519的十次十位上的1。
所以count = 5 * 10 + 10 = 60 次

百位和更高位置以此类推，只不过权重变为100，1000等，每增加一位，×10

具体方法

那么具体到某个位，其实计算1出现的次数都一样。可以用下面方法计算，借助图来表示

权重记为weight，该位的轮换次数记为round，当前数字是current
所以该位出现1的次数为：
若current为0：count = round * weight
若currnet为1：count = round * weight + former + 1
若current大于1：count = round * weight + weight

代码

function NumberOf1Between1AndN_Solution(n) {
  // write code here
  let weight = 1
  let number = n
  let count = 0
  while (number) {
    let current = number % 10
    let round = Math.floor(number / 10)
    if (current === 0) {
      count += round * weight
    } else if (current === 1) {
      count += round * weight + n % weight + 1
    } else {
      count += round * weight + weight
    }
    number = round
    weight *= 10
  }
  return count
}