本文最后更新于:2024年5月7日 下午

记录数组刷题方案。

1267.统计参与通信的服务器

这里有一幅服务器分布图,服务器的位置标识在 m * n 的整数矩阵网格 grid 中,1 表示单元格上有服务器,0 表示没有。

如果两台服务器位于同一行或者同一列,我们就认为它们之间可以进行通信。

请你统计并返回能够与至少一台其他服务器进行通信的服务器的数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
def countServers(self, grid: List[List[int]]) -> int:
if not grid:
return 0
row_num = len(grid)
col_num = len(grid[0])
if col_num == 0:
return 0

count_r = [0] * row_num
count_c = [0] * col_num

for index_r in range(row_num):
for index_c in range(col_num):
if grid[index_r][index_c]:
count_r[index_r] += 1
count_c[index_c] += 1

total_num = 0
for index_r in range(row_num):
for index_c in range(col_num):
if grid[index_r][index_c] and (count_r[index_r] > 1 or count_c[index_c] > 1):
total_num += 1
return total_num

1293. 网格中的最短路径

给你一个 m * n 的网格,其中每个单元格不是 0(空)就是 1(障碍物)。每一步,您都可以在空白单元格中上、下、左、右移动。

如果您 最多 可以消除 k 个障碍物,请找出从左上角 (0, 0) 到右下角 (m-1, n-1) 的最短路径,并返回通过该路径所需的步数。如果找不到这样的路径,则返回 -1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution:
def shortestPath(self, grid: List[List[int]], k: int) -> int:
import numpy as np
m = len(grid)
n = len(grid[0])
if k >= m+n-3:
return m+n -2
mark_tensor = np.ones([m, n, k+1]) * 99999
if grid[0][0]:
pad_queue = [(0, 0, 0, k-1)]
mark_tensor[0, 0, 1] = 0
else:
pad_queue = [(0, 0, 0, k)]
mark_tensor[0, 0, 0] = 0
while pad_queue:
cur_r, cur_c, cur_step, booms = pad_queue.pop(0)
for dr, dc in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
next_r = cur_r + dr
next_c = cur_c + dc
if 0 <= next_c < n and 0 <= next_r < m:
if not grid[next_r][next_c]:
if cur_step + 1 < mark_tensor[next_r, next_c, k-booms]:
mark_tensor[next_r, next_c, k-booms] = cur_step + 1
pad_queue.append((next_r, next_c, cur_step + 1, booms))
else:
if booms > 0:
cur_booms = booms - 1
if cur_step + 1 < mark_tensor[next_r, next_c, k-cur_booms]:
mark_tensor[next_r, next_c, k-cur_booms] = cur_step + 1
pad_queue.append((next_r, next_c, cur_step + 1, cur_booms))

min_step_num = mark_tensor[m-1, n-1, :].min()
if min_step_num > 88888:
return -1
else:
return int(min_step_num)

1091. 二进制矩阵中的最短路径

给你一个 n x n 的二进制矩阵 grid 中,返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径,返回 -1

二进制矩阵中的 畅通路径 是一条从 左上角 单元格(即,(0, 0))到 右下角 单元格(即,(n - 1, n - 1))的路径,该路径同时满足下述要求:

  • 路径途经的所有单元格的值都是 0
  • 路径中所有相邻的单元格应当在 8 个方向之一 上连通(即,相邻两单元之间彼此不同且共享一条边或者一个角)。

畅通路径的长度 是该路径途经的单元格总数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
import numpy as np

if not grid or grid[0][0] != 0:
return -1

length = len(grid)
mark_array = np.array(grid, dtype='int32') * (-1)
node_queue = [(0, 0, 1)]

while len(node_queue):

cur_r, cur_c, step = node_queue.pop(0)
for d_r in range(-1, 2):
for d_c in range(-1, 2):
neighbor_r, neighbor_c = cur_r + d_r, cur_c + d_c
if 0 <= neighbor_r < length and 0 <= neighbor_c < length:
if mark_array[neighbor_r, neighbor_c] == 0:
node_queue.append((neighbor_r, neighbor_c, step + 1))
mark_array[neighbor_r, neighbor_c] = 1
if neighbor_r ==length-1 and neighbor_c == length-1:
if d_r ==0 and d_c == 0:
return step
else:
return step + 1

return -1

2684. 矩阵中移动的最大次数

给你一个下标从 0 开始、大小为 m x n 的矩阵 grid ,矩阵由若干 整数组成。

你可以从矩阵第一列中的 任一 单元格出发,按以下方式遍历 grid

  • 从单元格 (row, col) 可以移动到 (row - 1, col + 1)(row, col + 1)(row + 1, col + 1) 三个单元格中任一满足值 严格 大于当前单元格的单元格。

返回你在矩阵中能够 移动最大 次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
def maxMoves(self, grid: List[List[int]]) -> int:
row_num = len(grid)
col_num = len(grid[0])
q = set()

for index in range(row_num):
q.add((index, 0))

max_step = 0
while q:
next_q = set()
for point in q:
row, col = point
cur_value = grid[row][col]
next_col = col + 1
if next_col < col_num:
for delta in range(-1, 2):
next_row = row+delta
if next_row < row_num and next_row >= 0:
if grid[next_row][next_col] > cur_value:
next_q.add((next_row,next_col))
if next_col > max_step:
max_step = next_col
q = next_q
return max_step


73. 矩阵置零

给定一个 *m* x *n* 的矩阵,如果一个元素为 0 ,则将其所在行和列的所有元素都设为 0 。请使用 原地 算法**。**

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
remove_row_set = set()
remove_row_col = set()

for row_index, row in enumerate(matrix):
for col_index, value in enumerate(row):
if value == 0:
remove_row_set.add(row_index)
remove_row_col.add(col_index)

for row_index, row in enumerate(matrix):
for col_index, value in enumerate(row):
if row_index in remove_row_set or col_index in remove_row_col:
matrix[row_index][col_index] = 0


文章链接:
https://www.zywvvd.com/notes/study/algorithm/grid/grid/


“觉得不错的话,给点打赏吧 ୧(๑•̀⌄•́๑)૭”

微信二维码

微信支付

支付宝二维码

支付宝支付

网格算法练习
https://www.zywvvd.com/notes/study/algorithm/grid/grid/
作者
Yiwei Zhang
发布于
2022年5月14日
许可协议