[Golang][Leetcode][Array]刷題系列-54-Spiral Matrix

Steven included in Leetcode Golang

2021-07-16 320 words 2 minutes

Contents

54. Spiral Matrix

Level : Medium

原題連結 : Click

題目 :

Given an m x n matrix, return all elements of the matrix in spiral order.

Example :

Note

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]

Output: [1,2,3,6,9,8,7,4,5]

以下是我自己的解法 - O(m*n)

Runtime: 0 ms, faster than 100.00% of Go online submissions for Spiral Matrix.

解題思路 :

這題與59題非常類似
首先題目要求螺旋式的從2D matrix中取出element
這個題目沒有特別的解法就是純粹需要設定好 “邊界條件” & “堅持循環不變量原則(與binary search相同)”
所以需要模擬順時針填入矩陣的過程

解法 :

首先我們可以先規劃出過程
1. 從左到右
2. 從上到下
3. 從右到左
4. 從下到上
然後我設定每次要走到底才算完成，像是 i = left -> right if left <= right
<= 是重點，也就是我們所謂的"堅持循環不變量原則"要定義的原則
且這邊多一個重點就是每一個過程都要判斷是否已經填完m*n個element了
再來想像每次走完一行或一列就很像築起了一道牆，同個方向的路程會 +-1
所以我們要設定4個邊界條件，也根據它們的初始位置跟矩陣的對應對他們賦值，m為row數，n為column數
1. left = 0
2. right = n - 1
3. top = 0
4. bottom = m - 1
先考慮在執行 1. 的情況，從j = left走到right，然後每個循環都將 res[e] = matrix[top][i]
因為已經成功築起了一道牆，所以top++
先考慮在執行 2. 的情況，從i = top走到bottom，然後每個循環都將 res[e] = matrix[i][right]
因為已經成功築起了一道牆，所以right–
先考慮在執行 3. 的情況，從j = right走到left，然後每個循環都將 res[e] = matrix[bottom][i]
因為已經成功築起了一道牆，所以bottom–
先考慮在執行 4. 的情況，從i = bottom走到top，然後每個循環都將 res[e] = matrix[i][left]
因為已經成功築起了一道牆，所以left++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
func spiralOrder(matrix [][]int) []int {
    
    m := len(matrix)
    n := len(matrix[0])
    
    left, right, top, bottom := 0, n-1, 0, m-1
    
    target := m*n -1
    
    e := -1
    
    res := make([]int, target +1)
    
    for e < target {
        
        for i := left; i <= right && e < target; i++ {
            
            e++
            
            res[e] = matrix[top][i]
        } 
        
        top++
        
        for i := top; i <= bottom && e < target; i++ {
            
            e++
            
            res[e] = matrix[i][right]
        }
        
        right--
        
        for i := right; i >= left && e < target; i-- {
            
            e++
            
            res[e] = matrix[bottom][i]
        } 
        
        bottom--
        
        for i := bottom; i >= top && e < target; i-- {
            
            e++
            
            res[e] = matrix[i][left]
        }
        
        left++
    }
    
    return res
    
}

最後祝福努力認真的各位 “All your dream of are hidden in your daily life” 我們峰頂見!!!