讨论/题目交流/ 🏆 第 165 场力扣周赛/
🏆 第 165 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

4 分 - 找出井字棋的获胜者
4 分 - 不浪费原料的汉堡制作方案
5 分 - 统计全为 1 的正方形子矩阵
6 分 - 分割回文串 III

展开讨论

看很多解答里,创建数组在最大长度上+5;请问这个5有什么说法吗?

分享下第三题的暴力解法和参考的预处理解法
暴力求解:

class Solution {
public:
 
    bool isLegalBox(vector<vector<int>>& matrix,int tx,int ty,int bx,int by){
        for(int i = bx;i>=tx;i--){
            for(int j = by;j>=ty;j--){
                if(matrix[i][j] == 0){
                    return false;    
                }
            }
        }
        return true;
    }
    int countSquares(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        int w = min(m,n);
        int result = 0;
        for(int i = m-1;i>=0;i--){
            for(int j = n-1;j>=0;j--){
               for(int a = 0;a<w;a++){
                   if(i-a >=0 && j-a >=0){
                       if(isLegalBox(matrix,i-a,j-a,i,j)){
                           result++;
                       }else{
                            //跳过边长更大的矩形
                            break;  
                       }   
                    }
               }
            }    
        }
        return result;
    }
};

预处理求解:

class Solution {
public:
    int sum[305][305];
    int getSum(int x1,int x2,int y1,int y2){
        return sum[x2][y2] - sum[x1][y2] - sum[x2][y1] + sum[x1][y1];
    }
    int countSquares(vector<vector<int>>& matrix) {
        
        int m = matrix.size();
        int n = matrix[0].size();
        //sum -> 0,0 ~ i,j 矩阵求和
        memset(sum,0,sizeof(sum));
        
        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + matrix[i][j];
            }
        }
        int w = min(n,m);
        int result = 0;
        
        for(int i = 0;i<=m;i++){
            for(int j = 0;j<=n;j++){
                for(int a = 1;a<=w;a++){
                    if(i+a <=m && j+a <=n){
                        if(getSum(i,i+a,j,j+a) == a*a){   
                            result++;
                        }else{
                            break;
                        }
                    }
                }
            }
        }
        return result;
    }
};
1
展开全部 11 讨论