[编程题] 128.统计 1 到 400 亿之间的自然数中含有多少个 1？比如 1-12 中，1，10，11，12 有 5 个 1

[qiilee]

答案：

归纳法

归纳法，对于个位出现的1：(n / 10) * 1 + (n % 10) >= 1 ? 1 : 0; 对于十位出现的1：(n / 100) * 10 + if (k > 19) 10 else if (k < 10) 0 else k - 10 + 1; 对于百位出现的1：(n / 1000) * 100 + if (k > 199) 10 else if (k < 100) 0 else k - 100 + 1; 最终归纳出: (n / (i * 10)) * i + if (k > 2 * i - 1) i else if (k < i) 0 else k - i + 1, 其中k = n % (i * 10);

代码：

var countDigitOne = function(n) {
    let count = 0;

    for (let i = 1; i <= n; i *= 10) {
        let divide = i * 10;
        let p = Math.floor(n / divide), k = n % divide, rest = 0;

        count += p * i;
        rest = (k > (2 * i - 1)) ? i : ((k < i) ? 0 : k - i + 1);
        count += rest;
    }
    return count;
};
countDigitOne(40000000000)

[Allihol]

朋友，1~21中，1，10，11，12，13，14，15，16，17，18，19，21，这些数字带有1，其中11有两个。所以总数为13.不是5.

function fn(位数) {
        if (位数 == 1) {
          // 个位数中只有1个'1'
          return 1;
        } else {
          // 此外2，3，4位数都包含1开头的10^n-1个数，和9*上一位中含1的数量。
          return Math.pow(10, 位数 - 1) + 9 * fn(位数 - 1);
        }
      }
      //   测试：数一数发现2位数0~99中有10~19 这10个1，其中11有两个1，加上21~91的8个，共19个
      // 三位数0~999中有271个1。
      console.log(fn(2));
      console.log(fn(3));
      console.log(fn(11) - fn(10) * 6);
      //   400亿是11位数，但没有包括11位数的全部数字。所以先计算11位数中所有的1，再减去6份不需要的10位数中的1。

[qiilee]

@Allihol 谢谢指出问题，已更新。

[qiilee]

也可参考

var countDigitOne = function(n) {
	let ret = 0;
	let base = 1;

	while (Math.floor(n / base) > 0) {
		let low = Math.floor(n / base) % 10;

		if (low == 0) {
			ret += Math.floor(n / (base * 10)) * base;
		} else if (low == 1) {
			ret += Math.floor(n / (base * 10)) * base + 1 + n % base;
		} else {
			ret += (Math.floor(n / (base * 10)) + 1) * base;
		}

		base = base * 10;
	}
	return ret;
};
countDigitOne(40000000000)