在C ++中总和小于或等于阈值的正方形的最大边长

假设我们有矩阵矩阵矩阵和一个整数阈值。我们必须达到一个正方形的最大边长，其总和小于或等于给定的阈值；如果没有这样的正方形，则返回0。所以如果输入像-

阈值为4，则输出将为2，因为边长为2的两个平方，所以max为2

为了解决这个问题，我们将遵循以下步骤-

• 定义一个名为ok的方法，它将采用x和矩阵m以及阈值th

• 设置curr：= 0

• 对于范围x – 1到垫子行数– 1的i

• curr：= mat [r，c]

• 如果c – x> = 0，则将curr降低mat [r，c – x]

• 如果r – x> = 0，则将curr降低mat [r-x，c]

• 如果c – x> = 0且r – x> = 0，则将curr增加mat [r – x，c-x]

• 如果curr <= th，则返回true

• 对于范围x中的c – 1到垫子的列数– 1

• 返回假

• 在主要方法中，它将采用矩阵和阈值

• r：=行数，c：=列数，低：= 1，高：= r和c的最小值，ans：= 0

• 对于我，范围从1到c – 1

• 将mat [j，i]增加mat [j，i-1]

• 对于j，范围从0到c – 1

• 当我在1到r – 1的范围内

• 将mat [j，i]增加mat [i-1，j]

• 对于j，范围从0到c – 1

• 而低<=高：

• 中：=低+（高-低）/ 2

• 如果of(mid,mat,th)，则ans：=中和低：=中+1，否则为高：=中– 1

• 返回ans

例子（C ++）

让我们看下面的实现以更好地理解-

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
   bool ok(int x, vector < vector<int> >& mat, int th){
      lli current = 0;
      for(int r = x - 1; r < mat.size(); r++){
         for(int c = x - 1; c < mat[0].size(); c++){
            current = mat[r][c];
            if(c - x >= 0)current -= mat[r][c-x];
            if(r -x >= 0)current -= mat[r - x][c];
            if(c - x >= 0 && r - x >= 0)current += mat[r-x][c-x];
            if(current <= th)return true;
         }
      }
      return false;
   }
   int maxSideLength(vector<vector<int>>& mat, int th) {
      int r = mat.size();
      int c = mat[0].size();
      int low = 1;
      int high = min(r, c);
      int ans = 0;
      for(int i = 1; i < c; i++){
         for(int j = 0; j < r; j++){
            mat[j][i] += mat[j][i - 1];
         }
      }
      for(int i = 1; i < r; i++){
         for(int j = 0; j < c; j++){
            mat[i][j] += mat[i - 1][j];
         }
      }
      while(low <= high){
         int mid = low + ( high - low ) / 2;
         if(ok(mid, mat, th)){
            ans = mid;
            low = mid + 1;
         }
         else{
            high = mid - 1;
         }
      }
      return ans;
   }
};
main(){
   vector<vector<int>> v = {{1,1,3,2,4,3,2},{1,1,3,2,4,3,2},{1,1,3,2,4,3,2}};
   Solution ob;
   cout << (ob.maxSideLength(v, 4));
}

输入值

[[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]]
4

输出结果

2