题解 | #素数伴侣#

素数伴侣

https://www.nowcoder.com/practice/b9eae162e02f4f928eac37d7699b352e

通过率 83.33%,最终结果打印出来,素数伴侣是成立的,但不是最大匹配,

我的天呢。。。我用匈牙利算法算出来的为什么不是“最大”匹配?

而且大家为什么用递归呢?我没有用递归额。。。

--------

我仔细想了下,大概猜到哪儿出问题了。

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
    // 若两个整数的和为素数,则这两个整数必定一个是奇数,一个是偶数。所以:
    // 1. 分成奇数数组 和 偶数数组
    // 2. 匈牙利算法

    let arr = [];
    while ((line = await readline())) {
        arr.push(line);
    }
    let nums = arr[1].split(" ").map(Number);
    let jis = [], // 存放奇数
        ous = []; // 存放偶数
    nums.forEach((item) => {
        if (item % 2 == 0) {
            ous.push(item);
        } else {
            jis.push(item);
        }
    });

    // 让多的去匹配少的,
    if (jis.length > ous.length) { // 让奇数去匹配偶数
        duoPeiShao(jis, ous);
    } else {    // 让偶数去匹配奇数
        duoPeiShao(ous, jis);
    }

    // 判断是不是素数
    function checkSushu(sum) {
        let flag = true; // 默认为是素数
        let i = 2;
        while (i < sum) {
            if (sum % i == 0) {
                // 可以被整除,说明不是素数,flag置为false,退出while循环
                flag = false;
                break;
            } else {
                i++;
            }
        }
        return flag;
    }

    function duoPeiShao(arr1, arr2) {
        let a1_obj = {},
            a2_obj = {};
        for (let i = 0; i < arr1.length; i++) {
            a1_obj[arr1[i]] = [];
            for (let k = 0; k < arr2.length; k++) {
                if (checkSushu(arr1[i] + arr2[k])) {
                    a1_obj[arr1[i]].push(arr2[k]); // 先占上
                    if (a2_obj[arr2[k]] == undefined) {
                        a2_obj[arr2[k]] = arr1[i];
                    } else {
                        let ex_ji = a2_obj[arr2[k]];
                        if (a1_obj[ex_ji].length > 1) {
                            let index_ou = a1_obj[ex_ji].indexOf(arr2[k]);
                            a1_obj[ex_ji].splice(index_ou, 1);

                            a2_obj[arr2[k]] = arr1[i];
                        } else {
                            // 该元素不能被占
                            a1_obj[arr1[i]].pop();
                        }
                    }
                }
            }
        }

        let max = 0;
        for (let key in a1_obj) {
            if (a1_obj[key].length > 0) {
                max++;
            }
        }
        console.log(max);
    }
})();

全部评论

相关推荐

工作基本定了,比较满意。这深度学习真是难搞啊,论文看不懂,代码看不懂,不会改,创新点???&nbsp;还有一个月中期,怎么搞,已经抑郁了,没有小论文要求,我真是非常幸运了,不然就我这科研能力…………&nbsp;感觉自己对自己失去信心,无时无刻不在否定自己取得一些成绩都是运气好罢了,真的能顺利毕业吗?严重内耗、无力感爆棚啊…………
AI牛可乐:哎呀,听起来你最近压力好大呀,毕业论文和工作的双重压力一定让你感觉像是背了两座山呢。深度学习确实挺复杂的,就像是要在一片迷雾中找到出路一样。但是,你已经很棒了,工作都定好了,这是很大的成就呢! 论文的事情,别太担心。每个人都有看不懂代码和论文的时候,这是正常的。至于创新点嘛,有时候灵感就像小猫一样,需要一点一点地哄出来的。你可以先试试把你看过的资料整理一下,说不定就能找到新的思路呢。 中期答辩前,你可以列个计划,一步一步来,把大问题分解成小问题,一点一点克服。记得,你不是一个人在战斗,你的导师、同学都是你的战友哦。 至于信心嘛,别否定自己,每个人都会有低谷的时候。你已经取得的成绩,都是你实力的体现。毕业不是问题,只要你不放弃,就一定能顺利走过去的。加油哦,我相信你可以的! 对了,如果你愿意的话,可以点击我的头像,我们私信聊,也许我能帮你出出主意,或者就是简单地聊聊天,分散一下你的注意力也好呀。🐮💪🌟
点赞 评论 收藏
分享
object3:开始给部分🌸孝子上人生第一课了
点赞 评论 收藏
分享
专心打鱼:互联网搬运工,贴子都要偷
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务