作者:Grey
原文地址:
博客园:矩阵类问题处理技巧
CSDN:矩阵类问题处理技巧
题目链接见:LeetCode 48. Rotate Image
本题主要的限制条件是:原地调整,即不开辟额外的二维数组来做。
主要思路如下
第一步,先处理外围的圈 然后同理依次处理每个内圈。
第二步,每个圈分组,组内每次一个元素占据下一个元素的位置,如果是N*N
就分(N-1)*(N-1)
个组。如下图。颜色一样的就是同一组。
第三步,每个组的每个数可以通过组号来定位。如下图:
编号一样的就是同一组,同一组的某个位置,按顺时针方向,可以很方便定位到本组下一个位置。
组内调整的核心代码如下
private static void rotate(int n, int[][] matrix, int zuoshangX, int zuoshangY, int youxiaX, int youxiaY) { int zu = n - 1; int youshangX = zuoshangX; int youshangY = youxiaY; int zuoxiaX = youxiaX; int zuoxiaY = zuoshangY; for (int i = 1; i <= zu; i++) { // 每组内部调整 int tmp = matrix[zuoshangX][zuoshangY]; matrix[zuoshangX][zuoshangY++] = matrix[zuoxiaX][zuoxiaY]; matrix[zuoxiaX--][zuoxiaY] = matrix[youxiaX][youxiaY]; matrix[youxiaX][youxiaY--] = matrix[youshangX][youshangY]; matrix[youshangX++][youshangY] = tmp; } }
完整代码见
class Solution { public static void rotate(int[][] matrix) { int n = matrix.length; int zuoshangX = 0; int zuoshangY = 0; int youxiaX = n - 1; int youxiaY = n - 1; while (n > 0) { // 先处理外围,然后逐步处理内圈。 rotate(n, matrix, zuoshangX++, zuoshangY++, youxiaX--, youxiaY--); n -= 2; } } private static void rotate(int n, int[][] matrix, int zuoshangX, int zuoshangY, int youxiaX, int youxiaY) { int zu = n - 1; int youshangX = zuoshangX; int youshangY = youxiaY; int zuoxiaX = youxiaX; int zuoxiaY = zuoshangY; for (int i = 1; i <= zu; i++) { // 每组内部调整 int tmp = matrix[zuoshangX][zuoshangY]; matrix[zuoshangX][zuoshangY++] = matrix[zuoxiaX][zuoxiaY]; matrix[zuoxiaX--][zuoxiaY] = matrix[youxiaX][youxiaY]; matrix[youxiaX][youxiaY--] = matrix[youshangX][youshangY]; matrix[youshangX++][youshangY] = tmp; } } }
LeetCode 54. Spiral Matrix
和上一题类似,先打印外围圈圈,然后切换到内圈,用同样的方式打印内圈,依次循环。
打印的时候,我们只需要定位左上和右下两个点的坐标位置即可确定一个矩形。
需要注意的是,最后有可能是一条直线,比如下述两种情况中的标红位置
对于形成一条直线的情况,单独处理并打印即可。
完整代码见
class Solution { public static List<Integer> spiralOrder(int[][] matrix) { if (null == matrix || matrix.length == 0 || matrix[0].length == 0) { return new ArrayList<>(); } int m = matrix.length; int n = matrix[0].length; // 左上角点 int a = 0, b = 0; // 右下角点 int c = m - 1, d = n - 1; List<Integer> ans = new ArrayList<>(); while (a <= c && b <= d) { spiral(matrix, a++, b++, c--, d--, ans); } return ans; } public static void spiral(int[][] matrix, int a, int b, int c, int d, List<Integer> ans) { if (a == c) { // 形成一条直线:共行 for (int i = b; i <= d; i++) { ans.add(matrix[a][i]); } return; } if (b == d) { // 形成一条直线:共列 for (int i = a; i <= c; i++) { ans.add(matrix[i][b]); } return; } for (int i = b; i < d; i++) { ans.add(matrix[a][i]); } for (int i = a; i < c; i++) { ans.add(matrix[i][d]); } for (int i = d; i > b; i--) { ans.add(matrix[c][i]); } for (int i = c; i > a; i--) { ans.add(matrix[i][b]); } } }
题目描述见:LintCode 185 · Matrix Zigzag Traversal
zigzag 方式如下
本题的主要思路是
从左上角的开始位置,准备两个变量 A 和 B,A 往左边走,走到不能再走的时候,往下走
B 往下走,走到不能再往下的时候,往左边走,每次 AB 构成的连线进行打印(方向交替变化)
完整代码见:
public class Solution { /** * @param matrix: An array of integers * @return: An array of integers */ public static int[] printZMatrix(int[][] matrix) { if (null == matrix || matrix.length == 0 || matrix[0].length == 0) { return null; } int m = matrix.length; int n = matrix[0].length; int[] ans = new int[m * n]; ans[0] = matrix[0][0]; // 右边-->下边 int a = 0, b = 0; // 下边-->右边 int c = 0, d = 0; int index = 1; boolean topToDown = true; for (int k = 0; k < m + n; k++) { if (b < n - 1) { b++; } else if (b == n - 1) { a++; } if (c < m - 1) { c++; } else if (c == m - 1) { d++; } if (topToDown) { int j = b; for (int i = a; i <= c; i++) { ans[index++] = matrix[i][j--]; } } else { int j = d; for (int i = c; i >= a; i--) { ans[index++] = matrix[i][j++]; } } topToDown = !topToDown; } return ans; } }
依旧是先处理外圈,然后依次内圈的处理方式,
完整代码见
package snippet; // 螺旋打印星号 public class Code_0093_PrintStar { public static void printStar(int N) { int leftUp = 0; int rightDown = N - 1; char[][] m = new char[N][N]; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { m[i][j] = ' '; } } while (leftUp <= rightDown) { set(m, leftUp, rightDown); leftUp += 2; rightDown -= 2; } for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { System.out.print(m[i][j] + " "); } System.out.println(); } } public static void set(char[][] m, int leftUp, int rightDown) { for (int col = leftUp; col <= rightDown; col++) { m[leftUp][col] = '*'; } for (int row = leftUp + 1; row <= rightDown; row++) { m[row][rightDown] = '*'; } for (int col = rightDown - 1; col > leftUp; col--) { m[rightDown][col] = '*'; } for (int row = rightDown - 1; row > leftUp + 1; row--) { m[row][leftUp + 1] = '*'; } } public static void main(String[] args) { printStar(5); } }
打印结果如下
* * * * * * * * * * * * * * *
算法和数据结构笔记