找出0-400亿中所有1的个数，求大神支招！！！
发布于 6 个月前 作者 frank320 1447 次浏览 来自 问答

试了for循环 内存直接爆掉

14 回复
2

深度二分， 不知道可行不. 自豪地采用 CNodeJS ionic

把0-400亿分成1w个数一组，最后统一加起来。

异步分块处理下

那么多内存怎么可能装的下，用流这样慢慢处理。 yield + rx.js 的 stream，或者试试 node 的 stream，或者 promise。

增加缓冲池处理, 在此基础上用多个子进程分批去跑.

不过我感觉这种同步计数的操作强行写成异步是不是不太好啊.

1

调试了一会发现这是一道数学题啊。 image.png

'use strict';

module.exports = main();

function counts(min, max) {
    return new Promise(resolve => {
        let result = 0;
        for (let i = min; i < max; i++) {
            result += count(i);
        }
        resolve(result);
    });
}

function count(num) {
    const len0 = (num + '').length;
    const len1 = (num + '').replace(/1/g, '').length;
    return len0 - len1;
}


async function main() {
    const start = 1;
    const end = 400000000;
    const step = 20000;
    async function reduce(sum, next) {
        let num = next;
        next = next + step;
        if (next > end) return sum + await counts(num, end + 1);
        return await reduce(sum + await counts(num, next), next);
    }
    const time = Date.now();
    const result = await reduce(0, start);
    console.log(`(${start}, ${end}), step=${step}，耗时：${(Date.now() - time) / 1000}，结果：${result}`);
}

试了for循环 内存直接爆掉

搜索，“惰性计算”。

这不是找规律吗？

@wbget 感谢！！！

1

这是数学问题了啊。。。

function main(max) {
    let maxSp = max.toString().split('');
    let maxSpFirst = maxSp[0];
    let maxSpCalacuLen = Math.max(0, maxSp.length - 1);
    let maxSpCalacuLen_1 = Math.max(0, maxSpCalacuLen-1);

    let maxCountOnes = maxSpFirst * Math.pow(10, maxSpCalacuLen_1) * maxSpCalacuLen + Math.pow(10, maxSpCalacuLen);

    console.log(`${maxSp},${maxSpFirst},${maxSpCalacuLen},${maxSpCalacuLen_1}:`,maxCountOnes);
}

如是处理400亿个字符，并对其进行处理可能需要分块完成或者惰性计算啊，这个计算出现次数，仅仅是数学问题。。。 PS：不要为了开发而开发啊，解决具体问题才是正道

按照排列组合问题的解法去做就行了

@zhhb 嗯嗯 你说的很对！ 主要这是个面试题啊 在网上没搜到合适答案 就来社区问问大神们

@wbget 你这界面挺漂亮，用的什么console呢？

回到顶部