1、螺旋矩阵
题目：
给定一个包含 m*n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
示例:
输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出:
[1, 2, 3, 6, 9, 8, 7, 4, 5]
思路：
使用两个个指针分别指向矩阵的左上角边界和右下角边界，在创建一个指针从矩阵的左上角开始顺时针移动，每次移动到边界进行调头。当移动完一圈后缩小边界指针的范围，当边界指针交叉时结束移动。
代码实现：
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> list = new ArrayList<>();
// 如果长度为 0 直接结束
if (matrix.length == 0) {
return list;
}
// 左上角边界指针
int minRow = 0, minCol = 0;
// 右下角边界指针
int maxRow = matrix.length - 1, maxCol = matrix[0].length - 1;
// 移动指针
int rowPointer = 0, colPointer = 0;
// 边界指针交叉时，结束循环
while (minRow <= maxRow && minCol <= maxCol) {
// 从左往后遍历行
while (colPointer <= maxCol) {
list.add(matrix[rowPointer][colPointer++]);
}
// 指针越界后归为
colPointer--;
rowPointer++;
// 从上往下编列列
while (rowPointer <= maxRow) {
list.add(matrix[rowPointer++][colPointer]);
}
rowPointer--;
colPointer--;
// 防止指针将输出过的 minRow和minCol再次输出
if (minRow < maxRow && minCol < maxCol) {
while (colPointer >= minCol) {
list.add(matrix[rowPointer][colPointer--]);
}
colPointer++;
rowPointer--;
while (rowPointer > minRow) {
list.add(matrix[rowPointer--][colPointer]);
}
rowPointer++;
colPointer++;
}
// 缩小边界范围
minCol++;
maxRow--;
minRow++;
maxCol--;
}
return list;
}
2、0 所在的行列清 0
题目：
如果矩阵中某个元素为 0，则将其所在行和列清零。
示例:
输入:
[
[ 1, 2, 3 ],
[ 4, 0, 6 ],
[ 7, 8, 9 ]
]
输出:
[ 1, 0, 3 ]
[ 0, 0, 0 ]
[ 7, 0, 9 ]
思路：
遍历矩阵将所有含有 0 的行和列分别保存到临时数组，遍历临时数组，将矩阵中指定的行和列换为 0。
代码实现：
public static void zero(int[][] matrix) {
// 记录含有0的行
int[] row = new int[matrix.length];
// 记录含有0的列
int[] col = new int[matrix[0].length];
// 查看矩阵中那些行和列中含有零
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] == 0) {
row[i] = 1;
col[j] = 1;
}
}
}
// 将矩阵中指定的行和列变为0
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (row[i] == 1 || col[j] == 1) {
matrix[i][j] = 0;
}
}
}
// 打印矩阵
for (int[] ints : matrix) {
System.out.println(Arrays.toString(ints));
}
}
3、Z 字型打印矩阵
题目：
将指定矩阵按 Z 字型打印出来
示例:
输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出:
[1, 2, 4, 7, 5, 3, 6, 8, 9]
思路：
创建一个指针以 Z 型遍历矩阵，指针斜着移动的方向有两个路，往右上方向移动时，当移动到上边界时往右移动一格再往左下移动，当移动到右边界时往下移动一格再往左下移动；往左下方向移动时，当移动到下边界时往右移动一格再往右上移动，当移动到左边界时往下移动一格再往右上移动。
代码实现：
public static void typeZ(int[][] matrix) {
// 指针
int col = 0;
int row = 0;
// 记录矩阵的边界
int colBoundary = matrix[0].length - 1;
int rowBoundary = matrix.length - 1;
// true为向右上走，false左下走
boolean direction = true;
// 如果超过边界则结束
while (col <= colBoundary && row <= rowBoundary) {
if (direction) {
System.out.print(matrix[row][col] + " ");
// 如果指针到了上边界，则往右走
if (row == 0 && col < colBoundary) {
col++;
direction = false;
} else if (col == colBoundary) {
// 如果到了右边界，则往下走，接着往左下走
row++;
direction = false;
} else {
// true往右上走
col++;
row--;
}
} else {
System.out.print(matrix[row][col] + " ");
if (col == 0 && row < rowBoundary) {
// 到左边界往下走
row++;
direction = true;
} else if (row == rowBoundary) {
// 到下边界往右走
col++;
direction = true;
} else {
// true往左下走
col--;
row++;
}
}
}
}
4、边界为 1 的最大正方形
题目：
给定一个 N*N 的矩阵，在这个矩阵中，只有 0 和 1 两种值，返回边框全是 1 的最大正方形的边长长度。
思路：
方法一：暴力破解，从最大的阶数往最小的阶数依次遍历，扫描所有能组成指定阶数的正方形，查看正方形的边是否含有 0。
方法二：动态规划，我们可以维护一个三维数组对矩阵做预处理，第一维是矩阵的行的个数，第二维是矩阵列的个数，第三维长度为二，分别存储该下标对应于矩阵指定位置，右边 1 的个数和下边 1 的个数（包含自己）。当判断正方形的边是否都是 1 的时候，只需要判断正方形的左上角、右上角、左下角在三维数组值是否满足条件即可，不需要再遍历正方形的每条边。
代码实现：
方法一：暴力破解
public static int largest1BorderedSquare1(int[][] grid) {
// 矩阵的高
int height = grid.length;
// 矩阵的宽
int wide=grid[0].length;
// 需要求正方形的阶数
int orderNumber = height;
while (orderNumber > 0) {
// 行， 当前位置加要寻找的阶数不能大于行总长度
for (int i = 0; i <= height - orderNumber; i++) {
col:
// 列， 当前位置加要寻找的阶数不能大于宽总长度
for (int j = 0;j <= wide - orderNumber ;j++) {
// 指针
int row = i;
int col = j;
// 计算对角坐标
int diagonalAngleRow = row + orderNumber - 1;
int diagonalAngleCol = col + orderNumber - 1;
// 检查上边是否含有0
while (col <= diagonalAngleCol) {
if (grid[row][col++] == 0) {
continue col;
}
}
// 越界后，归位
col = diagonalAngleCol;
// 检查右边是否含有0
while (row <= diagonalAngleRow) {
if (grid[row++][col] == 0) {
continue col;
}
}
// 检测下边是否含有0
while (diagonalAngleCol >= j) {
if (grid[diagonalAngleRow][diagonalAngleCol--] == 0) {
continue col;
}
}
// 越界后，归位
diagonalAngleCol = j;
// 检测左边是否含有0
while (diagonalAngleRow >= i) {
if (grid[diagonalAngleRow--][diagonalAngleCol] == 0) {
continue col;
}
}
// 返回阶数
return orderNumber;
}
}
orderNumber--;
}
return 0;
}
方法二：动态规划
public static int largest1BorderedSquare(int[][] grid) {
if (grid.length == 0) {
return 0;
}
int height = grid.length;
int wide = grid[0].length;
// 创建临时数组来对矩阵进行预处理，防止越界
int[][][] temp = new int[height + 1][wide + 1][2];
for (int i = height - 1; i >= 0; i--) {
for (int j = wide - 1; j >= 0; j--) {
// 如果当前数为1，则将其右边
if (grid[i][j] == 1) {
// 右边
temp[i][j][0] = 1 + temp[i][j + 1][0];
// 下边
temp[i][j][1] = 1 + temp[i + 1][j][1];
}
}
}
// 要寻找的正方形的阶数
int orderNumber = height;
while (orderNumber > 0) {
// 行， 当前位置加要寻找的阶数不能大于行总长度
for (int i = 0; i <= height - orderNumber; i++) {
// 列， 当前位置加要寻找的阶数不能大于宽总长度
for (int j = 0; j <= wide - orderNumber; j++) {
// 左上角往右数1的个数要>=n
// 左上角往下数1的个数要>=n
// 左下角往右数1的个数要>=n
// 右上角往下数1的个数要>=n
if (temp[i][j][0] >= orderNumber && temp[i][j][1] >= orderNumber && temp[i + orderNumber-1][j][0] >= orderNumber && temp[i][j + orderNumber-1][1] >= orderNumber){
return orderNumber;
}
}
}
orderNumber--;
}
return 0;
}
5、子数组最大累加和
题目：
给定一个数组 array，返回子数组的最大累加和。
示例:
输入：
array=[1, -2, 3, 5, -2, 6, -1]
输出：
12，因为所有子数组中[3, 5, -2, -6]可以累加出最大的和 12。
思路：
方法一：暴力破解，使用双重循环遍历每一种可能求出最大值即可。
方法二：动态规划，创建两个变量一个记录子数组的最大和，一个记录子数组的临时和。遍历数组，每次循环将当前数和临时和相加，如果临时和大于等于 0 则继续往后加，如果小于 0 则将临时数组清零，即重定向子数组的开头。
代码实现：
方法一：暴力破解
public static int maxSubArray(int[] nums) {
// 保存最大的和
int max = nums[0];
for (int i = 0; i < nums.length; i++) {
int sum = nums[i];
if (max < sum) {
max = sum;
}
for (int j = i + 1; j < nums.length; j++) {
// 每次往后加一个数，然后和最大的比较
sum += nums[j];
if (max < sum) {
max = sum;
}
}
}
return max;
}
方法二：动态规划
public static int maxSubArray(int[] nums) {
// 临时的和
int temp = 0;
// 保存最大的和
int max = nums[0];
for (int num : nums) {
temp += num;
if (max < temp) {
max = temp;
}
// 如果临时的和大于0则继续往下加，否则重定向开头
if (temp < 0) {
temp = 0;
}
}
return max;
}
6、子矩阵的最大累加和
题目：
给定一个矩阵 matrix，其中的值有正、有负、有 0，返回子矩阵的最大累加和。
示例:
输入：
[
[ -1, -1, -1],
[ -1, 2, 2],
[ -1, -1, -2]
]
输出：
4，其中最大累加和的子矩阵为：2 2
思路：
我们可以把矩阵按行分割成小矩阵，然后对小矩阵每一列上的值求和，可以得到一个数组，则求子矩阵的最大累加和就转换为子数组的最大累加和。所以我们只需要遍历由不同的矩阵组成的数组，求出子数组的最大累加和即可。
代码实现：
public static int maxMatrix(int[][] matrix) {
if (matrix.length == 0) {
return 0;
}
// 存储矩阵的高
int maxHeight = matrix.length;
int maxWide = matrix[0].length;
// 起始行
int row = 0;
// 保存最大的和
int max = 0;
while (row < maxHeight) {
int[] temp = new int[maxWide];
for (int i = row; i < maxHeight; i++) {
// 按列累加
for (int j = 0; j < maxWide; j++) {
temp[j] += matrix[i][j];
}
// 累加完成后求和
int t = maxSubArray(temp);
// 保留最大的值
if (max < t) {
max = t;
}
}
row++;
}
return max;
}
public static int maxSubArray(int[] nums) {
// 临时的和
int temp = 0;
// 保存最大的和
int max = nums[0];
for (int num : nums) {
temp += num;
if (max < temp) {
max = temp;
}
// 如果临时的和大于0则继续往下加，否则重定向开头
if (temp < 0) {
temp = 0;
}
}
return max;
}
7、矩阵的四则运算
1）加法和减法
两个矩阵相加减，即他们相同位置的元素相加减，矩阵的加法和减法满足交换律和结合律。注意：只能对于两个行数和列数都相等的矩阵进行加减法。
[ a1, a2, a3 ]
a = [ a4, a5, a6 ]
[ a7, a8, a9 ]
[ b1, b2, b3 ]
b = [ b4, b5, b6 ]
[ b7, b8, b9 ]
[ a1 ± b1, a2 ± b2, a3 ± b3 ]
a ± b = [ a4 ± b4, a5 ± b5, a6 ± b6 ]
[ a7 ± b7, a8 ± b8, a9 ± b9 ]
2）乘法和除法
将矩阵和一个数值进行乘法和除法时，则对矩阵中的每个元素进行乘/除。当两个矩阵进行乘除法时，将 A 矩阵的第一行的 B 矩阵的每一列相乘得到结果集的第一行。乘法和除法满足分配律和结合律。注意：A 矩阵的行数必须等于 B 矩阵的列数才能进行乘/除法。
[ a1, a2]
a = [ a3, a4]
[ b1, b2, b3 ]
b = [ b4, b5, b6 ]
[a1b1 + a2b4, a1b2 + a2b5, a1b3 + a2b6]
ab = [a3b1 + a4b4, a3b2 + a4b5, a3b3 + a4b6]
标题：多维数组和矩阵的相关算法题
作者：Yi-Xing
地址：http://47.94.239.232/articles/2019/11/24/1574587705274.html
博客中若有不恰当的地方，请您一定要告诉我。前路崎岖，望我们可以互相帮助，并肩前行！