题解 | #素数伴侣#
素数伴侣
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); } })();