门户网站建设 简报,济南高新区网站建设,房地产网官网,网络规划是干什么的目录 一#xff0c;3566. 等积子集的划分方案二#xff0c;3567. 子矩阵的最小绝对差三#xff0c;3568. 清理教室的最少移动四#xff0c;3569. 分割数组后不同质数的最大数目 一#xff0c;3566. 等积子集的划分方案
题目列表 本题有两种做法#xff0c;dfs 选或不选… 目录 一3566. 等积子集的划分方案二3567. 子矩阵的最小绝对差三3568. 清理教室的最少移动四3569. 分割数组后不同质数的最大数目 一3566. 等积子集的划分方案
题目列表 本题有两种做法dfs 选或不选 / 枚举子集代码如下
// dfs 选或不选
class Solution {public boolean checkEqualPartitions(int[] nums, long target) {return dfs(0, 1, 1, nums, target);}boolean dfs(int i, long mul1, long mul2, int[] nums, long target){if(mul1 target || mul2 target){return false;}if(i nums.length){return mul1 mul2 mul1 target;} return dfs(i1, mul1 * nums[i], mul2, nums, target)|| dfs(i1, mul1, mul2 * nums[i], nums, target);}
}// 枚举子集
class Solution {public boolean checkEqualPartitions(int[] nums, long target) {int n nums.length;for(int i 0; i 1 n; i){long mul1 1, mul2 1;for(int j 0; j n; j){if((i j 1) 0){mul1 * nums[j];}else{mul2 * nums[j];}if(mul1 target || mul2 target)break;}if(mul1 mul2 mul1 target) return true;}return false;}
}二3567. 子矩阵的最小绝对差
题目列表 本题数据范围较小直接暴力枚举每个 k * k 的矩阵代码如下
class Solution {public int[][] minAbsDiff(int[][] grid, int k) {int m grid.length;int n grid[0].length;int[][] ans new int[m-k1][n-k1];for(int i 0; i m - k 1; i){for(int j 0; j n - k 1; j){ListInteger lst new ArrayList();for(int a 0; a k; a){for(int b 0; b k; b){lst.add(grid[ia][jb]);}}Collections.sort(lst);int res Integer.MAX_VALUE;for(int p 1; p lst.size(); p){int x lst.get(p) - lst.get(p-1);if(x 0) continue;res Math.min(res, x);}ans[i][j] res Integer.MAX_VALUE ? 0 : res;}}return ans;}
}三3568. 清理教室的最少移动
题目列表 本题是一个 BFS 广度优先搜索问题只不过多了两个变量 —— 垃圾L、能量energy对于本题来说在使用 BFS 搜索的时候除了必须的坐标xy还需要记录一下当前还剩于的能量没有能量无法移动以及还剩下的垃圾个数以及位置。
对于垃圾个数以及位置
由于题目限制了垃圾个数至多为 10 个可以使用二进制集合来表示当前还有哪些垃圾没有处理对于垃圾所在的位置则可以额外使用一个 hashmap / 二维数组 来存储举个例子有 3 个垃圾分别在(1,2),(3,3),(4,3)将它们表示成二进制集合 mask 111使用 hashmap 存储{(1,2):0},{(2,3):1},{(4,3),2}
综上所述在 BFS 遍历时需要存储 4 个变量 (x,y,energy,mask)由于本题可以上下左右访问可能会出现重复访问的情况所以还需要一个四维布尔数组标记已经访问的位置。
优化可以将 energy 这个维度给优化掉贪心的想对于 (x,y,mask) 这个状态来说肯定是 energy 越多越好这样可以走的更远。实际上避免在两个相邻位置之间反复横跳避免无意义地消耗能量。
代码如下
// 未优化代码
class Solution {public int minMoves(String[] classroom, int energy) {int n classroom.length;int m classroom[0].length();char[][] s new char[n][m];int[] start new int[2];MapInteger, Integer map new HashMap();for(int i 0; i n; i){s[i] classroom[i].toCharArray();for(int j 0; j m; j){if(s[i][j] S){start[0] i;start[1] j;}else if(s[i][j] L){int t map.size(); map.put(i*20j, t);}} }Queueint[] que new LinkedList();int total map.size();que.offer(new int[]{start[0], start[1], energy, (1 total) - 1});boolean[][][][] vis new boolean[n][m][energy1][1total];vis[start[0]][start[1]][energy][(1total)-1] true;int[][] dirct {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};for(int ans 0; !que.isEmpty(); ans){int size que.size();while(size-- 0){int[] t que.poll();int i t[0], j t[1], e t[2], mask t[3];if(mask 0) return ans;if(e 0) continue;for(int[] d : dirct){int x i d[0];int y j d[1];if(x 0 x n y 0 y m s[x][y] ! X){int newE s[x][y] R ? energy : e - 1;int idx map.getOrDefault(x*20y, -1);int newMask idx 0 ? mask ~(1idx) : mask;if(!vis[x][y][newE][newMask]){vis[x][y][newE][newMask] true;que.add(new int[]{x, y, newE, newMask});}} }}}return -1;}
}// 优化代码
class Solution {public int minMoves(String[] classroom, int energy) {int n classroom.length;int m classroom[0].length();int[] start new int[2]; // 记录初始位置MapInteger, Integer map new HashMap();for(int i 0; i n; i){for(int j 0; j m; j){if(classroom[i].charAt(j) S){start[0] i;start[1] j;}else if(classroom[i].charAt(j) L){int t map.size(); map.put(i*20j, t); // 记录 (x,y) : i}} }Queueint[] que new LinkedList();int total map.size();que.offer(new int[]{start[0], start[1], energy, (1 total) - 1});byte[][][] maxEnergy new byte[n][m][1total];for(byte[][] x : maxEnergy){for(byte[] y : x){Arrays.fill(y, (byte)-1);}}maxEnergy[start[0]][start[1]][(1total)-1] (byte)energy;int[][] dirct {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};for(int ans 0; !que.isEmpty(); ans){int size que.size();while(size-- 0){int[] t que.poll();int i t[0], j t[1], e t[2], mask t[3];if(mask 0) return ans; // 垃圾捡完了直接返回if(e 0) continue; // 能量用完了无法移动for(int[] d : dirct){int x i d[0];int y j d[1];if(x 0 x n y 0 y m classroom[x].charAt(y) ! X){byte newE (byte)(classroom[x].charAt(y) R ? energy : e - 1);int idx map.getOrDefault(x*20y, -1);int newMask idx 0 ? mask ~(1idx) : mask;if(maxEnergy[x][y][newMask] newE){// 更新状态maxEnergy[x][y][newMask] newE;que.add(new int[]{x, y, newE, newMask});}} }}}return -1;}
}四3569. 分割数组后不同质数的最大数目
题目列表 本题明面上是一个前后缀的问题实际上是一个区间更新区间查询的题将每次查询的答案分成两个部分一部分是 nums 数组中所有不同质数的个数另一部分则是分割后能多出来的质数个数。第二个部分画个图来理解一下 根据上述图像可以发现我们需要维护每个质数第一次出现的位置以及最后一次出现的位置所有可以使用 TreeSet 有序集合来维护又因为不只一个质数所以还需要嵌套一个哈希表即需要使用MapInteger, TreeSetInteger 这个数据结构。 而区间更新 区间查询则是使用Lazy线段树来实现。
代码如下
class LazySegmentTree{// 懒标记初始值private static final int TODO_INIT 0;private static final class Node{int val;int todo;}private int mergeValue(int a, int b){return Math.max(a, b);}// 合并懒标记private int mergeTodo(int a, int b){return a b;}// 懒标记更新private void apply(int i, int l, int r, int todo){Node cur tree[i];cur.val todo;cur.todo mergeTodo(todo, cur.todo);}private final int n;private final Node[] tree;public LazySegmentTree(int n, int initVal){this.n n;int[] a new int[n];Arrays.fill(a, initVal);tree new Node[n2];build(1, 0, n-1, a);}public LazySegmentTree(int[] a){n a.length;tree new Node[n2];build(1, 0, n-1, a);}public void update(int ql, int qr, int f){update(1, 0, n-1, ql, qr, f);}private void spread(int i, int l, int r){int todo tree[i].todo;if(todo TODO_INIT){return;}int m (l r) / 2;apply(i 1, l, m, todo);apply(i 1 | 1, m 1, r, todo);tree[i].todo TODO_INIT;}private void maintain(int node){tree[node].val mergeValue(tree[node1].val, tree[node1|1].val);}private void build(int i, int l, int r, int[] a){tree[i] new Node();tree[i].todo TODO_INIT;if(l r){tree[i].val a[l];return;}int m (l r) / 2;build(i1, l, m, a);build(i1|1, m1, r, a);maintain(i);}private void update(int i, int l, int r, int L, int R, int f){if(L l r R){apply(i, l, r, f);return;}spread(i, l, r);int mid (l r) / 2;if(L mid){update(i1, l, mid, L, R, f);}if(R mid){update(i1|1, mid1, r, L, R, f);}maintain(i);}public int query(int l, int r){return query(1, 0, n-1, l, r);}private int query(int i, int l, int r, int ql, int qr){if(ql l r qr){return tree[i].val;}spread(i, l, r);int m (l r) / 2;if(qr m){return query(i1, l, m, ql, qr);}if(ql m){return query(i1|1, m1, r, ql, qr);}int lRes query(i1, l, m, ql, qr);int rRes query(i1|1, m1, r, ql, qr);return mergeValue(lRes, rRes);}
}
class Solution {private static final int MX 100_000;private static final boolean[] np new boolean[MX1];static{np[0] np[1] true;for(int i 2; i MX; i){if(!np[i]){for(int j i; j MX / i; j){np[i * j] true;}}}}public int[] maximumCount(int[] nums, int[][] queries) {int n nums.length;MapInteger, TreeSetInteger pos new HashMap();for(int i 0; i n; i){if(!np[nums[i]])pos.computeIfAbsent(nums[i], e-new TreeSet()).add(i);}LazySegmentTree t new LazySegmentTree(n, 0);// 初始化for(TreeSetInteger s : pos.values()){if(s.size() 1){t.update(s.first(), s.last(), 1);}}int m queries.length;int[] ans new int[m];for(int qi 0; qi m; qi){int i queries[qi][0], v queries[qi][1];int old nums[i];nums[i] v;if(!np[old]){ // 处理旧值TreeSetInteger s pos.get(old);if(s.size() 1){ // 先撤回之前的更新操作t.update(s.first(), s.last(), -1);}s.remove(i); // 删除后if(s.size() 1){ // 再执行更新操作t.update(s.first(), s.last(), 1);}else if(s.isEmpty()){pos.remove(old);}}if(!np[v]){ // 处理更新后的值TreeSetInteger s pos.computeIfAbsent(v, k-new TreeSet());if(s.size() 1){// 先撤回之前的更新操作t.update(s.first(), s.last(), -1);}s.add(i);// 添加后if(s.size() 1){// 再执行更新操作t.update(s.first(), s.last(), 1);}}// nums 中所有不同质数的个数 分割后能多出来的质数个数ans[qi] pos.size() t.query(0, n-1);}return ans;}
}
