矩阵
螺旋矩阵
题号54, 参考资料
给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
示例 1:
请在这里输入引用内容
输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]
原问题就是希望我们能顺时针转圈打印矩阵:
把抽象的问题转化成简单的，是这个题的精髓。如果我们将眼光局限于坐标每次该如何移动，如何判断矩阵中哪些点已经输出，哪些点还没有输出，那么你就是进坑里了，这种方法不是不行，但是在面试的场景下，扣各种边界会导致你非常容易出错。那么有什么办法可以快速解决呢？其实很简单，从全局来看，我们实际上是在绘制一个又一个的矩形边界：
如何绘制本层边界？如下图所示，我们每次绘制某一边界时（如矩形的上边界），不要把最后一个点绘制了，而是作为下一个边界的起点，那么最终结束位置在5，与下一圈的6正好衔接：
内外层衔接？
我们只需控制左上角和右下角两个点的坐标，然后每跑完一圈，坐标进行相应的增加或减少即可：
要考虑两个边界情况，一行和一列
public static void printMatrix(int[][] matrix){
// 设置对角点
if (matrix == null){
return;
}
// 两个对角点(a,b) 和 (c,d)
int a = 0;
int b = 0;
int c = matrix.length - 1;
int d = matrix[0].length - 1;
// 控制对角点向中心移动
while ( a<=c && b<=d) {
// 绘制轮廓函数
printContour(a++, b++, c--, d--, matrix);
}
}
public static void printContour(int a, int b, int c, int d, int[][] matrix){
// 一个点包含在一行和一列的情况中了
// 边界情况一：一行
if (a == c){
for (int j = b; j <= d; ++j){
System.out.print(matrix[a][j] + " ");
}
}else if (b == d){ // 边界情况二：一列
for (int i = a; i <= c; ++i){
System.out.print(matrix[i][b] + " ");
}
}else{
// up side
for (int j = b; j < d; ++j){
System.out.print(matrix[a][j] + " ");
}
// right side
for (int i = a; i < c; ++i){
System.out.print(matrix[i][d] + " ");
}
// bottom side
for (int j = d; j > b; --j){
System.out.print(matrix[c][j] + " ");
}
// left side
for (int i = c; i > a; --i){
System.out.print(matrix[i][b] + " ");
}
}
} 螺旋矩阵2
题号59
给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
输入: 3
输出:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]
继承与螺旋矩阵，这个题的思路就很清晰了，控制对角点打印并填充到list中，最后注意中心点要单独打印，这个是边界情况。
public static int[][] generateMatrix(int n){
// 因为是方阵，所以只需要控制两个对角点向中心移动，并填充轮廓
int[][] matrix = new int[n][n];
int a = 0;
int b = 0;
int c = matrix.length - 1;
int d = matrix[0].length - 1;
int num = 0;
// 不停的绘制轮廓，方法和 spiral_matrix_i 一致
while( a<=c && b<=d){
// top side
for (int j = b; j < d; ++j){
matrix[a][j] = ++num;
}
// right side
for (int i = a; i < c; ++i){
matrix[i][d] = ++num;
}
// bottom side
for (int j = d; j > b; --j){
matrix[c][j] = ++num;
}
// left side
for (int i = c; i > a; --i){
matrix[i][b] = ++num;
}
// central point
if ( a == c && b == d){
matrix[a][b] = ++ num;
}
++a;
++b;
--d;
--c;
}
return matrix;
} 图像旋转
力扣48
给定一个 n × n 的二维矩阵表示一个图像。
将图像顺时针旋转 90 度。
说明：
你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
解题思路：
首先观察旋转后的图像：
按照之前的思路，把问题分解，先观察最外面一圈的变化，问题就转换成如何将一个矩形边界旋转的问题了：
public static void rotate(int[][] matrix){
// 设置两个对角点
int tR = 0;
int tC = 0;
int dR = matrix.length-1;
int dC = matrix[0].length-1;
// 由外层到内层，逐步分解问题, 最后一个点不用处理
while (tR < dR){
rotateEdge(tR++, tC++, dR--, dC--, matrix);
}
} 我们先考虑最外面一层的第一个点，再考虑第二个点：
观察发现，这个跟遍历某一个边界的一边非常像，我们原地交换四个点只需要5步，再加上遍历某一边，旋转一个边界就此完成。
在交换的时候注意，如果按照顺时针顺序就会把前面的值覆盖了，如果采用逆时针，先记录1的值，然后让13覆盖它，再让16覆盖13，然后让4覆盖16，最后让temp覆盖4，按照这个顺序就只需要记录一个临时值。
public static void rotate(int[][] matrix){
// 设置两个对角点
int tR = 0;
int tC = 0;
int dR = matrix.length-1;
int dC = matrix[0].length-1;
// 由外层到内层，逐步分解问题, 最后一个点不用处理
while (tR < dR){
rotateEdge(tR++, tC++, dR--, dC--, matrix);
}
}
/*
(tR,tC) * * (tR,dC)
* * * *
* * * *
(dR,tC) * * (dR,dC)
第一次的时候:
0. 左上角的数(tR, tC), 用temp代理
1. 左上角(tR, tC) <-- 左下角的数(dR, tC)
2. 左下角(dR, tC) <-- 右下角的数(dR, dC)
3. 右下角(dR, dC) <-- 右上角(tR, dC)
4. 右上角(tR, dC) <-- 左上角的数代理(temp)
下一次的时候, 之后以此类推，做成循环
(tR, tC)向右移动->(tR, tC+1)
(dR, tC)向上移动->(dR-1, tC)
(dR, dC)向左移动->(dR, dC-1)
(tR, dC)向下移动->(tR+1, dC)
*/
public static void rotateEdge(int tR, int tC, int dR, int dC, int[][] matrix){
// 每一边有 dC-tC+1 个点，但只交换 dC-tC 次，每次最后一个点要剔除
// 比如 tC=0, dC=3, 一边4个点，只要交换3次
for (int i = 0; i < dC-tC; i++){
// 分析的时候只看成一次，移动一个点
// 每一次都是先用 temp 记录左上角的点
int temp = matrix[tR][tC+i];
// 1. 左上角(tR, tC) <-- 左下角的数(dR, tC)
matrix[tR][tC+i] = matrix[dR-i][tC];
// 2. 左下角(dR, tC) <-- 右下角的数(dR, dC)
matrix[dR-i][tC] = matrix[dR][dC-i];
// 3. 右下角(dR, dC) <-- 右上角(tR, dC)
matrix[dR][dC-i] = matrix[tR+i][dC];
// 4. 右上角(tR, dC) <-- 左上角的数代理(temp)
matrix[tR+i][dC] = temp;
}
} 
京公网安备 11010502036488号