資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律在 C++ 中查詢和為 k 的最大面積矩形子矩陣
假設我們有一個二維矩陣 mat 和一個值 K，我們需要找到和等於 K 的最長矩形子矩陣。
因此，如果輸入類似於
| 2 | 8 | -5 | 6 |
| -7 | 7 | 8 | -3 |
| 11 | -14 | 4 | 3 |
| -4 | 3 | 1 | 10 |
並且 K = 9
則輸出將是左上角點為 (1, 0) 且右下角點為 (3, 2)。
| -7 | 7 | 8 |
| 11 | -14 | 4 |
| -4 | 3 | 1 |
要解決此問題，我們將遵循以下步驟：
MAX := 100
定義一個函式 sum_k()，它將接收一個數組 arr、起始位置 start、結束位置 end、陣列長度 n 和 k 作為引數。
定義一個 map
sum := 0，maximum_length := 0
對於 i 從 0 開始，當 i < n 時，更新 (i 增加 1)，執行以下操作：
sum := sum + arr[i]
如果 sum 等於 k，則：
maximum_length := i + 1
start := 0
end := i
如果 sum 不在 map 中，則：
map[sum] := i
如果 (sum - k) 在 map 中，則：
如果 maximum_length < (i - map[sum - k])，則：
maximum_length := i - map[sum - k]
start := map[sum - k] + 1
end := i
當 maximum_length 不為 0 時返回 true
從主方法中執行以下操作：
row := mat 的行數，col := mat 的列數
定義一個大小為 row 的陣列 temp。
定義一個數組 final_point = {0,0,0,0}
maxArea := -inf
對於 left 從 0 開始，當 left < col 時，更新 (left 增加 1)，執行以下操作：
用 0 填充 temp
對於 right 從 left 開始，當 right < col 時，更新 (right 增加 1)，執行以下操作：
對於 i 從 0 開始，當 i < row 時，更新 (i 增加 1)，執行以下操作：
temp[i] := temp[i] + mat[i, right]
sum := sum_k(temp, up, down, row, k)
area := (down - up + 1) * (right - left + 1)
如果 sum 不為零且 maxArea < area，則：
final_point[0] := up，final_point[1] := down
final_point[2] := left，final_point[3] := right
maxArea := area
如果 final_point 為 [0,0,0,0] 且 mat[0,0] 不等於 k，則
返回“未找到子矩陣”
顯示左上角點 (final_point[0], final_point[2])
顯示右下角點 (final_point[1], final_point[3])
顯示 mat 元素。
示例
讓我們看看以下實現以獲得更好的理解：
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100;
bool sum_k(int arr[], int& start, int& end, int n, int k) {
unordered_map<int, int> map;
int sum = 0, maximum_length = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
if (sum == k) {
maximum_length = i + 1;
start = 0;
end = i;
}
if (map.find(sum) == map.end())
map[sum] = i;
if (map.find(sum - k) != map.end()) {
if (maximum_length < (i - map[sum - k])) {
maximum_length = i - map[sum - k];
start = map[sum - k] + 1;
end = i;
}
}
}
return (maximum_length != 0);
}
void sum_zero(vector<vector<int>> &mat, int k) {
int row = mat.size();
int col = mat[0].size();
int temp[row], area;
bool sum;
int up, down;
vector<int> final_point = {0,0,0,0};
int maxArea = INT_MIN;
for (int left = 0; left < col; left++) {
memset(temp, 0, sizeof(temp));
for (int right = left; right < col; right++) {
for (int i = 0; i < row; i++)
temp[i] += mat[i][right];
sum = sum_k(temp, up, down, row, k);
area = (down - up + 1) * (right - left + 1);
if (sum && maxArea < area) {
final_point[0] = up;
final_point[1] = down;
final_point[2] = left;
final_point[3] = right;
maxArea = area;
}
}
}
if (final_point[0] == 0 && final_point[1] == 0 && final_point[2] == 0 &&
final_point[3] == 0 && mat[0][0] != k) {
cout << "No sub-matrix found";
return;
}
cout << "(Top, Left) Coordinate: " << "(" << final_point[0] << ", " << final_point[2] << ")" << endl;
cout << "(Bottom, Right) Coordinate: " << "(" << final_point[1] << ", " << final_point[3] << ")" << endl;
for (int j = final_point[0]; j <= final_point[1]; j++) {
for (int i = final_point[2]; i <= final_point[3]; i++)
cout << mat[j][i] << " ";
cout << endl;
}
}
main(){
vector<vector<int>> v = {
{ 2, 8, -5, 6 },
{ -7, 7, 8, -3 },
{ 11, -14, 4, 3 },
{ -4, 3, 1, 10 }};
sum_zero(v, 9);
}輸入
{{ 2, 8, -5, 6 },
{ -7, 7, 8, -3 },
{ 11, -14, 4, 3 },
{ -4, 3, 1, 10 }},
9輸出
(Top, Left) Coordinate: (1, 0) (Bottom, Right) Coordinate: (3, 2) -7 7 8 11 -14 4 -4 3 1
206 次瀏覽
