当前位置: 首页 > news >正文

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;}
};
http://www.xdnf.cn/news/932599.html

相关文章:

  • 高保真组件库:按钮
  • GitHub 趋势日报 (2025年06月07日)
  • Langgraph实战-自省式RAG: Self-RAG
  • 材料力学速通
  • 北京工作周期7,8,9,10
  • 【react实战】如何实现监听窗口大小变化
  • 2025HNCTF - Crypto
  • webstorm 配置Eslint
  • Springboot 基于MessageSource配置国际化
  • C#调用Rust动态链接库DLL的案例
  • ​RBAC(基于角色的访问控制)权限管理详解
  • 学习日记-day24-6.8
  • 鸿蒙API自翻译
  • 70常用控件_QVBoxLayout的使用
  • 指针的使用——字符、字符串、字符串数组(char*)
  • C++进阶--C++11--智能指针(重点)
  • 12.7Swing控件6 JList
  • gitcode与github加速计划
  • LabVIEW Modbus 主站冗余控制
  • css | class中 ‘.‘ 和 ‘:‘ 的使用 | 如,何时用 .is-selected{ ... } 何时用 :hover{...}?
  • 3Ds Max 2026安装包+教程网盘下载与安装教程指南
  • [特殊字符] Whisper 模型介绍(OpenAI 语音识别系统)
  • WEB3全栈开发——面试专业技能点P1Node.js / Web3.js / Ethers.js
  • 【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)
  • 图神经网络(GNN)模型的基本原理
  • MySQL:CTE 通用表达式
  • 在React 中安装和配置 shadcn/ui
  • 我用Cursor写了一个视频转文字工具,已开源,欢迎体验
  • leetcode 10. 正则表达式匹配
  • 对比传统引擎,Unity3D 在生产配套中的独特优势