当前位置: 首页 > >

螺旋矩阵及python实现。leetcode54、leetcode59、leetcode885(python题解)华为笔试题

发布时间:

问题:数组的螺旋遍历,逻辑模拟,主要技巧在于四个方向的控制。


一、螺旋矩阵(leetcode54)
问题


题目来源:力扣(LeetCode)


leetcode54.螺旋矩阵


难度:中等


分析
python的zip技巧很妙,zip本身就带方向旋转的特性。
常规思路主要要写对方向。
解决方法
1:python技巧


class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
res = []
while matrix:
res += matrix.pop(0)
matrix = list(zip(*matrix))[::-1]
return res

2:常规思路


class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
if not matrix:return []
m,n = len(matrix),len(matrix[0])
x = y = di = 0
dx = [0,1,0,-1]
dy = [1,0,-1,0]
res = []
visited = set()

for i in range(m*n):
res.append(matrix[x][y])
visited.add((x,y))
nx,ny = x+dx[di],y+dy[di]
if 0<=nx x,y = nx,ny
else:
di = (di+1)%4 # 如果不满足条件,换一个方向进行遍历
x,y = x+dx[di],y+dy[di]
return res


3:递归写法


#链接:https: // leetcode - cn.com / problems / spiral - matrix / solution / yi - chong - you - ya - de - bian - li - fang - shi - dai - ma - zheng - q /
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
if not matrix: return []
NROW = len(matrix)
NCOL = len(matrix[0])

def helper(depth):
nrow, ncol = NROW - 2 * depth, NCOL - 2 * depth
if nrow <= 0 or ncol <= 0: return []
if nrow == 1: return matrix[depth][depth:depth + ncol]
if ncol == 1: return [matrix[r][depth] for r in range(depth, depth + nrow)]

res = []
res += matrix[depth][depth:depth + ncol - 1]
res += [matrix[r][depth + ncol - 1] for r in range(depth, depth + nrow - 1)]
res += reversed(matrix[depth + nrow - 1][depth + 1:depth + ncol])
res += [matrix[r][depth] for r in reversed(range(depth + 1, depth + nrow))]
return res + helper(depth + 1)

return helper(0)

二、螺旋矩阵II(leetcode59)
问题


题目来源:力扣(LeetCode)


leetcode59.螺旋矩阵II


难度:中等


分析
螺旋矩阵I的思路就能做,这里提供另外一种写法。
写法来自链接:
https://leetcode-cn.com/problems/spiral-matrix-ii/solution/spiral-matrix-ii-mo-ni-fa-she-ding-bian-jie-qing-x/
解决方法
1


class Solution:
class Solution:
def generateMatrix(self, n: int) -> [[int]]:
l, r, t, b = 0, n - 1, 0, n - 1
mat = [[0 for _ in range(n)] for _ in range(n)]
num, tar = 1, n * n
while num <= tar:
for i in range(l, r + 1): # left to right
mat[t][i] = num
num += 1
t += 1
for i in range(t, b + 1): # top to bottom
mat[i][r] = num
num += 1
r -= 1
for i in range(r, l - 1, -1): # right to left
mat[b][i] = num
num += 1
b -= 1
for i in range(b, t - 1, -1): # bottom to top
mat[i][l] = num
num += 1
l += 1
return mat

三、螺旋矩阵III(leetcode885)
问题


题目来源:力扣(LeetCode)


leetcode885.螺旋矩阵III


难度:中等


分析
基本思路与前两道相同,不同的是,这次的再网格外也可以行走,但是只记录网格内行走的路径。这也没关系,我们将图扩大到可能行走的最大尺寸,即较大维度的两倍。然后在行走的过程中判断路径是否在现有的网格中,如果在则记录下来。
题解来自官方解答的改进。
解决方法
1


class Solution(object):
def spiralMatrixIII(self, R, C, r0, c0):
ans = [(r0, c0)]
if R * C == 1: return ans

# For walk length k = 1, 3, 5 ...
for k in range(1, 2*(max(R,C)), 2):

# For direction (dr, dc) = east, south, west, north;
# and walk length dk...
for dr, dc, dk in ((0, 1, k), (1, 0, k), (0, -1, k+1), (-1, 0, k+1)):

# For each of dk units in the current direction ...
for _ in range(dk):
# Step in that direction
r0 += dr
c0 += dc

# If on the grid ...
if 0 <= r0 < R and 0 <= c0 < C:
ans.append((r0, c0))
if len(ans) == R * C:
return ans



友情链接: