美团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;
}
}
AC
第二题：字符串第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);
}
}
AC
第三题： 宠物大战
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的，检查了半天，脑袋麻了
#美团笔试#