資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++程式：查詢給定矩陣中 kxk 大小的相同值方陣
假設我們有一個二維矩陣，我們需要找到其中所有元素都相同值的最大 kxk 子矩陣，然後找到 k 的值。
例如，如果輸入如下：
| 1 | 1 | 8 | 3 |
| 1 | 5 | 5 | 5 |
| 2 | 5 | 5 | 5 |
| 4 | 5 | 5 | 5 |
則輸出為 3，因為存在一個 3x3 的值為 5 的方陣。
為了解決這個問題，我們將遵循以下步驟：
n := 矩陣的行數
m := 矩陣的列數
定義一個大小為 (nxm) 的二維陣列 dp 並將其填充為 1
ret := 1
初始化 i := n - 1，當 i >= 0 時，更新 (i 減 1)，執行：
初始化 j := m - 1，當 j >= 0 時，更新 (j 減 1)，執行：
val := inf
如果 i + 1 < n 且 v[i + 1, j] 與 v[i, j] 相同，則：
val := dp[i + 1, j] 和 val 的最小值
否則
val := 0
如果 j + 1 < m 且 v[i, j + 1] 與 v[i, j] 相同，則：
val := dp[i, j + 1] 和 val 的最小值
否則
val := 0
如果 i + 1 < n 且 j + 1 < m 且 v[i + 1, j + 1] 與 v[i, j] 相同，則：
val := dp[i + 1, j + 1] 和 val 的最小值
否則
val := 0
如果 val 等於 inf，則：
忽略以下部分，跳到下一個迭代
dp[i, j] := dp[i, j] + val
ret := ret 和 dp[i, j] 的最大值
返回 ret
示例
讓我們來看下面的實現以更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(vector<vector<int>>& v) {
int n = v.size();
int m = v[0].size();
vector<vector<int>> dp(n, vector<int>(m, 1));
int ret = 1;
for (int i = n - 1; i >= 0; i--) {
for (int j = m - 1; j >= 0; j--) {
int val = INT_MAX;
if (i + 1 < n && v[i + 1][j] == v[i][j]) {
val = min(dp[i + 1][j], val);
}
else {
val = 0;
}
if (j + 1 < m && v[i][j + 1] == v[i][j]) {
val = min(dp[i][j + 1], val);
}
else {
val = 0;
}
if (i + 1 < n && j + 1 < m && v[i + 1][j + 1] == v[i][j]) {
val = min(dp[i + 1][j + 1], val);
}
else {
val = 0;
}
if (val == INT_MAX)
continue;
dp[i][j] += val;
ret = max(ret, dp[i][j]);
}
}
return ret;
}
};
int solve(vector<vector<int>>& matrix) {
return (new Solution())->solve(matrix);
}
int main(){
vector<vector<int>> matrix = {
{1, 1, 8, 3},
{1, 5, 5, 5},
{2, 5, 5, 5},
{4, 5, 5, 5}
};
cout << solve(matrix);
}輸入
{ {1, 1, 8, 3}, {1, 5, 5, 5}, {2, 5, 5, 5}, {4, 5, 5,
5} };輸出
3
更新於：2020-12-23
瀏覽量：121
廣告