資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學在 C++ 中查詢具有給定和的子矩陣
在這個問題中，我們給定一個大小為 N*N 的二維矩陣和兩個變數 sum 和 size。我們的任務是查詢具有給定和的子矩陣。
我們需要找到一個大小為 size*size 且元素和等於 sum 的子矩陣。
讓我們來看一個例子來理解這個問題：
Input : mat[][] = {
{1, 5, 7, 9}
{2, 4, 6, 8}
{1, 2, 5, 6}
{3, 6, 9, 3}
}
sum = 22
Size = 2
Output : YES說明 −
The submatrix of size k with sum 22 is
{5, 7}
{4, 6}解決方案方法
解決這個問題的一個簡單方法是建立所有可能的 size*size 大小的子陣列，求和，然後將其與給定的 sum 值相等。如果兩者相等則返回。
另一種方法是使用動態規劃演算法的概念。在這種方法中，我們將建立一個 DP 陣列，該陣列將儲存直到當前索引值的總和，即 DP[i][j] 將儲存從行索引 0 到 i 和列索引 0 到 j 的所有陣列元素的總和。
使用這個 DP 陣列，我們將使用以下公式計算任意兩個起始索引和結束索引之間的總和：
$$\mathrm{sum((i_s,j_s)to(i_e,j_e))\:=\:DP[i_s][i_s]\:+\:DP[i_e][i_e]\:-\:DP[i_s][i_e]\:-\:DP[i_e][i_s]}$$
演算法
步驟 1 − 建立一個大小為 (n+1)*(n+1) 的 DP 矩陣。
步驟 2 − 對於矩陣的每個元素，找到直到當前索引的總和。
步驟 3 − 對於從 0 到 n 的所有索引，找到 size*size 大小的子矩陣的總和。使用公式並將結果儲存在 currSum 中。
步驟 4 − 如果 currSum == sum，則返回 true。
步驟 5 − 返回 false。
示例
程式演示了我們解決方案的工作原理
#include <iostream>
using namespace std;
#define N 4
bool findSubMatWithSum(int size, int sum, int mat[N][N]){
int DP[N + 1][N + 1];
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
DP[i + 1][j + 1] = DP[i + 1][j] + DP[i][j + 1] - DP[i][j] + mat[i][j];
int currSum = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++) {
currSum = DP[i][j] + DP[(i + size)][(j + size)] - DP[(i + size)][j] - DP[i][(j + size)];
if (currSum == sum)
return true;
}
return false;
}
int main(){
int mat[N][N] = { { 1, 5, 7, 9 },
{ 2, 4, 6, 8 },
{ 1, 2, 5, 6 },
{ 3, 6, 9, 3 } };
int size = 2;
int sum = 22;
if (findSubMatWithSum(size, sum, mat))
cout<<"Sub-Matrix of given size having the given sum is possible!";
else
cout<<"Sub-Matrix of given size having the given sum is not possible!";
}輸出
Sub-Matrix of given size having the given sum is possible!
更新於： 2022年1月25日
1K+ 次瀏覽
廣告