1. 矩阵旋转
将 n × n 矩阵顺时针旋转 90°。
我的思路是 “ 从外到内一层一层旋转 ”。
一个 n × n 矩阵有 (n + 1) / 2 层，每层有 4 部分，将这 4 部分旋转。
顺时针旋转 90° 就是将 matrix[n - 1 - q][p] 赋值给 matrix[p][q] 即可。
C++代码：
1 void rotate(vector<vector<int>>& matrix) { 2 int n = matrix.size(); 3 for (int i = 0; i < (n + 1) / 2; i++) { 4 for (int j = i; j < n - 1 - i; j++) { 5 int p = i, q = j; 6 int temp = matrix[p][q]; 7 for (int k = 0; k < 3; k++) { 8 matrix[p][q] = matrix[n - 1 - q][p]; 9 int tp = p; 10 p = n - 1 - q; 11 q = tp; 12 } 13 matrix[p][q] = temp; 14 } 15 } 16 }
答案的方法非常直观易懂！学到了！
首先将矩阵从上到下逆置，然后按对角线对称交换元素。
1 2 3 7 8 9 7 4 1 4 5 6 => 4 5 6 => 8 5 2 7 8 9 1 2 3 9 6 3
1 void rotate(vector<vector<int> > &matrix) { 2 reverse(matrix.begin(), matrix.end()); 3 for (int i = 0; i < matrix.size(); ++i) { 4 for (int j = i + 1; j < matrix[i].size(); ++j) 5 swap(matrix[i][j], matrix[j][i]); 6 } 7 }
逆时针旋转的原理类似。
首先将矩阵从左到右逆置，然后按对角线对称交换元素。注意从上到下和从左到右逆置矩阵的区别！
1 2 3 3 2 1 3 6 9 4 5 6 => 6 5 4 => 2 5 8 7 8 9 9 8 7 1 4 7
1 void anti_rotate(vector<vector<int> > &matrix) { 2 for (auto vi : matrix) 3 reverse(vi.begin(), vi.end()); 4 for (int i = 0; i < matrix.size(); ++i) { 5 for (int j = i + 1; j < matrix[i].size(); ++j) 6 swap(matrix[i][j], matrix[j][i]); 7 } 8 }
2. 矩阵螺旋遍历
给定 m x n 矩阵，以螺旋顺序遍历矩阵所有元素。
e.g. 给出如下矩阵
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
返回 [1, 2, 3, 6, 9, 8, 7, 4, 5]。
我尝试定义行标记 i 和列标记 j，第一层是 (0, 0)，第二层是 (1, 1)，不断循环。每次循环内改变 i 和 j，实现螺旋遍历。但实现起来代码要写的非常冗长，比如最内层只有一行或只有一列时，就会出错。于是看了别人的解法，深受启发！
方法一：死办法
1 vector<int> spiralOrder(vector<vector<int>>& matrix) { 2 if (matrix.empty()) return {}; 3 int m = matrix.size(), n = matrix[0].size(); 4 vector<int> result(m * n); 5 int u = 0, d = m - 1, l = 0, r = n - 1, k = 0; 6 while (1) { 7 for (int j = l; j <= r; j++) result[k++] = matrix[u][j]; 8 if (++u > d) break; 9 for (int i = u; i <= d; i++) result[k++] = matrix[i][r]; 10 if (--r < l) break; 11 for (int j = r; j >= l; j--) result[k++] = matrix[d][j]; 12 if (--d < u) break; 13 for (int i = d; i >= u; i--) result[k++] = matrix[i][l]; 14 if (++l > r) break; 15 } 16 return result; 17 }
定义 u（上），d（下），l（左），r（右）表示各个方向的极限下标，转了一圈后，由于 ++u、--r、--d、++l ，进入里面一层继续螺旋遍历。
此外，由于知道结果数组大小（m x n），预先分配空间并直接赋值要比 push_back 效率高。
方法二：方向矩阵法
原理：
螺旋遍历就是不断地向 4 个方向（右、下、左、上）移动。假设要处理一个 5 x 3 的矩阵，初始标志位坐标设为 (0, -1)，即 '0' 的位置。
0 [ 1 2 3 4 5] [ 6 7 8 9 10] [11 12 13 14 15]
接下来需要移动标志位：
- 向右移动 5 位
向下移动 2 位 - 向左移动 4 位
向上移动 1 位 - 向右移动 3 位
向下移动 0 位 --> 结束
注意到方向一直是 “ 右 → 下 → 左 →上 ”，水平移动的步数是 { 5，4，3 } （5 是矩阵的行数），竖直移动的步数是 { 2，1，0 } （2 是矩阵的列数减 1）。
因此，可以构造一个方向矩阵存储所有方向，以及一个含有两个元素的数组存储水平和竖直移动的步数。这样就用一次循环代替了四次循环。
而且这样做的一个好处是，如果我们要改变遍历的起点（如从右上角元素开始），或者改变螺旋的方向（如逆时针），只需要改变方向矩阵，循环主体不需要改变。虽然更为复杂，但增加了代码的可重用性！
C++实现：
1 vector<int> spiralOrder(vector<vector<int>>& matrix) { 2 if (matrix.empty()) return {}; 3 int m = matrix.size(), n = matrix[0].size(); 4 vector<int> result; 5 vector<vector<int>> dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; 6 vector<int> step = {n, m - 1}; 7 int i = 0, j = -1, dirIndex = 0, stepIndex = 0; 8 while (step[stepIndex]) { 9 for (int k = 0; k < step[stepIndex]; k++) { 10 i += dir[dirIndex][0]; 11 j += dir[dirIndex][1]; 12 result.push_back(matrix[i][j]); 13 } 14 step[stepIndex]--; 15 stepIndex = (stepIndex + 1) % 2; 16 dirIndex = (dirIndex + 1) % 4; 17 } 18 return result; 19 }
可以发现 stepIndex 刚好等于 dirIndex % 2，可以进行替换，少定义一个变量，但也降低了可读性。
3. 螺旋矩阵
给定一个整数 n，产生一个方阵，该方阵由元素 1 到 n2 以螺旋顺序填充。
e.g. n = 3，返回矩阵
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]
死办法，定义 u、d、l、r。
1 vector<vector<int>> generateMatrix(int n) { 2 /* 注意 vector<vector<int>> 的初始化方式 */ 3 vector<vector<int>> result(n, vector<int>(n)); 4 int u = 0, r = n - 1, d = n - 1, l = 0, k = 1; 5 while(1) { 6 for (int j = l; j <= r; j++) result[u][j] = k++; 7 if (++u > d) break; 8 for (int i = u; i <= d; i++) result[i][r] = k++; 9 if (--r < l) break; 10 for (int j = r; j >= l; j--) result[d][j] = k++; 11 if (--d < u) break; 12 for (int i = d; i >= u; i--) result[i][l] = k++; 13 if (++l > r) break; 14 } 15 return result; 16 }
也可以使用定义方向矩阵的方法。