資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++中求和小於等於閾值的正方形最大邊長
假設我們有一個 m x n 的矩陣 mat 和一個整數閾值。我們需要找到一個和小於等於給定閾值的正方形的最大邊長，如果不存在這樣的正方形，則返回 0。例如，如果輸入如下：
| 1 | 1 | 3 | 2 | 4 | 3 | 2 |
| 1 | 1 | 3 | 2 | 4 | 3 | 2 |
| 1 | 1 | 3 | 2 | 4 | 3 | 2 |
| 1 | 1 | 3 | 2 | 4 | 3 | 2 |
| 1 | 1 | 3 | 2 | 4 | 3 | 2 |
| 1 | 1 | 3 | 2 | 4 | 3 | 2 |
並且閾值為 4，則輸出為 2，因為存在兩個邊長為 2 的正方形，因此最大值為 2。
為了解決這個問題，我們將遵循以下步驟：
- 定義一個名為 ok 的方法，它將接收 x、矩陣 m 和閾值 th 作為引數。
- 設定 curr := 0
- 對於 i 從 x – 1 到 mat 的行數 – 1
- 對於 c 從 x – 1 到 mat 的列數 – 1
- 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
- 對於 c 從 x – 1 到 mat 的列數 – 1
- 返回 false
- 在主方法中，它將接收矩陣和閾值作為引數。
- r := 行數，c := 列數，low := 1，high := r 和 c 的最小值，ans := 0
- 對於 i 從 1 到 c – 1
- 對於 j 從 0 到 c – 1
- 將 mat[j, i] 加上 mat[j, i - 1]
- 對於 j 從 0 到 c – 1
- 對於 i 從 1 到 r – 1
- 對於 j 從 0 到 c – 1
- 將 mat[j, i] 加上 mat[ i - 1,j]
- 對於 j 從 0 到 c – 1
- 當 low <= high 時
- mid := low + (high - low) / 2
- 如果 ok(mid, mat, th) 為真，則 ans := mid 且 low := mid + 1，否則 high := mid – 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
更新於: 2020-04-30
165 次瀏覽
廣告