第 121 题：统计 1 ~ n 整数中出现 1 的次数

Question

统计 1 ~ n 整数中出现 1 的次数，例如统计 1 ~ 400W 出现 1 的次数。

Answer 1

function counts(num) {
let count = 0;
for (let i = 0; i<=4000000; i++) { //遍历1到 4000000的所有整数
let str = i + ""; //数字转成字符串
while(str.indexOf(num) != -1) {
count++;
str = str.substring(str.indexOf(num) + 1);
}
}
return count;
}
console.log(counts(1))

Answer 2

function countNum(n, count = 0) {
for (let i = 0; i <= n; i++) {
if ((i + '').indexOf('1') > -1) {
count++;
continue;
}
}
return count;
}

直接输出吧 鄙人才疏学浅 望各位指点

Answer 3

function countNum(n, count = 0) {
    for (let i = 0; i <= n; i++) {
        var pos;
        var arr = [];
        pos = i.toString().indexOf('1');//先判断有没有1
        while (pos > -1) {
            arr.push(pos);
            pos = i.toString().indexOf('1', pos + 1);
        }
        count += arr.length;//再判断1出现的次数
    }
  return count;
}
countNum(11);

Answer 4

/**

• @param {number} n
• @return {number}
  */
  var countDigitOne = function(n) {
  if(n <= 0)
  return 0;
  if(n < 10)
  return 1;
  let current = n, i = 1, total = 0;
  while(current){
  if(current%10 === 0)
  total += Math.floor(current/10)*i;
  if(current%10 === 1)
  total += Math.floor(current/10)*i+(n%i)+1;
  //在[1-10],统计为2
  if(current%10>1)
  total += Math.ceil(current/10.0)i;
  //除10，移动到下一个高位的数字
  current=Math.floor(current/10);
  //下一个要查看的数字的位数
  i=i10;
  }
  return total;
  };
  参考leetcode上面写的

Answer 5

先实现：

function count(n) {
  let res = 0;
  for (let i = 0; i <= n; i += 1) {
    `${i}`.split('').forEach(item => {
      if (item === '1') {
        res += 1;
      }
    })
  };
  return res;
}
console.time('count');
console.log(count(4000000));
console.timeEnd('count');
// 3400000
//count: 589.424ms

Answer 6

先实现：

function count(n) {
  let res = 0;
  for (let i = 0; i <= n; i += 1) {
    `${i}`.split('').forEach(item => {
      if (item === '1') {
        res += 1;
      }
    })
  };
  return res;
}
console.time('count');
console.log(count(4000000));
console.timeEnd('count');
// 3400000
//count: 589.424ms

楼上大佬的算法，性能优化了好多

function countOne(n) {
  var factor = 1;
  let count = 0;
  let next = parseInt(n / factor);
  while (next !== 0) {
      var lower = n - next * factor
      var curr = next % 10;
      var high = parseInt(n / (10 * factor));

      if (curr === 0) {
          count += high * factor;
      } else if (curr === 1) {
          count += high * factor + lower + 1
      } else {
          count += (high + 1) * factor
      }

      factor *= 10;
      next = parseInt(n / factor);
  }
  return count;
}
console.time('count');
console.log(countOne(4000000));
console.timeEnd('count');
// 3400000
// count: 2.363ms

Answer 7

先找规律

按递归的思路思考一个整数，比如n = 388，

我们可以把0-388划成四部分：

• 0 - 99
• 100 - 199
• 200 - 299
• 300 -388

对于前三个部分，如果我们省略最高位的话，那它们就是相同问题，可以归结为 howManyOnes(99) * 3；

对于最后一个部分，就是 howManyOnes(88)；

最后再考虑 100 - 199 这部分，因为388大于100，因此包含了所有最高位是1的100个整数；

因此，1的总数 = howManyOnes(99) * 3 + howManyOnes(88) + 100 = 179。

那么对于最高位不大于1的整数呢? 也很容易得到规律，比如n = 166：

我们可以把0-166划成两部分：

• 0 - 99
• 100 - 166

同样的，我们先考虑第一部分，即howManyOnes(99)；

然后再看第二部分，先拿到howManyOnes(66)，然后再统计100 - 166之间最高位是1的整数，是 66 + 1 个；

