算法很美——第三章：矩阵
-
题1：顺时针打印二维数组
原理：记录左上、右下坐标，递归打印一圈；递归跳出条件：行或列交错（相同），交错直接退出，相同打印后退出
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int m,n;
void fun(int **a,int leftuprow,int leftupcol,int rightdownrow,int rightdowncol)
{
if(leftuprow>rightdownrow||leftupcol>rightdowncol)return;
if(leftuprow==rightdownrow){for(int i=leftupcol;i<=rightdowncol;i++)printf("%d ",a[leftuprow][i]);return;}
if(leftupcol==rightdowncol){for(int i=leftuprow;i<=rightdownrow;i++)printf("%d ",a[i][leftupcol]);return;}
for(int i=leftupcol;i<=rightdowncol;i++)printf("%d ",a[leftuprow][i]);
for(int i=leftuprow+1;i<=rightdownrow;i++)printf("%d ",a[i][rightdowncol]);
for(int i=rightdowncol-1;i>=leftupcol;i--)printf("%d ",a[rightdownrow][i]);
for(int i=rightdownrow-1;i<=leftuprow+1;i++)printf("%d ",a[i][leftupcol]);
fun(a,leftuprow+1,leftupcol+1,rightdownrow-1,rightdowncol-1);
}
int main()
{
scanf("%d %d",&m,&n);
int **a;
a=(int **)malloc(sizeof(int *)*m);
for(int i=0;i<m;i++)a[i]=(int *)malloc(sizeof(int)*n);
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
scanf("%d",&a[i][j]);
fun(a,0,0,m-1,n-1);
return 0;
}
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main()
{
int m,n;
scanf("%d %d",&m,&n);
int a[m][n],row[m],col[n];
memset(row,0,sizeof(row));
memset(col,0,sizeof(col));
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
{scanf("%d",&a[i][j]);if(!a[i][j]){row[i]=1;col[j]=1;}}
for(int i=0;i<m;i++)
{
if(row[i])for(int j=0;j<n;j++)a[i][j]=0;
}
for(int j=0;j<n;j++)
{
if(col[j])for(int i=0;i<m;i++)a[i][j]=0;
}
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)printf("%d ",a[i][j]);
printf("\n");
}
return 0;
}
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int m,n;
int flag;
/*
flag=1:第一行或最后一行，向右走
flag=2:左下
flag=3:第一列或最后一列，向下走
flag=4:右上
*/
void fun(int **a,int i,int j,int flag)
{
printf("%d ",a[i][j]);
if(i==m-1&&j==n-1){printf("\n");return;}
if(flag==1)
{
j++;
if(i==0)fun(a,i,j,2);
else if(i==m-1)fun(a,i,j,4);
}
else if(flag==2)
{
i++;j--;
if(i==m-1)fun(a,i,j,1);
else if(j==0)fun(a,i,j,3);
else fun(a,i,j,2);
}
else if(flag==3)
{
i++;
if(j==0)fun(a,i,j,4);
else if(j==n-1)fun(a,i,j,2);
}
else if(flag==4)
{
i--;j++;
if(j==n-1)fun(a,i,j,3);
else if(i==0)fun(a,i,j,1);
else fun(a,i,j,4);
}
}
int main()
{
scanf("%d %d",&m,&n);
int **a;
a=(int **)malloc(sizeof(int *)*m);
for(int i=0;i<m;i++)a[i]=(int *)malloc(sizeof(int)*n);
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
scanf("%d",&a[i][j]);
fun(a,0,0,1);
return 0;
}
-
题4：边界为1的最大子矩阵
题目描述：给定N*N矩阵，矩阵中只有0、1两种值
思路1：枚举
从以N为边长的矩阵开始枚举，看是否边界都为1，一直到边长为1
枚举边长为n的矩阵：以左上角顶点为基准，横纵坐标为（0，N-n）范围内的点可作为边长为n的矩阵左上角顶点
优化：在判断以a[i][j]为边长为n的矩阵的左上角顶点，是否边界均为1前，可判断该点是否可作为边长为n的矩阵顶点
可初始化一个矩阵大小二维数组，记录包括该点及右方（下方）连续为1的顶点个数
生成该二维数组：初始化均为0，从最后一行最后一列开始，判断是否为一，是一，b[i][j]=b[i-1][j]+1;(最后一行、列，特殊令为1)
生成二维数组后：看左上角顶点下方右方有n个连续1，右上角顶点下方有n个连续1，左下角顶点右方有n个连续1，如以上条件均满足，则存在边长为n的边界为1的子矩阵
优化思路：枚举时间复杂度N的四次方，最外层是边长，不能优化，2~3层为行列数不能优化，只能优化判断以某顶点为左上角顶点的矩阵是否为所求，思考是否能把O(N)优化为O（logN）甚至O（1）
优化方法：打表
一位数组：以O（N^2）为基础优化
二维数组：以O（N^3）为基础优化
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int n;
typedef struct{
int x;
int y;
}helper;
void print(helper **a)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
printf("(%d,%d) ",a[i][j].x,a[i][j].y);
printf("\n");
}
}
void fun(int **a,helper **Helper)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
Helper[i][j].x=0;
Helper[i][j].y=0;
}
}
for(int j=n-1;j>=0;j--)
{
if(a[n-1][j]==1)
{
if(j==n-1)
Helper[n-1][j].x=1;
else
Helper[n-1][j].x=Helper[n-1][j+1].x+1;
Helper[n-1][j].y=1;
}
}
for(int i=n-2;i>=0;i--)
{
for(int j=n-1;j>=0;j--)
{
if(a[i][j]==1)
{
if(j==n-1)
Helper[i][j].x=1;
else
Helper[i][j].x=Helper[i][j+1].x+1;
Helper[i][j].y=Helper[i+1][j].y+1;
}
}
}
for(int N=n;N>=1;N--)
{
for(int i=0;i<=n-N;i++)
{
for(int j=0;j<=n-N;j++)
{
if(Helper[i][j].x>=N&&Helper[i][j].y>=N&&Helper[i][j+N-1].y>=N&&Helper[i+N-1][j].x>=N)
{
printf("%d\n",N);return;
}
}
}
}
}
int main()
{
scanf("%d",&n);
int **a;
a=(int **)malloc(sizeof(int *)*n);
for(int i=0;i<n;i++)a[i]=(int *)malloc(sizeof(int)*n);
helper **Helper;
Helper=(helper **)malloc(sizeof(helper *)*n);
for(int i=0;i<n;i++)Helper[i]=(helper *)malloc(sizeof(helper)*n);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
scanf("%d",&a[i][j]);
fun(a,Helper);
return 0;
}
-
题5：子数组最大累加和
思路：如果前部分累加和为负，则其对最大累加和无贡献
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int n;
void fun(int a[])
{
int max=a[0],now;
if(a[0]>0)now=a[0];
else now=0;
for(int i=1;i<n;i++)
{
now+=a[i];
if(now>max)max=now;
if(now<0)now=0;
}
printf("%d\n",max);
}
int main()
{
scanf("%d",&n);
int a[n];
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
fun(a);
return 0;
}
-
题6：求子矩阵最大累加和
思路：求任意连续n行最大累加和，可按列相加，求子数列最大累加和
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int m,n;
int max0;
void fun(int a[])
{
int now;
if(a[0]>0)now=a[0];
else now=0;
for(int i=1;i<n;i++)
{
now+=a[i];
if(now>max0)max0=now;
if(now<0)now=0;
}
//printf("%d\n",max);
}
void fun2(int **a)
{
for(int i=0;i<n;i++)//起始行
{
for(int j=1;j<=n-i-1;j++)//共几行
{
int sum[n];
memset(sum,0,sizeof(sum));
for(int p=0;p<n;p++)
{
for(int q=i;q<i+j;q++)
sum[p]+=a[q][p];
}
fun(sum);
}
}
printf("%d\n",max0);
}
int main()
{
scanf("%d %d",&m,&n);
int **a;
a=(int **)malloc(sizeof(int *)*n);
for(int i=0;i<n;i++)a[i]=(int *)malloc(sizeof(int)*n);
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
scanf("%d",&a[i][j]);
max0=a[0][0];
fun2(a);
return 0;
}