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;
    }
}