8
【LeetCode】matrix相关题目
source link: https://www.guofei.site/2022/04/03/lc-matrix.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
59. Spiral Matrix II
复用 Spiral Matrix I 那个题
- 先用一个矩阵填入连续数字
- 然后展开它，以此确定展开顺序，并记下来
- 按照上一步计算好的展开顺序，对结果矩阵填充
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
matrix=[list(range(i*n,(i+1)*n)) for i in range(n)]
matrix_copy=matrix.copy()
spiral=[]
while matrix_copy:
spiral.extend(matrix_copy.pop(0))
matrix_copy=list(zip(*matrix_copy))[::-1]
helper=dict(zip(spiral,range(1,n*n+1)))
for i in range(n):
for j in range(n):
matrix[i][j]=helper[matrix[i][j]]
return matrix
顺着旋转的思路，可以进一步简化代码
class Solution:
def generateMatrix(self, n: int):
res, lo = [], n * n + 1
while lo > 1:
lo, hi = lo - len(res), lo
res = [list(range(lo, hi))] + [list(line) for line in zip(*res[::-1])]
return res
73. Set Matrix Zeroes
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
rows=[all(line) for line in matrix]
cols=[all(col) for col in zip(*matrix)]
len_rows,len_cols=len(rows),len(cols)
for idx,col in enumerate(cols):
if col==0:
for i in range(len_rows):
matrix[i][idx]=0
for idx,row in enumerate(rows):
if row==0:
matrix[idx]=[0]*len_cols
756. Pyramid Transition Matrix
只需要求出1个，所以用dfs
import collections
class Solution:
def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:
bricks=collections.defaultdict(list)
for brick in allowed:
bricks[brick[:2]].append(brick[2])
res=[False]
def pyramid_once(bottom):
if len(bottom)==2:
if bricks[bottom]:
res[0]=True
return
next_bottoms=['']
for idx in range(len(bottom)-1):
if bottom[idx:idx+2] not in bricks:
return
next_bottoms=[next_bottom+i for i in bricks[bottom[idx:idx+2]]
for next_bottom in next_bottoms
]
for next_bottom in next_bottoms:
if res[0]:
return
pyramid_once(next_bottom)
pyramid_once(bottom)
return res[0]
766. Toeplitz Matrix
矩阵基础题。存储每个斜线的情况即可，也可以用位存储。
class Solution:
def isToeplitzMatrix(self, matrix: List[List[int]]) -> bool:
m,n=len(matrix),len(matrix[0])
val=[None]*(m+n-1)
for i in range(m):
for j in range(n):
if val[j-i+m-1] is None:
val[j-i+m-1]=matrix[i][j]
else:
if val[j-i+m-1]!=matrix[i][j]:
return False
return True
867. Transpose Matrix
return list(zip(*matrix))
542. 01 Matrix
- f(i,j) 定义为 i,j 到 0 的最近距离
- 如果
matrix[i][j]=0，那么f(i,j) = 0 - 否则
f(i,j)=min(f(i-1,j) ,f(i,j-1), f(i+1,j), f(i,j+1))+1 - 上面的迭代公式需要从4个方向向 i,j 计算
- 实际上可以简化位2个方向
class Solution:
def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
h,w=len(mat),len(mat[0])
dp=[[10000]*w for i in range(h)]
for i in range(h):
for j in range(w):
if mat[i][j]==0:
dp[i][j]=0
for i in range(h):
for j in range(w):
if i-1>=0:
dp[i][j]=min(dp[i][j],dp[i-1][j]+1)
if j-1>=0:
dp[i][j]=min(dp[i][j],dp[i][j-1]+1)
for i in range(h-1,-1,-1):
for j in range(w-1,-1,-1):
if i+1<h:
dp[i][j]=min(dp[i][j],dp[i+1][j]+1)
if j+1<w:
dp[i][j]=min(dp[i][j],dp[i][j+1]+1)
return dp
1975. Maximum Matrix Sum
这题简单：
- 负号可以任意沿行/列移动
- 每行偶数个负数字可以抵消，列也是
- 如果全部偶数个负数，返回和
- 如有有奇数个负数，转化为有1个负数，找到绝对值最小的那个即可
class Solution:
def maxMatrixSum(self, matrix: List[List[int]]) -> int:
h,w=len(matrix),len(matrix[0])
neg_is_odds=True
for i in range(h):
for j in range(w):
if matrix[i][j]<0:
neg_is_odds=not neg_is_odds
res=0
for i in range(h):
for j in range(w):
res+=abs(matrix[i][j])
if neg_is_odds:
return res
else:
min_num=100001
for i in range(h):
for j in range(w):
if min_num>abs(matrix[i][j]):
min_num = abs(matrix[i][j])
return res-2*min_num
面试题 01.07. Rotate Matrix LCCI
经典的旋转题，都会背了
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
res=list(zip(*matrix[::-1]))
n=len(matrix)
for i in range(n):
for j in range(n):
matrix[i][j]=res[i][j]
519. Random Flip Matrix
- 维护一个 dict，每个已经被筛选到的，映射到还没有被筛选到的
- 下次如果还选到它，就选择它映射到的
ranint(idx)中的idx--，以减少搜索区域
import random
class Solution:
def __init__(self, m: int, n: int):
self.m = m
self.n = n
self.idx = m * n
self.map = {}
def flip(self) -> List[int]:
self.idx -= 1
x = random.randint(0, self.idx)
new = self.map.get(x, x)
self.map[x] = self.map.get(self.idx, self.idx)
return divmod(new,self.n)
def reset(self) -> None:
self.idx = self.m * self.n
self.map.clear()
不过话说用随机性出题就很屑，卡bug就行
class Solution:
def __init__(self, m: int, n: int):
self.mn = m*n
self.n = n
self.idx = 0
def flip(self) -> List[int]:
self.idx+=1
if self.idx>=self.mn:
self.idx=0
return divmod(self.idx,self.n)
def reset(self) -> None:
pass
566. Reshape the Matrix
class Solution:
def matrixReshape(self, mat: List[List[int]], r: int, c: int) -> List[List[int]]:
if r*c==len(mat)*len(mat[0]):
return np.array(mat).reshape(r,c).tolist()
return mat
正经做也简单
class Solution:
def matrixReshape(self, mat, r: int, c: int):
h, w = len(mat), len(mat[0])
if h * w != r * c:
return mat
res = [[None] * c for i in range(r)]
for idx in range(h * w):
new_i, new_j = divmod(idx, c)
old_i, old_j = divmod(idx, w)
res[new_i][new_j] = mat[old_i][old_j]
return res
1572. 矩阵对角线元素的和
简单，一步过
class Solution:
def diagonalSum(self, mat: List[List[int]]) -> int:
res=0
n=len(mat)
for i in range(n):
res+=mat[i][i]
if i!=n-i-1:
res+=mat[i][n-i-1]
return res
面试题 01.08. Zero Matrix LCCI
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
h,w=len(matrix),len(matrix[0])
row_not_0=[all(row) for row in matrix]
col_not_0=[all(col) for col in zip(*matrix)]
for idx,val in enumerate(row_not_0):
if not val:
matrix[idx]=[0]*w
for idx,val in enumerate(col_not_0):
if not val:
for i in range(h):
matrix[i][idx]=0
885. Spiral Matrix III
!!! 此题是旋转类的典型题
和1/2差别是：
- 1从外环向内旋转，提取
- 2也是从外环向内旋转，填入
- 3从内向外旋转。似乎下面的方法在1/2里面也能用，但1/2的旋转矩阵法就不那么通用了
class Solution:
def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:
res=[]
direction=[(0,1),(1,0),(0,-1),(-1,0)] # 顺时针
left,right,upper,bottom=cStart-1,cStart+1,rStart-1,rStart+1 # 边界
x,y,num,direct=rStart,cStart,0,0
while num<rows*cols:
if x>=0 and x<rows and y>=0 and y<cols:
res.append([x,y])
num+=1
# 遇到边界
if direct==0 and y==right:
direct=1
right+=1
elif direct==1 and x==bottom:
direct=2
bottom+=1
elif direct==2 and y==left:
direct=3
left-=1
elif direct==3 and x==upper:
direct=0
upper-=1
x+=direction[direct][0]
y+=direction[direct][1]
return res
74. Search a 2D Matrix
二分法基础题，做一遍熟悉一下公式
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
h,w=len(matrix),len(matrix[0])
left,right=0,h*w-1
while left<right:
mid =(left+right)//2
i,j=divmod(mid,w)
if matrix[i][j]<target:
left=mid+1
elif matrix[i][j]>target:
right=mid-1
elif matrix[i][j]==target:
return True
mid=left
i,j=divmod(mid,w)
# print(mid,i,j)
return matrix[i][j]==target
240. Search a 2D Matrix II
这个题一开始想用二分法，做了很久之后发现二分法不成立。下面是抄的（感觉这思路耦合性很大）
从左下角开始
- 数值小，则往右
- 数值大，则往上
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
if not matrix:
return False
if not matrix[0]:
return False
h,w=len(matrix),len(matrix[0])
i,j=h-1,0
while i>=0 and j<w:
if matrix[i][j]>target:
i-=1
elif matrix[i][j]<target:
j+=1
else:
return True
return False
面试题 10.09. Sorted Matrix Search LCCI
与 240. Search a 2D Matrix II 一样的题
1329. Sort the Matrix Diagonally
非常直白，不知道还有没有更好的方法
class Solution:
def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:
h,w=len(mat),len(mat[0])
res=[[None]*w for i in range(h)]
for k in range(-(h-1),w):
if k<=0:
tmp_lst=list()
i1,j1=-k,0
while i1<h and j1<w:
tmp_lst.append(mat[i1][j1])
i1+=1
j1+=1
tmp_lst.sort()
i1,j1=-k,0
l=0
while i1<h and j1<w:
res[i1][j1]=tmp_lst[l]
l+=1
i1+=1
j1+=1
if k>0:
tmp_lst=list()
i1,j1=0,k
while i1<h and j1<w:
tmp_lst.append(mat[i1][j1])
i1+=1
j1+=1
tmp_lst.sort()
i1,j1=0,k
l=0
while i1<h and j1<w:
res[i1][j1]=tmp_lst[l]
l+=1
i1+=1
j1+=1
return res
861. Score After Flipping Matrix
- 先反转行，使得第一列全1
- 然后对每列，反转使1多于0
- 进一步的，有些步骤不需要真的反转矩阵。
class Solution:
def matrixScore(self, grid: List[List[int]]) -> int:
h,w=len(grid),len(grid[0])
for i in range(h):
if grid[i][0]==0:
for j in range(w):
grid[i][j]=1-grid[i][j]
res=sum(grid[i][0] for i in range(h))
for col in range(1,w):
num_of_one=sum(grid[i][col] for i in range(h))
if num_of_one<=h//2:
for i in range(h):
grid[i][col]=1-grid[i][col]
res=res<<1
res+=(sum(grid[i][col] for i in range(h)))
return res
其实第二步，矩阵不用真的反转
class Solution:
def matrixScore(self, grid: List[List[int]]) -> int:
h,w=len(grid),len(grid[0])
for i in range(h):
if grid[i][0]==0:
for j in range(w):
grid[i][j]=1-grid[i][j]
res=h
for col in range(1,w):
num_of_one=sum(grid[i][col] for i in range(h))
res=res<<1
res+=(max(num_of_one,h-num_of_one))
return res
1632. Rank Transform of a Matrix
并查集+拓扑排序，之后做
https://leetcode-cn.com/problems/rank-transform-of-a-matrix/submissions/
1380. Lucky Numbers in a Matrix
不想用暴力搜索，所以推导一下得到更好的解法。
- 可以证明，结果必然是唯一的
- 那么结果必然是行最小和列最大的交集
class Solution:
def luckyNumbers (self, matrix: List[List[int]]) -> List[int]:
min_row={min(row) for row in matrix}
max_col={max(col) for col in zip(*matrix)}
return list(min_row&max_col)
1091. Shortest Path in Binary Matrix
!!!BFS 类似level order 的做法一定要会背。另外要知道这种方法是从 queue 而来的
class Solution:
def shortestPathBinaryMatrix(self, grid) -> int:
if grid[0][0] != 0:
return -1
h, w = len(grid), len(grid[0])
if grid[h - 1][w - 1] != 0:
return -1
for i in range(h):
for j in range(w):
if grid[i][j] == 1:
grid[i][j] = None
queue = [(0, 0)]
grid[0][0] = 1
level = 1
while queue:
new_queue = []
for idx_i, idx_j in queue:
if idx_i == h - 1 and idx_j == w - 1:
return level
for diff_i, diff_j in ((1, 1), (-1, -1), (1, -1), (-1, 1), (0, 1), (1, 0), (0, -1), (-1, 0)):
new_i, new_j = idx_i + diff_i, idx_j + diff_j
if 0 <= new_i < h and 0 <= new_j < w and grid[new_i][new_j] == 0:
grid[new_i][new_j] = level
new_queue.append((new_i, new_j))
queue = new_queue
level += 1
return -1
改矩阵的方法感觉不太美观，可以用一个 visited 变量来记录是否已经访问到。不过那样内存消耗就多了一点
1030. Matrix Cells in Distance Order
- 还是需要用set来存放 visited，而不是直接判断 res，否则容易超时
class Solution:
def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int):
queue, res,visited = {(rCenter, cCenter)}, [(rCenter, cCenter)],{(rCenter, cCenter)}
while queue:
# print(queue)
new_queue = set()
for idx_i, idx_j in queue:
for diff_i, diff_j in ((-1, 0), (1, 0), (0, 1), (0, -1)):
new_i, new_j = idx_i + diff_i, idx_j + diff_j
if 0 <= new_i < rows and 0 <= new_j < cols and (new_i, new_j) not in visited:
new_queue.add((new_i, new_j))
queue = new_queue
res.extend(queue)
visited.update(queue)
return res
方法2:直接全部计算，然后sort，速度更快（以为这样很慢的）
class Solution:
def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int):
dist_dict = dict()
for i in range(rows):
for j in range(cols):
dist_dict[(i, j)] = abs(i - rCenter) + abs(j - cCenter)
return sorted(dist_dict, key=lambda x: dist_dict[x])
简化一下，也就两行，哈哈哈
class Solution:
def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int):
dist_dict = {(i, j): abs(i - rCenter) + abs(j - cCenter) for i in range(rows) for j in range(cols)}
return sorted(dist_dict, key=lambda x: dist_dict[x])
1253. Reconstruct a 2-Row Binary Matrix
BFS总是超时，所以用直白方法输出一个解
class Solution:
def reconstructMatrix(self, upper: int, lower: int, colsum):
if upper + lower != sum(colsum):
return []
num_2, num_1, num_0, len_res = colsum.count(2), colsum.count(1), colsum.count(0), len(colsum)
if upper - num_2 < 0 or lower - num_2 < 0:
return []
upper_num_1 = upper - num_2
lower_num_1 = lower - num_2
if upper_num_1 < 0 or lower_num_1 < 0 or upper_num_1 + lower_num_1 + num_2 + num_0 != len_res:
return []
res = []
for i in colsum:
if i == 2:
res.append([1, 1])
elif i == 0:
res.append([0, 0])
elif i == 1:
if upper_num_1 > 0:
res.append([1, 0])
upper_num_1 -= 1
else:
res.append([0, 1])
return list(zip(*res))
1582. Special Positions in a Binary Matrix
class Solution:
def numSpecial(self, mat: List[List[int]]) -> int:
h,w=len(mat),len(mat[0])
col_is_good=[None]*w
res=0
for i,row in enumerate(mat):
if sum(row)==1:
j=row.index(1)
if col_is_good is None:
continue
if sum(mat[i_1][j] for i_1 in range(h))>1:
col_is_good[j]=False
continue
res+=1
return res
378. Kth Smallest Element in a Sorted Matrix
import heapq
class Solution:
def kthSmallest(self, matrix, k: int) -> int:
n = len(matrix)
heap = matrix[0] + [matrix[i][0] for i in range(1, n)]
heapq.heapify(heap)
for i in range(1, n):
k_smallest = heapq.nsmallest(k, heap)
if len(k_smallest) == k and matrix[i][i] > k_smallest[-1]:
return k_smallest[k - 1]
for val in matrix[i][i:]:
heapq.heappush(heap, val)
for i1 in range(i + 1, n):
heapq.heappush(heap, matrix[i1][i])
k_smallest = heapq.nsmallest(k, heap)
return k_smallest[k - 1]
1337. The K Weakest Rows in a Matrix
直接用 heapq
import heapq
class Solution:
def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
res = heapq.nsmallest(k, iterable=[(i, sum(mat[i])) for i in range(len(mat))], key=lambda x: x[1])
return list(zip(*res))[0]
1252. Cells with Odd Values in a Matrix
以下情况：
- 初始为偶数：如果一行只有一个，那么这一个仍是偶数，其它都变成奇数。
- 如果一行有2个，这两个是奇数，其它仍然是偶数。
- 也就是说，如果一行有奇数个，有数的全是偶数，其它全是奇数。一行有偶数个，有数的是奇数，其它全是偶数。
（以上作废，是我想复杂了）直白的做就行了
class Solution:
def oddCells(self, m: int, n: int, indices: List[List[int]]) -> int:
res=[[0]*n for i in range(m)]
for (idx_i,idx_j) in indices:
for i in range(m):
res[i][idx_j]=1-res[i][idx_j]
for j in range(n):
res[idx_i][j]=1-res[idx_i][j]
return sum(sum(row) for row in res)
1351. Count Negative Numbers in a Sorted Matrix
class Solution:
def countNegatives(self, grid: List[List[int]]) -> int:
return sum(sum(i < 0 for i in row) for row in grid)
1594. Maximum Non Negative Product in a Matrix
- 求全局值，所以用bfs而不是dfs
- 有个边界条件是格子里面可以为0，因此如果按照无0做的结果是空，并且有0，那么有个保底解是0
- 结果要取模
- queue要用set
class Solution:
def maxProductPath(self, grid) -> int:
h, w = len(grid), len(grid[0])
queue = {(0, 0)}
val = {(0, 0): [grid[0][0]]}
def get_max(point_val, next_point, next_point_val):
tmp = [i * next_point for i in point_val] + next_point_val
tmp_min, tmp_max = min(tmp), max(tmp)
if tmp_min < 0:
if tmp_max >= 0:
return [tmp_min, tmp_max]
if tmp_max < 0:
return [tmp_min]
return [tmp_max]
while queue:
new_queue = set()
for point in queue:
for diff in ((1, 0), (0, 1)):
next_point = point[0] + diff[0], point[1] + diff[1]
if 0 <= next_point[0] < h and 0 <= next_point[1] < w:
val[next_point] = get_max(val[point], grid[next_point[0]][next_point[1]],
val[next_point] if next_point in val else list())
new_queue.add(next_point)
queue = new_queue
max_last_val = max(val[(h - 1, w - 1)])
if max_last_val >= 0:
return max_last_val%(10**9+7)
else:
for i in range(h):
for j in range(w):
if grid[i][j] == 0:
return 0
return -1
1605. Find Valid Matrix Given Row and Column Sums
class Solution:
def restoreMatrix(self, rowSum, colSum):
def get_matrix(rowSum, colSum):
h, w = len(rowSum), len(colSum)
if h == 0:
return []
num = rowSum[0]
row = [0] * w
i = 0
while num > 0:
# 贪心填充一行
if num <= colSum[i]:
row[i] = num
colSum[i] -= num
num = 0
else:
row[i] = colSum[i]
num -= colSum[i]
colSum[i] = 0
i += 1
return [row] + get_matrix(rowSum[1:], colSum)
return get_matrix(rowSum, colSum)
1886. Determine Whether Matrix Can Be Obtained By Rotation
旋转类的基本题了，一次成型
class Solution:
def findRotation(self, mat, target) -> bool:
def rotate(mat):
return list(zip(*mat))[::-1]
target = [tuple(row) for row in target]
mat_new = mat
for i in range(4):
mat_new = rotate(mat_new)
if mat_new == target:
return True
return False
1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix
！！！好题，想到这些：
- 如果某个解存在，那么其顺序任意调换不会影响结果
- 某一个格子翻转两次等于不翻转。
- 因此每个格子翻转1次或0次一定能得到答案。计算1的数量就能得到结果
- DFS 可解了，但是有 2n2n 复杂度
- 想到剪枝：如果某个格子附近都已经遍历过，但这个格子没有归0，那么这个分支不可能为解，剔除即可
- 发现第二行开始，都被剪成1种可能性了，这样的话只需要回溯第一行，2w2w复杂度
class Solution:
def minFlips(self, mat) -> int:
h, w = len(mat), len(mat[0])
n = h * w
res = [None]
def flip(i, j):
for diff_i, diff_j in ((0, -1), (0, 0), (0, 1), (-1, 0), (1, 0)):
new_i, new_j = i + diff_i, j + diff_j
if 0 <= new_i < h and 0 <= new_j < w:
mat[new_i][new_j] ^= 1
def dfs(cnt, flip_cnt):
if res[0] is not None:
return
if cnt == n:
if sum(sum(row) for row in mat) == 0:
res[0] = flip_cnt
return
idx_i, idx_j = divmod(cnt, w)
if idx_i == 0:
# 第一个可能路径：不反转
dfs(cnt + 1, flip_cnt)
if res[0] is not None:
return
# 第二个可能路径：翻转。这里用回溯法
flip(idx_i, idx_j)
dfs(cnt + 1, flip_cnt + 1)
flip(idx_i, idx_j)
else:
if mat[idx_i - 1][idx_j] == 0:
dfs(cnt + 1, flip_cnt)
else:
flip(idx_i, idx_j)
dfs(cnt + 1, flip_cnt + 1)
flip(idx_i, idx_j)
dfs(0, 0)
return res[0] if res[0] is not None else -1
1439. Find the Kth Smallest Sum of a Matrix With Sorted Rows
- 为了剪枝，每次迭代只取前k个即可（我咋没想到）
import heapq
class Solution:
def kthSmallest(self, mat, k: int) -> int:
total_sums = [0]
for row in mat:
total_sums = [total_sum + val for total_sum in total_sums for val in row]
total_sums = heapq.nsmallest(k, total_sums)
res = heapq.nsmallest(k, total_sums)
return res[-1]
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK