未分類

Spiral Matrix II

Array, Go, LeetCode

Spiral Matrix II

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

For example:

Given n = 3,

You should return the following matrix:

1
2
3
4
5
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]
提示 解題應用
Array 二元陣列

Default:

1
2
3
func generateMatrix(n int) [][]int {
}

解答思路:

建議可以先參考先前Spiral Matrix的解法，解說較為詳細，基本上概念完全一樣，只是將先前題的程式碼稍做修改而已，如果能將二元陣列以螺旋的方式輸出所有元素，當然要直接輸出一個nxn二元陣列以螺旋排序的元素1~n^2就不會太困難。

一開始先初始化空的nxn二元陣列，剩下的就是以螺旋的方式一邊遍歷一邊將值依序放入目標位置即可，而一樣也是藉由四個變數來控制要遍歷的位置以避免重覆，並且隨著最外圈遍歷結束後四個變數也跟著向內縮，有概念之後就可以很容易順勢寫程式碼了。

程式碼解說:

這邊只解說與先前題目程式碼的相異之處，因為這次是要直接輸出一個nxn二元陣列以螺旋排序的元素1~n^2，所以一開始利用迴圈先初始化空的nxn二元陣列，並用一個變數來慢慢遞增用以儲存至陣列的元素值，接著就是藉由四個變數來控制要遍歷的位置，以遍歷最上面的邊來說，將原本要從二元陣列上邊位置取出值的部分改為將該位置放入我們要的值(變數)，放入之後再將變數+1，待上邊遍歷結束再內縮直到全數遞增的值放入完畢才回傳整個二元陣列結果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var rowStart int
rowEnd := n - 1
var colStart int
colEnd := n - 1
var matrix [][]int
count := 1
for i := 1; i <= n; i++ {
	matrix = append(matrix, make([]int, n))
}
for colStart <= colEnd && rowStart <= rowEnd {
	for i := colStart; i <= colEnd; i++ {
		matrix[rowStart][i] = count
		count++
	}
	rowStart++
	...
}
return matrix

完整程式碼:

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
func generateMatrix(n int) [][]int {
	var rowStart int
	rowEnd := n - 1
	var colStart int
	colEnd := n - 1
	var matrix [][]int
	count := 1
	for i := 1; i <= n; i++ {
		matrix = append(matrix, make([]int, n))
	}
	for colStart <= colEnd && rowStart <= rowEnd {
		for i := colStart; i <= colEnd; i++ {
			matrix[rowStart][i] = count
			count++
		}
		rowStart++
		for i := rowStart; i <= rowEnd; i++ {
			matrix[i][colEnd] = count
			count++
		}
		colEnd--
		if rowStart <= rowEnd {
			for i := colEnd; i >= colStart; i-- {
				matrix[rowEnd][i] = count
				count++
			}
		}
		rowEnd--
		if colStart <= colEnd {
			for i := rowEnd; i >= rowStart; i-- {
				matrix[i][colStart] = count
				count++
			}
		}
		colStart++
	}
	return matrix
}

總結:

建議可以先參考先前Spiral Matrix的解法，解說較為詳細，基本上概念完全一樣，只是這次是要輸出一個nxn二元陣列以螺旋排序的元素1~n^2，所以一開始先初始化空的nxn二元陣列，剩下的就是以螺旋的方式一邊遍歷一邊將值依序放入目標位置即可，而一樣也是藉由四個變數來控制要遍歷的位置以避免重覆，並且隨著最外圈遍歷結束後四個變數也跟著向內縮，有概念之後就可以很容易順勢寫程式碼了。

分享到