📑 题目：54. 螺旋矩阵

🚀 本题 LeetCode 传送门

题目大意

给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。

解题思路

  • 给出一个二维数组，按照螺旋的方式输出
  • 解法一：需要注意的是特殊情况，比如二维数组退化成一维或者一列或者一个元素。注意了这些情况，基本就可以一次通过了。
  • 解法二：提前算出一共多少个元素，一圈一圈地遍历矩阵，停止条件就是遍历了所有元素（count == sum）

代码

  1. package leetcode
  3. // 解法 1
  4. func spiralOrder(matrix [][]int) []int {
  5.  if len(matrix) == 0 {
  6.   return []int{}
  7.  }
  8.  res := []int{}
  9.  if len(matrix) == 1 {
  10.   for i := 0; i < len(matrix[0]); i++ {
  11.    res = append(res, matrix[0][i])
  12.   }
  13.   return res
  14.  }
  15.  if len(matrix[0]) == 1 {
  16.   for i := 0; i < len(matrix); i++ {
  17.    res = append(res, matrix[i][0])
  18.   }
  19.   return res
  20.  }
  21.  visit, m, n, round, x, y, spDir := make([][]int, len(matrix)), len(matrix), len(matrix[0]), 0, 0, 0, [][]int{
  22.   []int{0, 1},  // 朝右
  23.   []int{1, 0},  // 朝下
  24.   []int{0, -1}, // 朝左
  25.   []int{-1, 0}, // 朝上
  26.  }
  27.  for i := 0; i < m; i++ {
  28.   visit[i] = make([]int, n)
  29.  }
  30.  visit[x][y] = 1
  31.  res = append(res, matrix[x][y])
  32.  for i := 0; i < m*n; i++ {
  33.   x += spDir[round%4][0]
  34.   y += spDir[round%4][1]
  35.   if (x == 0 && y == n-1) || (x == m-1 && y == n-1) || (y == 0 && x == m-1) {
  36.    round++
  37.   }
  38.   if x > m-1 || y > n-1 || x < 0 || y < 0 {
  39.    return res
  40.   }
  41.   if visit[x][y] == 0 {
  42.    visit[x][y] = 1
  43.    res = append(res, matrix[x][y])
  44.   }
  45.   switch round % 4 {
  46.   case 0:
  47.    if y+1 <= n-1 && visit[x][y+1] == 1 {
  48.     round++
  49.     continue
  50.    }
  51.   case 1:
  52.    if x+1 <= m-1 && visit[x+1][y] == 1 {
  53.     round++
  54.     continue
  55.    }
  56.   case 2:
  57.    if y-1 >= 0 && visit[x][y-1] == 1 {
  58.     round++
  59.     continue
  60.    }
  61.   case 3:
  62.    if x-1 >= 0 && visit[x-1][y] == 1 {
  63.     round++
  64.     continue
  65.    }
  66.   }
  67.  }
  68.  return res
  69. }
  71. // 解法 2
  72. func spiralOrder2(matrix [][]int) []int {
  73.  m := len(matrix)
  74.  if m == 0 {
  75.   return nil
  76.  }
  78.  n := len(matrix[0])
  79.  if n == 0 {
  80.   return nil
  81.  }
  83.  // top、left、right、bottom 分别是剩余区域的上、左、右、下的下标
  84.  top, left, bottom, right := 0, 0, m-1, n-1 
  85.  count, sum := 0, m*n
  86.  res := []int{}
  88.  // 外层循环每次遍历一圈
  89.  for count < sum {
  90.   i, j := top, left
  91.   for j <= right && count < sum {
  92.    res = append(res, matrix[i][j])
  93.    count++
  94.    j++
  95.   }
  96.   i, j = top + 1, right
  97.   for i <= bottom && count < sum {
  98.    res = append(res, matrix[i][j])
  99.    count++
  100.    i++
  101.   }
  102.   i, j = bottom, right - 1
  103.   for j >= left && count < sum {
  104.    res = append(res, matrix[i][j])
  105.    count++
  106.    j--
  107.   }
  108.   i, j = bottom - 1, left
  109.   for i > top && count < sum {
  110.    res = append(res, matrix[i][j])
  111.    count++
  112.    i--
  113.   }
  114.   // 进入到下一层
  115.   top, left, bottom, right = top+1, left+1, bottom-1, right-1
  116.  }
  117.  return res
  118. }