力扣第357场周赛补题

6925. 故障键盘 - 力扣（LeetCode）

思路：模拟

class Solution {
public:string finalString(string s) {string res;for(auto c : s){if(c == 'i') reverse(res.begin(), res.end());else res += c;}return res;}
};

6953. 判断是否能拆分数组 - 力扣（LeetCode）

思路：脑筋急转弯

class Solution {
public:bool canSplitArray(vector<int>& nums, int m) {int n = nums.size();if(n <= 2) return true;for(int i = 0; i < n - 1; i ++ )if(nums[i] + nums[i + 1] >= m) return true;return false;}
};

2812. 找出最安全路径 - 力扣（LeetCode）

思路：多源bfs+倒序枚举+并查集

class Solution {
public:int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};typedef pair<int, int> PII;int maximumSafenessFactor(vector<vector<int>>& grid) {int n = grid.size();vector<PII> q;vector<vector<int>> dist(n, vector<int>(n, -1));for(int i = 0; i < n; i ++ )for(int j = 0; j < n; j ++ )if(grid[i][j]){q.emplace_back(i, j);dist[i][j] = 0;}vector<vector<PII>> groups = {q};//groups每一层就代表的到1的距离相同的点//第0层就是1那些点，然后第一层就是第一层遍历的点，以此类推while (q.size()){vector<PII> nq;for(auto &[i, j] : q){for (int k = 0; k < 4; k ++ ) {int x = i + dx[k], y = j + dy[k];if(x >= 0 && x < n && y >= 0 && y < n && dist[x][y] < 0){nq.emplace_back(x, y);dist[x][y] = groups.size();}}}groups.push_back(nq);q = move(nq);//move将nq强制转化为右值引用}//并查集vector<int> p(n * n);iota(p.begin(), p.end(), 0);//0,1,2,3,4...function<int(int)> find = [&](int x) -> int {if(p[x] != x) return p[x] = find(p[x]); return p[x];};//因为最后还加了一层空数组，所以减2for(int res = groups.size() - 2; res > 0; res -- ){for(auto &[i, j] : groups[res]){for (int k = 0; k < 4; k ++ ) {int x = i + dx[k], y = j + dy[k];if(x >= 0 && x < n && y >= 0 && y < n && dist[x][y] >= dist[i][j])p[find(x * n + y)] = find(i * n + j);}}if(find(0) == find(n * n - 1)) return res;}return 0;}
};