因此，1的总数 = howManyOnes(99) + howManyOnes(66) + 66 + 1 = 104。

代码实现

找到方法后代码实现就不难了：

function howManyOnes(n) {
    if (n < 1) {
        return 0
    }
    if (n < 10) {
        return 1
    }
    const str = String(n)
    const rest = Number(str.slice(1))
    const power = 10 ** (str.length - 1)
    const head = Number(str.slice(0, 1))
    if (head === 1) {
        return howManyOnes(rest) + howManyOnes(power - 1) + rest + 1
    } else {
        return howManyOnes(rest) + power + howManyOnes(power - 1) * head
    }
}

console.time('count');
console.log(howManyOnes(4000000));
console.timeEnd('count');
// count: 0.298095703125ms

Answer 8

//  统计 1 的次数

// 忽略掉1这一个数的话，每一个位（bit）上出现1的数目为
//          个  十  ...   最后把1这个数补上，即 + 1
// 66       6 + 10 + 1
// 76       7 + 10 + 1
// 666      66 + 10 * (6 + 1) + 100 + 1
// 6666     666 + 10 * (66 + 1) + 100 * (6 + 1) + 1000 + 1
// 7777     777 + 10 * (77 + 1) + 100 * (7 + 1) + 1000 + 1
// 22232    2223 + 10 * (222 + 1) + 100 * (22 + 1) + 1000 * (2 + 1) + 10000 + 1

// 其实就是简单概括起来就是 (n / bit) * (n % bit + 1)

// 此时某一位bit出现小于或等于1的数需要特殊处理
// 如果是0:  则需把 n / bit取下限并减1。
// 如果是1:  则在0的基础上加上该bit所在后面的余数，比如说114，百位的数字是1，这时候，百位存在的就不会加上100，而是加上它取余100的结果再+1，即14 + 1
// 20002    2000 + 10 * (199 + 1) + 100 * (19 + 1) + 1000 * (1 + 1) + 10000 + 1
// 20202    2020 + 10 * (201 + 1) + 100 * (20 + 1) + 1000 * (1 + 1) + 10000 + 1
// 20212    2021 + (10 * (201 + 1) + 3) + 100 * (20 + 1) + 1000 * (1 + 1) + 10000 + 1

// 10101    1010 + 10 * (100 + 1) + (100 * (9 + 1) + 2) + 1000 * (0 + 1) + (101 + 1) + 1
// 10314    1031 + (10 * (102 + 1) + 4 + 1) + 100 * (10 + 1) + 1000 * (0 + 1) + (314 + 1) + 1
const oneNums = n => {

    let multiple = 1,
        count = 10,
        res = 0;
    
    while(n >= multiple) {

        let bitVal = Math.floor(n / multiple) % 10;

        if(bitVal > 1) {
            res += (Math.floor(n / count) + 1) * multiple;
        }
        //  bitVal小于1时特殊处理
        else{
            if(bitVal === 0){
                res += Math.floor(n / count) * multiple;
            }else{
                res += Math.floor(n / count) * multiple + n % multiple + 1;
            }
        }
        multiple *= 10;
        count *= 10;
    }

    return res;
}

Answer 9

这个跟之前自己写过的一道统计0的次数是一样的。

//  2019-07-03：统计从 1、2、3...一直到 n，这个过程中所有出现 0 的总数。
//  比如说 n 的值为 11，此时从 1、2...到 11这列数只有 10 有一个 0，故而 0 的总数为 1个。注意 100 是 2个零， 1000 是 3 个零

const zeroNums = n => {

    let res = 0;

    while( n > 0) {

        res += Math.floor( n / 10 );
        n /= 10;
    }
    return res;
}
return zeroNums(101);

Answer 10

function countNum(n, count = 0) {
for (let i = 0; i <= n; i++) {
if ((i + '').indexOf('1') > -1) {
count++;
continue;
}
}
return count;
}

直接输出吧 鄙人才疏学浅 望各位指点

你应该没有测试过的吧

• ①不是 (i + '').indexOf('1') 是 (n[i] + '').indexOf('1')
• ②不是 i <= n 而是 i < n.length
• ③题目是查询有多少个，不是查询有没有出现过。一个数可能出现几个1

Answer 11

