全民k歌二面4.20

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode insert0 (ListNode head) {
        // write code here
        ListNode temp = head;
        while(temp!=null && temp.next!=null){
            ListNode newNode = new ListNode(0);
            newNode.next = temp.next;
            temp.next = newNode;
            temp = newNode.next;
        }
        return head;
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param a int整型一维数组
     * @return int整型
     */
    public int getMethods (int[] a) {
        // int n = a.length;
        // int[][] dp = new int[n][n];
        // for
        // write code here
        int n = a.length;
        boolean[] used = new boolean[n];
        Arrays.sort(a);
        Set<String> ans = new HashSet<>();
        dfs(a, 0, used, n, new ArrayList<Integer>(), ans);
        return ans.size();
    }

    public static void dfs( int[] a, int index, boolean[] used, int maxx,
                            ArrayList<Integer> temp, Set<String> ans) {
        if (index == maxx) {
            //System.out.println(1);
            if (isRight(temp)) {
                ans.add(temp.toString());
            }
            return;
        }
        // System.out.println(maxx);
        for (int i = 0; i < maxx; i++) {
            if (used[i] == false) {
                temp.add(a[i]);
                used[i] = true;
                dfs(a, index + 1, used, maxx, temp, ans);
                used[i] = false;
                temp.remove(index);
            }
        }
    }

    public static boolean isRight(ArrayList<Integer> temp) {
        for (int i = 1; i < temp.size(); i++) {
            // System.out.println(i);
            if (isSu(temp.get(i - 1) + temp.get(i)) == false) {
                return false;
            }
        }
        return true;
    }

    public static boolean isSu(int k) {
        for (int i = 2; i * i < k; i++) {
            if (k % i == 0) return false;
        }
        return true;
    }
}

import java.util.*;

public class Solution {
    private Set<String> ans;
    private int[] a;
    private boolean[] used;
    private int n;
    private List<Integer> primes;  // Store primes up to a certain number

    public int getMethods(int[] a) {
        this.a = a;
        this.n = a.length;
        this.used = new boolean[n];
        Arrays.sort(a);
        this.ans = new HashSet<>();
        int maxPossibleSum = 2 * a[n-1];  // Maximum sum of two elements
        generatePrimes(maxPossibleSum);
        dfs(0, new ArrayList<>());
        return ans.size();
    }

    private void dfs(int index, ArrayList<Integer> temp) {
        if (index == n) {
            if (isRight(temp)) {
                ans.add(temp.toString());
            }
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!used[i]) {
                if (temp.size() > 0 && !primes.contains(temp.get(temp.size() - 1) + a[i])) {
                    continue;  // Early pruning if the sum is not prime
                }
                temp.add(a[i]);
                used[i] = true;
                dfs(index + 1, temp);
                used[i] = false;
                temp.remove(temp.size() - 1);  // Remove the last element
            }
        }
    }

    private boolean isRight(ArrayList<Integer> temp) {
        for (int i = 1; i < temp.size(); i++) {
            if (!primes.contains(temp.get(i - 1) + temp.get(i))) {
                return false;
            }
        }
        return true;
    }

    private void generatePrimes(int max) {
        primes = new ArrayList<>();
        boolean[] isPrime = new boolean[max + 1];
        Arrays.fill(isPrime, true);
        for (int i = 2; i <= max; i++) {
            if (isPrime[i]) {
                primes.add(i);
                for (int j = 2 * i; j <= max; j += i) {
                    isPrime[j] = false;
                }
            }
        }
    }
}

import java.util.*;

public class Solution {
    private Set<List<Integer>> uniquePerms = new HashSet<>();
    private List<List<Integer>> validPairs = new ArrayList<>();
    private boolean[] visited;
    private int[] nums;

