Baozi Training Leetcode solution 54: Spiral Matrix

包子面试培训

发布于 2020-01-02 11:50:02

3600

发布于 2020-01-02 11:50:02

包子小道消息@12/21/2019

住在Burlingame的小伙伴们房价要大涨了！小扎准备全力进军VR的硬件设备，放一个4000多人的campus。滴滴经历了惨淡的2019年之后，希望2020年重振雄风，LATAM发展的同时在国内再次启动拼车业务，共享经济与Uber Lyft相似的难兄难弟。

Blogger:https://blog.baozitraining.org/2019/12/leetcode-solution-54-sprial-matrix.html

Youtube: https://youtu.be/h_7iIk7sz0A

博客园: https://www.cnblogs.com/baozitraining/p/12015938.html

B站: https://www.bilibili.com/video/av78728782/

Problem Statement

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]

Problem link

Video Tutorial

You can find the detailed video tutorial here

Youtube
B站

Thought Process

It's a straight forward implementation question, we can simply just simulate the spiral order and print. You can choose to do it either iteratively (see reference to download the official Leetcode solution) or use recursion.

There is this awesome one line solution from this guy which is pretty insane.

def spiralOrder(self, matrix):
    return matrix and list(matrix.pop(0)) + self.spiralOrder(zip(*matrix)[::-1])

https://leetcode.com/problems/spiral-matrix/discuss/20571/1-liner-in-Python-%2B-Ruby

Solutions

 1 public List<Integer> spiralOrder(int[][] matrix) {
 2     List<Integer> res = new ArrayList<>();
 3 
 4     if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
 5         return res;
 6     }
 7 
 8     this.printSpiralOrder(0, 0, matrix.length, matrix[0].length, res, matrix);
 9 
10     return res;
11 }
12 
13 // printSpiralOrder is a poor name, function starts with verb, printSpiralOrder, class is noun, function is verb
14 private void printSpiralOrder(int i, int j, int rowSize, int colSize, List<Integer> res, int[][] matrix) {
15     if (rowSize <= 0 || colSize <= 0) {
16         return;
17     }
18 
19     if (rowSize == 1 && colSize == 1) {
20         res.add(matrix[i][j]);
21         return;
22     }
23     if (rowSize == 1) {
24         for (int k = j; k < j + colSize; k++) {
25             res.add(matrix[i][k]);
26         }
27         return;
28     }
29 
30     if (colSize == 1) {
31         for (int k = i; k < i + rowSize; k++) {
32             res.add(matrix[k][j]);
33         }
34         return;
35     }
36 
37     // do the spiral
38     for (int k = j; k < j + colSize; k++) {
39         res.add(matrix[i][k]);
40     }
41 
42     for (int k = i + 1; k < i + rowSize; k++) {
43         res.add(matrix[k][j + colSize - 1]);
44     }
45 
46     for (int k = j + colSize - 2; k >= i; k--) {
47         res.add(matrix[i + rowSize - 1][k]);
48     }
49 
50     for (int k = i + rowSize - 2; k > i; k--) {   // both the start and end need to be i, j, and also care about length
51         res.add(matrix[k][j]);
52     }
53 
54     this.printSpiralOrder(i + 1, j + 1, rowSize - 2, colSize - 2, res, matrix);
55 }