function countOne(n) {
	let str = JSON.stringify(n);
	return str.match(eval("/1/ig")).length;
}
console.log(countOne([1,111,11111,11110]))  // 13

Answer 12

先记录下自己的想法，再看大佬们的优化方法

function calculateOne(last) {
	let total = 0;
	for (let i = 0; i < last + 1; i++) {
		for (let temp of String(i)) {
			if (Number(temp) === 1) total += 1;
		}
	}
	return total;
}

Answer 13

才疏学浅，只能暴力了，哈哈
function add(n){
var sum = 0;
for(var i = 0; i <= n; i++){
var i = "" + i;
sum += i.split("1").length - 1;
}
return sum;
}
console.log(add(11));//4
console.log(add(40000));//26000

Answer 14

9=>1,99=>20,999=>300,9999=>4000,99999=>50000
根据这个规律写出来的代码：
function orgnum(num){
var str = num.toString();
var arr = str.split("");
var arrlen = arr.length;
var totle=0;
for(var i=0;i<arrlen;i++){
if(arr[i]==0){continue}
var x = arr[i]* Math.pow(10,arrlen-i-1);
prev(i);
totle+=maxnum(x);
}
console.log(totle);
function prev(n){
if(n==0){
return;
}
var shu=0;
for(var j=n;j>0;j--){
arr[j-1]==1&&shu++;
}
totle+=shux;
}
function maxnum(n){
var str=n.toString();
var len = str.length;
function num(leng){
//console.log(leng * Math.pow(10, leng-1));
return lengMath.pow(10,leng-1)
}
if(str[0]==1){
return num(len-1)+1;
}
return num(len)-num(len-1)*(10-str[0]) ;
}
}

Answer 15

把数字转成字符串，利用正则进行字符串匹配
传入 n，输出 1-n 之间出现 1 的次数

let foo = n => {
  let arr = Array.from(new Array(n + 1).keys())
  arr.splice(0,1)
  return JSON.stringify(arr).match(/1/g).length
}

foo(10)  // 2

Answer 16

function findOne(arr = Array.from({ length: 4000000 }, (v, i) => i + '')) { let num = 0; arr.forEach(element => { element.split('').forEach(item => { if (item === '1') { num += 1 } }) }); return num }

Answer 17

为啥都是暴力循环，这不都是算法题吗？
分析归纳一下，按照每一位上的数字来分析
比如55， 个位可能产生的 1 是 6个(1, 11, 21, 31, 41, 51, 注意这里11只计算的个位的1)， 十位5 可能产生的 1是 10个，(10 - 19， 这里的11只计算的十位的1)；

比如222， 个位 可能产生的 1 是 23个(1, 11, 21, ... 221, 只关注个位)， 十位2 可能产生的 1是 30个(10-19, 110-119, 210-219, 只关注十位), 百位2 产生的 1是100个(100 - 199， 只关注百位).

以此类推， 每一位数字可能产生的1的个数跟他的高位部分和低位部分相关：
其中0和1需要特殊处理，代码如下

function countOne(n) {
    var factor = 1;
    let count = 0;
    let next = parseInt(n / factor);
    while (next !== 0) {
        var lower = n - next * factor
        var curr = next % 10;
        var high = parseInt(n / (10 * factor));

        if (curr === 0) {
            count += high * factor;
        } else if (curr === 1) {
            count += high * factor + lower + 1
        } else {
            count += (high + 1) * factor
        }

        factor *= 10;
        next = parseInt(n / factor);
    }
    return count;
}

给大佬献出膝盖

发现这个逻辑可以用于计算1-9出现次数

function countOne(n, token = 1) {
    let factor = 1;
    let count = 0;
    let next = parseInt(n / factor);
    while (next !== 0) {
        var lower = n - next * factor;
        var curr = next % 10;
        var high = parseInt(n / (10 * factor));

        if (curr < token) {
            count += high * factor;
        } else if (curr === token) {
            count += high * factor + lower + 1
        } else {
            count += (high + 1) * factor
        }

        factor *= 10;
        next = parseInt(n / factor);
    }
    return count;
}

Answer 18

var num = [];
for (var i = 1; i<=20;i++) {
num.push(i);
}
var str = num.join('');
var num1 = str.match(/1/g);
console.log('num1 :', num1.length);

