本文最后更新于 2 分钟前，文中所描述的信息可能已发生改变。
3566. 等积子集的划分方案 - 力扣（LeetCode）
解题思路
递归，选或选
示例代码
python
class Solution:
def checkEqualPartitions(self, nums: List[int], target: int) -> bool:
n = len(nums)
def dfs(i, m1, m2):
if i == n:
return m1 == m2 == target
return dfs(i + 1, m1 * nums[i], m2) or dfs(i + 1, m1, m2 * nums[i])
return dfs(0, 1, 1)3567. 子矩阵的最小绝对差 - 力扣（LeetCode）
解题思路
模拟，选择子矩阵元素，重新排序计算即可
示例代码
python
class Solution:
def minAbsDiff(self, grid: List[List[int]], k: int) -> List[List[int]]:
n, m = len(grid), len(grid[0])
ans = [[] for _ in range(n - k + 1)]
for i in range(k, n + 1):
for j in range(k, m + 1):
a = []
for ni in range(i - 1, i - k - 1, -1):
a.extend(grid[ni][j - k: j])
a = sorted(set(a))
res = inf if len(a) > 1 else 0
for x, y in pairwise(a):
res = min(res, abs(x - y))
ans[i - k].append(res)
return ans3568. 清理教室的最少移动 - 力扣（LeetCode）
解题思路
广度优先搜索，两种做法，都要记录(x, y, energy, msk)状态，剪枝方式不同，一种是全状态记录（会超时），另一种是记录最大 energy，具体见代码实现
示例代码
python
class Solution:
def minMoves(self, classroom: List[str], energy: int) -> int:
n, m = len(classroom), len(classroom[0])
x, y = 0, 0
r = {}
for i, row in enumerate(classroom):
for j, c in enumerate(row):
if c == 'S':
x, y = i, j
elif c == 'L':
r[(i, j)] = ~(1 << len(r))
if len(r) == 0:
return 0
ans = 0
t = (1 << len(r)) - 1
q = [(x, y, energy, t)]
vis = [[[[False] * (t + 1) for _ in range(energy + 1)] for _ in range(m)] for _ in range(n)]
vis[x][y][energy][t] = True
while q:
tmp = q
q = []
for x, y, e, msk in tmp:
if msk == 0:
return ans
if e == 0:
continue
for dx, dy in (0, 1), (1, 0), (0, -1), (-1, 0):
nx = x + dx
ny = y + dy
if 0 <= nx < n and 0 <= ny < m and classroom[nx][ny] != 'X':
ne = energy if classroom[nx][ny] == 'R' else e - 1
nmsk = msk & r[(nx, ny)] if classroom[nx][ny] == 'L' else msk
if not vis[nx][ny][ne][nmsk]:
vis[nx][ny][ne][nmsk] = True
q.append((nx, ny, ne, nmsk))
ans += 1
return -1python
class Solution:
def minMoves(self, classroom: List[str], energy: int) -> int:
n, m = len(classroom), len(classroom[0])
x, y = 0, 0
r = {}
for i, row in enumerate(classroom):
for j, c in enumerate(row):
if c == 'S':
x, y = i, j
elif c == 'L':
r[(i, j)] = ~(1 << len(r))
if len(r) == 0:
return 0
ans = 0
t = (1 << len(r)) - 1
q = [(x, y, energy, t)]
max_energy = [[[-1] * (t + 1) for _ in range(m)] for _ in range(n)]
max_energy[x][y][t] = energy
while q:
tmp = q
q = []
for x, y, e, msk in tmp:
if msk == 0:
return ans
if e == 0:
continue
for dx, dy in (0, 1), (1, 0), (0, -1), (-1, 0):
nx = x + dx
ny = y + dy
if 0 <= nx < n and 0 <= ny < m and classroom[nx][ny] != 'X':
ne = energy if classroom[nx][ny] == 'R' else e - 1
nmsk = msk & r[(nx, ny)] if classroom[nx][ny] == 'L' else msk
if ne > max_energy[nx][ny][nmsk]:
max_energy[nx][ny][nmsk] = ne
q.append((nx, ny, ne, nmsk))
ans += 1
return -13569. 分割数组后不同质数的最大数目 - 力扣（LeetCode）
解题思路
示例代码
python
TODO