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

试了for循环 内存直接爆掉

14 回复

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

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

异步分块处理下

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

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

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

调试了一会发现这是一道数学题啊。 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 感谢!!!

这是数学问题了啊。。。

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呢?

回到顶部