题目描述

求出 1-13 的整数中 1 出现的次数,并算出 100~1300 的整数中 1 出现的次数？为此他特别数了一下 1-13 中包含 1 的数字有 1、10、11、12、13 因此共出现 6 次,但是对于后面问题他就没辙了。ACMer 希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中 1 出现的次数（从 1 到 n 中 1 出现的次数）。 方法一：对于每个数来说求个位只需对 10 取余(%10)，然后将原数除以 10 取整，再对 10 取余拿到十位...依次类推

测试用例

用例1:

• 输入：n = 12
• 输出：5

用例2：

• 输入：n = 13
• 输出：6

代码实现

时间复杂度很高，个别用例无法通过，比如上亿的数 —— 824883294

var __readline = require("readline-sync");
__readline.setDefaultOptions({ prompt: "" });
var readline = __readline.prompt;

console.log("请输入n: ");
const n = parseInt(readline());

// 对于每个数来说求个位只需对 10 取余(%10)，
// 然后将原数除以 10 取整，再对 10 取余拿到十位...依次类推

// 枚举统计每一个数位含有1的个数，同时记录总数，最后返回总数即可
// 比如判断12，就计算1-12之间1,2,3,4 —— 12 每个数位中含有1的个数
function NumberOf1Between1AndN_Solution(n) {
  // write code here
  var count = 0;
  for (let i = n; i > 0; i--) {
    for (let j = i; j > 0; j = parseInt(j / 10)) {
      //对j/10取整
      if (j % 10 === 1) {
        count++;
      }
    }
  }
  return count;
}


const res = NumberOf1Between1AndN_Solution(n);
console.log("结果为: ", res);

/* 
  请输入n:
  111111
  结果为:  66672
*/


const res = NumberOf1Between1AndN_Solution(n);
console.log("结果为: ", res);