Answer 19

function sum (res) {
let ac = ''
for (let ab = 1; ab <= res; ab ++) {
ac+= ab;
}
console.log (ac.split('1').length - 1)
}
sum(400000)

Answer 20

剑指 Offer 的版本

以 21345 例，为了方便递归求解，将其分为两段

• 1 ~ 1345（使用递归求解）
• 1346 ~ 21345

约定如下变量代表其中一些值：

• first 最高位数值
• length 当前数转为字符串后的长度
• remain 除最高位外剩余数字字符串

---

1346 ~ 21345 段计数过程

1. 先统计最高位出现 1 的次数

• first > 1

  以本例来说，将存在区间 [10000, 19999] 共计 10000 个数字，即最高位出现 10000 个 1

  即 10 ^ (length - 1)

• first = 1

  假设该数为 11345

  则最高位出现 1 的区间范围是 [10000, 11345]，共计 1345 + 1 个数

  即 remain + 1

2. 再统计 1346 ~ 21345 段中非最高位出现 1 的次数

由于 [1346, 21345] 段是完整连续的 20000 个数，因此除最高位外，剩下的4个位置，出现 0 ~ 9 的机会是均等的

因此，根据排列组合，我们可以得出如下计算方式

first * (remain.length) * 10 ^ (remain.length - 2)

其含义是，剩下的4个位置，选择其中一个放 1 ，其他位置可放置 0 ~ 9 中任意一个数字

最高位决定这样的排列组合重复几遍

---

以上，即为 1346 ~ 21345 段计数过程，再加上递归求解的剩余子串出现次数，即为总出现次数

---

如下为一个实现示例：

function NumberOf1Between1AndN_Solution(str) {
    if (!str) return 0;
    str = str.toString();
    
    let len = str.length;
    let first = str[0];
    
    if (len === 1) return first > 0 ? 1 : 0;
    
    let firstCount, otherCount, remainCount;
    let remain = str.slice(1);
    
    firstCount = first > 1
                    ? Math.pow(10, len - 1)
                    : +remain + 1;
    
    otherCount = first * (len - 1) * Math.pow(10, len - 2);
    
    remainCount = NumberOf1Between1AndN_Solution(+remain);
    
    return +firstCount + +otherCount + +remainCount;
}

Answer 21

例如统计 1 ~ 400W 出现 1 的次数。

function init(mathNum){
var num = 0;
var str = "1";
var len = (mathNum+"").length-1;
for(var i=0;i<len;i++){
num += mathNum/10;
str += "0";
}
if(mathNum+"0".substr(0,1)=="1"){
num+=1;
}else{
num += Number(str)
}

return num;

}
console.log(init(2000));

Answer 22

一位数： 1
二位数： [10-99): 19， 1+19 = 20
三位数： [100-200): 20+100， [200-1000): 8*（1+19） [0-1000): 160+140
四位数： [1000-2000): 1000+300 [0-2000): 1000+300+300
可以这样搞得， 也可以采用了 @wilesen 这种

看看数学规律 看每位出现1的次数
n为个位，f(n) = 个位
n为十位，f(n) = 十位+个位
n为百位，f(n) = 十位+个位+百位
以此类推
这样子是以十进制去循环的，效率大概在log(10)400000 = log(10^5 *4)
log(log10^6) > 结果> log(log10^5) =》 6~5之间

Answer 23

一位数： 1
二位数： [10-99): 19， 1+19 = 20
三位数： [100-200): 20+100， [200-1000): 8*（1+19） [0-1000): 160+140
四位数： [1000-2000): 1000+300 [0-2000): 1000+300+300
可以这样搞得， 也可以采用了 @wilesen 这种

看看数学规律 看每位出现1的次数
n为个位，f(n) = 个位
n为十位，f(n) = 十位+个位
n为百位，f(n) = 十位+个位+百位
以此类推
这样子是以十进制去循环的，效率大概在log(10)400000 = log(10^5 *4)
log(log10^6) > 结果> log(log10^5) =》 6~5之间

我也是使用数学的思路写的

Answer 24

Array.from({length:4000000},(_,i)=>i+1).join('').split('').filter(val=>val==='1').length

Answer 25

排列组合，问高中生

