2023.2.26LeetCode第334场周赛

A. 左右元素和的差值

思路

前缀和+后缀和

代码

class Solution {
public:vector<int> leftRigthDifference(vector<int>& nums) {int n = nums.size();vector<int> l(n), r(n), ans(n);for (int i = 1; i < n; i ++ )l[i] = l[i - 1] + nums[i - 1];for (int i = n - 2; i >= 0; i -- )r[i] = r[i + 1] + nums[i + 1];for (int i = 0; i < n; i ++ )ans[i] = abs(l[i] - r[i]);return ans;}
};

B. 找出字符串的可整除数组

思路

高精度除法，模拟列示除法计算，每次计算的正好是前i位的数除以m的结果，看余数是否为0即为答案

代码

class Solution {
public:vector<int> divisibilityArray(string word, int m) {vector<int> ans;long long d = 0;for (int i = 0; i < word.size(); i ++ ) {d = d * 10 + word[i] - '0';d %= m;ans.push_back(!d);}return ans;}
};

C. 求出最多标记下标

思路

二分+贪心
排序不影响结果，先排序便于查找
如果可以找到k对匹配，那么小于k对一定能找到，去掉几个数
即越小越能找到，具有二分性，使用二分算法找到最多的匹配数量
给定k，判断能否找到k对匹配
nums[i] * 2 <= nums[j]，nums[i]越小，nums[j]越大，越容易满足条件
故选择最小的k个数和最大的k个数
若能一一匹配说明能找到k对匹配

代码

class Solution {
public:int maxNumOfMarkedIndices(vector<int>& nums) {sort(nums.begin(), nums.end());int n = nums.size();int l = 0, r = n / 2;while (l < r) {int mid = l + r + 1 >> 1;if (check(mid, nums)) l = mid;else r = mid - 1;}return l * 2;}bool check(int mid, vector<int>& a) {for (int i = 0, j = a.size() - mid; i < mid; i ++ , j ++ ) {if (a[i] * 2 > a[j])return false;}return true;}
};

D. 在网格图中访问一个格子的最少时间

思路

只要第一步能走，就一定能走到任何一点，因为遇到时间更大的，可以先往回走，再回来，消耗时间
可看作每个点与上下左右四个点连通
使用Dijkstra最短路的思想，每次找出离起始点最近的点，它的距离是最短的，然后用它更新它的邻居的最短路径值
如果遇到不能直接走的，需要回头走消耗时间，判断奇偶性后更新最短路径值

代码

class Solution {
public:int n, m;struct Node {int x, y, ti;bool operator < (const Node a) const {return ti > a.ti;}};vector<vector<int>> f = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};int minimumTime(vector<vector<int>>& grid) {n = grid.size(), m = grid[0].size();if (grid[0][1] > 1 && grid[1][0] > 1) return -1;priority_queue<Node> q;q.push({0, 0, 0});vector<vector<int>> d(n, vector<int>(m, -1));while (q.size()) {auto t = q.top();q.pop();for (int i = 0; i < 4; i ++ ) {int x = t.x + f[i][0], y = t.y + f[i][1];if (x < 0 || x >= n || y < 0 || y >= m || d[x][y] != -1) continue;if (t.ti + 1 >= grid[x][y]) { //能直接走d[x][y] = t.ti + 1;} else { //不能直接走if ((grid[x][y] - t.ti) % 2 == 0)d[x][y] = grid[x][y] + 1;elsed[x][y] = grid[x][y];}q.push({x, y, d[x][y]});}}return d[n - 1][m - 1];}
};