2025 题库（阶段一）
1、 密码锁
给定两个 4 位数组，数组中的每一位表示一个密码，取值范围[0-9]，第一个数组为锁的当前密码，第二个数组为开锁密码，密码只能往小拨动，如：9->8，8->7，0->9，一次只能拨动一个数字，请问最少需要拨动多少次才能打开密码锁。
示例：
[9, 0, 1, 2] -> [1, 2, 3, 4]
解答：
public static int minOps(int[] source, int[] target) {
if (source == null || target == null || source.length != target.length) {
return -1;
}
int count = 0;
for (int i = 0; i < source.length; i++) {
count += (source[i] - target[i] + 10) % 10;
}
return count;
}
2、 字符串大小写转换
给定一组大写字母组成的字符串，将字符串的下标转为二进制，如果二进制表示中 1 的个数是偶数，则将对应的字母转为小写，输出转换后的字符串。
解答：
public static String convertByBitCount(String source) {
char[] chars = source.toCharArray();
for (int i = 0; i < chars.length; i++) {
if (Integer.bitCount(i) % 2 == 0) {
chars[i] = Character.toLowerCase(chars[i]);
}
}
return String.valueOf(chars);
}
3、 不含 0 的最长子串
给定一个由数字组成的字符串，找出不含 0 的最长子串的长度。
解答：
public static String noneZeroMaxLen(String source) {
int maxLen = 0;
int curStart = 0;
int maxStart = 0;
for (int i = 0; i < source.length(); i++) {
if (source.charAt(i) == '0') {
curStart = i + 1;
} else {
if (i - curStart + 1 > maxLen) {
maxLen = i - curStart + 1;
maxStart = curStart;
}
}
}
return maxLen == 0 ? "" : source.substring(maxStart, maxStart + maxLen);
}
4、 与人对应的所有游戏
给定 n 对数据，每组包含（人名，游戏），人名可以重复，游戏也可以重复，最后输出 人名对应的所有游戏，空格分开，人名要按输入顺序，游戏也要按输入顺序。
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
sc.nextLine();
Map<String, List<String>> map = new LinkedHashMap<>();
for (int i = 0; i < n; i++) {
String line = sc.nextLine();
String[] parts = line.split(" ", 2);
if (parts.length != 2) {
continue;
}
String user = parts[0];
String game = parts[1];
List<String> list = map.computeIfAbsent(user, u -> new ArrayList<>());
if (!list.contains(game)) {
list.add(game);
}
}
for (Map.Entry<String, List<String>> entry : map.entrySet()) {
System.out.println(entry.getKey() + " " + String.join(" ", entry.getValue()));
}
}
5、 最优解
给定一个数组相减，值不能为负数，相减的结果放到两个数中较大的那个数的位置，求数组各元素之和最小是多少。
示例数组：[6, 15, 21]，然后一步步操作，
- 先看 6 和 15，→ 15 - 6 = 9 → [6, 9, 21]
- 再看 6 和 9，→ 9 - 6 = 3 → [6, 3, 21]
- 再看 6 和 3，→ 6 - 3 = 9 → [3, 3, 21]
- 再看 3 和 21，→ 21 - 3 = 18 → [3, 3, 18]
- 继续下去，最终会发现所有数字都变成 3（因为 GCD(6,15,21)=3）
无论你如何选择哪两个数进行操作，“最终剩下的那个数”一定是数组所有数的最大公约数（GCD），因此就是求数组所有数的 GCD。
解答：
public static int minSum(int[] nums) {
int result = nums[0];
for (int i = 1; i < nums.length; i++) {
result = gcd(result, nums[i]);
if (result == 1) {
break; // GCD 为 1 后无法再变小
}
}
return result;
}
6、 牛妹吃糖问题
牛妹喜欢吃糖，现在有一排共 n 个糖果，第 i 个糖果具有一个甜度值 αi。因为吃甜食太多了会得蛀牙，所以牛妹吃的糖果的甜度值总和不能超过 k。她可以以任意的顺序吃糖，请问她最多能吃多少个糖果？
输入描述：第一行给出两个正整数 n，k(1≤n≤2*10 的 5 次幂,1≤k≤10 的 9 次幂），意义如题面所示 第二行有 n 个整数，分别代表每一个糖果的甜度 α(1≤αi≤10 的 9 次幂)
输出描述：输出一行一个整数代表牛妹最多可以吃掉的糖果数。
解答：贪心算法
- 输入：第一行读取两个正整数 n 和 k。第二行读取 n 个整数，表示每个糖果的甜度值 αi 。
- 排序：将糖果的甜度值从小到大排序。这样可以优先选择甜度值最小的糖果。
- 计算：初始化一个变量 sum 表示当前吃掉的糖果的甜度值总和，初始值为 0。初始化一个变量 count 表示吃掉的糖果数量，初始值为 0。遍历排序后的糖果甜度值，每次将当前糖果的甜度值加到 sum 上，如果 sum 超过 k ，则停止遍历。每次成功吃掉一个糖果，将 count 加 1。
- 输出：输出 count 的值，即牛妹最多能吃掉的糖果数。
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
Arrays.sort(a);
int sum = 0;
int count = 0;
for (int i = 0; i < n; i++) {
if (sum + a[i] < k) {
sum += a[i];
count++;
} else {
break;
}
}
System.out.println(count);
}
7、 商品打折
给定两个数组，一组表示价格，一组表示折扣，两个数组长度一致，可任意搭配，每个只能用一次，求商品打折后最小价格，且只保留小数点三位。
解答：
public static String maxDiscount(int[] prices, double[] discounts) {
Arrays.sort(prices);
Arrays.sort(discounts);
double sum = 0;
for (int i = 0; i < prices.length; i++) {
sum += prices[i] * discounts[prices.length - i - 1];
}
return String.format("%.3f", sum);
}
8、 十进制转二进制
给定一个十进制整数，将其转换为二进制后，找出从末位向前第一个不为 0 的数到末位这一段二进制子串，并将它转回十进制输出。
解答：
public static int firstNonZeroBinary(int n) {
String binStr = Integer.toBinaryString(n); // 转换为二进制字符串
for (int i = binStr.length() - 1; i >= 0; i--) { // 从后往前找第一个 '1'
if (binStr.charAt(i) == '1') {
//从第 i 个位置开始，一直到最后一个字符，提取出一个新的子字符串
String subStr = binStr.substring(i);
//字符串解析成整数，2，表示按二进制解析
return Integer.parseInt(subStr, 2);
}
}
return 0; // 如果没找到（比如 n == 0），返回 0
}
9、 数组严格单调递增
给定一个整数数组 nums（下标从 0 开始）。每一次操作中，你可以选择数组中一个元素，并将它增加 1 。比方说，如果 nums = [1,2,3] ，你可以选择增加 nums[1] 得到 nums = [1,3,3]。请你返回使 nums 严格递增的最少操作次数。
我们称数组 nums 是严格递增的，当它满足对于所有的 0 <= i < nums.length - 1 都有 nums[i] < nums[i+1] 。一个长度为 1 的数组是严格递增的一种特殊情况。
示例 1：
输入：nums = [1,1,1]
输出：3
解释：你可以进行如下操作：
1. 增加 nums[2] ，数组变为 [1,1,2] 。
2. 增加 nums[1] ，数组变为 [1,2,2] 。
3. 增加 nums[2] ，数组变为 [1,2,3] 。
示例 2：
输入：nums = [1,5,2,4,1]
输出：14
示例 3：
输入：nums = [8]
输出：0
解答：
public static int minOps(int[] nums) {
if (nums == null || nums.length <= 1) {
return 0;
}
int count = 0;
for (int i = 1; i < nums.length; i++) {
if (nums[i - 1] > nums[i]) {
count += nums[i - 1] - nums[i] + 1;
nums[i] = nums[i - 1] + 1;
}
}
return count;
}
10、 答案取反
小红的数学很差，暑假后，他拿出自己的答案（只有 A 和 B），他想如果所有的答案都取反（既：A 变成 B，B 变成 A），答案的准确率是否有提升，如果是返回 true，否则返回 false。
解答：
public static boolean checkFlipAnswers(char[] source, char[] target) {
int sourceCount = 0;
int flipCount = 0;
if (source != null && target != null && source.length == target.length) {
for (int i = 0; i < source.length; i++) {
if (source[i] == target[i]) {
sourceCount++;
}
if ((source[i] == 'A' ? 'B' : 'A') == target[i]) {
flipCount++;
}
}
}
return flipCount > sourceCount;
}
11、 二进制好数异或和
给定 n 组二进制数，当二进制表示中 1 的个数为偶数时，定义为好数，求所有好数异或和。
解答：
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int result = 0;
for (int i = 0; i < n; i++) {
String str = sc.next();
int num = Integer.parseInt(str, 2);
if (Integer.bitCount(num) % 2 == 0) {
result ^= num;
}
}
System.out.println(result);
}
12、 二进制字符串截取
给出一串二进制字符串，从 0 开始截取，第一次截 1 个，第二次截 2 个，且每次截取完都删掉，第 n 次想要截 n 个，但长度达不到 n，则不删除。输出每次删除的二进制对应的十进制。
解答：
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.next();
int len = 1;
while (str.length() > len) {
int num = Integer.parseInt(str.substring(0, len), 2);
System.out.println(num);
str = str.substring(len++);
}
}
13、 最长前缀括号匹配
给出一串由“(”和“)”组成的字符串，一个完整的：“()”可以消除，例如“()()”可以，“(())”可以，“)()(”不行，截取这串字符串前置最长串，满足匹配要求。
解答：
public static String maxMatchBrackets(String str) {
Stack<Character> stack = new Stack<>();
int maxIdx = 0;
char ch;
for (int i = 0; i < str.length(); i++) {
ch = str.charAt(i);
if (ch == '(') {
stack.push(ch);
} else {
if (!stack.isEmpty() && stack.peek() == '(') {
maxIdx = i + 1;
stack.pop();
} else {
break;
}
}
}
return str.substring(0, maxIdx);
}
14、 去除字符
输入两个字符串，从第一个字符串中去除出现在第二个字符串中的所有字符，输出结果。
解答：
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s1 = sc.next();
String s2 = sc.next();
Set<Character> cSet = new HashSet<>();
for (char c : s2.toCharArray()) {
cSet.add(c);
}
StringBuilder sb = new StringBuilder();
for (char c : s1.toCharArray()) {
if (!cSet.contains(c)) {
sb.append(c);
}
}
System.out.println(sb.toString());
}
15、 元音解密
提供一串小写字母的字符串，若字母是元音，明文无需转换；辅音，需要转换为辅音 + 距离辅音近的元音（若距离一样，取字母表靠前的）+ 下一个辅音。转换后输出。
这个题有两种：
- 输出解密后的字符串；
- 输出解密后的字符串增加的长度。这种只需要计算辅音的个数，个数 ×2 即是增加的长度。
下面代码以输出解密后的字符串为例。
解答：
public static final char[] VOWELS = new char[]{'a', 'e', 'i', 'o', 'u'};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.next();
System.out.println(solve(str));
}
//是否是元音
public static boolean isNotVowel(char c) {
return "aeiou".indexOf(c) == -1;
}
//元音直接添加，辅音：辅音+最近且最靠前元音+后一个辅音
public static String solve(String str) {
StringBuilder sb = new StringBuilder();
char ch;
for (int i = 0; i < str.length(); i++) {
ch = str.charAt(i);
sb.append(ch);
if (isNotVowel(ch)) {
sb.append(closeVowel(ch));
sb.append(nextChar(ch));
}
}
return sb.toString();
}
//获取最近且最靠前元音
public static char closeVowel(char ch) {
char vowel = ' ';
int dif = Integer.MAX_VALUE;
for (char vc : VOWELS) {
int abs = Math.abs(ch - vc);
if (dif > abs) {
dif = abs;
vowel = vc;
}
}
return vowel;
}
public static char nextChar(char ch) {
char next = (char) (ch + 1);
if (isNotVowel(next)) {
return next;
} else {
return (char) (next + 1);
}
}
16、 数组中出现频率最高的数字
给定一个数组，可以对数组中的元素进行操作，操作包括：+1，-1，或不变，每个元素只能操作一次，求经过一定数量操作后，数组中出现频率最高的数字。
解答：
public static int maxFreq(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
int val;
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
val = num + 1;
map.put(val, map.getOrDefault(val, 0) + 1);
val = num - 1;
map.put(val, map.getOrDefault(val, 0) + 1);
}
int max = Integer.MIN_VALUE;
for (int freq : map.values()) {
max = Math.max(max, freq);
}
return max;
}
17、 质数和
给定一个由数字组成的字符串，在数字之间可以插入“+”，计算这个表达式的值，然后求其中值是质数的和。
示例：
输入："1234"
插入“+”的表达式：
1+2+3+4
12+34
123+4
1+234
...
解答：
public static boolean isPrime(int n) {
if (n <= 1) return false;
if (n <= 3) return true;
if (n % 2 == 0 || n % 3 == 0) return false;
int sqrt = (int) (Math.sqrt(n));
for (int i = 5; i <= sqrt; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) {
return false;
}
}
return true;
}
public static int calcPrimeSum(String numStr) {
int primeSum = 0;
// 比如 "1_2_3_4" 有 3 个空格可以插入 '+'，所以共有 2^3 = 8 种情况
int l = numStr.length();
int n = 1 << (l - 1);
for (int mask = 0; mask < n; mask++) {
StringBuilder exp = new StringBuilder();
int val = 0;
int sum = 0;
for (int i = 0; i < l; i++) {
exp.append(numStr.charAt(i));
val = val * 10 + (numStr.charAt(i) - '0');
// 如果不是最后一个字符，并且mask在该位上为1，则插入+
if (i < l - 1 && (mask & (1 << i)) != 0) {
sum += val;
val = 0;
exp.append('+');
}
}
sum += val; // 把最后一段加上
System.out.println("表达式: " + exp + " = " + sum);
if (isPrime(sum)) {
primeSum += sum;
}
}
return primeSum;
}
18、 小红的 01 串（好串）
小红拿到了一个 01 串，指仅由'0'和'1'两种字符组成的字符串。小红可以进行任意次以下操作选择字符串的一个字符，将其取反('0'变'1'或者'1'变'0')；
小红定义一个 01 串为好串，当且仅当该 01 串不包含"010"子串和"101"子串。 例如，"1001"是好串，但"100100"则不是好串,小红想知道，自己最少操作多少次可以将给定字符串变成好串?
解答：
public static int makeGoodTimes(String binStr) {
int times = 0;
int index = 0;
String binSub;
while (index < binStr.length() - 3) {
binSub = binStr.substring(index, index + 3);
if (binSub.equals("010") || binSub.equals("101")) {
times++;
index += 3;
} else {
index++;
}
}
return times;
}
19、 小欧的括号操作
小欧拿到了一个只包含字符'('和')'的字符串，她有以下两种操作：
- 用“(”替换一对括号：“()”；
- 用“)”替换一对括号：“()”；
请注意，只有相邻的括号字符可以操作。
小欧想知道，经过若干次操作后，该字符串的最小长度是多少。
解答：
// 此答案已验证错误，仅供参考
public static int minStrLength(String s) {
Stack<Character> stack = new Stack<>();
char c;
boolean flag;
for (int i = 0; i < s.length(); i++) {
c = s.charAt(i);
if (!stack.isEmpty() && c == ')' && stack.peek() == '(') {
stack.pop();
flag = true;
} else {
flag = false;
}
if (flag) {
stack.push('(');
} else {
stack.push(c);
}
}
return stack.size();
}
20、 求中位数、平均数、去极平均数
中位数：一组数据从小到大排列后，位于中间位置的数；当数据个数为奇数时，就是正中间的那个数；数据个数为偶数时，中位数是中间两个数的平均值。
去极平均数：去掉最大值和最小值后的平均数。
解答：
// 求中位数
public static double median(int[] nums) {
int n = nums.length;
int[] copy = Arrays.copyOf(nums, n);
Arrays.sort(copy);
if (n % 2 == 0) {
return (copy[n / 2 - 1] + copy[n / 2]) / 2.0;
} else {
return copy[n / 2];
}
}
// 求平均数
public static double mean(int[] nums) {
if (nums.length == 0) return 0;
long sum = 0;
for (int num : nums) {
sum += num;
}
return (double) sum / nums.length;
}
// 求去极平均数
public static double trimMean(int[] nums) {
if (nums.length <= 2) return 0; // 至少要有3个元素才能去极
int n = nums.length;
int[] copy = Arrays.copyOf(nums, n);
Arrays.sort(copy); // 排序后第一个是最小，最后一个是最大
long sum = 0;
for (int i = 1; i < n - 1; i++) {
sum += copy[i];
}
return (double) sum / (n - 2);
}
21、 大小写转换
有 n 位字符串（只含大小写字符）。小红可以将任意的大写转小写，小写转大写，求 K 次操作后，字符串最多有多少个大写字符。有可能存在小写转大写后K没用完的情况
解答：
public static int maxUpperCount(String s, int k) {
int upperCount = 0;
for (int i = 0; i < s.length(); i++) {
if (Character.isUpperCase(s.charAt(i))) {
upperCount++;
}
}
int lowerCount = s.length() - upperCount;
return upperCount + Math.min(lowerCount, k);
}
22、 非连续序列分为 K 份
给定一个非连续序列，将它分成 K 份，每一份中的最大值减去最小值为极值，问怎么分，这 K 份极值和最大（不一定按顺序分，可随意抽取，最后分成 K 份即可）。
解答：
public static long maxExtremeSum(long[] nums, int k) {
Arrays.sort(nums);
long sum = 0;
for (int i = 0; i < k; i++) {
sum += nums[nums.length - i - 1] - nums[i];
}
return sum;
}
动态规划：
public static int maxExtremeSumDP(int[] nums, int k) {
int n = nums.length;
int[][] dp = new int[n + 1][k + 1];
int min;
int max;
for (int i = 1; i < n; i++) {
for (int j = 1; j < Math.min(i, k); j++) {
min = Integer.MAX_VALUE;
max = Integer.MIN_VALUE;
for (int m = i; m >= j; m--) {
min = Math.min(min, nums[m - 1]);
max = Math.max(max, nums[m - 1]);
dp[i][j] = Math.max(dp[i][j], dp[m - 1][j - 1] + (max - min));
}
}
}
return dp[n][k];
}
23、 小红和小蓝的游戏
小红和小蓝的游戏，给两个数组代表他们两个的得分，ai 代表本局游戏得分，如果小红的得分相比于上一局得分增加，小蓝减少，则小红可以嘲笑小蓝；小红的得分增长幅度比小蓝增长幅度大，则小红可以嘲笑小蓝；小红的减少的得分比小蓝减少的少，小红也可以嘲笑小蓝。只有当两人增长和减少的幅度一致时，则相互不能嘲笑，问相互不嘲笑的长度。
解答：
public static int noRidiculeLen(int[] rs, int[] bs, int n) {
if (n <= 1) return 1;
int maxLen = 1;
int curLen = 1;
int rd, bd;
for (int i = 1; i < n; i++) {
// 计算本局相对于上一局的变化量
rd = rs[i] - rs[i - 1];
bd = bs[i] - bs[i - 1];
if (rd == bd) {
// 变化量相同，延长不能嘲笑的长度
curLen++;
maxLen = Math.max(curLen, maxLen);
} else {
// 变化量不同，重置长度
curLen = 1;
}
}
return maxLen;
}
24、 小红的数组操作
给定两个数组 A 和 B，在 A 和 B 中各取一个元素并+1，问经过多少轮操作，两个数组中各个元素都相等，如果最终无法配平则输出-1；举例[1,2,4,5][1,2,3,6]只需要增加一次 1 即可。
解答：
public static int countSteps(int n, int[] a, int[] b) {
int result = -1;
int da = 0;
int db = 0;
for (int i = 0; i < n; i++) {
if (a[i] > b[i]) {
da += a[i] - b[i];
} else if (a[i] < b[i]) {
db += b[i] - a[i];
}
}
if (da == db) {
result = da;
}
return result;
}
25、 添加括号
给定一个由'[]'和'{}'组成的字符串，如：“[]{}[[[]”，求最少添加多少个括号，使得字符串合法。
解答：
public static int matchBrackets(String s) {
Stack<Character> stack = new Stack<>();
char c;
for (int i = 0; i < s.length(); i++) {
c = s.charAt(i);
if (stack.isEmpty()) {
stack.push(c);
continue;
}
if ((c == ']' && stack.peek() == '[') || (c == '}') && stack.peek() == '{') {
stack.pop();
} else {
stack.push(c);
}
}
return stack.size();
}
26、 DRE 字符串
给定一个字符串，求有多少个连续子串，子串要包含“r”和“e”，但不包含“d”。
解答：
public static int countSub(String s) {
int count = 0, start = 0;
int lastR = -1, lastE = -1;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == 'd') {
start = i + 1;
lastR = lastE = -1;
} else {
if (c == 'r') lastR = i;
if (c == 'e') lastE = i;
if (lastR != -1 && lastE != -1) {
int valid = Math.max(start, Math.min(lastR, lastE));
count += valid - start + 1; // 这个计算方法没看懂
}
}
}
return count;
}
27、 买花
给妈妈买花，给定一个数组代表每种花的支数，每种花只能买奇数支，或者不买，最终买完的支数也要是奇数，问最多能买多少支花。如:3，{5,5,8}，最多买 17 朵，5+5+7，因为 8 支是偶数，所以买 7 支。
解答：
public static int maxOddFlowers(int[] flowers) {
int total = 0;
int minEven = Integer.MAX_VALUE;
for (int count : flowers) {
if (count % 2 == 0) {
total += count - 1;// 取最大的奇数
minEven = Math.min(minEven, count);
} else {
total += count;
}
}
//如果总和是偶数，需要减去最小的偶数-1的值
if (total % 2 == 0) {
total -= (minEven - 1);
total += (minEven % 2 == 0) ? 0 : -1;
}
return total;
}
28、 括号互换
'{'可以跟'['互换，'}'可以跟']'互换，给定一个左右括号一致，但不完全匹配的字符串，返回最少的替换次数，使得字符串完全匹配。
解答：
public static int countBrackets(String s) {
int count = 0;
Stack<Character> stack = new Stack<>();
char c;
for (int i = 0; i < s.length(); i++) {
c = s.charAt(i);
if (c == '[' || c == '{') {
stack.push(c);
} else if (!stack.isEmpty()) {
if ((c == ']' && stack.peek() == '{') || (c == '}' && stack.peek() == '[')) {
count++;
}
stack.pop();
}
}
return count;
}
29、 棋子移动次数
一个棋盘上面有 n 个棋子 0 < n < 2019，输入一个数组 ai 表示当前各个棋子的位置，输入移动次数 m，输入 bi 表示要移动棋子的位置，每次只能将要移动的棋子向右移动一个位置，如果目标位置有棋子，则取消当次移动，输出移动后的数字 ai。
解答：
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 读取棋子数量
int[] positions = new int[n];
Set<Integer> pieces = new HashSet<>(); // 使用Set存储棋子位置，便于快速查找
Map<Integer, Integer> posToIndex = new HashMap<>(); // 位置->索引的映射
for (int i = 0; i < n; i++) { // 读取初始棋子位置
positions[i] = scanner.nextInt();
pieces.add(positions[i]);
posToIndex.put(positions[i], i); // 建立映射
}
int m = scanner.nextInt(); // 读取移动次数
for (int i = 0; i < m; i++) { // 处理每次移动
int movePos = scanner.nextInt(); // 要移动的棋子位置
if (pieces.contains(movePos)) { // 检查该位置是否有棋子
int targetPos = movePos + 1; // 向右移动一个位置
if (!pieces.contains(targetPos)) { // 检查目标位置是否有棋子
pieces.remove(movePos); // 从原位置移除
pieces.add(targetPos); // 添加到新位置
int index = posToIndex.get(movePos); // 找到对应的索引，直接更新
positions[index] = targetPos; // 更新数据结构
posToIndex.remove(movePos); // 更新映射
posToIndex.put(targetPos, index);
}
// 如果目标位置有棋子，则取消移动（什么都不做）
}
// 如果要移动的位置没有棋子，也取消移动
}
// 输出最终位置（按照原来的顺序）
for (int i = 0; i < n; i++) {
System.out.print(positions[i]);
if (i < n - 1) {
System.out.print(" ");
}
}
System.out.println();
}
30、 定时炸弹
定时炸弹上有很多带有数字的按钮，当倒计时结束时，当且仅当有两个按钮被触发，且按钮数字和为 k 时，炸弹就会爆炸。输入为两行，第一行是按钮的个数 n 和使得炸弹爆炸的和 k，第二行是每个按钮代表的数字。思路：在数组中删除最少的元素，使得剩下的任意两个数的和都不等于 k。
import java.util.HashMap;
import java.util.Scanner;
public class BombDefuse {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
}
System.out.println(minDeletion(nums, k));
}
public static int minDeletion(int[] nums, int k) {
HashMap<Integer, Integer> freq = new HashMap<>();
int deletions = 0;
// 统计每个数字出现的频率
for (int num : nums) {
freq.put(num, freq.getOrDefault(num, 0) + 1);
}
// 处理每个数字
for (int num : nums) {
if (!freq.containsKey(num)) continue;
int complement = k - num;
if (freq.containsKey(complement)) {
// 处理数字对
if (num == complement) {
// 相同数字的情况，需要保留最多一个
deletions += freq.get(num) - 1;
freq.remove(num);
} else {
// 不同数字的情况，删除出现次数较少的那个
if (freq.get(num) > freq.get(complement)) {
deletions += freq.get(complement);
freq.remove(complement);
}
}
}
}
return deletions;
}
}