[LeetCode] 54. Spiral Matrix

轉自LeetCode

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:

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

You should return [1,2,3,6,9,8,7,4,5].

<Solution>

這題是要對一個 m x n 的二維矩陣，用螺旋的方式，依序排到一個一維陣列

方向是 : 右  -> 下  ->  左  ->  上，這樣做循環直到結束

比較難的部分是 index 怎麼取，做法不只一種

code 如下
c++

	class Solution {
	public:
	vector<int> spiralOrder(vector<vector<int>>& matrix) {
	if(matrix.empty()) {
	return vector<int>();
	}
	else if(matrix.size() == 1) {
	return matrix[0];
	}
	int rowUp = 0, rowDown = matrix.size();
	int colLeft = -1, colRight = matrix[0].size();
	const int total = rowDown * colRight;
	int cnt = 0, moveD = 0;
	int r = 0, c = 0;
	vector<int> ans(total, 0);
	while(cnt < total) {
	ans[cnt++] = matrix[r][c];
	switch(moveD) {
	case 0: //> go right
	if(++c == colRight) {
	++r;
	--colRight;
	c = colRight;
	moveD = 1;
	}
	break;
	case 1: //> go down
	if(++r == rowDown) {
	--c;
	--rowDown;
	r = rowDown;
	moveD = 2;
	}
	break;
	case 2: //> go left
	if(--c == colLeft) {
	--r;
	++colLeft;
	c = colLeft;
	moveD = 3;
	}
	break;
	case 3: //> go up
	if(--r == rowUp) {
	++c;
	++rowUp;
	r = rowUp;
	moveD = 0;
	}
	break;
	}
	}
	return ans;
	}
	};

view raw spiralMatrix.cpp hosted with ❤ by GitHub

kotlin

	class Solution {
	fun spiralOrder(matrix: Array<IntArray>): List<Int> {
	var rowFirst = 0
	var rowLast = matrix.lastIndex
	var colFirst = 0
	var colLast = matrix[0].lastIndex
	val total = matrix.size * matrix[0].size
	val ans = mutableListOf<Int>()
	var r = 0
	var c = 0
	var direction = 0
	while(ans.size < total) {
	ans.add(matrix[r][c])
	when(direction) {
	0 -> { //>> move right
	if(++c > colLast) {
	++r
	c = colLast
	++rowFirst
	direction = 1
	}
	}
	1 -> { //>> move down
	if (++r > rowLast) {
	--c
	r = rowLast
	--colLast
	direction = 2
	}
	}
	2 -> { //>> move left
	if (--c < colFirst) {
	--r
	c = colFirst
	--rowLast
	direction = 3
	}
	}
	else -> { //>> move up
	if (--r < rowFirst) {
	++c
	r = rowFirst
	++colFirst
	direction = 0
	}
	}
	}
	}
	return ans
	}
	}

view raw spiral_matrix.kt hosted with ❤ by GitHub