美团2024 10-12笔试

第一题：求出好数的个数

package meituan;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

    static int maxPowerImprove = 0; // 最大战斗力提升
    static Map<Integer, Integer> maxXMCombatPowerMap = new HashMap<>(); // 记录XM与XT的最佳配对

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt(); 
        int n = in.nextInt(); 

        int[] xmCombatPower = new int[m]; 
        int[] xtCombatPower = new int[n]; 

   
        for (int i = 0; i < m; i++) {
            xmCombatPower[i] = in.nextInt();
        }

        for (int i = 0; i < n; i++) {
            xtCombatPower[i] = in.nextInt();
        }

        int[] xmUsed = new int[m]; 
        int[] xtUsed = new int[n]; 
        Arrays.fill(xmUsed, -1); 
        Arrays.fill(xtUsed, -1);

  
        maxPowerImprove(xmUsed, xtUsed, new HashMap<>(), xmCombatPower, xtCombatPower, 0);


        System.out.println(maxPowerImprove);

  
        for (int i = 0; i < xmCombatPower.length; i++) {
            if (maxXMCombatPowerMap.containsKey(i)) {
                System.out.print(maxXMCombatPowerMap.get(i) + 1 + " "); 
            } else {
                System.out.print("-1 "); // 未匹配则输出 -1
            }
        }
    }


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

    private static void maxPowerImprove(int[] xmUsed, int[] xtUsed, Map<Integer, Integer> xmCombatPowerMap,
                                        int[] xmCombatPower, int[] xtCombatPower, int powerImprove) {
 
        if (count(xmUsed) == xmCombatPower.length || count(xtUsed) == xtCombatPower.length) {
         
            if (powerImprove > maxPowerImprove) {
                maxPowerImprove = powerImprove;
                maxXMCombatPowerMap.clear();
                maxXMCombatPowerMap.putAll(xmCombatPowerMap);
            }
            return;
        }

     
        for (int i = 0; i < xmCombatPower.length; i++) {
            if (xmUsed[i] == -1) { 
                for (int j = 0; j < xtCombatPower.length; j++) {
                    if (xtUsed[j] == -1) { 
                        int tempImprove = 0;

                       
                        if (isPrime(xmCombatPower[i]) && isPrime(xtCombatPower[j])) {
                            tempImprove = (xmCombatPower[i] + xtCombatPower[j]) * 2;
                        } else if (isPrime(xmCombatPower[i]) || isPrime(xtCombatPower[j])) {
                            tempImprove = Math.max(xmCombatPower[i], xtCombatPower[j]) * 2;
                        } else {
                            tempImprove = xmCombatPower[i] + xtCombatPower[j];
                        }
                        
                        xmUsed[i] = j;
                        xtUsed[j] = i;
                        powerImprove += tempImprove;
                        xmCombatPowerMap.put(i, j);
                        
                        maxPowerImprove(xmUsed, xtUsed, xmCombatPowerMap, xmCombatPower, xtCombatPower, powerImprove);

                        // 回溯
                        xmUsed[i] = -1;
                        xtUsed[j] = -1;
                        powerImprove -= tempImprove;
                        xmCombatPowerMap.remove(i);
                    }
                }
            }
        }
    }
    
    public static int count(int[] arr) {
        int count = 0;
        for (int i : arr) {
            if (i != -1) {
                count++;
            }
        }
        return count;
    }
}

