2024.05.25 第 131 场双周赛

本文主要是介绍2024.05.25 第 131 场双周赛，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Leetcode 第 131 场双周赛

求出出现两次数字的 XOR 值

[Leetcode 求出出现两次数字的 XOR 值](https://leetcode.cn/problems/find-the-xor-of-numbers-which-appear-twice/description/]

给你一个数组 nums ，数组中的数字要么出现一次，要么出现两次。
请你返回数组中所有出现两次数字的按位_ _XOR 值，如果没有数字出现过两次，返回 0 。

第 131 场双周赛_1.png

用 HashMap 存储出现两次的数字，然后对数字进行 XOR 计算，即 ‘^’。

完整代码

class Solution {public int duplicateNumbersXOR(int[] nums) {Map<Integer, Integer> map = new HashMap<Integer, Integer>();for (int num : nums) {map.put(num, map.getOrDefault(num, 0) + 1);}int res = 0;Iterator<Map.Entry<Integer, Integer>> iterator = map.entrySet().iterator();while (iterator.hasNext()) {Map.Entry<Integer, Integer> entry = iterator.next();if (entry.getValue() > 1) {res ^= entry.getKey();}}return res;}
}

查询数据中元素的出现位置

Leetcode 查询数组中元素的出现位置

给你一个整数数组 nums ，一个整数数组 queries 和一个整数 x 。
对于每个查询 queries[i] ，你需要找到 nums 中第 queries[i] 个 x 的位置，并返回它的下标。如果数组中 x 的出现次数少于 queries[i] ，该查询的答案为 -1 。
请你返回一个整数数组 answer ，包含所有查询的答案。

第 131 场双周赛_2.png

先找出数组中值为 x 的位置数组，再从数组中获得结果。

完整代码

class Solution {public int[] occurrencesOfElement(int[] nums, int[] queries, int x) {List<Integer> list = new ArrayList<Integer>();for (int i = 0; i < nums.length; i++) {if (nums[i] == x) {list.add(i);}}for (int i = 0; i < queries.length; i++) {if (queries[i] > list.size()) {queries[i] = -1;} else {queries[i] = list.get(queries[i] - 1);}}return queries;}
}

所有球里面不同颜色的数目

Leetcode 所有球里面不同颜色的数目

给你一个整数 limit 和一个大小为 n x 2 的二维数组 queries 。
总共有 limit + 1 个球，每个球的编号为 [0, limit] 中一个 互不相同 的数字。一开始，所有球都没有颜色。queries 中每次操作的格式为 [x, y] ，你需要将球 x 染上颜色 y 。每次操作之后，你需要求出所有球中不同颜色的数目。
请你返回一个长度为 n 的数组 result ，其中 result[i] 是第 i 次操作以后不同颜色的数目。
注意，没有染色的球不算作一种颜色。

第 131 场双周赛_3.png

需要求出每次操作之后颜色的种类数。
需要用到两个 Map，一个 Map 记录每个球的颜色编号；一个 Map 记录每个颜色的数目，每次操作后获取颜色 Map 的大小既是所求结果。

更新 Map 球的颜色，直接使用 map.put()进行更新
更新球颜色数目的 Map，
如果在记录球颜色的 Map 中有这个球的记录，则需要将此 Map 中颜色的数量减一；并如果其减为零，需要从 Map 中移除。
更新颜色的数目加一。

这里可以使用数组来记录球的颜色，这样可能有些球的颜色一直没有更新，就会出现浪费内存的情况，因此使用 Map 来存储球的颜色，使用的内存更小一点。

完整代码

class Solution {public int[] queryResults(int limit, int[][] queries) {Map<Integer, Integer> balls = new HashMap<Integer, Integer>();Map<Integer, Integer> map = new HashMap<Integer, Integer>();int[] res = new int[queries.length];for (int i = 0; i < queries.length; i++) {int ball = queries[i][0];int color = queries[i][1];if (balls.containsKey(ball)) {int val = balls.get(ball);if (map.get(val) == 1) {map.remove(val);} else {map.put(val, map.get(val) - 1);}}balls.put(ball, color);map.put(color, map.getOrDefault(color, 0) + 1);res[i] = map.size();}return res;}
}

物块放置查询

Leetcode 物块放置查询

有一条无限长的数轴，原点在 0 处，沿着 x 轴正方向无限延伸。
给你一个二维数组 queries ，它包含两种操作：

操作类型 1 ：queries[i] = [1, x] 。在距离原点 x 处建一个障碍物。数据保证当操作执行的时候，位置 x 处没有任何障碍物。
操作类型 2 ：queries[i] = [2, x, sz] 。判断在数轴范围 [0, x] 内是否可以放置一个长度为 sz 的物块，这个物块需要完全放置在范围 [0, x] 内。如果物块与任何障碍物有重合，那么这个物块不能被放置，但物块可以与障碍物刚好接触。注意，你只是进行查询，并不是真的放置这个物块。每个查询都是相互独立的。

请你返回一个 boolean 数组results ，如果第 i 个操作类型 2 的操作你可以放置物块，那么 results[i] 为 true ，否则为 false 。

第 131 场双周赛_4.png

对于操作类型 1，添加障碍物，将其放入一个数组中，存储障碍物的坐标，并保证坐标是递增的。
对于操作类型2，判断是否能放置物块，在障碍物数组中遍历到查询的位置，判断障碍物之间的间距是否大于等于物块的长度。

完整代码

class Solution {public List<Boolean> getResults(int[][] queries) {List<Integer> barries = new LinkedList<Integer>();List<Boolean> res = new ArrayList<Boolean>();for (int i = 0; i < queries.length; i++) {if (queries[i].length == 2) {// 加障碍int index = 0;while (index < barries.size() && queries[i][1] > barries.get(index)) {index++;}barries.add(index, queries[i][1]);} else {int tag = 0;// 判断是否可放入if (queries[i][2] > queries[i][1]) {res.add(false);continue;}int before = 0;for (Integer num : barries) {if (num > queries[i][1]) break;if ((num - before) >= queries[i][2]) {tag = 1;break;}before = num;}if ((queries[i][1] - before) >= queries[i][2]) tag = 1;if (tag == 1) res.add(true);else res.add(false);}}return res;}
}