    public int getMethods(int[] nums) {
        this.nums = nums;
        Arrays.sort(nums); // 排序以处理重复元素
        this.visited = new boolean[nums.length];
        prepareValidPairs(nums);

        // 尝试每个数字作为起始点
        for (int i = 0; i < nums.length; i++) {
            if (i == 0 || nums[i] != nums[i - 1]) { // 跳过重复的起始数字
                visited[i] = true;
                dfs(i, new ArrayList<>(Arrays.asList(nums[i])));
                visited[i] = false;
            }
        }
        return uniquePerms.size();
    }

    private void dfs(int currentIndex, List<Integer> currentPath) {
        if (currentPath.size() == nums.length) {
            uniquePerms.add(new ArrayList<>(currentPath));
            return;
        }

        for (int nextIndex : validPairs.get(currentIndex)) {
            if (!visited[nextIndex]) {
                visited[nextIndex] = true;
                currentPath.add(nums[nextIndex]);
                dfs(nextIndex, currentPath);
                currentPath.remove(currentPath.size() - 1);
                visited[nextIndex] = false;
            }
        }
    }

    private void prepareValidPairs(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            validPairs.add(new ArrayList<>());
            for (int j = 0; j < nums.length; j++) {
                if (i != j && isPrime(nums[i] + nums[j])) {
                    validPairs.get(i).add(j);
                }
            }
        }
    }

    private boolean isPrime(int num) {
        if (num <= 1) return false;
        if (num <= 3) return true;
        if (num % 2 == 0 || num % 3 == 0) return false;
        for (int i = 5; i * i <= num; i += 6) {
            if (num % i == 0 || num % (i + 2) == 0) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] input = {1, 1, 2};
        System.out.println("Total permutations: " + solution.getMethods(input));
    }
}

import java.util.*;

public class Solution {
    private Set<List<Integer>> uniquePerms = new HashSet<>();
    private List<List<Integer>> validPairs = new ArrayList<>();
    private boolean[] visited;
    private int[] nums;

    public int getMethods(int[] nums) {
        this.nums = nums;
        Arrays.sort(nums); // 排序以处理重复元素
        if (nums.length > 0 && allSame(nums)) {
            return 1; // All elements are the same, only one valid permutation
        }
        this.visited = new boolean[nums.length];
        prepareValidPairs(nums);

        // 尝试每个数字作为起始点
        for (int i = 0; i < nums.length; i++) {
            if (i == 0 || nums[i] != nums[i - 1]) { // 跳过重复的起始数字
                visited[i] = true;
                dfs(i, new ArrayList<>(Arrays.asList(nums[i])));
                visited[i] = false;
            }
        }
        return uniquePerms.size();
    }

    private void dfs(int currentIndex, List<Integer> currentPath) {
        if (currentPath.size() == nums.length) {
            uniquePerms.add(new ArrayList<>(currentPath));
            return;
        }

        for (int nextIndex : validPairs.get(currentIndex)) {
            if (!visited[nextIndex]) {
                visited[nextIndex] = true;
                currentPath.add(nums[nextIndex]);
                dfs(nextIndex, currentPath);
                currentPath.remove(currentPath.size() - 1);
                visited[nextIndex] = false;
            }
        }
    }

    private void prepareValidPairs(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            validPairs.add(new ArrayList<>());
            for (int j = 0; j < nums.length; j++) {
                if (i != j && isPrime(nums[i] + nums[j])) {
                    validPairs.get(i).add(j);
                }
            }
        }
    }

    private boolean isPrime(int num) {
        if (num <= 1) return false;
        if (num <= 3) return true;
        if (num % 2 == 0 || num % 3 == 0) return false;
        for (int i = 5; i * i <= num; i += 6) {
            if (num % i == 0 || num % (i + 2) == 0) return false;
        }
        return true;
    }

    private boolean allSame(int[] array) {
        int first = array[0];
        for (int num : array) {
            if (num != first) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] input = {1, 1, 2};
        System.out.println("Total permutations: " + solution.getMethods(input));
    }
}