给定一个01方阵mat及方阵的边长n，该方阵每个单元非0及1，请设计一个高效的算法，返回四条边颜色相同的最大子方阵的边长。保证母方阵边长小于等于100。
测试样例：
[[1,1,1],[1,0,1],[1,1,1]],3
返回：3
[编程题]最大子方阵
class SubMatrix {
private:
bool checkRec(vector<vector<int>>& mat, int x, int y, int len)
{
int digit = mat[x][y];
for (int i = 0; i < len; ++i) if (mat[x + i][y] != digit || mat[x + i][y + len - 1] != digit) return false;
for (int j = 0; j < len; ++j) if (mat[x][y + j] != digit || mat[x + len - 1][y + j] != digit) return false;
return true;
}
public:
int maxSubMatrix(vector<vector<int>> mat, int n)
{
int maxLen = 1;
for (int i = 0; i < n - maxLen; ++i)
{
for (int j = 0; j < n - maxLen; ++j)
{
for (int k = maxLen + 1; max(i, j) + k - 1 < n; ++k)
{
if (checkRec(mat, i, j, k)) maxLen = max(maxLen, k);
}
}
}
return maxLen;
}
};
发表于 2017-07-02 18:47:41
回复(3)
import java.util.*;
public class SubMatrix {
/**
* 使用动态规划
* left[i][j]: 坐标[i,j]的左边有连续相同的数个数，包含自己
* above[i][j]: 坐标[i,j]的上边有连续相同的数个数，包含自己
* 初始值：left[i][j]=1; above[i][j]=1
* 递推式：
* left[i][j]=left[i][j-1]+1, mat[i][j]==mat[i][j-1];
* left[i][j]=1, mat[i][j]!=mat[i][j-1];
* above[i][j]=above[i-1][j]+1, mat[i][j]==mat[i-1][j];
* above[i][j]=1, mat[i][j]!=mat[i-1][j];
* 在递推的过程中求解： mat[i][j]==mat[i][j-1]&&mat[i][j]==mat[i-1][j]
* @param mat
* @param n
* @return
*/
public int maxSubMatrix(int[][] mat, int n) {
int max = 1;
int[][] left = new int[n][n];
int[][] above = new int[n][n];
initial(mat, n, left, above);
for (int i = 1; i < n; i++) {
for (int j = 1; j < n; j++) {
if (mat[i - 1][j] != mat[i][j] || mat[i][j - 1] != mat[i][j]) {
if (mat[i - 1][j] != mat[i][j]
&& mat[i][j - 1] != mat[i][j]) {
left[i][j] = 1;
above[i][j] = 1;
} else if (mat[i][j - 1] != mat[i][j]) {
left[i][j] = 1;
above[i][j] = above[i-1][j] + 1;
} else {
above[i][j] = 1;
left[i][j] = left[i][j-1] + 1;
}
} else {
left[i][j] = left[i][j - 1] + 1;
above[i][j] = above[i - 1][j] + 1;
int min = Math.min(left[i][j - 1], above[i - 1][j]);
for (int k = min; k > 0 && min>=max; k--) {//此处求解结果
if (above[i][j - min] >= (min + 1)
&& left[i - min][j] >= (min + 1)) {
max = Math.max(max, min + 1);
break;
}
}
}
}
}
return max;
}
public void initial(int[][] mat, int n, int[][] left, int[][] above) {
left[0][0] = 1;
Arrays.fill(above[0], 1);
for (int i = 1; i < n; i++) {
left[i][0] = 1;
if (mat[0][i] != mat[0][i - 1]) {
left[0][i] = 1;
} else {
left[0][i] = left[0][i - 1] + 1;
}
}
for (int i = 1; i < n; i++) {
if (mat[i][0] != mat[i - 1][0]) {
above[i][0] = 1;
} else {
above[i][0] = above[i - 1][0] + 1;
}
}
}
}
发表于 2016-08-05 23:02:46
回复(6)
import java.util.*;
public class SubMatrix {
public int maxSubMatrix(int[][] mat, int n) {
int max = 1;
int[][] left = new int[n][n];
int[][] above = new int[n][n];
initial(mat, n, left, above);
for (int i = 1; i < n; i++) {
for (int j = 1; j < n; j++) {
if (mat[i][j]==mat[i-1][j] && mat[i][j]==mat[i][j-1]) {
left[i][j] = left[i][j-1]+1;
above[i][j] = above[i-1][j]+1;
int len = Math.min(left[i][j],above[i][j]);
for(int k=len-1;k>0&&k+1>max;k--){
if(above[i][j-k]>k && left[i-k][j]>k){
max = k+1;
break;
}
}
} else if(mat[i][j]!=mat[i-1][j] && mat[i][j]!=mat[i][j-1]){
left[i][j] = 1;
above[i][j] = 1;
} else if(mat[i][j]==mat[i][j-1]){
left[i][j] = left[i][j-1]+1;
above[i][j] = 1;
} else if(mat[i][j]==mat[i-1][j]){
left[i][j] = 1;
above[i][j] = above[i-1][j]+1;
}
}
}
return max;
}
public void initial(int[][] mat, int n, int[][] left, int[][] above) {
for(int i=0;i<n;i++){
left[i][0] = 1;
above[0][i] = 1;
}
for(int j=1;j<n;j++){
if(mat[0][j]==mat[0][j-1])
left[0][j] = left[0][j-1]+1;
else
left[0][j] = 1;
}
for(int i=1;i<n;i++){
if(mat[i][0]==mat[i-1][0])
above[i][0] = above[i-1][0]+1;
else
above[i][0] = 1;
}
}
}
发表于 2020-03-05 20:02:57
回复(1)
class SubMatrix {
public:
int maxSubMatrix(vector<vector<int> > mat, int n) {
//选定最大子方阵的边长，选择顶点，判断是合法
int maxLength = n;
while(maxLength){
for(int i = 0; i <= n - maxLength; ++i){
for(int j = 0; j <= n - maxLength; ++j){
int pixel = mat[i][j];
bool flag = true;
for(int k = 0; k < maxLength; ++k){
int top = mat[i][j + k]; // 上边的线
int bottom = mat[i + maxLength - 1][j + k]; // 下边的线
int left = mat[i + k][j]; // 左边的线
int right = mat[i + k][j + maxLength -1]; // 右边的线
if(top != pixel || bottom != pixel || left != pixel || right != pixel){
flag = false;
break;
}
}
if(flag)
return maxLength;
}
}
maxLength--;
}
return 0;
}
};
发表于 2017-05-05 21:44:55
回复(3)
import java.util.*;
public class SubMatrix {
public int maxSubMatrix(int[][] mat, int n) {
// write code here
for(int size = n ; size>=1;size--)
for(int row = 0;row< n ;row++){
for(int col =0;col< n ;col++){
if(isSquare0(mat,row,col,size) || isSquare1(mat,row,col,size)){
return size;
}
}
}
return -1;
}
// 第row 行 col列 （0开始） 开始的矩阵，矩阵大小是 size
public boolean isSquare0(int[][] mat, int row, int col,int size){
// 检查 上 下 边界
for(int j = 0; j < size; j++){
if(col+j>=mat.length || row+size-1>=mat.length)
return false;
if(mat[row][col+j] == 1)
return false;
if(mat[row+size-1][col+j] ==1)
return false;
}
// 检测 左 右 边界
for(int i = 0;i< size - 1;i++){
if(row+i>=mat.length || col+size-1>=mat.length)
return false;
if( mat[row+i][col] == 1)
return false;
if(mat[row+i][col+size-1]==1)
return false;
}
return true;
}
public boolean isSquare1(int[][] mat, int row, int col,int size){
// 检查 上 下 边界
for(int j = 0; j < size; j++){
if(col+j>=mat.length || row+size-1>=mat.length)
return false;
if(mat[row][col+j] == 0)
return false;
if(mat[row+size-1][col+j] ==0)
return false;
}
// 检测 左 右 边界
for(int i = 0;i< size - 1;i++){
if(row+i>=mat.length || col+size-1>=mat.length)
return false;
if( mat[row+i][col] == 0)
return false;
if(mat[row+i][col+size-1]==0)
return false;
}
return true;
}
}
发表于 2016-02-26 22:09:45
回复(0)
/*
根据20150909期左老师的视频将的方法做的，这里有一点不同都为0组成的方形也要与最大边长比较。
这里主要的问题是验证过程，需要遍历wide到1。
*/
class SubMatrix {
public:
int maxSubMatrix(vector<vector<int> > mat, int n) {
// write code here
if(n == 0) return 0;
vector<vector<int> > matA = mat;//坐标点下方连续1的个数
vector<vector<int> > matB = mat;//坐标点右方连续1的个数
vector<vector<int> > matAA = mat;//坐标点下方连续0的个数
vector<vector<int> > matBB = mat;//坐标点右方连续0的个数
int i,j;
int len = 0;
int wide;
for(i=n-1;i>=0;--i){
for(j=n-1;j>=0;--j){
if(mat[i][j] == 0){
matA[i][j] = 0;
matB[i][j] = 0;
if(i == n-1){
matAA[i][j] = 1;
}else{
matAA[i][j] = matAA[i+1][j]+1;
}
if(j == n-1){
matBB[i][j] = 1;
}else{
matBB[i][j] = matBB[i][j+1]+1;
}
}else {
if(i == n-1){
matA[i][j] = 1;
}else{
matA[i][j] = matA[i+1][j]+1;
}
if(j == n-1){
matB[i][j] = 1;
}else{
matB[i][j] = matB[i][j+1]+1;
}
matAA[i][j] = 0;
matBB[i][j] = 0;
}
}
}
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(mat[i][j] == 0){
wide = min(matAA[i][j],matBB[i][j]);
while(wide>0){
if(matAA[i][j+wide-1] >= wide && matBB[i+wide-1][j] >= wide){
len = len<wide?wide:len;
}
wide--;
}
}else{
wide = min(matA[i][j],matB[i][j]);
while(wide>0){
if(matA[i][j+wide-1] >= wide && matB[i+wide-1][j] >= wide){
len = len<wide?wide:len;
}
wide--;
}
}
}
}
return len;
}
};
发表于 2015-09-10 15:23:11
回复(0)
//参考票数最多的答案，对计算过程做了优化，同样是使用两个数组的动态规划思路
//1、对矩阵中的每个点设置一个竖方向与其连续相同像素的点数目，一个水平方向与其连续相同像素点数目
//2、最大子方阵即为当该点左侧和上侧的像素都与其相同，此时相当于知道了矩阵的下边和右边长度
//往上遍历点若其左侧连续点数目不低于短边（因为是方阵所以只能选最短边），同理，向左遍历点,
//若其上侧连续点数目不低于短边，则此时已经找到一个满足题目要求的子方阵。
class SubMatrix {
public:
int maxSubMatrix(vector > mat, int n) {
// write code here
if(n < 1)
return 0;
vector> left(n,vector(n,1));
vector> above(n,vector(n,1));
for(int i=1;i<n;++i)
{
if(mat[0][i] == mat[0][i-1])
{
left[0][i] = left[0][i-1] + 1;
}
if(mat[i][0] == mat[i-1][0])
{
above[i][0] = above[i-1][0] + 1;
}
}
int min_n = 0;
int max_n = 1;
for(int i=1;i<n;++i)
{
for(int j=1;j<n;++j)
{
if(mat[i][j]==mat[i-1][j] && mat[i][j]==mat[i][j-1])
{
left[i][j] = left[i][j-1]+1;
above[i][j] = above[i-1][j]+1;
min_n = min(left[i][j],above[i][j]);
if(min_n <= max_n)
continue;
for(int k=0;k<min_n;++k)
{
if(above[i][j-k]>=min_n && left[i-k][j]>=min_n)
{
if(k+1 > max_n)
{
max_n = k+1;
}
}
}
}else
{
if(mat[i][j]==mat[i-1][j])
above[i][j] = above[i-1][j]+1;
else if(mat[i][j]==mat[i][j-1])
left[i][j] = left[i][j-1]+1;
}
}
}
return max_n;
}
};
发表于 2020-07-09 00:20:18
回复(0)
为每个点赋予四个带有上、下、左、右四个向量，向量长度等于该点颜色向该反向最多延伸的距离，当且仅当子方阵左上角的点的右、下向量长度大于等于子方阵边长，右下角的点的左、上向量长度大于等于子方阵边长时满足要求。
这个算法的第一个关键所在是如何计算向量长度，我的算法只写到了纯暴力计算的长度，优化的思路：
例如
1.如果一个点的right向量长度是3，那么它右边2个点的right向量长度依次为：2、1
2.如果一个点的left向量长度为3，right向量长度为3，那么他右面的2个点的left向量长度依次为：4、5
等等
程序有两个要注意的点：二维vector的初始化，边缘点向量长度的计算。
vector<vector<int> > up(n);
vector<vector<int> > down(n);
vector<vector<int> > left(n);
vector<vector<int> > right(n);
for (int i = 0; i < n; i++)
{
up[i].resize(n);
down[i].resize(n);
left[i].resize(n);
right[i].resize(n);
}
int max = 1;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
for (int k = j; k < n; k++)
{
if (k == n - 1)
{
right[i][j] = k - j + 1;
break;
}
if (mat[i][k + 1] != mat[i][j])
{
right[i][j] = k - j + 1;
break;
}
}
for (int k = j; k >= 0; k--)
{
if (k == 0)
{
left[i][j] = j - k + 1;
break;
}
if (mat[i][k - 1] != mat[i][j])
{
left[i][j] = j - k + 1;
break;
}
}
for (int k = i; k < n; k++)
{
if (k == n - 1)
{
down[i][j] = k - i + 1;
break;
}
if (mat[k + 1][j] != mat[i][j])
{
down[i][j] = k - i + 1;
break;
}
}
for (int k = i; k >= 0; k--)
{
if (k == 0)
{
up[i][j] = i - k + 1;
break;
}
if (mat[k - 1][j] != mat[i][j])
{
up[i][j] = i - k + 1;
break;
}
}
}
}
/*向量长度矩阵测试
cout << "r" << endl;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cout << right[i][j];
}
cout << endl;
}
cout << "d" << endl;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cout << down[i][j];
}
cout << endl;
}
cout << "l" << endl;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cout << left[i][j];
}
cout << endl;
}
cout << "u" << endl;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cout << up[i][j];
}
cout << endl;
}*/
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
for (int a = i + 1, b = j + 1; b < n&&a < n; a++, b++)
{
if (right[i][j] >= b - j + 1 && down[i][j] >= a - i + 1 && left[a][b] >= b - j + 1 && up[a][b] >= a - i + 1)
{
if (max < b - j + 1)
{
max = b - j + 1;
}
}
}
}
}
return max;
}};
编辑于 2019-03-30 18:23:36
回复(0)
//想半天别的不如此土法
class SubMatrix {
public:
int maxSubMatrix(vector<vector<int> > mat, int n) {
// write code here
int l=n;
int left,right,down,up;
while(l)
{
for(int i=0;i<=n-l;i++)
{
for(int j=0;j<=n-l;j++)
{
int val=mat[i][j];
int p=0;
for(;p<l;p++)
{
left=mat[i+p][j];
right=mat[i+p][j+l-1];
up=mat[i][j+p];
down=mat[i+l-1][j+p];
if(left!=val||up!=val||down!=val||right!=val)
break;
}
if(p==l)
return l;
}
}
l--;
}
return 1;
}
};
发表于 2018-07-05 10:24:05
回复(0)
/*暴力法，用例复杂度不高，侥幸通过*/
import java.util.*;
public class SubMatrix {
public int maxSubMatrix(int[][] mat, int n) {
// write code here
int max=0;
for (int i=0; i<n; i++){
for (int j=0; j<n; j++){
int maxlen = LentoEdge(n,i,j);
for (int k=0; k<=maxlen; k++){
if (fun(mat,k,i,j) && k>max){
max = k;
}
}//for
}//for
}//for
return max;
}
public boolean fun (int[][] mat, int n, int x, int y){//以(x,y)为左上角点，边长为n是否满足边框颜色一致
int temp = mat[x][y];
for (int i=0; i<n; i++){
if(mat[x+i][y] != temp)
return false;
}
for (int i=0; i<n; i++){
if(mat[x][y+i] != temp)
return false;
}
for (int i=0; i<n; i++){
if(mat[x+n-1][y+i] != temp)
return false;
}
for (int i=0; i<n; i++){
if(mat[x+i][y+n-1] != temp)
return false;
}
return true;
}
public int LentoEdge(int n, int x, int y){
return Math.min(n-x, n-y);
}
}
发表于 2017-11-01 09:27:16
回复(0)
class SubMatrix {
public:
int maxSubMatrix(vector<vector<int> > mat, int n) {
// int x = 0;//测试长度为x大小的方阵
int max=1;
int m=0;
for(int i=0;i<n;i++) //i ，j 基点坐标位置；
for(int j=0;j<n;j++)
{
int k;
k = mat[i][j];
int y;//行列余量判断，即测试方阵x所能达到的最大维数
if(i<j)
y = n-j;
else y = n-i;
for(int x=1;x<=y;x++)
{
for(int l=0;l<x;l++)
{
if((mat[i][j+l]!=k)||(mat[i+l][j]!=k)||(mat[i+l][j+x-1]!=k)||(mat[i+x-1][j+l]!=k))
break;
else m=l+1;//误点：开始总是吧x的值赋给m，其实子方阵是否有效取决于l，因为x可能取的大于 }
if(max < m)
max = m;
}
}
return max;
}
};
编辑于 2017-07-31 21:15:50
回复(2)
int maxSubMatrix(vector<vector<int> > mat, int n) {
vector<int> ones(n, 1);
vector<vector<int>> left(n, ones); //当前点左边连续相同的点个数(算自己)
vector<vector<int>> above(n, ones); //当前点上边连续相同的点个数（算自己）
initail(mat, n, left, above);
int maxLength = 1;
for (int i = 1; i < n; i++) {
for (int j = 1; j < n; j++) {
if (mat[i][j] != mat[i][j - 1] || mat[i][j] != mat[i - 1][j]) {
if (mat[i][j] != mat[i][j - 1] && mat[i][j] != mat[i - 1][j]) {
left[i][j] = above[i][j] = 1;
}
else if (mat[i][j] != mat[i][j - 1]) {
left[i][j] = 1;
above[i][j] = above[i - 1][j] + 1;
}
else if (mat[i][j] != mat[i - 1][j]) {
above[i][j] = 1;
left[i][j] = left[i][j - 1] + 1;
}
}
else {
left[i][j] = left[i][j - 1] + 1;
above[i][j] = above[i - 1][j] + 1;
int minLength = min(left[i][j - 1], above[i - 1][j]);//由于是方阵，长宽要一致，因此取二者最小的那个
for (int length = minLength; length > 0 && length >= maxLength; length--) { //在最小中找最大
if (left[i - length][j] >= minLength + 1 && above[i][j - length] >= minLength + 1) {//考察对边的长度
maxLength = max(maxLength, length + 1);
}
}
}
}
}
return maxLength;
}
void initail(vector<vector<int>> mat, int n, vector<vector<int>> &left, vector<vector<int>> &above) {
for (int i = 1; i < n; i++) {
if (mat[0][i] == mat[0][i - 1]) {
left[0][i] = left[0][i - 1] + 1;
}
if (mat[i][0] == mat[i - 1][0]) {
above[i][0] = above[i - 1][0] + 1;
}
}
}
编辑于 2017-07-14 11:11:10
回复(0)
class SubMatrix:
def maxSubMatrix(self, mat, n):
B = [[[0, 0] for i in range(n + 1)] for i in range(n + 1)] #预处理，构建黑白最长边，降为O(N^3)
H = [[[0, 0] for i in range(n + 1)] for i in range(n + 1)]
for i in xrange(n - 1, -1, -1):
for j in xrange(n - 1, -1, -1):
if mat[i][j] == 1:
fill(B, i, j)
else:
fill(H, i, j)
for t in xrange(n, 0, -1):
for i in xrange(n - t + 1):
for j in xrange(n - t + 1):
if isSqure(B, i, j, t) or isSqure(H, i, j, t): #判断黑边和白边是否在范围内
return t
def fill(A, i, j):
A[i][j][0] = A[i + 1][j][0] + 1
A[i][j][1] = A[i][j + 1][1] + 1
def isSqure(A, i, j, t):
return A[i][j][0] >= t and A[i][j][1] >= t and A[i + t - 1][j][1] >= t and A[i][j + t - 1][0] >= t
发表于 2017-03-22 18:20:00
回复(0)
struct NODE
{
int left;
int right;
int up;
int bottom;
NODE():left(1),right(1),up(1),bottom(1){}
};
class SubMatrix {
public:
void count(vector<vector<NODE>> &num,vector<vector<int>>& mat,int n)
{
for(int i=1;i<n;i++)
{
if(mat[0][i] == mat[0][i-1])
num[0][i].left = num[0][i-1].left + 1;
if(mat[i][0] == mat[i-1][0])
num[i][0].up = num[i-1][0].up + 1;
}
for(int i=n-2;i>=0;i--)
{
if(mat[n-1][i] == mat[n-1][i+1])
num[n-1][i].right = num[n-1][i+1].right + 1;
if(mat[i][n-1] == mat[i+1][n-1])
num[i][n-1].bottom = num[i+1][n-1].bottom + 1;
}
for(int i=1;i<n;i++)
{
for(int j=1;j<n;j++)
{
if(mat[i][j] == mat[i-1][j])
num[i][j].up = num[i-1][j].up + 1;
if(mat[i][j] == mat[i][j-1])
num[i][j].left = num[i][j-1].left + 1;
}
}
for(int i=n-2;i>=0;i--)
{
for(int j=n-2;j>=0;j--)
{
if(mat[i][j] == mat[i+1][j])
num[i][j].bottom = num[i+1][j].bottom + 1;
if(mat[i][j] == mat[i][j+1])
num[i][j].right = num[i][j+1].right + 1;
}
}
}
int getmax(vector<vector<NODE>> &num,vector<vector<int>> &mat,int n)
{
int res = 1;
for(int i=1;i<n;i++)
{
for(int j=1;j<n;j++)
{
int cur_min = min(num[i][j].up,num[i][j].left);
if(cur_min <= res)
continue;
int fence = cur_min;
int nr,nc;
while(--fence)
{
nr = i-fence;
nc = j-fence;
if(mat[nr][nc] != mat[i][j])
continue;
int cur_min2 = min(num[nr][nc].right,num[nr][nc].bottom);
if(cur_min2 >= fence+1)
{
res = max(res,fence+1);
break;
}
}
}
}
return res;
}
int maxSubMatrix(vector<vector<int> > mat, int n) {
if(n < 2)
return 1;
vector<vector<NODE>> node(n,vector<NODE>(n));
count(node,mat,n);
return getmax(node,mat,n);
}
};
n三方的算法，再剪枝，主要思想就是维护每个点的上下左右连续的0或1的个数。然后遍历每个点求解。
编辑于 2015-07-30 12:55:20
回复(0)
模仿排名第一的python实现
# -*- coding:utf-8 -*- class SubMatrix: def checkRec(self, mat, x, y, k): digit = mat[x][y] for i in range(k): if mat[x + i][y] != digit&nbs***bsp;mat[x + i][y + k - 1] != digit: return False for j in range(k): if mat[x][y + j] != digit&nbs***bsp;mat[x + k - 1][y + j] != digit: return False return True def maxSubMatrix(self, mat, n): # write code here maxLen = 1 for i in range(n-maxLen): for j in range(n-maxLen): k = maxLen+1 while max(i,j) + k -1 < n: if self.checkRec(mat, i, j, k): maxLen = max(maxLen, k) k += 1 return maxLen
发表于 2022-07-27 17:11:45
回复(0)
def maxSubMatrix(self, mat, n): for j in range(n,1,-1): for x in range(n-j+1): for y in range(n-j+1): for k in range(j): t = 0 m0 = mat[x][y] m1 = mat[x][y+k] m2 = mat[x+k][y] m3 = mat[x+k][y+j-1] m4 = mat[x+j-1][y+k] if m1 != m0&nbs***bsp;m2 != m0&nbs***bsp;m3 != m0&nbs***bsp;m4 != m0: break else: k += 1 if k == j: return j return 1
发表于 2020-08-21 17:33:02
回复(0)
struct Count{
int n_right;//右边颜色相同连续子段长度
int n_down;
Count(){
n_right = 1;
n_down = 1;
}
friend ostream& operator<<(ostream &o,const Count &a){
o<<"["<< a.n_right<<" "<<a.n_down<<"]";
return o;
}
};
class SubMatrix {
public:
int maxSubMatrix(vector<vector<int> > mat, int n) {
// write code here
if(n==0) return 0;
//1.暴力解法
//2.事先统计每个位置上右边、下边连续段长度O(n^3)
vector<vector<Count> > counts(n,vector<Count>());//统计所有坐标位置上的右边、下边连续数字数目
for(auto i=0;i<n;i++){
for(auto j=0;j<n;j++){
counts[i].push_back(Count());
}
}
//O(n^2)
//预先计算每个位置右边、下边的连续长度
for(auto i=n-1;i>=0;i--){
for(auto j=n-1;j>=0;j--){
if(i!=n-1){
if(mat[i][j]==mat[i+1][j]){
counts[i][j].n_down = counts[i+1][j].n_down+1;
}
}
if(j!=n-1){
if(mat[i][j]==mat[i][j+1]){
counts[i][j].n_right = counts[i][j+1].n_right+1;
}
}
}
}
//PR(counts);
int ans = 0;
//计算i,j位置开始的最大方块(长度从右、下两边中最小连续段长度开始)
for(auto i=0;i<n;i++){
for(auto j=0;j<n;j++){
for(auto len=min(counts[i][j].n_right,counts[i][j].n_down);len>0;len--){
if(counts[i+len-1][j].n_right>=len and counts[i][j+len-1].n_down>=len){
ans = max(ans,len);
break;
}
}
}
}
return ans;
}
};
发表于 2020-02-09 09:17:34
回复(0)
public static int maxSubMatrix(int[][] mat, int n) {
// write code here
int max = n; //设定最大子方阵边长max为n
while(max > 1) { //当最大子方阵边长为1时退出死循环
//变量startY,startX代表方阵的左上角定点,确定测试方阵
for(int startY = 0; startY <= n-max; startY++) {
//n为总方阵的边长,max为测试方阵的边长
for(int startX = 0; startX <= n-max; startX++) {
//n - max + 1为测试方阵的个数
boolean flag = true; //true代表测试结果成立
int k = mat[startY][startX];//k为方阵左上角数据
int moveX = startX;
int moveY = startY; //moveX,moveY抽象移动光标测试
int endX = max + startX - 1;
int endY = max + startY - 1; //endX,endY为测试矩阵终点
//测试子矩阵除右上角的最上边
while(flag == true && moveX < endX) {
if(mat[moveY][moveX] != k) {
flag = false;//若存在一数据不相同,变为false
break;//跳出循环
}
moveX++;//横坐标累加
} //以下循环同理
//测试子矩阵除右下角的最右边
while(flag == true && moveY < endY) {
if(mat[moveY][moveX] != k) {
flag = false;
break;
}
moveY++;
}
//测试子矩阵除左下角的最下边
while(flag == true && moveX > startX) {
if(mat[moveY][moveX] != k) {
flag = false;
break;
}
moveX--;
}
//测试子矩阵除左上角的最左边
while(flag == true && moveY > startY) {
if(mat[moveY][moveX] != k) {
flag = false;
break;
}
moveY--;
}
//若仍为true,说明测试结果成立,返回子阵的最大边长
if(flag == true) return max;
}
}
//若测试的所有定点均不满足最大边长条件,最大边长递减依次测试
max--;
}
return max;
}
发表于 2019-09-22 13:47:14
回复(0)
class SubMatrix {
public:
int maxSubMatrix(vector<vector<int> > mat, int n) {
// write code here
int maxLen=n,up,down,left,right;
while(maxLen){
for(int i=0;i+maxLen<=n;i++){
for(int j=0;j+maxLen<=n;j++){
up=left=1;
down=right=0;
for(int m=1;m<maxLen;m++){
if(mat[i][j+m]==mat[i][j])up++;
else break;
}
for(int m=1;m<maxLen;m++){
if(mat[i+m][j]==mat[i][j])left++;
else break;
}
for(int m=0;m<maxLen;m++){
if(mat[i+maxLen-1][j+m]==mat[i][j])down++;
else break;
}
for(int m=0;m<maxLen;m++){
if(mat[i+m][j+maxLen-1]==mat[i][j])right++;
else break;
}
if(up==maxLen && down==maxLen && left==maxLen && right==maxLen)return maxLen;
}
}
maxLen--;
}
return 1;
}
};
public:
int maxSubMatrix(vector<vector<int> > mat, int n) {
// write code here
int maxLen=n,up,down,left,right;
while(maxLen){
for(int i=0;i+maxLen<=n;i++){
for(int j=0;j+maxLen<=n;j++){
up=left=1;
down=right=0;
for(int m=1;m<maxLen;m++){
if(mat[i][j+m]==mat[i][j])up++;
else break;
}
for(int m=1;m<maxLen;m++){
if(mat[i+m][j]==mat[i][j])left++;
else break;
}
for(int m=0;m<maxLen;m++){
if(mat[i+maxLen-1][j+m]==mat[i][j])down++;
else break;
}
for(int m=0;m<maxLen;m++){
if(mat[i+m][j+maxLen-1]==mat[i][j])right++;
else break;
}
if(up==maxLen && down==maxLen && left==maxLen && right==maxLen)return maxLen;
}
}
maxLen--;
}
return 1;
}
};
发表于 2019-06-19 22:51:31
回复(0)
问题信息
难度：
51条回答
86收藏
18052浏览
通过挑战的用户
查看代码-
2023-02-16 19:43:47
-
2023-02-14 15:05:28 -
2022-10-13 09:43:57 -
2022-08-25 07:51:45 -
2022-08-20 18:09:26
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
