在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