力扣第 340 场周赛

题目链接：https://leetcode.cn/contest/weekly-contest-340/

# T1. 对角线上的质数

链接：https://leetcode.cn/problems/prime-in-diagonal/

	class Solution {
	public int diagonalPrime(int[][] nums) {
	int n = nums.length;
	int max = 0;
	for (int i = 0; i < n; ++i) {
	if (max < nums[i][i] && isPrime(nums[i][i])) {
	max = nums[i][i];
	}
	if (max < nums[i][n - 1 - i] && isPrime(nums[i][n - 1 - i])) {
	max = nums[i][n - 1 - i];
	}
	}

	return max;
	}

	private boolean isPrime(int k) {
	if (k < 2) return false;

	int q = (int) Math.sqrt(k);

	for (int i = 2; i <= q; ++i) {
	if (k % i == 0) return false;
	}

	return true;
	}
	}

链接：https://leetcode.cn/problems/sum-of-distances/

将数组中的相同值的下标分成一组
计算每一组内的各个下标的距离之和，这个可以使用递推进行计算，减少时间复杂度：
- dp[i] = dp[i-1] + (i-1) * (arr[i] - arr[i-1]) ， dp[i] 表示 0, 1, ... i-1 到 i 的距离之和

	class Solution {
	public long[] distance(int[] nums) {
	int n = nums.length;
	Map<Integer, List<Integer>> map = new HashMap<>();

	for (int i = 0; i < n; ++i) {
	List<Integer> list = map.get(nums[i]);
	if (list == null) {
	list = new ArrayList<>();
	list.add(i);
	map.put(nums[i], list);
	} else {
	list.add(i);
	}
	}

	long[] arr = new long[n];
	for (Map.Entry<Integer, List<Integer>> e : map.entrySet()) {
	List<Integer> vals = e.getValue();
	if (vals != null && vals.size() > 1) {
	int sz = vals.size();
	long[] dp = new long[sz];

	for (int i = sz - 2; i >= 0; --i) {
	dp[i] = dp[i + 1] + (long) (sz - 1 - i) * (vals.get(i + 1) - vals.get(i));
	}

	long preSum = 0;
	for (int i = 0; i < sz; ++i) {
	if (i > 0) {
	preSum += (long) i * (vals.get(i) - vals.get(i - 1));
	}
	arr[vals.get(i)] = preSum + dp[i];
	}
	}

	}

	return arr;
	}
	}

链接：

具体见代码注释

	class Solution {
	public int minimizeMax(int[] nums, int p) {
	int n = nums.length;
	if (n < 2 \|\| p < 1) return 0;

	Arrays.sort(nums);

	int left = 0, right = nums[n - 1] - nums[0];
	// 标记数组
	boolean[] vis = new boolean[n];

	// 二分搜索每一个值
	while (left < right) {
	int mid = left + (right - left) / 2;
	Arrays.fill(vis, false);
	int pair = 0;

	for (int i = 1, j = 0; pair < p && i < n; ++i) {
	while (j < i && (nums[i] - nums[j] > mid \|\| vis[j])) ++j;
	if (j < i) {
	// 找到一对 <= mid 差值对
	vis[i] = true;
	vis[j] = true;
	++pair;
	}
	}

	// 当前枚举的 mid 已经找到了 p 对差值对，可能还会有更小的
	if (pair == p) right = mid;
	// 没有找到 <= mid 的 p 对差值对，需要扩大查找范围
	else left = mid + 1;
	}

	return left;
	}
	}

题目链接：https://leetcode.cn/problems/minimum-number-of-visited-cells-in-a-grid/

BFS 应用，需要使用 dis 来标记已经到达过的点

	class Solution {
	public int minimumVisitedCells(int[][] grid) {
	int m = grid.length;
	int n = grid[0].length;
	// 处理特殊情况
	if (m < 2 && n < 2) return 1;

	Queue<int[]> que = new ArrayDeque<>();
	// 记录步数
	int[][] dis = new int[m][n];

	que.offer(new int[] {0, 0});
	dis[0][0] = 1;

	while (!que.isEmpty()) {
	for (int i = que.size(); i > 0; --i) {
	int[] d = que.poll();
	int cx = d[0];
	int cy = d[1];

	for (int x = cx + 1; x < m && x <= cx + grid[cx][cy]; ++x) {
	if (dis[x][cy] == 0) {
	// 没访问过
	que.offer(new int[] {x, cy});
	dis[x][cy] = dis[cx][cy] + 1;
	// 到达目标点
	if (x == m - 1 && cy == n - 1) return dis[x][cy];
	}
	}

	for (int y = cy + 1; y < n && y <= cy + grid[cx][cy]; ++y) {
	if (dis[cx][y] == 0) {
	// 没访问过
	que.offer(new int[] {cx, y});
	dis[cx][y] = dis[cx][cy] + 1;
	// 到达目标点
	if (cx == m - 1 && y == n - 1) return dis[cx][y];
	}
	}
	}
	}

	return -1;
	}
	}