题目
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
思路
利用一个双向队列数组vector<deque>,
vector[start] 从前往后输出，vector[end]从后往前输出，其余队列输出首元素和尾元素，最外圈完毕vector 开始位置start+1(也就是从第二个队列开始），vector 结束位置，end-1,然后开递归查询。
示例
输入： {{1 , 2, 3 ,4 ,5 , 6} ,{5 , 6, 7, 8 , 9, 10} ,{9,10,11,12,14,15} , {13,14,15,16,17,18} ,{21,22,23,24,25,26} ,{31,32,33,34,35,36}}; 输出： 1 2 3 4 5 6 10 15 18 26 36 35 34 33 32 31 21 13 9 5 6 7 8 9 14 17 25 24 23 22 14 10 11 12 16 15
代码
#include <iostream>
#include <deque>
#include <vector>
using namespace std;
class Solution{
public:
vector<int> printMatrix(vector<vector<int>> matrix){
vector<deque<int>> v_sum;
vector<int> result;
if (matrix.size() == 0 || matrix[0].size() == 0)
return result;
// 每行为一个双向队列,整体为一个双向队列数组
for (int i = 0; i < matrix.size(); ++i) {
deque<int> temp;
for (int j = 0; j < matrix[i].size() ; ++j)
temp.push_back(matrix[i][j]);
v_sum.push_back(temp);
}
return printMatrix(v_sum,0,matrix.size()-1);
}
private:
vector<int> printMatrix(vector<deque<int>> matrix,int v_start, int v_end){
vector<int> result;
for (int i = v_start; i <= v_end ; ++i) {
if(i == v_start)
while (!matrix[i].empty()){
result.push_back(matrix[i].front());
cout << matrix[i].front() << " ";
matrix[i].pop_front();
} else if (i == v_end)
while (!matrix[i].empty()){
result.push_back(matrix[i].back());
cout << matrix[i].back() << " ";
matrix[i].pop_back();
} else {
result.push_back(matrix[i].back());
cout << matrix[i].back() << " ";
matrix[i].pop_back();
}
}
for (int j = v_end-1; j > v_start ; --j) {
result.push_back(matrix[j].front());
cout << matrix[j].front() << " ";
matrix[j].pop_front();
}
cout << endl;
v_start++; v_end--;
if (v_start <= v_end) {
vector<int> re = printMatrix(matrix, v_start, v_end);
result.insert(result.end(),re.begin(),re.end());
re.clear(); re.shrink_to_fit();
// result.insert(result.end(),printMatrix(matrix, v_start, v_end).begin(),printMatrix(matrix, v_start, v_end).end());
}
return result;
}
};
int main(){
vector<vector<int>> matrix = {{1,2,3,4,5,6},{5,6,7,8,9,10},{9,10,11,12,14,15},{13,14,15,16,17,18},{21,22,23,24,25,26},{31,32,33,34,35,36}};
vector<vector<int>> test = {{}};
Solution result;
cout << endl << test.size() << " " << test.capacity() << endl;
cout << endl << test[0].size() << " " << test[0].capacity() << endl;
vector<int> re = result.printMatrix(test);
cout << endl << " 结果是： " ;
for (int j = 0; j < re.size() ; ++j) {
cout << re[j] << " ";
}
return 0;
}