第二题：字符串第K个数字

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main2 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int k = in.nextInt();
        String s = in.next();

        if (s == null || s.isEmpty()) {
            System.out.println("N");
            return;
        }

        List<BigInteger> nums = extractNums(s);
        BigInteger result = getKthNum(nums, k);

        if (result.equals(BigInteger.valueOf(-1))) {
            System.out.println("N");
        } else {
            System.out.println(result);
        }
    }

    private static List<BigInteger> extractNums(String s) {
        List<BigInteger> nums = new ArrayList<>();
        char[] chars = s.toCharArray();
        StringBuilder sb = new StringBuilder();
        for (char c : chars) {
            if (Character.isDigit(c)) {
                sb.append(c);
            } else {
                if (sb.length() > 0) {
                    nums.add(new BigInteger(sb.toString()));
                    sb = new StringBuilder();
                }
            }
        }
        if (sb.length() > 0) {
            nums.add(new BigInteger(sb.toString()));
        }
        return nums;
    }

    private static BigInteger getKthNum(List<BigInteger> nums, int k) {
        if (k > nums.size()) {
            return BigInteger.valueOf(-1);
        }
        nums.sort((o1, o2) -> o2.compareTo(o1));
        return nums.get(k - 1);
    }
}

第三题：宠物大战

package meituan;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

    static int maxPowerImprove = 0; // 最大战斗力提升
    static Map<Integer, Integer> maxXMCombatPowerMap = new HashMap<>(); // 记录XM与XT的最佳配对

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        int n = in.nextInt();

        int[] xmCombatPower = new int[m];
        int[] xtCombatPower = new int[n];


        for (int i = 0; i < m; i++) {
            xmCombatPower[i] = in.nextInt();
        }

        for (int i = 0; i < n; i++) {
            xtCombatPower[i] = in.nextInt();
        }

        int[] xmUsed = new int[m];
        int[] xtUsed = new int[n];
        Arrays.fill(xmUsed, -1);
        Arrays.fill(xtUsed, -1);


        maxPowerImprove(xmUsed, xtUsed, new HashMap<>(), xmCombatPower, xtCombatPower, 0);


        System.out.println(maxPowerImprove);


        for (int i = 0; i < xmCombatPower.length; i++) {
            if (maxXMCombatPowerMap.containsKey(i)) {
                System.out.print(maxXMCombatPowerMap.get(i) + 1 + " ");
            } else {
                System.out.print("-1 "); // 未匹配则输出 -1
            }
        }
    }


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

    private static void maxPowerImprove(int[] xmUsed, int[] xtUsed, Map<Integer, Integer> xmCombatPowerMap,
                                        int[] xmCombatPower, int[] xtCombatPower, int powerImprove) {

        if (count(xmUsed) == xmCombatPower.length || count(xtUsed) == xtCombatPower.length) {

            if (powerImprove > maxPowerImprove) {
                maxPowerImprove = powerImprove;
                maxXMCombatPowerMap.clear();
                maxXMCombatPowerMap.putAll(xmCombatPowerMap);
            }
            return;
        }


        for (int i = 0; i < xmCombatPower.length; i++) {
            if (xmUsed[i] == -1) {
                for (int j = 0; j < xtCombatPower.length; j++) {
                    if (xtUsed[j] == -1) {
                        int tempImprove = 0;


                        if (isPrime(xmCombatPower[i]) && isPrime(xtCombatPower[j])) {
                            tempImprove = (xmCombatPower[i] + xtCombatPower[j]) * 2;
                        } else if (isPrime(xmCombatPower[i]) || isPrime(xtCombatPower[j])) {
                            tempImprove = Math.max(xmCombatPower[i], xtCombatPower[j]) * 2;
                        } else {
                            tempImprove = xmCombatPower[i] + xtCombatPower[j];
                        }

                        xmUsed[i] = j;
                        xtUsed[j] = i;
                        powerImprove += tempImprove;
                        xmCombatPowerMap.put(i, j);

                        maxPowerImprove(xmUsed, xtUsed, xmCombatPowerMap, xmCombatPower, xtCombatPower, powerImprove);

                        // 回溯
                        xmUsed[i] = -1;
                        xtUsed[j] = -1;
                        powerImprove -= tempImprove;
                        xmCombatPowerMap.remove(i);
                    }
                }
            }
        }
    }

    public static int count(int[] arr) {
        int count = 0;
        for (int i : arr) {
            if (i != -1) {
                count++;
            }
        }
        return count;
    }
}

好气啊！！！结束才发现，都不是质数的情况是不需要×2的，检查了半天，脑袋麻了

#美团笔试#