6361. Prime In Diagonal
给你一个下标从 0 开始的二维整数数组 nums 。
返回位于 nums 至少一条 对角线 上的最大 质数 。如果任一对角线上均不存在质数，返回 0 。
注意：
- 如果某个整数大于 1 ，且不存在除 1 和自身之外的正整数因子，则认为该整数是一个质数。
- 如果存在整数 i ，使得 nums[i][i] = val 或者 nums[i][nums.length - i - 1]= val ，则认为整数 val 位于 nums 的一条对角线上。
在上图中，一条对角线是 [1,5,9] ，而另一条对角线是 [3,5,7] 。
测试样例
输入：nums = [[1,2,3],[5,6,7],[9,10,11]]
输出：11
解释：数字 1、3、6、9 和 11 是所有 "位于至少一条对角线上" 的数字。由于 11 是最大的质数，故返回 11 。
解答：这题就是暴力枚举所有对角线的数字，如果是质数就更新result
class Solution {
public int diagonalPrime(int[][] nums) {
int n = nums.length, res = 0;
for (int i = 0; i < n; ++i) {
if (isPrime(nums[i][i])) {
res = Math.max(res, nums[i][i]);
}
if (isPrime(nums[i][n - i - 1])) {
res = Math.max(res, nums[i][n - i - 1]);
}
}
return res;
}
private boolean isPrime(int n) {
if (n <= 1) return false;
for (int i = 2; i * i <= n; ++i) {
if (n % i == 0) return false;
}
return true;
}
}6360. Sum of Distances
给你一个下标从 0 开始的整数数组 nums 。现有一个长度等于 nums.length 的数组 arr 。对于满足 nums[j] == nums[i] 且 j != i 的所有 j ，arr[i] 等于所有 |i - j| 之和。如果不存在这样的 j ，则令 arr[i] 等于 0 。
返回数组 arr 。
请注意，二维数组的每一行上可以存在不同数量的元素。
测试样例：
输入：nums = [1,3,1,1,2]
输出：[5,0,3,4,0]
解释：
- i = 0 ，nums[0] == nums[2] 且 nums[0] == nums[3] 。因此，arr[0] = |0 - 2| + |0 - 3| = 5 。
- i = 1 ，arr[1] = 0 因为不存在值等于 3 的其他下标。
- i = 2 ，nums[2] == nums[0] 且 nums[2] == nums[3] 。因此，arr[2] = |2 - 0| + |2 - 3| = 3 。i = 3 ，nums[3] == nums[0] 且 nums[3] == nums[2] 。因此，arr[3] = |3 - 0| + |3 - 2| = 4 。
- i = 4 ，arr[4] = 0 因为不存在值等于 2 的其他下标。
解答: 哈希表聚合所有相同数字的位数，然后变化一下前缀和计算绝对值差之和。注意返回的是long[], 所以计算和的时候使用int可能有超出范围的风险。
class Solution {
public long[] distance(int[] nums) {
int len = nums.length;
long[] res = new long[len];
HashMap<Integer, ArrayList<Integer>> mem = new HashMap<Integer, ArrayList<Integer>>();
for (int i = 0; i < len; ++i) {
if (!mem.containsKey(nums[i])) {
mem.put(nums[i], new ArrayList<>());
}
mem.get(nums[i]).add(i);
}
for (Map.Entry<Integer, ArrayList<Integer>> kv : mem.entrySet()) {
if (kv.getValue().size() != 1) {
long rightSum = 0, leftSum = 0;
for (int i : kv.getValue()) {
rightSum += i;
}
long rightCount = kv.getValue().size(), leftCount = 0;
for (int i : kv.getValue()) {
leftSum += i;
rightSum -= i;
++leftCount;
--rightCount;
res[i] = leftCount * i - leftSum + rightSum - i * rightCount;
}
}
}
return res;
}
}6359. Minimize the Maximum Difference of Pairs
给你一个下标从 0 开始的整数数组 nums 和一个整数 p 。请你从 nums 中找到 p 个下标对，每个下标对对应数值取差值，你需要使得这 p 个差值的 最大值 最小。同时，你需要确保每个下标在这 p 个下标对中最多出现一次。
对于一个下标对 i 和 j ，这一对的差值为 |nums[i] - nums[j]| ，其中 |x| 表示 x 的 绝对值 。
请你返回 p 个下标对对应数值 最大差值 的 最小值 。
测试样例
输入：nums = [4,2,1,2], p = 1
输出：0
解释：
选择下标 1 和 3 构成下标对。差值为 |2 - 2| = 0 ，这是最大差值的最小值。
解答：注意这个：确保每个下标在这 p 个下标对中最多出现一次，一开始我没认真看条件直接Wrong Answer了一次。有这个条件之后，题目就变得容易很多了，排序之后，利用折半搜索可以寻找到答案。
折半搜索的时候，需要判断当前的mid是否满足要求。这个时候用贪婪即可以了。因为队列已经排序好，那么当前的数字能够找到pair就最好，否则继续寻找下一个数。因为下一个数一定比当前数字更大，所以能够配对的希望也会更大。
class Solution {
public int minimizeMax(int[] nums, int p) {
Arrays.sort(nums);
int min = 0, max = 1_000_000_000;
while (min < max) {
int mid = (min + max) / 2;
if (count(nums, mid) < p) {
min = mid + 1;
} else {
max = mid;
}
}
return min;
}
private long count(int[] nums, int target) {
int res = 0;
int pos = 0;
while (pos + 1 < nums.length) {
if (nums[pos + 1] - nums[pos] <= target) {
++res;
++pos;
}
++pos;
}
return res;
}
}6353. Minimum Number of Visited Cells in a Grid
给你一个下标从 0 开始的 m x n 整数矩阵 grid 。你一开始的位置在 左上角 格子 (0, 0) 。
当你在格子 (i, j) 的时候，你可以移动到以下格子之一：
- 满足 j < k <= grid[i][j] + j 的格子 (i, k) （向右移动），或者
- 满足 i < k <= grid[i][j] + i 的格子 (k, j) （向下移动）。
请你返回到达 右下角 格子 (m - 1, n - 1) 需要经过的最少移动格子数，如果无法到达右下角格子，请你返回 -1 。
测试样例
输入：grid = [[3,4,2,1],[4,2,3,1],[2,1,0,0],[2,4,0,0]]
输出：4
解答：这道题目的难点在于寻找能够到达当前位置的最小次数。我们可以利用TreeMap来存储可以到达当前位置的所有可能次数。那么map的firstKey就是最小次数。
然后我们可以利用优先队列在储存一个点可以到达的位置，如果当前位置不满足要求，那就出队并更新TreeMap。因为我们的遍历方式是从小到大遍历，如果当前节点不满足，之后的节点也不可能满足。出队就是安全的。
最后一个注意点，二维计算比较麻烦，所以我们将行列分开记忆计算。
class Solution {
public int minimumVisitedCells(int[][] grid) {
int col = grid[0].length;
TreeMap<Integer, Integer>[] colMems = new TreeMap[col];
PriorityQueue<int[]>[] colMarks = new PriorityQueue[col];
for (int i = 0; i < col; ++i) {
colMems[i] = new TreeMap<>();
colMarks[i] = new PriorityQueue<>((a, b) -> (a[0] - b[0]));
}
colMarks[0].add(new int[]{0, 0});
colMems[0].put(0, 1);
int offset = 0;
for (int[] row : grid) {
TreeMap<Integer, Integer> rowMem = new TreeMap<>();
PriorityQueue<int[]> rowMark = new PriorityQueue<>((a, b) -> (a[0] - b[0]));
for (int i = 0; i < col; ++i) {
while (!colMarks[i].isEmpty() && colMarks[i].peek()[0] < offset) {
int r = colMarks[i].poll()[1];
remove(colMems[i], r);
}
int min = Integer.MAX_VALUE;
if (!colMems[i].isEmpty()) {
min = Math.min(min, colMems[i].firstKey());
}
while (!rowMark.isEmpty() && rowMark.peek()[0] < i) {
int r = rowMark.poll()[1];
remove(rowMem, r);
}
if (!rowMem.isEmpty()) {
min = Math.min(min, rowMem.firstKey());
}
if (min != Integer.MAX_VALUE) {
++min;
int maxRowDis = row[i] + i, maxColDis = row[i] + offset;
rowMark.add(new int[]{maxRowDis, min});
add(rowMem, min);
colMarks[i].add(new int[]{maxColDis, min});
add(colMems[i], min);
if (offset == grid.length - 1 && i == col - 1) {
return min;
}
}
}
++offset;
}
return -1;
}
private void remove(Map<Integer, Integer> map, int key) {
int c = map.get(key);
if (c == 1) {
map.remove(key);
} else {
map.put(key, c - 1);
}
}
private void add(Map<Integer, Integer> map, int key) {
map.put(key, map.getOrDefault(key, 0) + 1);
}
}