資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中給定大小的二進位制子矩陣數量查詢
在這個問題中，我們給定一個大小為 nXm 的二進位制矩陣 bin[][]。我們的任務是解決所有 q 個查詢。對於查詢(x, y)，我們需要找到大小為 x*x 的子矩陣的數量，使得陣列 y（二進位制數）的所有元素都滿足條件。
問題描述
這裡，我們需要計算給定大小的子矩陣的總數，這些子矩陣僅包含兩個位元中的一個，即子矩陣的所有元素都是 0/1。
讓我們舉個例子來理解這個問題，
輸入
n = 3 , m = 4
bin[][] = {{ 1, 1, 0, 1}
{ 1, 1, 1, 0}
{ 0, 1, 1, 1}}
q = 1
q1 = (2, 1)輸出
2
解釋
所有元素都為 1 的大小為 2 的子矩陣為 -
{{ 1, 1, 0, 1}
{ 1, 1, 1, 0}
{ 0, 1, 1, 1}}
{{ 1, 1, 0, 1}
{ 1, 1, 1, 0}
{ 0, 1, 1, 1}}這個問題的解決方案是使用**動態規劃**方法。為了解決這個問題，我們將維護一個二維矩陣 DP[][] 來儲存相同位元的最大子矩陣。即 DP[i][j] 將儲存以 (i, j) 為結束索引的子矩陣的值，並且所有元素都相同。
為了方便理解，如果 DP[4][5] = 2，則 bin[3][4]、bin[3][5]、bin[4][4] 和 bin[4][5] 中的元素相同。
因此，為了找到 DP[i][j]，我們有兩個情況 -
**情況 1** - 如果 i = 0 或 j = 0：DP[i][j] = 1，因為只有一個子矩陣是可能的。
**情況 2** - 否則，bin[i-(k-1)][j] = bin[i][j - (k-1)] …：在這種情況下，DP[i][j] = min(DP[i][j-1]，DP[i -1][j]，DP[i-1][j-1] ) + 1。這將有助於我們所需的子矩陣。讓我們概括一下 k = 2 的情況，即如果我們考慮一個大小為 2X2 的子矩陣。然後我們需要檢查是否 bin[i][j] = bin[i] [j - 1] = bin[i- 1][j] = bin[i -1 ][j -1]，如果可能，我們將找到 k =2 的 DP[i][j]。
如果不滿足情況 2 的條件，我們將設定 DP[i][j] = 1，這可以被視為預設值。
DP[i][j] 的這個值可以用於設定位元或未設定位元。我們將檢查 bin[i][j] 的值以檢視 k 值屬於設定或未設定值中的哪一個。為了找到頻率，我們將建立兩個陣列，zeroFrequrency 用於儲存為 0 生成的子矩陣的頻率。而 oneFrequrency 用於儲存為 1 生成的子矩陣的頻率。
程式說明了解決方案的工作原理，
示例
#include <iostream>
using namespace std;
#define N 3
#define M 4
int min(int a, int b, int c) {
if (a <= b && a <= c)
return a;
else if (b <= a && b <= c)
return b;
else
return c;
}
int solveQuery(int n, int m, int bin[N][M], int x, int y){
int DP[n][m], max = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (i == 0 || j == 0)
DP[i][j] = 1;
else if ((bin[i][j] == bin[i - 1][j]) && (bin[i][j] == bin[i][j - 1]) && (bin[i][j] == bin[i - 1][j - 1])) {
DP[i][j] = min(DP[i - 1][j], DP[i - 1][j - 1], DP[i][j - 1]) + 1;
if (max < DP[i][j])
max = DP[i][j];
}
else
DP[i][j] = 1;
}
}
int zeroFrequency[n+m] = { 0 }, oneFrequency[n+m] = { 0 };
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (bin[i][j] == 0)
zeroFrequency[DP[i][j]]++;
else
oneFrequency[DP[i][j]]++;
}
}
for (int i = max - 1; i >= 0; i--) {
zeroFrequency[i] += zeroFrequency[i + 1];
oneFrequency[i] += oneFrequency[i + 1];
}
if (y == 0)
return zeroFrequency[x];
else
return oneFrequency[x];
}
int main(){
int n = 3, m = 4;
int mat[N][M] =
{{ 1, 1, 0, 1},
{ 1, 1, 1, 0},
{ 0, 1, 1, 1}};
int Q = 2;
int query[Q][2] = {{ 2, 1}, { 1, 0}};
for(int i = 0; i < Q; i++){
cout<<"For Query "<<(i+1)<<": The number of Binary sub-matrices of Given size is " <<solveQuery(n, m, mat, query[i][0], query[i][1])<<"\n";
}
return 0;
}輸出
For Query 1: The number of Binary sub-matrices of Given size is 2 For Query 2: The number of Binary sub-matrices of Given size is 3
89 次瀏覽
