难度: Medium
Submission
运行时间: 28 ms
内存: 16.7 MB
class Solution:
def removeOnes(self, grid: List[List[int]]) -> int:
m,n=len(grid),len(grid[0])
size=m*n
#暴力状压
mask=0
for i in range(m):
for j in range(n):
if grid[i][j]==1:
x=i*n+j
mask|=(1<<x)
#BFS爆搜
quene=deque()
quene.append(mask)
vis=set()
vis.add(mask)
time=0
while quene:
k=len(quene)
while k:
stat=quene.popleft()
if stat==0:
return time
for i in range(m):
for j in range(n):
x=i*n+j
#选定格子
if stat>>x&1:
cur=stat
#以这一行,这一列扩展
for t in range(n):
#(i,t)
now=i*n+t
if cur>>now&1:
cur^=(1<<now)
for t in range(m):
#(t,j)
now=t*n+j
if cur>>now&1:
cur^=(1<<now)
if cur not in vis:
vis.add(cur)
quene.append(cur)
k-=1
time+=1
Explain
这个题解采用了'状态压缩'和'广度优先搜索(BFS)'的方法来解决问题。首先，题解通过状态压缩将二维网格转换成一个整数（位掩码），其中每个位代表网格中的一个元素，1表示该位置是1，0表示该位置是0。接着，使用BFS方法来尝试翻转行或列，并检查每次翻转后的结果。如果达到全0的状态，即完成任务。每次翻转时，将当前状态的所有1都尝试翻转对应的行和列，生成新的状态，并检查是否已生成过这个状态，避免重复工作。这个过程一直持续，直到找到解或遍历完所有可能的状态。
时间复杂度: O((m*n)*2^(m*n))
空间复杂度: O(2^(m*n))
class Solution:
def removeOnes(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
size = m * n
# 使用位掩码来表示网格状态
mask = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
x = i * n + j
mask |= (1 << x)
# 使用BFS搜索所有可能的状态
queue = deque()
queue.append(mask)
visited = set()
visited.add(mask)
time = 0
while queue:
k = len(queue)
while k:
state = queue.popleft()
if state == 0:
return time
for i in range(m):
for j in range(n):
x = i * n + j
if state >> x & 1:
cur = state
# 翻转(i, j)所在的行和列
for t in range(n):
now = i * n + t
if cur >> now & 1:
cur ^= (1 << now)
for t in range(m):
now = t * n + j
if cur >> now & 1:
cur ^= (1 << now)
if cur not in visited:
visited.add(cur)
queue.append(cur)
k -= 1
time += 1
Explore
在状态压缩中，我们选择一个位掩码来表示整个网格的状态。每个位掩码中的位对应于网格中的一个单元格。为了准确映射每个网格的状态到位掩码，我们定义一个映射方式，通常是行优先或列优先。在这个题解中，我们采用行优先方式，即先遍历每行的所有列。对于一个位置 (i, j)，我们将其映射到位掩码中的第 `i * n + j` 位（假设网格宽度为 n）。通过这种方式，每次我们访问或修改网格中的一个元素时，都可以通过计算来准确找到对应的位，并通过位操作（如位与、位或和位异或）来读取或更新其状态。
在这个问题中，我们的目标是找到最快的方式来将网格中所有的 '1' 转换为 '0'。广度优先搜索（BFS）在这种情况下更合适，因为BFS是层次化搜索，它首先探索与起始点距离最近的所有状态，逐层向外扩展。这意味着一旦我们通过BFS找到一个全0的状态，我们可以保证找到的解是需要的最小翻转次数。相比之下，深度优先搜索（DFS）可能会深入探索某一路径而忽略其他更短的解决方案，因此不保证最先找到的解是最优解。
为了避免重复翻转同一行或列导致的无效操作，可以通过记录每一行和每一列的翻转状态来优化。具体方法是维护两个数组，一个用于记录行的翻转状态，另一个用于列的翻转状态。每次翻转时，更新相应行或列的状态。在进行翻转操作前，检查对应行或列的当前状态，如果已经标记为翻转过，则跳过该操作。这样可以减少不必要的重复操作，提高算法的效率。
在算法实现中首先应对特殊边界情况进行处理。对于最小网格大小，如1x1，直接检查单个元素即可。若初始状态已经全部为0，则直接返回0，因为不需要任何翻转。对于全1的初始状态，可以计算翻转整个行和列所需的最小步骤。此外，为了优化算法性能，可以在状态压缩之初就检查网格是否已经是全0状态，从而避免不必要的搜索过程。这样的预处理可以显著减少算法的运行时间，特别是在处理极端或特殊情况时更为有效。