【python】Leetcode每日一题-螺旋矩阵

Leetcode每日一题-螺旋矩阵

【题目描述】

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

示例1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

示例2：

输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrixi <= 100

【分析】

• 思路：

  首先打印矩阵周围一圈，再对矩阵进行切片，成为一个新的矩阵，再对新矩阵进行打印，有点递归的感觉。

  切片代码：matrix = [matrix_[c:m_-c][i][c:n_-c] for i in range(m_-c*2)]

• AC代码：

  class Solution(object):
      def spiralOrder(self, matrix_):
          """
          :type matrix: List[List[int]]
          :rtype: List[int]
          """
          output = []
          m_ = len(matrix_)
          n_ = len(matrix_[0])
          cycle =  m_ if m_ < n_ else n_
          for c in range((cycle+1)//2):
          	matrix = [matrix_[c:m_-c][i][c:n_-c] for i in range(m_-c*2)]
          	#print(matrix)
          	n = len(matrix[0])
  	        m = len(matrix)
  	        for i in range(n):
  	        	output.append(matrix[0][i])
  	        for i in range(m-1):
  	        	output.append(matrix[i+1][n-1])
  	        for i in range(n-1):
  	        	if(m-1==0):
  	        		break
  	        	output.append(matrix[m-1][n-i-2])
  	        for i in range(m-2):
  	        	if(n-1==0):
  	        		break
  	        	output.append(matrix[m-i-2][0])
          return output
  

• 讨论：

  • java版的0ms代码：

    class Solution {
        public List spiralOrder(int[][] matrix) {
            List ans = new ArrayList<>();
            int[] pos = { 0, 0 };
            // 上 右 下 左
            int[] ract = { 0, matrix[0].length - 1, matrix.length - 1, 0, };
            // d = 0,1,2,3时 分别代表往右、往下、往左、往上
            int d = 0;
            while (ans.size() < matrix.length * matrix[0].length) {
                ans.add(matrix[pos[0]][pos[1]]);
                if (d == 0 && pos[1] < ract[1]){
                    pos[1] ++;
                    continue;
                }
                if (d == 0 && pos[1] == ract[1]){
                    pos[0] ++;
                    ract[d] ++;
                    d = (d + 1) % 4 ;
                    continue;
                }
                if (d == 1 && pos[0] < ract[2]){
                    pos[0] ++;
                    continue;
                }
                if (d == 1 && pos[0] == ract[2]){
                    pos[1] --;
                    ract[d] --;
                    d = (d + 1) % 4 ;
                    continue;
                }
                if (d == 2 && pos[1] > ract[3]){
                    pos[1] --;
                    continue;
                }
                if (d == 2 && pos[1] == ract[3]){
                    pos[0] --;
                    ract[d] --;
                    d = (d + 1) % 4 ;
                    continue;
                }
                if (d == 3 && pos[0] > ract[0]){
                    pos[0] --;
                    continue;
                }
                if (d == 3 && pos[0] == ract[0]){
                    pos[1] ++;
                    ract[d] ++;
                    d = (d + 1) % 4 ;
                    continue;
                }
            }
            return ans; 
        }
    }
    

  • 螺旋向量的转移方程：

    di, dj = 0, 1
    di, dj = dj, -di
    

    取自点赞量最高的讨论

  • 官方题解： 戳这里