2023.4.9LeetCode第340场周赛

A. 对角线上的质数

思路

枚举所有对角线上的数，判断是否为质数
使用O(n)O(\\sqrt n)O(n​)的算法判断质数
判断x是否为质数，若x=a*b，只用考虑a<=b的情况，故只用枚举到n\\sqrt{n}n​

代码

class Solution {
public:bool isp(int x) {if (x == 1) return false;for (int i = 2; i * i <= x; i ++ ) {if (x % i == 0)return false;}return true;}int diagonalPrime(vector<vector<int>>& a) {int m = a.size();int ans = 0;for (int i = 0; i < m; i ++ ) {if (isp(a[i][i]))ans = max(ans, a[i][i]);if (isp(a[i][m - i - 1]))ans = max(ans, a[i][m - i - 1]);}return ans;}
};

B. 等值距离和

思路

将所有数按照相同元素分组
枚举每个组，计算绝对值之和时数组是有序的，可以分为前半部分和后半部分，设当前数为x，前半部分x较大，绝对值和为(x*前半部分的数量-前半部分的前缀和)，后半部分x较小，绝对值和为(后半部分的前缀和 - x*后半部分的数量)，两部分的前缀和分别用两个变量维护

代码

class Solution {
public:typedef long long ll;vector<long long> distance(vector<int>& a) {unordered_map<int, vector<int>> mp;int n = a.size();for (int i = 0; i < n; i ++ ) {mp[a[i]].push_back(i);}vector<ll> ans(n);for (auto& [k, v] : mp) {int m = v.size();if (m == 1) continue;ll s = 0;for (int i = 0; i < m; i ++ )s += v[i];ll t = 0;for (int i = 0; i < m; i ++ ) {s -= v[i];ans[v[i]] = ((ll)v[i] * i) - t + (s - (ll)v[i] * (m - i - 1));t += v[i];}}return ans;}
};

C. 最小化数对的最大差值

思路

二分，答案越大越能满足，越小越不能满足，具有二分性
使用贪心的策略判断，将数组排序后尽量选择相邻的两个数，满足条件向后移动两位，不满足则向后移动一位

代码

class Solution {
public:int minimizeMax(vector<int>& a, int p) {sort(a.begin(), a.end());int n = a.size();int l = 0, r = 1e9;while (l < r) {int mid = l + r >> 1;if (check(mid, a, p)) r = mid;else l = mid + 1;}return l;}bool check(int x, vector<int>& a, int p) {int t = p;for (int i = 0; i + 1 < a.size();) {if (a[i + 1] - a[i] <= x) {p -- ;i += 2;                } else i ++ ;}return p <= 0;}
};

D. 网格图中最少访问的格子数

思路

bfs

代码

#define x first
#define y secondclass Solution {
public:typedef pair<int, int> PII;int minimumVisitedCells(vector<vector<int>>& g) {int n = g.size();int m = g[0].size();vector<vector<int>> d(n, vector<int>(m, -1));d[0][0] = 1;queue<PII> q;q.push({0, 0});while (q.size()) {auto t = q.front();q.pop();for (int k = t.y + 1; k <= min(g[t.x][t.y] + t.y, m - 1); k ++ ) {if (d[t.x][k] == -1) {d[t.x][k] = d[t.x][t.y] + 1;if (t.x == n - 1 && k == m - 1)return d[t.x][k];q.push({t.x, k});}}for (int k = t.x + 1; k <= min(g[t.x][t.y] + t.x, n - 1); k ++ ) {if (d[k][t.y] == -1) {d[k][t.y] = d[t.x][t.y] + 1;if (k == n - 1 && t.y == m - 1)return d[k][t.y];q.push({k, t.y});}}}return d[n - 1][m - 1];}
};