Leetcode 54. Spiral Matrix & 59. Spiral Matrix II
54. Spiral Matrix [Medium]
Description
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
Example 1:
Input:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]
Example 2:
Input:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]
Solution
Approach 1. 按照外围圈遍历
用r标记圈数(r = 0开始)，同时(r, r)也为起始坐标。
注意：
对于 [6 7]，避免再次回转到6，应加入判断条件：m > 1
对于[7
8
9] 避免再次回转到7，应加入判断条件：n > 1
class Solution:
def spiralOrder(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
r = 0
ret = []
if not matrix or not matrix[0]:
return ret
m, n = len(matrix), len(matrix[0])
while m >= 1 and n >= 1:
for i in range(n):
ret.append(matrix[r][r + i])
for i in range(m - 1):
ret.append(matrix[r + 1 + i][r + n - 1]) if m > 1:
for i in range(n - 1):
ret.append(matrix[r + m - 1][r + n - 1 - 1 - i])
if n > 1:
for i in range(m - 2):
ret.append(matrix[r + m - 1 -1 - i][r])
m -= 2
n -= 2
r += 1
return ret
Beats: 75.70%
Runtime: 36ms
Approach 2. Simulation
参考Leetcode官方Solution
Intuition
Draw the path that the spiral makes. We know that the path should turn clockwise whenever it would go out of bounds or into a cell that was previously visited.
Algorithm
Let the array have R rows and C columns. seen[r][c] denotes that the cell on the r-th row and c-th column was previously visited.
Our current position is (r, c), facing direction \text{di}di, and we want to visit R x C total cells.
As we move through the matrix, our candidate next position is (cr, cc).
If the candidate is in the bounds of the matrix and unseen, then it becomes our next position;
otherwise, our next position is the one after performing a clockwise turn.
class Solution:
def spiralOrder(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
if not matrix: return []
R, C = len(matrix), len(matrix[0])
seen = [[False] * C for _ in matrix]
ans = []
dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]
r = c = di = 0 for _ in range(R * C):
ans.append(matrix[r][c])
seen[r][c] = True
cr, cc = r + dr[di], c + dc[di]
if 0 <= cr < R and 0 <= cc < C and not seen[cr][cc]:
r, c = cr, cc
else:
di = (di + 1) % 4
r, c = r + dr[di], c + dc[di]
return ans
Beats: 75.70%
Runtime: 36ms
59. Spiral Matrix II [Medium]
Description
Given a positive integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
Example:
Input: 3
Output:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]
Solution
用r标记圈数
1 2 3 | 4
-------- |
12| 13 14 | 5
11| 16 15 | 6
10| 9 8 7
------------
注意当n == 1时，for循环中n - 1 = 0，则不能执行，
如input = 3 时，9不能输出，
所以需要单独写 n == 1 时的情况。
class Solution:
def generateMatrix(self, n):
"""
:type n: int
:rtype: List[List[int]]
"""
matrix = [([0] * n) for _ in range(n)]
cnt = 1
r = 0
while n >= 2:
for i in range(n - 1):
matrix[r][r + i] = cnt
cnt += 1
for i in range(n - 1):
matrix[r + i][r + n - 1] = cnt
cnt += 1
for i in range(n - 1):
matrix[r + n - 1][r + n - 1 - i] = cnt
cnt += 1
for i in range(n - 1):
matrix[r + n - 1 - i][r] = cnt
cnt += 1 n -= 2
r += 1
if n == 1:
matrix[r][r] = cnt
return matrix
Beats: 48.93%
Runtime: 44ms
最新文章
- 自定cordova插件笔记demo
- OpenERP/Odoo命令行参数
- js展开一颗树
- university, school, college, department, institute的区别
- JavaScript之With语句讲解
- SSH整合常见错误
- Hibernate之HQL介绍
- struts2标签学习笔记（一）
- iOS 开发之照片框架详解
- plsql developer日期时间格式设置
- Result Maps collection does not contain value for com.man.impet.dao.OrderBeanMapper.map
- JBOSSAS 5.x/6.x 反序列化命令执行漏洞(CVE-2017-12149)
- cf14d 树的直径，枚举删边
- 网页异步加载之AJAX理解
- 记一次Oracle分区表错误：ORA-14400: 插入的分区关键字未映射到任何分区
- idea如何整理代码格式
- redis 事务、Jedis事务处理流程
- [Winter Vacation] 语文实词虚词练习册答案
- spring boot&&cloud干货系列
- Laraver 框架资料