问题： 顺时针打印二维方阵：
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;
}
}
![[极客大挑战 2019]Knife1](https://i-blog.csdnimg.cn/direct/150c4f6dfefa4820bcd59d67a7e88140.png)
