6361. 对角线上的质数
给你一个下标从 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] 。
示例 1：
输入：nums = [[1,2,3],[5,6,7],[9,10,11]]
输出：11
解释：数字 1、3、6、9 和 11 是所有 "位于至少一条对角线上" 的数字。由于 11 是最大的质数，故返回 11 。
示例 2：
输入：nums = [[1,2,3],[5,17,7],[9,11,10]]
输出：17
解释：数字 1、3、9、10 和 17 是所有满足"位于至少一条对角线上"的数字。由于 17 是最大的质数，故返回 17 。
提示：
1 <= nums.length <= 300
nums.length == numsi.length
1 <= nums[i][j] <= 4*10^6解答：按照题意暴力解答
class Solution {
public int diagonalPrime(int[][] nums) {
int n = nums.length;
boolean[][] isPrime = new boolean[2][n]; // 用于存储两条对角线上的数是否为质数
int maxPrime = 0; // 存储最大的质数
for (int i = 0; i < n; i++) {
int val1 = nums[i][i];
int val2 = nums[i][n - i - 1];
if (isPrime(val1)) {
isPrime[0][i] = true; // 标记第一条对角线上的数为质数
maxPrime = Math.max(maxPrime, val1);
}
if (isPrime(val2)) {
isPrime[1][i] = true; // 标记第二条对角线上的数为质数
maxPrime = Math.max(maxPrime, val2);
}
}
return maxPrime;
}
// 判断一个数是否为质数
private boolean isPrime(int num) {
if (num <= 1) {
return false;
}
for (int i = 2; i * i <= num; i++) {
if (num % i == 0) {
return false;
}
}
return true;
}
}
6360. 等值距离和
给你一个下标从 0 开始的整数数组 nums 。现有一个长度等于 nums.length 的数组 arr 。对于满足 nums[j] == nums[i] 且 j != i 的所有 j ，arr[i] 等于所有 |i - j| 之和。如果不存在这样的 j ，则令 arr[i] 等于 0 。
返回数组 arr 。
示例 1：
输入：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 的其他下标。
示例 2：
输入：nums = [0,5,3]
输出：[0,0,0]
解释：因为 nums 中的元素互不相同，对于所有 i ，都有 arr[i] = 0 。
提示：
1 <= nums.length <= 10^5
0 <= nums[i] <= 10^9解答：哈希表+前缀和
最后三个用例一直没过，原来是计算的时候，没转long导致右侧溢出
res[idx] =(sum-left)-(len-i)*idx+idx*i-left;public class Solution {
public long[] distance(int[] nums) {
int n = nums.length;
long[] res = new long[n];
Map<Integer, ArrayList<Integer>> indexMap = new HashMap<>();
for (int i = 0; i < n; i++) {
int num = nums[i];
if (!indexMap.containsKey(num)) {
indexMap.put(num, new ArrayList<>());
}
indexMap.get(num).add(i);
}
for (Map.Entry<Integer, ArrayList<Integer>> entry : indexMap.entrySet()) {
ArrayList<Integer> indices = entry.getValue();
Collections.sort(indices);
long left=0,sum=0;
for (int a:indices)sum+=a;
int len=indices.size();
for (int i = 0; i < indices.size(); i++) {
int idx = indices.get(i);
res[idx] =(sum-left)-(len-i*1L)*idx+1L*idx*i-left;
left+=idx;
}
}
return res;
}
}6359. 最小化数对的最大差值
给你一个下标从 0 开始的整数数组 nums 和一个整数 p 。请你从 nums 中找到 p 个下标对，每个下标对对应数值取差值，你需要使得这 p 个差值的 最大值 最小。同时，你需要确保每个下标在这 p 个下标对中最多出现一次。
对于一个下标对 i 和 j ，这一对的差值为 |nums[i] - nums[j]| ，其中 |x| 表示 x 的 绝对值 。
请你返回 p 个下标对对应数值 最大差值 的 最小值 。
示例 1：
输入：nums = [10,1,2,7,1,3], p = 2
输出：1
解释：第一个下标对选择 1 和 4 ，第二个下标对选择 2 和 5 。
最大差值为 max(|nums[1] - nums[4]|, |nums[2] - nums[5]|) = max(0, 1) = 1 。所以我们返回 1 。
示例 2：
输入：nums = [4,2,1,2], p = 1
输出：0
解释：选择下标 1 和 3 构成下标对。差值为 |2 - 2| = 0 ，这是最大差值的最小值。
提示：
1 <= nums.length <= 10^5
0 <= nums[i] <= 10^9
0 <= p <= (nums.length)/2解答：贪心+二分
class Solution {
public int minimizeMax(int[] nums, int p) {
Arrays.sort(nums);
int n = nums.length;
int l = 0;
int r = nums[n - 1] - nums[0];
int res = r;
while(l <= r) {
int m = (l + r) / 2;
if (check(nums, p, m)) {
res = m;
r = m - 1;
} else {
l = m + 1;
}
}
return res;
}
private boolean check(int[] nums, int p, int d) {
int i = 1;
int cnt = 0;
while(i < nums.length) {
if (nums[i] - nums[i - 1] <= d) {
cnt++;
if (cnt == p) {
break;
}
i++;
}
i++;
}
return cnt >= p;
}
}6353. 网格图中最少访问的格子数
给你一个下标从 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 。
示例 1：
输入：grid = [[3,4,2,1],[4,2,3,1],[2,1,0,0],[2,4,0,0]]
输出：4
解释：上图展示了到达右下角格子经过的 4 个格子。
示例 2：
输入：grid = [[3,4,2,1],[4,2,1,1],[2,1,1,0],[3,4,1,0]]
输出：3
解释：上图展示了到达右下角格子经过的 3 个格子。
示例 3：
输入：grid = [[2,1,0],[1,0,0]]
输出：-1
解释：无法到达右下角格子。
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 10^5
1 <= m * n <= 10^5
0 <= grid[i][j] < m * n
grid[m - 1][n - 1] == 0解答：迪杰斯特拉+优先队列
import java.util.Comparator;
import java.util.PriorityQueue;
class Solution {
public int minimumVisitedCells(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] dist = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
dist[i][j] = Integer.MAX_VALUE;
}
}
dist[0][0] = 1;
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> dist[a[0]][a[1]]));
pq.offer(new int[]{0, 0});
while (!pq.isEmpty()) {
int[] cur = pq.poll();
int i = cur[0];
int j = cur[1];
if (i == m - 1 && j == n - 1) {
return dist[m - 1][n - 1];
}
for (int k = j + 1; k <= j + grid[i][j] && k < n; k++) {
if (dist[i][k] > dist[i][j] + 1) {
dist[i][k] = dist[i][j] + 1;
pq.offer(new int[]{i, k});
}
}
for (int k = i + 1; k <= i + grid[i][j] && k < m; k++) {
if (dist[k][j] > dist[i][j] + 1) {
dist[k][j] = dist[i][j] + 1;
pq.offer(new int[]{k, j});
}
}
}
return -1;
}
}
