【題目描述】
輸入一個矩陣,按照從外向裡以順時針的順序依次列印出每一個數字。
例如,如果輸入如下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.
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIiclRnblN2XjlGcjAzNfRHLGZkRGZkRfJ3bs92YsYTMfVmepNHL9gjVkRnVYJmb1cVWvB3MMBjVtJWd0ckW65UbM5WOHJWa5kHT20ESjBjUIF2X0hXZ0xCMx81dvRWYoNHLrdEZwZ1Rh5WNXp1bwNjW1ZUba9VZwlHdssmch1mclRXY39CXldWYtlWPzNXZj9mcw1ycz9WL49zZuBnL0kjMxETNykTMyATMxAjMwIzLc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)
【官方解法】
class Solution {
public:
//定義print函數列印每一個圈的數字
//本題有兩個圈,外圈:[1,2,3,4,8,12,16,15,14,13,9,5],内圈:[6,7,11,10]
//lx ly rx ry分别為左上角和右下角的坐标,matrix為原矩陣,ret為輸出數組
void print(int lx, int ly, int rx, int ry, vector<vector<int>> &matrix, vector<int> &ret) {
for (int j=ly; j<=ry; ++j) ret.push_back(matrix[lx][j]);
//1.ly=0,ry=3,ret中有1,2,3,4
//2.ly=1,ry=2,ret中有1,2,3,4,8,12,16,15,14,13,9,5,6,7
for (int i=lx+1; i<=rx; ++i) ret.push_back(matrix[i][ry]);
//1.lx+1=1,rx=4,ret中有1,2,3,4,8,12,16
//2.ret中有1,2,3,4,8,12,16,15,14,13,9,5,6,7,11
int h = rx - lx + 1;
//1.h=3-0+1=4
//2.h=2-1+1=2
if (h > 1)
for (int rj=ry-1; rj>=ly; --rj) ret.push_back(matrix[rx][rj]);
//1.ry-1=3,ly=3,ret中有1,2,3,4,8,12,16,15,14,13
//2.ret中有1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10
int w = ry - ly + 1;
//1.w=3-0+1=4
//2.w=2-1+1=2
if (w > 1)
for (int ri = rx-1; ri>=lx+1; --ri) ret.push_back(matrix[ri][ly]);
// 1.rx-1=3,lx+1=1,ret中有1,2,3,4,8,12,16,15,14,13,9,5
//2.rx-1=1,lx+1=2,不滿足for循環條件不執行
}
//matrix為[[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]
vector<int> printMatrix(vector<vector<int>>& matrix) {
vector<int> ret;//定義輸出矩陣ret
if (matrix.empty()) return ret;//判空操作
int lx = 0, ly = 0; //左上角坐标為(0,0)
int rx = matrix.size()-1, ry = matrix[0].size()-1;//右下角坐标
while (lx <= rx && ly <= ry) {
print(lx++, ly++, rx--, ry--, matrix, ret);//先用再--
//1.lx=0,ly=0,rx=3,ry=3,ret中有1,2,3,4,8,12,16,15,14,13,9,5
//2.lx=1,ly=1,rx=2,ry=2,ret中有1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10
//3.lx=2,ly=2,rx=1,ry=1,條件不滿足不執行
}
return ret;
}
};
【B站解法】
class Solution {
public:
vector<int> printMatrix(vector<vector<int> > matrix) {
vector<int> res;
//定義方向
//碰壁換方向 右下左上
if(matrix.empty()) return res;//判空操作
int n = matrix.size(), m = matrix[0].size(); //查詢數組大小
vector<vector<bool>> state(n, vector<bool>(m, false));//定義臨時存儲數組
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; //換方向提示變量 上右下左
int x = 0, y = 0, d = 1;//由于是右下左上是以是d=1
for(int i = 0; i < n * m; i ++)
{
res.push_back(matrix[x][y]); 1;2
state[x][y] = true;
int a = x + dx[d], b = y + dy[d]; 0,1;
if(a < 0 || a >= n || b < 0 || b >= m || state[a][b] == true)
{
d = (d + 1) % 4;//除以4取餘數
a = x + dx[d], b = y + dy[d];
}
x = a, y = b; 0,1
}
return res;
}
};
思考;
若int dx[4] = { 0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};右下左上
那麼int d=0;下面的 d = d + 1
解決:
不應該是d=d+1,還應該是d=(d+1)%4,因為不止有一圈,是以數組會越界。
按道理可以想法可以,但是無法通過,不太了解?