Answer 26

    // 转化为概率计算
    // 不考虑key=0
    // 分割n 实例 52312 => 50000,52000,52300,52310,52312
    // 计算 00000-49999 50000-51999 52000-52299 52300-52309 52310-52312   1 * 0.9 * (长度 - 1) ||  (首位 - 1) / 首位 * 0.9 * (长度 - 1)
    // k = 0时，第一项（00000-49999）计算结果不同  => 结果等同于 0-9999 取 0/1/2/3/4/5/6/7 的次数 执行 （5-1）次 => 结果等同于 1-9999 取 1的次数 执行 4次
    const getOneCount = (n, key) => {
        let length = (n + '').length;
        let arr = [];
        let i = 0;
        let count = 0;
        while (i < length) {
            let times = Math.pow(10, length - i - 1);
            let num = Math.floor(n / times);
            count += getKeyCount(num * times, i, key);
            i++;
            // 检测到 上一位是key 且不是最后一位
            if (num % 10 === key && i < length) {
                count += (n - num * times) + 1;
                break;
            }
        }
        return count;
    };
    // 不含 n 大于一位  0 ~ n-1
    function getKeyCount(n, i, k) {
        let arr = (n + '').split('').map(item => +item);
        let newArr = arr.slice(i);
        if (i === 0 && k === 0) {
            return arr[0] * getOneCount(+Array(arr.length - 1).fill('9').join(''), 1) - 1;
        }
        if (newArr.length > 1) {
            let count = +newArr.join('');
            let probability = (newArr[0] <= k ? 1 : (newArr[0] - 1) / newArr[0]) * Math.pow(0.9, newArr.length - 1);
            return Math.round((1 - probability) * count);
        }
        else {
            return newArr[0] >= k ? 1 : 0;
        }
    }
    console.log('copy-getOneCount(11, 1)');
    console.log(getOneCount(13, 2));
    console.log(getOneCount(16, 2));
    console.log(getOneCount(20, 0));
    console.log(getOneCount(26, 0));
    console.log(getOneCount(20, 1));
    console.log(getOneCount(40000000, 1));

Answer 27

// 思路：for循环，对每一个数进行出现1的统计
// 最后累加即可
function calcOnetimes(num, sum = 0) {
if (num) {
if (num % 10 === 1) {
sum++
}
sum = calcOnetimes(parseInt(num / 10), sum)
}
return sum
}
const arr = []
for (let i = 1; i <= 2333; i++) {
arr.push(i)
}
const result = arr.reduce((sum, num) => {
return calcOnetimes(num, sum) //是把return的结果累加到sum身上
}, 0)
console.log(result)//1774

Answer 28

这差距太明显了，用规律和暴力的时间差距太大，一个用了26870ms, 一个小于1ms.

Answer 29

这不剑指原题么，有一个公式可以直接推出来

function NumberOf1Between1AndN_Solution(n)
{
    let ones = 0;
    for(let i = 1;i <= n;i *= 10){
        let a = Math.floor(n/i),b = n%i;
        ones += Math.floor((a+8) / 10) * i + (a % 10 === 1) * (b + 1);
    }
    return ones;
}

原文

Answer 30

function test(n){
let count = 0;
while(n>0){
if(n.toString().indexOf('1')>-1){ count ++;}
n--;
}
return count;
}

Answer 31

function countOne(n) {
    if(n == 0) {
        return 0
    }
    if(n<10){
        return 1
    }
    let str = ''+n;
    let first = str[0];
    let length = str.length-1;
    let rest = n % 10**length
    console.log(first,length,rest)
    if(first == 1){
        return rest + countOne(n-rest-1) +1
    }else if (first > 1) {
        return length*10 + countOne(rest) + countOne(10**length-1)*(first-1)
    }
}

Answer 32

主要就是考虑当前位数上的数字大小

