Работа с матрицей в Python — шпаргалка
Понимание матричных операций.
Матрица представляет собой двумерный массив. Часто матрицы используются для представления графа (матрицы смежности) или состояния динамического программирования. Матрицы также используются для моделирования таких игр, как крестики-нолики, судоку, кроссворд, морской бой и т. д.
Мы можем сгенерировать матрицу m * n со всеми нулями в python следующим образом:
matrix = [[0 for _ in range(n)] for _ in range(m)]
Обход матрицы
Приведенный ниже код описывает логику обхода матрицы.
matrix = [
['a', 'b', 'c', 'd'],
['e', 'f', 'g', 'h'],
['i', 'j', 'k', 'l'],
['m', 'n', 'o', 'p']
]
m, n = len(matrix), len(matrix[0]) # get matrix size
for i in range(m): # iterate through rows
print(f"Row No:=====> {i}")
for j in range(n): # iterate through cols
print(f"\t Col No {j}")
Проход по колонке
matrix = [
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16]
]
for col in zip(*matrix):
print(*col)
# alternative
m, n = len(matrix), len(matrix[0])
for col in range(n):
for row in range(m):
print(matrix[row][col], end=' ')
print()
Проверить наличие всех чисел во всех строках и столбцах
Обход соседей ячейки
Приведенный ниже код описывает код для обхода соседних ячеек.
matrix = [
['a', 'b', 'c', 'd'],
['e', 'f', 'g', 'h'],
['i', 'j', 'k', 'l'],
['m', 'n', 'o', 'p']
]
row, col = (1, 2) # current position
directions = [
(0, 1), # right
(1, 1), # right down
(1, 0), # down
(1, -1), # down left
(0, -1), # left
(-1, -1), # left up
(-1, 0), # up
(-1, 1) # right, up
]
print(f"Current cell: {matrix[row][col]}")
for dx, dy in directions:
new_row, new_col = row + dx, col + dy
if 0 <= new_row < m and 0<=new_col<n: # boundary check
print(f"New Pos {(new_row, new_col)}: {matrix[new_row][new_col]}")
Наибольшее локальное значение в матрице
Особые позиции в бинарной матрице
Счастливые числа в матрице
Сглаживание изображения
Диагональные ячейки матрицы
Диагональные элементы в матрице удовлетворяют одному из следующих двух ограничений
1. i == j 2. j == n-i-1
matrix = [
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16]
]
m, n = len(matrix), len(matrix[0])
for i in range(m):
for j in range(n):
if j == i or j == n-i-1:
print(matrix[i][j])
Самый большой магический квадрат
k x k магический квадрат представляет собой сетку k x k, заполненную целыми числами, так что суммы каждой строки, суммы каждого столбца и суммы обеих диагоналей равны. Целые числа в магическом квадрате не обязательно должны быть различными. Каждая сетка 1 x 1 представляет собой магический квадрат.
Учитывая m x n целое число grid, вернуть размер (т. е. длину стороныk) наибольшего магического квадрата, который можно найти. в этой сетке.
class Solution:
def largestMagicSquare(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
size = min(m, n)
for k in range(size, 0, -1):
for i in range(m-k+1):
for j in range(n-k+1):
if self.is_magic_square(grid, i, j, k):
return k
def is_magic_square(self, grid, x, y, k):
diag_sum, anti_diag_sum = 0, 0
for i in range(k):
diag_sum += grid[x+i][y+i]
anti_diag_sum += grid[x+i][y+k-i-1]
if diag_sum != anti_diag_sum:
return False
for i in range(k):
row_sum = sum(grid[x+i][y:y+k])
if row_sum != diag_sum:
return False
col_sum = sum((grid[x+j][y+i] for j in range(k)))
if col_sum != diag_sum:
return False
return True
Примечание. Приведенное выше решение можно оптимизировать, используя сумму префиксов. Оставил это здесь, так как этот блог посвящен матрицам. Прочитайте мой другой блог, в котором объясняется сумма префиксов.
Модульные операции над списком для создания матрицы
В приведенном ниже коде описывается код для создания матрицы размерности m * n из сплющенной матрицы.
flattened = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
print(f"Flattened :\n{flattened}")
m, n = 3, 5
matrix = [['' for _ in range(n)] for _ in range(m)]
for idx, val in enumerate(flattened):
row, col = divmod(idx, n)
matrix[row][col] = val
print(f"Matrix:\n{matrix}")
Спиральная матрица
Учитывая m x n matrix, вернуть все элементы matrix по спирали.
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
res = [[0]*n for i in range(n)]
top, bottom, left, right = 0, n-1, 0, n-1
move=1
elem = 1
while left <= right and top <= bottom:
if move==1:
for i in range(left, right+1):
res[top][i] = elem
elem += 1
top += 1
elif move==2:
for i in range(top, bottom + 1):
res[i][right] = elem
elem += 1
right -= 1
elif move==3:
for i in range(right, left-1, -1):
res[bottom][i] = elem
elem += 1
bottom -= 1
else:
for i in range(bottom, top-1, -1):
res[i][left] = elem
elem += 1
left += 1;
move += 1;
move=move%4
return res
Транспонировать матрицу
Транспонирование матрицы достигается заменой ее строк столбцами или столбцов строками.
В приведенном ниже коде описывается логика транспонирования матрицы.
matrix = [
['a', 'b', 'c', 'd'],
['e', 'f', 'g', 'h'],
['i', 'j', 'k', 'l'],
['m', 'n', 'o', 'p']
]
print(f"Current Matrix:\n{matrix}")
transpose = []
for row in zip(*matrix):
transpose.append(list(row))
print(f"Transposed Matrix:\n{transpose}")
Повернуть матрицу на 90 градусов по часовой стрелке
Код ниже описывает логику поворота матрицы на 90 градусов по часовой стрелке. Для этого мы транспонируем и переворачиваем значения столбцов в середине транспонированной матрицы.
matrix = [
['a', 'b', 'c', 'd'],
['e', 'f', 'g', 'h'],
['i', 'j', 'k', 'l'],
['m', 'n', 'o', 'p']
]
print(f"Current Matrix:\n{matrix}")
transpose = []
for row in zip(*matrix):
transpose.append(list(row))
print(f"Transposed Matrix:\n{transpose}")
m, n = len(transpose), len(transpose[0])
for i in range(m):
for j in range(n//2):
transpose[i][j], transpose[i][n-j-1] = transpose[i][n-j-1], transpose[i][j]
print(f"Flipped Matrix:\n{transpose}")
Проверить, можно ли получить матрицу вращением
Крайний левый столбец, по крайней мере, с одной 1
Двоичная матрица с сортировкой по строкам означает, что все элементы равны 0 или 1, а каждая строка матрицы отсортирована в неубывающем порядке.
Учитывая двоичную матрицу, отсортированную по строкам binaryMatrix, вернуть индекс (0-индексированный) крайнего левого столбца с 1 в нем. Если такого индекса не существует, вернуть -1.
Решите эту задачу в меньшем произведении размерности.
class Solution:
def leftMostColumnWithOne(self, binaryMatrix: 'BinaryMatrix') -> int:
rows, cols = binaryMatrix.dimensions()
current_row = 0
current_col = cols - 1
while current_row < rows and current_col >= 0:
if binaryMatrix.get(current_row, current_col) == 0:
current_row += 1
else:
current_col -= 1
return current_col + 1 if current_col != cols - 1 else -1
На шахматной доске 8 x 8 есть ровно одна белая ладья 'R' и некоторое количество белых слонов 'B', черных пешек 'p' и пустых полей '.'.
Когда ладья ходит, она выбирает одно из четырех основных направлений (север, восток, юг или запад), затем движется в этом направлении, пока не решит остановиться, не достигнет края доски, не захватит черную пешку или не будет заблокирована белый епископ. Ладья считается атакующей пешку, если ладья может взять пешку на ходу ладьи. Число доступных взятий для белой ладьи — это количество пешек, которые ладья атакует.
Возвращает число доступных взятий белой ладьи.
class Solution:
def numRookCaptures(self, board: List[List[str]]) -> int:
for i in range(8):
for j in range(8):
if board[i][j] == 'R':
rook_x, rook_y = i, j
res = 0
for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
x, y = rook_x + dx, rook_y + dy
while 0 <= x < 8 and 0 <= y < 8:
if board[x][y] == 'p':
res += 1
if board[x][y] != '.':
break
x, y = x + dx, y + dy
return res
Площадь поверхности трехмерных фигур
Вам дается n x n grid, куда вы поместили 1 x 1 x 1 кубиков. Каждое значение v = grid[i][j] представляет собой башню из v кубов, расположенную поверх ячейки (i, j).
Разместив эти кубики, вы решили склеить любые непосредственно соседние кубики друг с другом, образовав несколько неправильных трехмерных фигур.
Возвращает общую площадь поверхности получившихся фигур.
Примечание. Нижняя грань каждой фигуры учитывается в площади ее поверхности.
class Solution:
def surfaceArea(self, grid: List[List[int]]) -> int:
l = len(grid)
area = 0
for row in range(l):
for col in range(l):
if grid[row][col]:
area += (grid[row][col]*4) +2
if row:
area -= min(grid[row][col],grid[row-1][col])*2
if col:
area -= min(grid[row][col],grid[row][col-1])*2
return area
Количество подматриц, суммирующихся с целью
Учитывая matrix и target, вернуть количество непустых подматриц, сумма которых равна цели.
Подматрица x1, y1, x2, y2 представляет собой набор всех ячеек matrix[x][y] с x1 <= x <= x2 и y1 <= y <= y2.
Две подматрицы (x1, y1, x2, y2) и (x1', y1', x2', y2') различны, если у них есть какая-то другая координата: например, если x1 != x1'.
from collections import defaultdict
class Solution:
def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:
r, c = len(matrix), len(matrix[0])
ps = [[0] * (c + 1) for _ in range(r + 1)]
for i in range(1, r + 1):
for j in range(1, c + 1):
ps[i][j] = ps[i - 1][j] + ps[i][j - 1] - ps[i - 1][j - 1] + matrix[i - 1][j - 1]
count = 0
for r1 in range(1, r + 1):
for r2 in range(r1, r + 1):
h = defaultdict(int)
h[0] = 1
for col in range(1, c + 1):
curr_sum = ps[r2][col] - ps[r1 - 1][col]
count += h[curr_sum - target]
h[curr_sum] += 1
return count
Угловые случаи для матрицы для проверки:
- Пустая матрица. Убедитесь, что ни один из массивов не имеет длины 0
- 1 х 1 матрица
- Матрица только с одной строкой или столбцом
Удачного кодирования !!
