Mündəricat
Problem bəyanat
Hamısı ilə Submatrisləri Sayın LeetCode Həlli – Bizə mxn ikili matrisi verilir və hamısına malik olan submatrislərin sayını qaytarmağımız xahiş olunur.
Nümunələr və izahatlar
Misal 1:
Input: mat = [[1,0,1],[1,1,0],[1,1,0]] Output: 13 Explanation: There are 6 rectangles of side 1x1. There are 2 rectangles of side 1x2. There are 3 rectangles of side 2x1. There is 1 rectangle of side 2x2. There is 1 rectangle of side 3x1. Total number of rectangles = 6 + 2 + 3 + 1 + 1 = 13.
Misal 2:
Input: mat = [[0,1,1,0],[0,1,1,1],[1,1,1,0]] Output: 24 Explanation: There are 8 rectangles of side 1x1. There are 5 rectangles of side 1x2. There are 2 rectangles of side 1x3. There are 4 rectangles of side 2x1. There are 2 rectangles of side 2x2. There are 2 rectangles of side 3x1. There is 1 rectangle of side 3x2. Total number of rectangles = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24.
Yanaşma
Kobud güc yanaşması haqqında düşünsək, ağlımıza gələn açıq fikir, bir olan bütün mümkün ölçülərin submatrislərini saymaqdır. Bununla belə, bu yanaşma TLE ilə nəticələnəcək. Beləliklə, bu həlli necə təkmilləşdirə bilərik?
Həll etməklə dinamik proqramlaşdırma biz bilirik ki, alt problemlərin həlli və sonra onların əsasında həll yolu tapılması problemi həll etmək üçün tamamilə yeni strategiya ilə çıxış etməkdən daha asan olur. Baxmayaraq ki, biz DP tətbiq etmirik, lakin bir olan bütün submatrisləri saymaq üçün onun strategiyasından istifadə edəcəyik. DP ideyasından istifadə edərək, yuxarı sol küncü olan bütün submatrisləri hansısa mövqeyə qədər sayacağıq.
a-nın [0,m] və b-nin [0,n]-ə aid olduğu axb ölçülü alt matrisa yaradaq. Həmin mövqedə yuxarı sol küncü olan bütün submatrisləri sayacağıq. Döngədə axtarış yerini azaltmaq üçün əlavə olaraq bağlı dəyişəndən istifadə edə bilərik. Döngüdə axtarış sahəsinin azaldılması həmişə işləyəcək, çünki dövrə sıfıra dəydikdə, saymaq üçün daha submatrislər qalmayacaq, ona görə də o, dövrədən çıxacaq.
Kodu
Submatrisləri Hamısı ilə Saymaq üçün C++ kodu
class Solution {
int countSubMatrices(vector<vector<int>>& mat, int a, int b) {
int r=mat.size(), c=mat[0].size();
int bound=c, count=0;
for(int i=a; i<r; i++) {
for(int j=b; j<bound; j++) {
if(mat[i][j]) count++;
else bound=j;
// cout<<i<<" "<<j<<" "<<bound<<" "<<count<<"\n";
}
}
return count;
}
public:
int numSubmat(vector<vector<int>>& mat) {
int r=mat.size(), c=mat[0].size();
int res=0;
for(int i=0; i<r; i++) {
for(int j=0; j<c; j++) {
res+=countSubMatrices(mat,i,j);
// cout<<"res = "<<res<<"\n";
}
}
return res;
}
};
Submatrisləri Hamısı ilə Saymaq üçün Java kodu
class Solution {
public int countSubMatrices(int[][] mat, int a, int b) {
int r=mat.length, c=mat[0].length;
int bound=c, count=0;
for(int i=a; i<r; i++) {
for(int j=b; j<bound; j++) {
if(mat[i][j]==1) count++;
else bound=j;
}
}
return count;
}
public int numSubmat(int[][] mat) {
int r=mat.length, c=mat[0].length;
int res=0;
for(int i=0; i<r; i++) {
for(int j=0; j<c; j++) {
res+=countSubMatrices(mat,i,j);
}
}
return res;
}
}
Hamısı LeetCode Həlli ilə Sayı Submatrisləri üçün Mürəkkəblik Təhlili
- Zamanın mürəkkəbliyi: O(m*m*n*n)
- bütün ölçülü submatrislərin yaradılması O(m*n) alacaq
- Hər submatris üçün 2 döngəyə malik başqa bir funksiya çağırılır və ən pis zamanda O(m*n) alır.
- Kosmik Mürəkkəblik: O (1)
- Əlavə yer tələb olunmur
