您好,欢迎访问代理记账网站
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

【力扣笔记54】螺旋矩阵

题目

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

示例 1:

img

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

示例 2:

img

输入: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/


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进