Hamısı LeetCode Həlli ilə Submatrisləri Sayın

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur google microsoftBaxılıb 25

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:

Hamısı LeetCode Həlli ilə Submatrisləri SayınPin

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:

Hamısı LeetCode Həlli ilə Submatrisləri SayınPin

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
Translate »