LeetCode Biweekly Contest 113

8039. Minimum Right Shifts to Sort the Array

给你一个长度为 n 下标从 0 开始的数组 nums ，数组中的元素为 互不相同 的正整数。请你返回让 nums 成为递增数组的 最少右移 次数，如果无法得到递增数组，返回 -1 。

一次 右移 指的是同时对所有下标进行操作，将下标为 i 的元素移动到下标 (i + 1) % n 处。

测试样例

输入：nums = [3,4,5,1,2]

输出：2

解释：第一次右移后，nums = [2,3,4,5,1] 。第二次右移后，nums = [1,2,3,4,5] 。现在 nums 是递增数组了，所以答案为 2 。

解答：暴力枚举右移情况，判断最少移动次数。

class Solution {
    public int minimumRightShifts(List<Integer> nums) {
        int[] arr = new int[nums.size()];
        int offset = 0;
        for (int n : nums) {
            arr[offset++] = n;
        }

        int count = 0;
        while (!isValid(arr) && count < arr.length) {
            int st = arr[arr.length - 1];
            for (int i = arr.length - 1; i >= 0; --i) {
                if (i == 0) {
                    arr[i] = st;
                } else {
                    arr[i] = arr[i - 1];
                }
            }
            ++count;
        }
        return count < arr.length ? count : -1;
    }

    private boolean isValid(int[] arr) {
        for (int i = 1; i < arr.length; ++i) {
            if (arr[i] < arr[i - 1]) {
                return false;
            }
        }
        return true;
    }
}

100020. Minimum Array Length After Pair Removals

给你一个下标从 0 开始的 非递减 整数数组 nums 。

你可以执行以下操作任意次：

• 选择 两个 下标 i 和 j ，满足 i < j 且 nums[i] < nums[j] 。
• 将 nums 中下标在 i 和 j 处的元素删除。剩余元素按照原来的顺序组成新的数组，下标也重新从 0 开始编号。

请你返回一个整数，表示执行以上操作任意次后（可以执行 0 次），nums 数组的 最小 数组长度。

测试样例：

输入：nums = [1,3,4,9]

输出：0

解释：

一开始，nums = [1, 3, 4, 9] 。
第一次操作，我们选择下标 0 和 1 ，满足 nums[0] < nums[1] <=> 1 < 3 。
删除下标 0 和 1 处的元素，nums 变成 [4, 9] 。
下一次操作，我们选择下标 0 和 1 ，满足 nums[0] < nums[1] <=> 4 < 9 。
删除下标 0 和 1 处的元素，nums 变成空数组 [] 。
所以，可以得到的最小数组长度为 0 。

解答: 真的是痛恨脑经急转弯。这道题目主要是寻找出现次数最多的数字，并记录它出现的次数。如果它出现的次数大于总数的一半，那么它一定无法被完全消去，否则判断数组长度的奇偶性。

class Solution {
    public int minLengthAfterRemovals(List<Integer> nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int max = 0;
        for (int n : nums) {
            int curCount = map.getOrDefault(n, 0) + 1;
            max = Math.max(max, curCount);
            map.put(n, curCount);
        }
        int len = nums.size();
        if (len >= 2 * max) {
            return len % 2;
        } else {
            return max - (len - max);
        }
    }
}

6988. Count Pairs of Points With Distance k

给你一个 二维 整数数组 coordinates 和一个整数 k ，其中 coordinates[i] = [xi, yi] 是第 i 个点在二维平面里的坐标。

我们定义两个点 (x1, y1) 和 (x2, y2) 的 距离 为 (x1 XOR x2) + (y1 XOR y2) ，XOR 指的是按位异或运算。

请你返回满足 i < j 且点 i 和点 j之间距离为 k 的点对数目。

测试样例：

输入：coordinates = [[1,2],[4,2],[1,3],[5,2]], k = 5

输出：2

解释：

以下点对距离为 k ：

• (0, 1)：(1 XOR 4) + (2 XOR 2) = 5 。
• (2, 3)：(1 XOR 5) + (3 XOR 2) = 5 。