function countOne(n) {
    if (n < 10) {
        return 1
    }
    var count = 0
    var currentDecimals = 0;
    var biggerDecimals = 0;
    var smallerDecimals = '';
    // 当前是第几位
    var current_10 = 0
    while ((temp = n / 10) > 0) {
        currentDecimals = n % 10
        biggerDecimals = parseInt(temp)
        current_10 = String(smallerDecimals).length
        if (currentDecimals < 1) {
            // 往前借
            count += biggerDecimals * Math.pow(10, current_10)
        } else if (currentDecimals == 1) {
            count += biggerDecimals * Math.pow(10, current_10) + 1 + parseInt(smallerDecimals == '' ? 0 : smallerDecimals)
        } else if (currentDecimals > 1) {
            count += (biggerDecimals + 1) * Math.pow(10, current_10)
        }
        n = biggerDecimals
        smallerDecimals = parseInt('' + currentDecimals + smallerDecimals)
    }
    return count
}

Answer 33

// 统计每个位数上面1出现的次数
function statisticsAppearNum(num) {
  let res = 0;
  // i表示位数，个位数、十位数、百位数...
  for (let i = 1; i <= num; i = i * 10) {
    let cur = Math.floor((num / i) % 10); // 当前位数的数字，如123，个位数是3，十位数是2，百位数是1；
    let high = Math.floor(num / (i * 10)); // 高位部分，如123，个位数时是12，十位数时是1，百位数时是0；
    let low = num % i; // 低位部分，如123，个位数时是0，十位数时是2，百位数时是23；
    // 根据当前位数的不同来判断，分别是0，1，>1三种情况
    if (cur === 0) {
      // 如120，个位数是0时，则个位数的1有1,11,21,31,...,111；共12 * 1个1；
      // 如202，十位数是0时，则十位数的1有10~19,110~119，共2 * 10 个1；
      // 如2011，百位数是0时，则百位数的1有100~199,1100~1199，共2 * 100个1；
      res += high * i;
    } else if (cur === 1) {
      // 如121，个位数是1时，则个位数的1有1,11,21,31,...,111,121；共12 * 1 + 1个1；
      // 如212，十位数是1时，则十位数的1有10~19,110~119,210~212，共2 * 10 + 2 + 1个1；
      // 如2111，百位数是1时，则百位数的1有100~199,1100~1199，2100~2111，共2 * 100 + 11 + 1个1；
      res += high * i + low + 1;
    } else {
      // 如123，个位数>1时，则个位数的1有1,11,21,31,...,111,121；共(12 + 1) * 1个1；
      // 如222，十位数>1时，则十位数的1有10~19,110~119,210~219，共(2 + 1) * 10个1；
      // 如2311，百位数>1时，则百位数的1有100~199,1100~1199，2100~2199，共(2 + 1) * 100个1；
      res += (high + 1) * i;
    }
  }
  return res;
}

Answer 34

为啥都是暴力循环，这不都是算法题吗？
分析归纳一下，按照每一位上的数字来分析
比如55， 个位可能产生的 1 是 6个(1, 11, 21, 31, 41, 51, 注意这里11只计算的个位的1)， 十位5 可能产生的 1是 10个，(10 - 19， 这里的11只计算的十位的1)；

比如222， 个位 可能产生的 1 是 23个(1, 11, 21, ... 221, 只关注个位)， 十位2 可能产生的 1是 30个(10-19, 110-119, 210-219, 只关注十位), 百位2 产生的 1是100个(100 - 199， 只关注百位).

以此类推， 每一位数字可能产生的1的个数跟他的高位部分和低位部分相关：
其中0和1需要特殊处理，代码如下

function countOne(n) {
    var factor = 1;
    let count = 0;
    let next = parseInt(n / factor);
    while (next !== 0) {
        var lower = n - next * factor
        var curr = next % 10;
        var high = parseInt(n / (10 * factor));

        if (curr === 0) {
            count += high * factor;
        } else if (curr === 1) {
            count += high * factor + lower + 1
        } else {
            count += (high + 1) * factor
        }

        factor *= 10;
        next = parseInt(n / factor);
    }
    return count;
}

Answer 35

动不动400W，这怎么跑起来

Answer 36

let findOne = (len)=> { let count = ''; for (let i = 1; i <= len; i++) { count += i.toString().replace(/[^1]/ig, ''); } return count.length; }
先解决有没有，后续再解决好不好。

Answer 37

var count = 0;
var n = 4000000;
for(var i = 1; i <= n;i++){
if(i.toString().match(/[1]/g)){
count++;
}
}
console.log(count);

Answer 38

