题解 | #素数伴侣#

贪心和深搜（题目：素数伴侣）
中心思想：将所有数分为奇数和偶数，分别找到每一个奇数（偶数）的素数伴侣，可能有多个，都记录下来。先匹配伴侣少的奇数（偶数），再匹配伴侣多的奇数（偶数），这样就会找到尽可能多的素数伴侣对，组成素数伴侣的对数最多就是奇数（偶数）的个数（取决于奇数和偶数谁个数少）
步骤及示例：
#1.将所有数分为偶数even(ArrayList)和奇数odd(ArrayList)，分别从小到大排序（假设长度较小的为odd）
#2.开辟一个长度和odd相同的list数组，list[i]存储：odd[i]的素数伴侣even[j]的所有j值
#3.将list按照元素个数的多少从小到大排序（并且去掉奇数没有素数伴侣的项）
---------------------------例子-----------------------------
22
20923 22855 2817 1447 29277 19736 20227 22422 24712 27054 27050 18272 5477 27174 13880 15730 7982 11464 27483 19563 5998 16163
---------------------------例子-----------------------------
even:5998 7982 11464 13880 15730 18272 19736 22422 24712 27050 27054 27174
odd:1447 2817 5477 16163 19563 20227 20923 22855 27483 29277

odd的素数伴侣：
1447:11464，22422，27174----下标为：2，7，11
2817:7982，11464，18272，24712，27050----下标为：1，2，5，8，9
5477:27054----下标为：10
16163:19736----下标为：6
19563:5998----下标为：0
20227:22422 24712----下标为：7，8
20923:5998 15730 27054----下标为：0，4，10
22855:11464----下标为：2
27483:没有
29277:15730----下标为：4

组成的list数组如下，并将list按照元素个数从小到大排序：
0: 10
1: 6
2: 0
3: 2
4: 4
5: 7,8
6: 2,7,11
7: 0,4,10
8: 1,2,5,8,9

#4.开辟一个flag数组，大小和even相同，flag[i]用来标记even[i]是否已经参与匹配，然后如图从上往下进行匹配，即深度优先搜索，红色代表匹配成功，蓝色代表尝试匹配，匹配失败，采用一个变量maxNum用来记录可以匹配的最大个数。
特别需要注意的是：当搜索到list的第7项(下标7）时，由于even数组中的下标为0，4，10的偶数已经参与过匹配，所以在这一层没有匹配到的时候，应该跳到下一层继续匹配，只要当前匹配的层数没有超过list数组的长度。跳到下一层继续匹配体现在代码中如下图所示的if判断：

代码如下：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

public class Main {
    private static int maxNum = 0;
    private static boolean isFind = false;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = null;
        while((str = br.readLine()) != null)
        {
            isFind = false;
            maxNum = 0;
            ArrayList<Integer> even = new ArrayList<>();
            ArrayList<Integer> odd = new ArrayList<>();
            int num = Integer.valueOf(str);
            String strs[] = br.readLine().split(" ");
            for(int i = 0; i<strs.length; i++)
            {
                int temp = Integer.valueOf(strs[i]);
                if(temp % 2 == 0)
                    even.add(temp);
                else
                    odd.add(temp);
            }
            Collections.sort(even);
            Collections.sort(odd);
            if(even.size()==0 || odd.size() == 0)
                System.out.println(0);
            else
            {
                if(odd.size()>=even.size())
                {
                    buildList(even, odd);
                }
                else
                {
                    buildList(odd, even);
                }
            }
        }
    }
    public static void dfs(ArrayList<Integer> list[], boolean flag[], int pos, int cnt)
    {
        if(isFind == true)
            return;
        if(cnt>maxNum)
        {
            maxNum = cnt;
        }
        if(maxNum == list.length)
        {
            isFind = true;
            return;
        }
        if(pos>=list.length)
        {
            return;
        }
        boolean isJug = true;
        for(int i = 0; i<list[pos].size() && isFind==false; i++)
        {
            if(flag[list[pos].get(i)] == false)
            {
                isJug = false;
                flag[list[pos].get(i)] = true;
                dfs(list, flag, pos+1, cnt+1);
                flag[list[pos].get(i)] = false;
            }
        }
        if (isJug == true && pos<list.length)
        {
            dfs(list, flag, pos+1, cnt);
        }
    }
    public static void buildList(ArrayList<Integer> min, ArrayList<Integer> max) {

        ArrayList<ArrayList<Integer>> arrList = new ArrayList<>();
        for(int i = 0;i<min.size(); i++)
        {
            ArrayList<Integer> subList = new ArrayList<>();
            for(int j = 0; j<max.size(); j++)
            {
                if(isPrime(min.get(i)+max.get(j)) == true)
                {
                    subList.add(j);
                }
            }
            if(subList.size()>0)
                arrList.add(subList);
        }

        Object obj[] = arrList.toArray();
        ArrayList<Integer> list[] = new ArrayList[obj.length];
        for(int i = 0; i<obj.length; i++)
        {
            list[i] = (ArrayList<Integer>) obj[i];
        }
        Arrays.sort(list, new Comparator<ArrayList<Integer>>() {
            @Override
            public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {
                return o1.size()-o2.size();
            }
        });

        boolean flag[] = new boolean[max.size()];
        if(list.length>0)
        {
            dfs(list, flag, 0, 0);
            System.out.println(maxNum);
        }

        else
            System.out.println(0);
    }
    public static boolean isPrime(int num)
    {
        if(num == 2)
            return true;
        if(num%2 == 0)
            return false;
        for(int i = 3; i<=(int)Math.sqrt(num)+1; i+=2)
        {
            if(num % i == 0)
                return false;
        }
        return true;
    }
}