矩阵简单问题(Java)

 问题： 顺时针打印二维方阵：
 1 2 3 4 15
 5 6 7 8 14
 9 10 11 12 13
 13 14 15 16

public class Test1 {public static void main(String[] args) {int[][] arr = new int[][]{{1, 2, 3, 4,100},{5, 6, 7, 8,101},{9, 10, 11, 12,102},{13, 14, 15, 16,103}};f1(arr);}static void f1(int[][] arr) {int leftRow = 0, leftCol = 0; //左上int rightRow = arr.length - 1, rightCol = arr[0].length - 1; //右下while (leftRow <= rightRow && leftCol <= rightCol) {for (int i = leftCol; i <= rightCol; i++) {System.out.print(arr[leftRow][i] + " ");}for (int i = leftRow + 1; i <= rightRow; i++) {System.out.print(arr[i][rightCol] + " ");}for (int i = rightCol - 1; i >= leftCol; i--) {System.out.print(arr[rightRow][i] + " ");}for (int i = rightRow - 1; i > leftRow; i--) {System.out.print(arr[i][leftCol] + " ");}leftRow++;leftCol++;rightRow--;rightCol--;}}
}

 问题：0所在的行和列清零
 1 2 3 4
 6 0 7 8
 9 10 0 11

只能先遍历一遍记录下0的位置，然后在改0

public class Test1 {public static void main(String[] args) {int[][] arr = new int[][]{{1, 2, 3, 4,100},{5, 6, 0, 8,101},{9, 10, 11, 0,102},{13, 14, 15, 16,103}};f2(arr);for (int[] ints : arr) {for (int i : ints) {System.out.print(i+" ");}System.out.println("");}}static void f2(int[][] arr){int m = arr.length,n = arr[0].length;int[] row = new int[m];int[] col = new int[n];for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(arr[i][j] == 0){row[i]=1;col[j]=1;}}}for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(row[i]==1 || col[j]==1){arr[i][j]=0;}}}}
}

 问题：“Z”型打印
1,2, 3, 4
5,6, 7, 8
9,10,11,12 结果为1 2 5 9 6 3 4 7 10 11 8 12

public class Test1 {public static void main(String[] args) {int[][] arr = new int[][]{{1,2, 3, 4},{5,6, 7, 8},{9,10,11,12}};f3(arr);}static void f3(int[][] arr){int row = 0,m = arr.length;int col = 0,n = arr[0].length;boolean flag = true;  //控制是斜向上打印还是斜向下打印while(row<m && col<n){if(flag){System.out.print(arr[row][col]+" ");if(row==0 && col <n-1){ //斜上打印，碰到上端，就打印右边的，然后在斜向下col++;flag=false;} else if (row>0 && col== n-1) {//斜上打印，碰到右端，就打印下边的，然后在斜向下row++;flag=false;}else {row--;col++;}}else {System.out.print(arr[row][col]+" ");if(col==0 && row < m-1){ //斜下打印，碰到左端，就打印下边的，然后在斜向上row++;flag=true;} else if (col > 0 && row == m - 1) {//斜下打印，碰到下端，就打印右边的，然后在斜向上col++;flag=true;}else {row++;col--;}}}}
}

给定一个n*n矩阵，值只有0和1 返回边框为1的最大正方形的边长长度
0,1,1,1,1
0,1,0,0,1
0,1,0,0,1
0,1,1,1,1
0,1,0,1,1 返回4

public class Test1 {public static void main(String[] args) {int[][] arr = new int[][]{{0,1,1,1,1},{0,1,0,0,1},{0,1,0,0,1},{0,1,1,1,1},{0,1,0,1,1}};System.out.println(f4(arr));}static int f4(int[][] arr){int n = arr.length;helper(arr);while(n>=1){for(int i=0;i<arr.length;i++){for(int j=0;j<arr.length;j++){if(i+n>arr.length || j+n>arr.length){continue;}/*if(test(arr,i,j,n)){return n;}*/if(help[i][j][0]>=n && help[i][j][1]>=n && help[i][j+n-1][1]>=n && help[i+n-1][j][0]>=n)return n;}}n--;}return 0;}static int[][][] help;  // 0为右边1的个数，1为下面1的个数//构建三维数组，维护每一元素1的个数static void helper(int[][] arr){int n=arr.length;help=new int[n][n][2];int row= n-1;//先填充好最下面的一行for(int j=n-1;j>=0;j--){int value = arr[row][j];if(value==1){if(j==n-1)help[row][j][0]=1;else help[row][j][0]=help[row][j+1][0]+1;help[row][j][1]=1;}}row--;//在逐渐向上遍历for (int i=row;i>=0;i--){for(int j=n-1;j>=0;j--){int value = arr[i][j];if(value==1){if(j==n-1)help[i][j][0]=1;else help[i][j][0]=help[i][j+1][0]+1;help[i][j][1]=help[i+1][j][1]+1;}}}}
}

问题：求最大子矩阵累加和，其值有正、有负、有0，返回子矩阵的最大累加和
解法：将矩阵中每行的相同列的元素逐渐相加，转化为 无序的一维数组求最大连续累加和。

那么我们先求一个一维无序数组arr，返回arr中子数组（连续）的最大累加和。

public class Test2 {public static void main(String[] args) {}static int f1(int[] arr){if(arr.length==0) return 0;int sum=arr[0],max=arr[0];int left = 0, right = 0;for(int i=1;i<arr.length;i++){if(sum<=0){sum=arr[i];left=i;//这里不能用continue，因为不能保证最大累加和大于0，可能每个元素都小于0.}else sum+=arr[i];if(sum>max){max=sum;right=i;}}System.out.println("left="+left+" ,right="+right);return max;}
}

然后按列求和，维护一个sum数组，sum[i]为第i列的元素求和，先是从第0行到最后一行的所有列求和，每加一次，求一次sum数组的最大子序列。然后在清空sum，然后在是第1行到最后一行的所有列求和，每次求和，求一次sum数组的最大子序列，然后在从第2行开启，直到遍历完所有行。

public class Test2 {public static void main(String[] args) {int[][] arr = new int[][]{{-90,48,78},{64,-40, 64},{-81,-7,66}};System.out.println(f2(arr));}static int f1(int[] arr){if(arr.length==0) return 0;int sum=arr[0],max=arr[0];int left = 0, right = 0;for(int i=1;i<arr.length;i++){if(sum<=0){sum=arr[i];left=i;//这里不能用continue，因为不能保证最大累加和大于0，可能每个元素都小于0.}else sum+=arr[i];if(sum>max){max=sum;right=i;}}System.out.println("left="+left+" ,right="+right);return max;}static int f2(int[][] arr){int row = 0; //从第一行作为起始行int m = arr.length;int n = arr[0].length;//按列求和int[] sums = new int[m];int max=0; //历史子矩阵累加和while(row<m){for(int i=row;i<m;i++){for(int j=0;j<n;j++){sums[j]+=arr[j][i];}//累加完成//求无序一维数组的最大连续累加和int t = f1(sums);max=Math.max(max,t);}//以下一行作为起始行，Arrays.fill(sums,0);row++;}return max;}
}