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