LeetCode --- 452周赛
题目列表
3566. 等积子集的划分方案
3567. 子矩阵的最小绝对差
3568. 清理教室的最少移动
3569. 分割数组后不同质数的最大数目
一、等积子集的划分方案
由于本题的数据范围不大，我们可以暴力枚举所有可能的划分方式，代码如下
// C++
class Solution {
public:bool checkEqualPartitions(vector<int>& nums, long long target) {int n = nums.size();// 用二进制位的 0/1 对 nums 进行划分for(int i = 1; i < (1 << n) - 1; i++){long long mul[2] = {1, 1};for(int j = 0; j < n; j++){mul[i >> j & 1] *= nums[j];if(mul[i >> j & 1] > target){ // 在计算的过程中进行数值判断，防止数据超范围break;}}if(mul[0] == target && mul[1] == target){return true;}}return false;}
};
# Python
class Solution:def checkEqualPartitions(self, nums: List[int], target: int) -> bool:n = len(nums)for i in range(1, 1 << n):mul = [1, 1]for j in range(n):mul[i >> j & 1] *= nums[j]if mul[i >> j & 1] > target:breakif mul[0] == target and mul[1] == target:return Truereturn False
二、子矩阵的最小绝对差
由于数据范围不大，直接暴力模拟即可，代码如下
// C++
class Solution {
public:vector<vector<int>> minAbsDiff(vector<vector<int>>& grid, int k) {int n = grid.size(), m = grid[0].size();auto oneMinAbsDiff = [&](int x, int y)->int{set<int> st;for(int i = 0; i < k; i++){for(int j = 0; j < k; j++){st.insert(grid[x + i][y + j]);}}if(st.size() == 1) return 0;int ret = INT_MAX;for(auto it = ++st.begin(); it != st.end(); ++it){ret = min(ret, *it - *prev(it));}return ret;};vector ans(n - k + 1, vector<int>(m - k + 1));for(int i = 0; i <= n - k; i++){for(int j = 0; j <= m - k; j++){ans[i][j] = oneMinAbsDiff(i, j);}}return ans;}
};
# Python
class Solution:def minAbsDiff(self, grid: List[List[int]], k: int) -> List[List[int]]:n, m = len(grid), len(grid[0])ans = [[0] * (m - k + 1) for _ in range(n - k + 1)]for i in range(n - k + 1):rows = grid[i:i+k]for j in range(m - k + 1):a = []for row in rows:a.extend(row[j:j + k])a.sort()mn = inffor x, y in pairwise(a):if y > x:mn = min(mn, y - x)if mn < inf:ans[i][j] = mnreturn ans
三、清理教室的最少移动
求最短路径问题一般考虑 bfs、dfs 或者更高级的图的相关算法，本题用 bfs 就可以，但是我们一般写 bfs 只考虑走的步数，更复杂一些的会有障碍物，需要判断哪些结点不能走，为了防止结点重复走，还需要有一个 vis数组 标记走过的结点
本题的难点在于学生移动需要有能量，而某些结点能恢复能量，同时，对垃圾的收集的顺序不同，也会导致不同的步数，所以对于一个网格是否被标记为遍历过，还需要有额外的参数进行判断。
-
如何设计
vis数组的参数？- 基本参数，当前网格的位置信息
(x,y) - 走到当前网格所剩的能量
energy - 剩余还有哪些垃圾需要被处理，本参数记为
mask由二进制进行表示，需要先对垃圾进行编号0~n，然后将其映射到二进制的每一位 - 故有
vis[x][y][energy][mask] 表示到达网格 (x,y) 所剩余的能量为energy，剩余未被收集的垃圾为mask的结点状态是否被遍历过 - 时间复杂度为
vis的状态个数O(n*m*energy*2^k)，其中k为垃圾的个数
- 基本参数，当前网格的位置信息
代码如下
// C++
class Solution {static constexpr int dirs[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
public:int minMoves(vector<string>& classroom, int energy) {int n = classroom.size(), m = classroom[0].size();map<pair<int,int>, int> mp;int start_x = 0, start_y = 0;for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){if(classroom[i][j] == 'S'){start_x = i, start_y = j;}else if(classroom[i][j] == 'L'){mp[{i, j}] = mp.size();}}}vector vis(n, vector(m, vector(energy + 1, vector<bool>(1 << mp.size()))));int step = 0;queue<tuple<int,int,int,int>> q;q.emplace(start_x, start_y, energy, (1 << mp.size()) - 1);vis[start_x][start_y][energy][(1 << mp.size()) - 1] = true;while(q.size()){int sz = q.size();while(sz--){auto [x, y, e, mask] = q.front(); q.pop();if(mask == 0){ // 垃圾全部收集完return step;}for(int i = 0; i < 4; i++){int nx = x + dirs[i][0], ny = y + dirs[i][1];if(nx < 0 || nx >= n || ny < 0 || ny >= m || classroom[nx][ny] == 'X' || e == 0) // 如果越界、是障碍物、没有能量，则不能走continue;int new_e = classroom[nx][ny] == 'R' ? energy : e - 1;int new_mask = classroom[nx][ny] == 'L' ? (mask & ~(1 << mp[{nx, ny}])) : mask;if(!vis[nx][ny][new_e][new_mask]){q.emplace(nx, ny, new_e, new_mask);vis[nx][ny][new_e][new_mask] = true;}}}step++;}return -1;}
};
四、分割数组后不同质数的最大数目
将 nums 数组分为前缀 A 和 后缀 B，求 max(A中不同质数个数 + B中不同质数个数)，该问题可以转换成 nums 中不同质数个数 + 哪些质数能被计算两次。
-
nums中不同质数的个数，我们可以直接用哈希表计算处理- 前置问题：如何快速判断一个数字是否是质数，我们可以用埃氏筛进行预处理，具体见代码
-
哪些质数能被计算两遍？对于一个质数
x，我们只需要知道它出现的最左下标l和最右下标r，只要k 在 (l,r] 中，那么x对答案的贡献就能+1，而这就是区间 +1 操作，然后我们只要找出区间的+1次数最多的位置即可，即维护区间最大值-
区间+1和维护区间最大值，可以用线段树来维护 -
同时，由于会不断的跟新数组中的数组，质数的下标位置信息也会变化，故我们需要用
set维护质数的下标信息- 在通过质数下标数据对线段树进行跟新时，为了简化跟新判断逻辑，我们可以先对原本的操作进行撤销，然后再进行跟新操作即可
-
代码如下
//C++
#include <ranges>
const int MX = 1e5 + 5;
vector<bool> is_prime(MX, true);
int init = []{ // 预处理出所有的质数is_prime[0] = is_prime[1] = false;for(int i = 2; i < MX; i++){if(is_prime[i]){for(int j = 2*i; j < MX; j += i){is_prime[j] = false;}}}return 0;
}();
// 要求 质数的数量之和最大
// 转换成 总的不同质数个数 + 哪些质数能被计算两遍
// 对于任意一个质数来说，只要划分区间的点 k 在 (left, right] 之间，答案就能 +1
//=> 区间+1/-1问题 + 求区间最值问题，可以用 线段树 来维护
class SegTree{
public:SegTree(int n):t(n<<2), todo(n<<2){}SegTree(const vector<int>& a){int n = a.size();t.resize(n << 2);todo.resize(n << 2);build(a, 1, 0, n - 1);}void maintain(int o){t[o] = max(t[o << 1], t[o << 1 | 1]);}void build(const vector<int>& a, int o, int l, int r){if(l == r){t[o] = a[l];return;}int m = l + (r - l)/2;build(a, o << 1, l, m);build(a, o << 1 | 1, m + 1, r);maintain(o);}void do_(int o, int l, int r, int add){todo[o] += add;t[o] += add;}void down(int o, int l, int r){if(todo[o]){ // 判断是否有需要跟新的数据没有下放给子节点int m = l + (r - l)/2;do_(o << 1, l, m, todo[o]);do_(o << 1|1, m + 1, r, todo[o]);todo[o] = 0;}}void update(int o, int l, int r, int L, int R, int add){if(L <= l && r <= R){ // 到达该结点时，子节点的数据可以暂且不用更新，数据保存在 todo 数组中即可（懒更新）do_(o, l, r, add);return;}down(o, l, r); // 将 懒处理的数据 下发到子节点int m = l + (r - l)/2;if(m >= L) update(o << 1, l, m, L, R, add);if(m < R) update(o << 1|1, m + 1, r, L, R, add);maintain(o);}int query(){ // 由于本题只要求整个区间的最大值，所以直接返回根节点即可return t[1];}private:vector<int> t, todo;
};class Solution {
public:vector<int> maximumCount(vector<int>& nums, vector<vector<int>>& qs) {unordered_map<int,set<int>> pos;int n = nums.size();for(auto&& [idx, val] : nums | ranges::views::enumerate){ // 同时遍历下标和元素if(is_prime[val]){pos[val].insert(idx);}}SegTree t(n);for(auto [_, st] : pos){if(st.size() > 1){t.update(1, 0, n - 1, *st.begin() + 1, *st.rbegin(), 1);}}vector<int> ans(qs.size());for(auto&& [i, q] : qs | ranges::views::enumerate){ // 同时遍历下标和元素int j = q[0], val = q[1];if(is_prime[nums[j]]){auto & st = pos[nums[j]];if(st.size() > 1){ // 撤销原本的区间 +1 操作t.update(1, 0, n - 1, *st.begin() + 1, *st.rbegin(), -1);}st.erase(j);if(st.size() > 1){ // 跟新现在的区间 +1 操作t.update(1, 0, n - 1, *st.begin() + 1, *st.rbegin(), 1);}if(st.empty()){ // 维护 总的不同质数个数pos.erase(nums[j]);}}if(is_prime[val]){auto& st = pos[val];if(st.size() > 1){ // 撤销原本的区间 +1 操作t.update(1, 0, n - 1, *st.begin() + 1, *st.rbegin(), -1);}st.insert(j);if(st.size() > 1){ // 跟新现在的区间 +1 操作t.update(1, 0, n - 1, *st.begin() + 1, *st.rbegin(), 1);}nums[j] = val; // 注意跟新数组数据}ans[i] = t.query() + pos.size(); // 答案为 能被计算两次的质数 + 总的不同质数个数}return ans;}
};