一，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(i+1, mul1 * nums[i], mul2, nums, target)
|| dfs(i+1, 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-k+1][n-k+1];
for(int i = 0; i < m - k + 1; i++){
for(int j = 0; j < n - k + 1; j++){
List<Integer> lst = new ArrayList<>();
for(int a = 0; a < k; a++){
for(int b = 0; b < k; b++){
lst.add(grid[i+a][j+b]);
}
}
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 搜索的时候除了必须的坐标（x，y），还需要记录一下当前还剩于的能量（没有能量无法移动），以及还剩下的垃圾个数以及位置。
对于垃圾个数以及位置：
- 由于题目限制了垃圾个数至多为 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];
Map<Integer, 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*20+j, t);
}
}
}
Queue<int[]> 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][energy+1][1<<total];
vis[start[0]][start[1]][energy][(1<<total)-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*20+y, -1);
int newMask = idx >= 0 ? mask & ~(1<<idx) : 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]; // 记录初始位置
Map<Integer, 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*20+j, t); // 记录 (x,y) : i
}
}
}
Queue<int[]> 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][1<<total];
for(byte[][] x : maxEnergy){
for(byte[] y : x){
Arrays.fill(y, (byte)-1);
}
}
maxEnergy[start[0]][start[1]][(1<<total)-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*20+y, -1);
int newMask = idx >= 0 ? mask & ~(1<<idx) : 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 有序集合来维护，又因为不只一个质数，所以还需要嵌套一个哈希表，即需要使用Map<Integer, TreeSet<Integer>> 这个数据结构。 而区间更新 + 区间查询则是使用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[n<<2];
build(1, 0, n-1, a);
}
public LazySegmentTree(int[] a){
n = a.length;
tree = new Node[n<<2];
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[node<<1].val, tree[node<<1|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(i<<1, l, m, a);
build(i<<1|1, m+1, 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(i<<1, l, mid, L, R, f);
}
if(R > mid){
update(i<<1|1, mid+1, 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(i<<1, l, m, ql, qr);
}
if(ql > m){
return query(i<<1|1, m+1, r, ql, qr);
}
int lRes = query(i<<1, l, m, ql, qr);
int rRes = query(i<<1|1, m+1, r, ql, qr);
return mergeValue(lRes, rRes);
}
}
class Solution {
private static final int MX = 100_000;
private static final boolean[] np = new boolean[MX+1];
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;
Map<Integer, TreeSet<Integer>> 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(TreeSet<Integer> 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]){ // 处理旧值
TreeSet<Integer> 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]){ // 处理更新后的值
TreeSet<Integer> 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;
}
}