【力扣笔记54】螺旋矩阵

题目

给你一个 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 <= matrix[i][j] <= 100

解法1（错误）

思想：

利用递归的思想，一圈一圈的遍历，如图所示，紫色是第一圈，红色是第二圈：

每一次旋转遍历的起点都为（i，i）,i属于{0，1，2，...}，递归的判停条件是i>(行或列-1)/2，

golang代码：

func spiralOrder(matrix [][]int) []int {
   
   row := len(matrix)    //行
   col := len(matrix[0]) //列
   result := []int(nil)

   var rorate func(start int)

   rorate = func(start int) {
   
      if start > (row-1)/2 || start > (col-1)/2 {
   
         return
      }
      curRow, curCol := start, start
      //********往右
      for ; curCol < col-start; curCol++ {
   
         result = append(result, matrix[curRow][curCol])
      }
      //如果没有下一行则停止
      if curRow+1 == row-start {
   
         return
      }
      result = result[:len(result)-1]
      //********往下
      for ; curRow < row-start; curRow++ {
   
         result = append(result, matrix[curRow][curCol-1])
      }
      result = result[:len(result)-1]
      //********往左
      for ; curCol > start; curCol-- {
   
         result = append(result, matrix[curRow-1][curCol-1])
      }
      result = result[:len(result)-1]
      //********往上
      for ; curRow > start; curRow-- {
   
         result = append(result, matrix[curRow-1][curCol])
      }
      result = result[:len(result)-1]
      //下一圈
      rorate(start + 1)
   }

   rorate(0)
   return result
}

结果：

执行结果：解答错误

输入：[[7],[9],[6]]

输出：[7,9,6,9]

预期结果：[7,9,6]

错误分析：

没有判断只有一列的情况，此时并不需要再往左和上遍历了。

解法2（正确）

思想：以解法1代码为基础，增加了只有一列的判断条件

代码：

func spiralOrder(matrix [][]int) []int {
   
   row := len(matrix)    //行
   col := len(matrix[0]) //列
   result := []int(nil)
   //定义递归函数
   var rorate func(start int)
   rorate = func(start int) {
   
      //递归结束条件，即没有圈了则停止
      if start > (row-1)/2 || start > (col-1)/2 {
   
         return
      }
      curRow, curCol := start, start
      //********往右
      for ; curCol < col-start; curCol++ {
   
         result = append(result, matrix[curRow][curCol])
      }
       		//如果只有一行，则返回，不再往下
      if curRow+1 == row-start {
   
         return
      }
      result = result[:len(result)-1]
      //********往下
      for ; curRow < row-start; curRow++ {
   
         result = append(result, matrix[curRow][curCol-1])
      }
       		//如果只有一列，则返回，不再往左
      if curCol-1 == start {
   
         return
      }
      result = result[:len(result)-1]
      //********往左
      for ; curCol > start; curCol-- {
   
         result = append(result, matrix[curRow-1][curCol-1])
      }
      result = result[:len(result)-1]
      //********往上
      for ; curRow > start; curRow-- {
   
         result = append(result, matrix[curRow-1][curCol])
      }

      result = result[:len(result)-1]
      //遍历下一圈
      rorate(start + 1)
   }

   //调用递归函数
   rorate(0)
   
   return result
}

结果：

执行结果：通过

执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户

内存消耗：1.9 MB, 在所有 Go 提交中击败了62.93%的用户

官方解答：

https://leetcode-cn.com/problems/spiral-matrix/solution/luo-xuan-ju-zhen-by-leetcode-solution/

转载：https://blog.csdn.net/bestzy6/article/details/117266205