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
dp方法
- 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
bfs
- 还是需要用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 可解了，但是有 $2^n$ 复杂度
- 想到剪枝：如果某个格子附近都已经遍历过，但这个格子没有归0，那么这个分支不可能为解，剔除即可
- 发现第二行开始，都被剪成1种可能性了，这样的话只需要回溯第一行，$2^w$复杂度
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]
