四、多维数组与矩阵
1、顺时针打印二维数组
顺时针打印二维数组:
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
public class PrintTwoDArr {
public static void main(String[] args) {
int[][] matrix = {
{1,2,3,4},
{5,6,7,8},
{9,10,11,12},
{13,14,15,16},
};
print(matrix);
}
static void print(int[][] matrix) {
//左上角行、左上角列、右下角行、右下角列
int leftUpRow = 0, leftUpCol = 0, rightDownRow = matrix.length - 1, rightDownCol = matrix[0].length - 1;
while (leftUpRow<=rightDownRow && leftUpCol<=rightDownCol) {
int r = leftUpRow, c = leftUpCol;
//上面一条边
while (c <= rightDownCol) {
System.out.print(matrix[r][c++] + " ");
}
//恢复
c = rightDownCol;
r++;
//右边的一条边
while (r <= rightDownRow) {
System.out.print(matrix[r++][c] + " ");
}
//恢复
r = rightDownRow;
c--;
//下面的一条边
while (c >= leftUpCol) {
System.out.print(matrix[r][c--] + " ");
}
//恢复
c = leftUpCol;
r--;
//左边的一条边
while (r > leftUpRow) {
System.out.print(matrix[r--][c] + " ");
}
leftUpRow++;
leftUpCol++;
rightDownRow--;
rightDownCol--;
}
}
}
2、零所在的行列清零
矩阵中含有某个元素0，将其所在的行和列清零
1 2 3 4
5 6 0 8
9 0 11 12
13 14 15 16
输出：
1 0 0 4
0 0 0 0
0 0 0 0
13 0 0 16
public class CleanZeroInTwoDArr {
public static void main(String[] args) {
int[][] matrix = {
{1,2,3,0},
{5,6,0,8},
{9,0,11,12},
{13,14,15,16},
};
solve(matrix);
printMatrix(matrix);
}
public static void solve(int[][] matrix) {
int M = matrix.length;
int N = matrix[0].length;
//记录哪些行出现0
int[] rowRecord = new int[M];
//记录哪些列出现0
int[] colRecord = new int[N];
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (matrix[0][0]==0){
//标记
rowRecord[i]=1;
colRecord[j]=1;
}
}
}
for (int row = 0; row < M; row++) {
for (int col = 0; col < N; col++) {
//当前的行或列，被标记了，这个元素就应该变为0
if (rowRecord[row] ==1 || colRecord[col] ==1) {
matrix[row][col] = 0;
}
}
}
}
public static void printMatrix(int[][] matrix) {
for (int[] arr: matrix) {
for (int e:arr) {
System.out.print(e+"\t");
}
System.out.println();
}
}
}
一点小疑惑：这道题我检查了很多遍，甚至在码云上扣下了源代码来对比，但我的编译器输出仍然是原来一模一样的数组，也没有报错，所以还是学习下思路吧，求大家看后给我个评论呀。
3、Z字形打印二维数组
Z字形打印数组，相当于打印斜线
public class PrintMatrixZ {
public static void main(String[] args) {
int[][] matrix = {
{1,2,3,4},
{5,6,7,8},
{9,10,11,12},
{13,14,15,16},
};
print(matrix);
}
private static void print(int[][] matrix) {
int r=0, m=matrix.length;
int c=0, n=matrix[0].length;
boolean l2r = true; //左到由left to right
while (r<m && c<n) {
//左下到右上的斜线
if (l2r) {
System.out.print(matrix[r][c]+" ");
//在第一行，列未到边界，只能向右走
if (r==0 && c<n-1) {
l2r = !l2r; //切方向
c++;
continue;
}
//现在最后一列，只能向下走
else if (r>0 && c==n-1) {
l2r = !l2r;
r++;
continue;
}else {
//继续上坡
r--;
c++;
}
}
//反之，下坡
else {
System.out.print(matrix[r][c]+" ");
//走到第一列，只能向下走
if (c==0 &&r<m-1) {
l2r = !l2r;
r++;
continue;
}
//到最后一行，只能右走
else if (r==m-1) {
l2r = !l2r;
c++;
continue;
}else {
//下坡
r++;
c--;
}
}
}
}
}
4、子数组最大累加和
给定一个数组arr，返回子数组最大累加和
如：arr={1，-2,3，5，-2,6，-1} 所有的子数组中[3,5，-2,6]累加最大和12，则返回12
public class MaxSubArray {
//暴力解法O(n²)
static void findByForce(int[] arr) {
int maxSum = arr[0];
for (int j = 0; j < arr.length; j++) {
int sum = arr[j]; //某个元素为子数组的第一个元素
int maxOfJ = sum;
for (int i = j+1; i < arr.length; i++) {
sum += arr[i]; //累加后续元素
if (sum >maxOfJ) {
maxOfJ = sum;
}
}
if (maxOfJ>maxSum) {
maxSum =maxOfJ;
}
}
System.out.println(maxSum);
}
//递推法O（n）
static int findByDp(int[] arr) {
int sumJ = arr[0]; //前J个元素的最大贡献值
int max= sumJ;
int left=0, right=0;
for (int j = 1; j < arr.length; j++) {
if (sumJ>=0) { //左子表的最大和为正，继续向后累加
sumJ += arr[j];
}else {
sumJ = arr[j];
left = j; //丢弃前部分和的同时，更新left
}
if (sumJ>max) {
max = sumJ;
right = j; //更新max的同时更新right
}
}
return max;
}
public static void main(String[] args) {
int[] arr = {1,-2,3,5,-2,6,-1};
findByForce(arr);
findByDp(arr);
}
}
5、子矩阵最大累加和
给定一个矩阵matrix， 其中的值有正、有负、有零，返回子矩阵最大累加和
如：给出matrix
-1 -1 -1
-1 2 2
-1 -1 -1
其中最大累加和的子矩阵是2 2
所以返回4
import java.util.Arrays;
public class MaxSubMatrix {
public static void main(String[] args) {
int[][] matrix = {
{-1, -1, -1},
{-1, 2, 2},
{-1, -1, -1}
};
int res = maxSum(matrix);
System.out.println(res);
}
private static int maxSum(int[][] matrix) { //O（N^3）
int beginRow = 0; //以它为起始行
final int M = matrix.length;
final int N = matrix[0].length;
int[] sums = new int[N]; //按列求和
int max = 0; //历史最大子矩阵和
while (beginRow < M) { //起始行
for (int i = beginRow; i < M; i++) { //从起始行到第i行
//按列累加
for (int j = 0; j < N; j++) {
sums[j] += matrix[i][j];
}
//累加完成
//求出sums的最大和子数组
int t = MaxSubArray.findByDp(sums);
if (t > max) {
max = t;
}
}
//另起一行作为起始行，把sums清零
Arrays.fill(sums,0); //将sums的每个元素设为0
beginRow++;
}
return max;
}
}