题解 | #素数伴侣#

素数伴侣

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

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            int[] nums = new int[n];
            for(int i=0;i<n;i++){
                nums[i] = sc.nextInt();
            }
            ArrayList<Integer> evens = new ArrayList<>();
            ArrayList<Integer> odds = new ArrayList<>();

            for(int i=0;i<n;i++){
                if((nums[i]&1)==1){
                    odds.add(nums[i]);
                }else{
                    evens.add(nums[i]);
                }
            }
            int[] evensMatch = new int[evens.size()];
            int count = 0;
            for(int i=0;i<odds.size();i++){
                int[] used = new int[evens.size()];
                if(find(used,evens,odds.get(i),evensMatch)){
                    count++;
                }
            }
            System.out.println(count);
        }
    }
    public static boolean isPrime(int num){
        for(int i=2;i*i<=num;i++){
            if(num%i==0){
                return false;
            }
        }
        return true;
    }

    public static boolean find(int[] used,ArrayList<Integer> evens,int num,int[] evensMatch){
        for(int i=0;i<evens.size();i++){
            if(isPrime(num+evens.get(i))&&used[i]==0){
                used[i]=1;
                //第二个条件相当于回溯,新的奇数要匹配这个偶数,但是这个偶数已经被旧的奇数占用了
                //那么就让旧的奇数再去找一个新的匹配结果,used保证了不会重复冲突
                if(evensMatch[i]==0||find(used,evens,evensMatch[i],evensMatch)){
                    evensMatch[i] = num;
                    return true;
                }
            }
        }
        return false;
    }

}

全部评论

相关推荐

Hakasee:我的简历和你的基本一样,上周去了上海,boss投了三百家, 三家线下面试 第一家没有做题,全是八股和项目,因为第一次面试不怎么熟练,挂了 第二家,给你几个题目(①css垂直居中文字,字体每两秒闪烁一下以及点击弹窗,②给你一个链接,实现可视化地图,③然后是八股,图片性能优化,以及对图片app有什么想法),45分钟内做完,然后老板面试) 第三家特别偏僻,有点阴森,到了之后让了一个工位给我,有四个题目,①格式化时间 年月日当前时间星期几② 正则表达式提取新闻文字,③在文本域输入文字生成选择题以及选项④生成商品排版还是什么来着 三家都是不超过50人的小公司 两家线上牛客笔试(卡伦特,七牛云,但是笔试不仅要考前端,还要考后端,算法,甚至数学题 我的建议是如果只做了这两个vue项目且不怎么熟练的情况下,先沉淀沉淀,把react学了,上海好的公司基本都是react查看图片
点赞 评论 收藏
分享
自学java狠狠赚一...:骗你点star的,港卵公司,记得把star收回去
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务