// 暴力正则匹配
function hasXFromOneToN(n, x) {
  let reg = new RegExp(`${x}`, 'g'), count = 0;
  for(let i=1; i<=n; i++ ) {
    ((i + '').match(reg)) && (count += (i + '').match(reg).length);
  }
  return count;
}


/*
* 特征规律： 举个栗子先
* 要寻找1～n中有多少个个位数x
* 首先按照位数来推断(只考虑当前位出现x的次数)
* 10中个位出现x的次数是1次（1）
* 100中十位出现x的次数是10次（10-19）
* 1000中百位出现x的次数是100次（100-199）
* 当前位有三种可能（n为当前位数）
* 1.大于x，则为：(左侧数+1)*10^(n-1)
* 2.小于x，则为：左侧数*10^(n-1)
* 3.等于x，则为：左侧数*10^(n-1) + 右侧数
* 
* 假设n=2333， x=1
* 个位：有233个10，个位为3，所以总数为234个
* 十位：有23个100，十位3大于x，2310～2319中为10次，(23+1)*10 = 240
* 百位：有2个1000，百位3大于x，2001～2333中100次（2100～2199总计100次）， 100*2+ 100 = 300
* 千位：有0个10000，千位2大于x, 总计为1000次（1000～1999总计1000次）， 1000
* count = 234 + 240 + 300 + 1000 = 1774
* */
function hasXFromOneToN(n, x) {
  if(x<0 || x>9 || n <0) {
    return 0;
  }
  let i =1, left = n, count = 0;
  while(left != 0) {
    let tmp = parseInt(n / Math.pow(10, i-1));
    let right = n - tmp * Math.pow(10, i-1);
    let current = tmp%10;
    left = parseInt(n/Math.pow(10, i));
    if(current < x) {
      count += left * Math.pow(10, i - 1);
    }else if(current > x) {
      count += (left + 1) * Math.pow(10 ,i - 1);
    } else {
      count += left * Math.pow(10, i - 1);
      count += (right + 1);
    }
    i++;
  }
  return count;
}

Answer 39

let get1Total = function (max) {
	let count = 0;	
	for(let i = 1;i <= max;i++) {
		let arr = i.toString().match(/[1]/g)
		arr && (count += arr.length)
	}
	return count;
}

Answer 40

感觉不太清晰，像11这个数字，算是出现1次还算是出现2次呢？像130这种带1的是不是也算呢？感觉详细描述下，或者举几个例子这样会更好理解一些 @yygmind

比如说1-11中1，10，11算4次，即11算2次

Answer 41

看看数学规律 看每位出现1的次数
n为个位，f(n) = 个位
n为十位，f(n) = 十位+个位
n为百位，f(n) = 十位+个位+百位
以此类推
这样子是以十进制去循环的，效率大概在log(10)400000 = log(10^5 *4)
log(log10^6) > 结果> log(log10^5) =》 6~5之间

Answer 42

应该是说1-n的时候中间出现1的次数，比如1到11的时候 1、10、11这种 其实就算4次了，因为11中有两个1

function findOne(n){
	let count = 0;
	for(let i=0;i<=n;i++){
		count+=String(i).split('').filter(item=>item==='1').length
	}
	return count;
}

Answer 43

感觉不太清晰，像11这个数字，算是出现1次还算是出现2次呢？像130这种带1的是不是也算呢？感觉详细描述下，或者举几个例子这样会更好理解一些 @yygmind

Answer 44

//暴力版本
function NumberOf1Between1AndN(n){
	let count = 0;
    for (let i = 0; i <= n; i++) {
        let temp = i;
        while (temp > 0) {
            if (Math.floor(temp % 10) == 1) {
                count++;
            }
            temp /= 10;
        }
    }
    return count;
}
//跑过测试，复杂度为O(logn)版本
var countDigitOne = function(n) {
   if (n < 1)
        return 0;
    let count = 0,
        base = 1,
        round = n;
    while (round > 0) {
        let weight = Math.floor(round % 10);
        round = Math.floor(round / 10);
        count += Math.floor(round * base);
        if (weight == 1)
            count += Math.floor(n % base) +1;
        else if (weight > 1)
            count += base;
        base *= 10;
    }
    return count;
};

Answer 45

数字是有序还是无序的呢