二維數組相關題目 力扣 Python

二維數組相關題目 力扣 Python

• • 48. 旋轉圖像
  • 73. 矩陣置零
  • 498. 對角線遍歷
  • 118. 楊輝三角
  • 119. 楊輝三角 II
  • 54. 螺旋矩陣
  • 59. 螺旋矩陣 II
  • 289. 生命游戲

48. 旋轉圖像

解題思路：
解法 1. 主對角線反轉加豎直反轉。

解法 2. 水平反轉加主對角線反轉。

class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
""" Do not return anything, modify matrix in-place instead. """
n = len(matrix)
for i in range(n // 2):
for j in range(n):
matrix[i][j], matrix[n-i-1][j] = matrix[n-i-1][j], matrix[i][j]
#沿對角線反轉
for i in range(n):
for j in range(i):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

73. 矩陣置零

解題思路：

題目要求常量空間且原地解決。

利用矩陣的第一行和第一列來標記有 0 的行與列。

1. 設置兩個變量來記錄每行或每列是否應被置 0。
2. 先遍歷矩陣的第一行和第一列。
3. 再遍歷除第一行和第一列的矩陣。
4. 先置 0 除第一行和第一列的矩陣。
5. 再置 0 第一行和第一列的矩陣。

class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
""" Do not return anything, modify matrix in-place instead. """
m = len(matrix)
n = len(matrix[0])
flag_col0 = False
flag_row0 = False
#遍歷第一行
for i in range(m):
if matrix[i][0] == 0:
flag_col0 = True
break
#遍歷第一列
for j in range(n):
if matrix[0][j] ==0:
flag_row0 = True
break
#用第一行與第一列，記錄其余的矩陣有 0 的行與列
for i in range(1, m):
for j in range(1, n):
if matrix[i][j] == 0:
matrix[i][0] = matrix[0][j] = 0
#置 0
for i in range(1, m):
for j in range(1, n):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
if flag_col0:
for i in range(m):
matrix[i][0] = 0
if flag_row0:
for j in range(n):
matrix[0][j] = 0

498. 對角線遍歷

解題思路：

1. 奇數列向右上方移動，偶數列向右下方移動。
2. 向右上方移動：
   遍歷方向 x - 1, y + 1；
   邊界問題：遇到第一行，y + 1；遇到最後一列，x + 1
3. 向左下方移動：
   遍歷方向 x + 1, y - 1；
   邊界問題：遇到最後一行，y + 1；遇到第一列，x + 1

class Solution:
def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
m, n = len(mat), len(mat[0])
count = m * n
x,y= 0,0
res = []
for i in range(count):
res.append(mat[x][y])
#右上方移動
if(x + y) % 2 ==0:
# 最後一列
if y == n - 1:
x += 1
#第一行
elif x== 0:
y += 1
else:
x -= 1
y += 1
#左下方移動
else:
#最後一行
if x == m - 1:
y += 1
#第一列
elif y ==0:
x += 1
else:
x += 1
y -= 1
return res

118. 楊輝三角

解題思路：
模擬
邊界兩邊各為 1
第 i 行的元素 j 為第 i - 1 行的元素 j - 1 和 j 的和

class Solution:
def generate(self, numRows: int) -> List[List[int]]:
res = []
for i in range(numRows):
row = []
for j in range(i+1):
if j ==0 or j ==i:
row.append(1)
else:
row.append(res[i-1][j-1] + res[i-1][j])
res.append(row)
return res

119. 楊輝三角 II

解題思路：
與 118 邏輯相同還是模擬，不同的是輸出給定的索引行。

使用一個數組，進行兩重循環遍歷。
先遍歷 k 行，再對每一行每個位置上的元素進行逆序賦值計算。
逆序是因為 res[j] = res[j-1] + res[j] 。

class Solution:
#模擬
def getRow(self, rowIndex: int) -> List[int]:
res = [0] * (rowIndex + 1)
for i in range(rowIndex + 1):
for j in range(i, -1, -1):
if j==0 or j== i:
res[j] = 1
else:
res[j] = res[j-1] + res[j]
return res

54. 螺旋矩陣

解題思路：
設定邊界 up, down, left, right ，再模擬。

class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
up, down, left, right = 0, len(matrix) - 1, 0, len(matrix[0]) - 1
res = []
while True:
for i in range(left, right + 1):
res.append(matrix[up][i])
up += 1
if up > down:
break
for i in range(up, down + 1):
res.append(matrix[i][right])
right -= 1
if right < left:
break
for i in range(right, left - 1, -1):
res.append(matrix[down][i])
down -= 1
if down < up:
break
for i in range(down, up - 1, -1):
res.append(matrix[i][left])
left += 1
if left > right:
break
return res

59. 螺旋矩陣 II

解題思路：
與 54 思路相同。
不給過這次是先定義一個矩陣，順勢時針給矩陣賦值。

class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
matrix = [[0 for _ in range(n)] for _ in range(n)]
up, down, left, right = 0, len(matrix) - 1, 0, len(matrix[0]) - 1
index = 1
while True:
for i in range(left, right + 1):
matrix[up][i] = index
index += 1
up += 1
if up > down:
break
for i in range(up, down + 1):
matrix[i][right] = index
index += 1
right -= 1
if right < left:
break
for i in range(right, left - 1, -1):
matrix[down][i] = index
index += 1
down -= 1
if down < up:
break
for i in range(down, up - 1, -1):
matrix[i][left] = index
index += 1
left += 1
if left > right:
break
return matrix

289. 生命游戲

解題思路：

生存條件：

1. 原來是活的，周圍有2-3個活的，成為活的
2. 原來是死的，周圍有3個活的，成為活的
3. 其他都是死了

利用活的細胞去影響其他格子，而不是依次遍歷每個細胞的周圍八個格子來判斷。

被影響的格子裡面的數字加 10，個位存折格子原來的狀態，十位存著它周圍有多少個活的格子。

例如一個格子為 31， 表示其周圍有 3 個活的細胞，且之前的狀態為 1，也就是活的。

題目要求原地解決，當判斷所有的格子之後，再根據生存條件統一改變 borad。

class Solution:
def gameOfLife(self, board: List[List[int]]) -> None:
""" Do not return anything, modify board in-place instead. """
m=len(board)
n=len(board[0])
#用每個活著的點去影響其他的點
def affect( x, y):
for i in [x-1, x, x+1]:
for j in [y-1, y, y+1]:
if i < 0 or i >= m or j<0 or j>=n or(i==x and j ==y):
continue
board[i][j] += 10
def calculate(x, y):
value = board[x][y]
if value // 10 == 3:
board[x][y] = 1
elif value // 10 ==2 and value % 10 == 1:
board[x][y] = 1
else:
board[x][y] = 0
for i in range(m):
for j in range(n):
if board[i][j] % 10 == 1:
affect(i,j)
for i in range(m):
for j in range(n):
calculate(i,j)