好久沒寫文章了...
自罰30大板
在刷leetcode
就繼續(xù)更新吧
Q：Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
eg 1:
Input:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]
eg 2:
Input:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]
題目很好理解，就是把一個(gè)矩陣螺旋著輸出憔恳。
看到這個(gè)題目瓤荔，我首先就想著使用深度優(yōu)先進(jìn)行搜索。這有點(diǎn)像迷宮的搜索钥组，我們可以定義搜索規(guī)則如下：
定義一個(gè)輔助矩陣输硝，判斷這個(gè)cell是否被搜索過(guò)。
eg
[
[1, 1, 1],
[1, 1, 1],
[1, 1, 1]
]
在這里者铜，1代表未被搜索過(guò)腔丧，0代表已經(jīng)被搜索過(guò)。
當(dāng)我們搜索完第一行作烟，matrix變成
[
[0, 0, 0 ],
[1, 1, 1 ],
[1, 1, 1]
]
這時(shí)候我們只有一個(gè)方向可以繼續(xù)往下走愉粤，就是朝下，因?yàn)樯舷伦笥叶际菬o(wú)法走的（0也是無(wú)法走的）拿撩，類似地衣厘，可以一直走到這個(gè)狀態(tài)
[
[0, 0, 0 ],
[0, 1, 0 ],
[0, 0, 0 ]
]
然后就只剩1可以走啦，也就是我們的搜索結(jié)束了ORZ
也就是說(shuō)我們需要定義的變量有以下幾個(gè)：
1 現(xiàn)在前進(jìn)的方向direction當(dāng)只有一個(gè)方向可以前行的時(shí)候進(jìn)行改變
2 保存答案的數(shù)組
3 現(xiàn)在的位置压恒，以便于下一次進(jìn)行Move的時(shí)候方便找到初始位置
4 狀態(tài)數(shù)組
然后就開始愉快地?cái)]碼影暴。
/**
direction： 方向
cur_i，cur_j：現(xiàn)在的位置
recMatrix： 狀態(tài)數(shù)組
ans： 保存答案的數(shù)組
**/
class Solution {
void move(int direction,int cur_i, int cur_j, vector<vector<int>>& matrix, vector<vector<int>>& recMatrix, vector<int>& ans){
if(direction == 0){
if( cur_j >= matrix[0].size() || recMatrix[cur_i][cur_j] == 0 ) return; //先判斷是否還有路可走探赫，沒有的話返回
for( int j = cur_j; ;j++){ //然后開始走型宙，并且記錄答案
if( j < matrix[cur_i].size() && recMatrix[cur_i][j] != 0 ){
cout << matrix[cur_i][j] << endl;
ans.push_back(matrix[cur_i][j]);
recMatrix[cur_i][j] = 0;
cur_j =j;
}
else break;
}
direction = 1;
move(direction, cur_i + 1, cur_j , matrix, recMatrix, ans);
}
else if(direction == 1){
if( cur_i >= matrix.size() || recMatrix[cur_i][cur_j] == 0 ) return;
for( int i = cur_i; ;i++){
if( i < matrix.size() && recMatrix[i][cur_j] != 0 ){
ans.push_back(matrix[i][cur_j]);
recMatrix[i][cur_j] = 0;
cur_i =i;
}
else break;
}
direction = 2;
move(direction, cur_i , cur_j - 1, matrix, recMatrix, ans);
}
else if(direction == 2){
if( cur_j < 0 || recMatrix[cur_i][cur_j] == 0 ) return;
for( int j= cur_j;; j--){
if( j >= 0 && recMatrix[cur_i][j] != 0 ){
ans.push_back(matrix[cur_i][j]);
recMatrix[cur_i][j] = 0;
cur_j =j;
}
else break;
}
direction = 3;
move(direction, cur_i - 1, cur_j , matrix, recMatrix, ans);
}
else if(direction == 3){
if( cur_i < 0 || recMatrix[cur_i][cur_j] == 0 ) return;
for( int i = cur_i; ;i--){
if( i >= 0 && recMatrix[i][cur_j] != 0 ){
ans.push_back(matrix[i][cur_j]);
recMatrix[i][cur_j] = 0;
cur_i =i;
}
else break;
}
direction = 0;
move(direction, cur_i , cur_j + 1, matrix, recMatrix, ans);
}
}
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> res;
// 定義的狀態(tài)舉證
vector<vector<int>> recMatrix;
if(matrix.size() ==0 ) return res;
// 初始化
for( int i = 0; i< matrix.size(); i++){
vector<int> tempMatrix;
for( int j = 0; j<matrix[i].size(); j++ ){
tempMatrix.push_back(1);
}
recMatrix.push_back(tempMatrix);
}
// direction 0:right 1:down 2:left 3:up
int direction = 0;
move(0, 0, 0, matrix, recMatrix, res);
return res;
}
};
提交結(jié)果 AC beats 100% 看來(lái)只有這一個(gè)解了。其實(shí)這個(gè)狀態(tài)數(shù)組完全是不需要的伦吠，但是我太懶了妆兑，AC了就不想改了魂拦，讀者也可是實(shí)現(xiàn)拋棄這個(gè)狀態(tài)數(shù)組進(jìn)行實(shí)現(xiàn)。