解答: 0 <= k <= 100是一个非常重要的提示，因为(x1 XOR x2) + (y1 XOR y2) = k，且x1 XOR x2 >=0，且y1 XOR y2 >= 0。这样枚举所有0 <= x1 XOR x2 <= 100可能情况，就能得到对应的x2和y2值，类和一下x2, y2出现次数。

class Solution {
    private static final long mul = 1_000_500;

    public int countPairs(List<List<Integer>> coordinates, int k) {
        HashMap<Long, Integer> count = new HashMap<>();
        int res = 0;
        for (List<Integer> coor : coordinates) {
            int x = coor.get(0), y = coor.get(1);
            for (int i = 0; i <= k; ++i) {
                int xt = i ^ x, yt = (k - i) ^ y;
                long find = xt * mul + yt;
                res += count.getOrDefault(find, 0);
            }
            long key = x * mul + y;
            count.put(key, count.getOrDefault(key, 0) + 1);
        }
        return res;
    }
}

100041. Minimum Edge Reversals So Every Node Is Reachable

给你一个 n 个点的 简单有向图 （没有重复边的有向图），节点编号为 0 到 n - 1 。如果这些边是双向边，那么这个图形成一棵 树 。

给你一个整数 n 和一个 二维 整数数组 edges ，其中 edges[i] = [ui, vi] 表示从节点 ui 到节点 vi 有一条 有向边 。

边反转 指的是将一条边的方向反转，也就是说一条从节点 ui 到节点 vi 的边会变为一条从节点 vi 到节点 ui 的边。

对于范围 [0, n - 1] 中的每一个节点 i ，你的任务是分别 独立 计算 最少 需要多少次 边反转 ，从节点 i 出发经过 一系列有向边 ，可以到达所有的节点。

请你返回一个长度为 n 的整数数组 answer ，其中 answer[i]表示从节点 i 出发，可以到达所有节点的 最少边反转 次数。

测试样例：

输入：n = 4, edges = [[2,0],[2,1],[1,3]]

输出：1,1,0,2]

解释：

对于节点 0 ：反转 [2,0] ，从节点 0 出发可以到达所有节点。
所以 answer[0] = 1 。
对于节点 1 ：反转 [2,1] ，从节点 1 出发可以到达所有节点。
所以 answer[1] = 1 。
对于节点 2 ：不需要反转就可以从节点 2 出发到达所有节点。
所以 answer[2] = 0 。
对于节点 3 ：反转 [1,3] 和 [2,1] ，从节点 3 出发可以到达所有节点。
所以 answer[3] = 2 。

解答: 这道题目难度不大。首先我们假定0是根，计算出从0开始，最少边反转次数。第二次我们从0开始遍历，如果父节点 -> 子节点，那么子节点的最小边反转次数 = 父节点次数 + 1，否则 = 父节点 - 1（这个性质非常重要，想明白的，就能轻松AK了）。

class Solution {
    private List<Integer>[] edges, reverse;

    public int[] minEdgeReversals(int n, int[][] _edges) {
        edges = new List[n];
        reverse = new List[n];
        for (int i = 0; i < n; ++i) {
            edges[i] = new ArrayList<>();
            reverse[i] = new ArrayList<>();
        }
        for (int[] e : _edges) {
            edges[e[0]].add(e[1]);
            reverse[e[1]].add(e[0]);
        }

        int[] res = new int[n];
        Arrays.fill(res, -1);
        res[0] = initialZero(0, -1);
        dfsScore(0, -1, res);
        return res;
    }

    private int initialZero(int cur, int last) {
        int res = 0;
        for (int s : edges[cur]) {
            if (s != last) {
                res += initialZero(s, cur);
            }
        }

        for (int s : reverse[cur]) {
            if (s != last) {
                res += 1;
                res += initialZero(s, cur);
            }
        }
        return res;
    }

    private void dfsScore(int cur, int pre, int[] res) {
        for (int s : edges[cur]) {
            if (s != pre) {
                res[s] = res[cur] + 1;
                dfsScore(s, cur, res);
            }
        }

        for (int s : reverse[cur]) {
            if (s != pre) {
                res[s] = res[cur] - 1;
                dfsScore(s, cur, res);
            }
        }
    }
}