整数中1出现的次数（从1到n整数中1出现的次数）

题目描述

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

---

思路

1. 设n=abcde，自右至左，从1开始标号。
2. 如果第i位上的数字为0，则第i位可能出现1的次数由其高位决定，若没有高位，则视为0，此时第i位可能出现1的次数为：其高位数*10^{(i-1)，例如若c为0，则次数为ab*10}2;
3. 如果第i位上的数字为1，则第i位上可能出现1的次数受其高位和低位影响，若没有，则视为0，此时第i位可能出现1的次数：其高位数*10^{(i-1)+（低位数+1），例如若c为1，则次数为ab*10}2+（de+1）;
4. 如果第i位上的数字大于1，则第i位上可能出现1的次数受其高位影响，若没有，则视为0，此时第i位可能出现1的次数：（其高位数+1）*10^{(i-1)，例如若c大于1，则次数为（ab+1）*10}2;

实现代码

function NumberOf1Between1AndN_Solution(n) {

    if (n < 0) return 0;

    var high, low, cur, temp, i = 1;

    high = n;

    var count = 0;

    while (high !== 0) {

        high = parseInt(n / Math.pow(10, i)); // 第i位数的高位

        temp = n % Math.pow(10, i);

        cur = parseInt(temp / Math.pow(10, i - 1)); // 第i位数

        low = temp % Math.pow(10, i - 1); // 第i位数的低位

        if (cur === 1) {

            count += high * Math.pow(10, i - 1) + low + 1;

        } else if (cur < 1) {

            count += high * Math.pow(10, i - 1);

        } else {

            console.log(count, high);

            count += (high + 1) * Math.pow(10, i - 1);

        }

        i++;

    }

    return count;

}