Range Sum Query 2D – Dəyişməz Leetcode Həlli

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon Bloomberg Facebook google lyft microsoft Nvidia Samsung
Dinamik proqramlaşdırma LeetCode LeetCodeSolutionsBaxılıb 107

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

Range Sum Query 2D – Dəyişməz Leetcode Həlli – 2D matrisi nəzərə alınmaqla matrix, aşağıdakı tipli çoxsaylı sorğuları idarə edin:

  • Hesablayın məbləğ elementlərindən matrix ilə müəyyən edilmiş düzbucaqlı daxilində yuxarı sol künc (row1, col1) və sağ alt künc (row2, col2).

NumMatrix sinfini həyata keçirin:

  • NumMatrix(int[][] matrix) Obyekti tam ədəd matrisi ilə işə salır matrix.
  • int sumRegion(int row1, int col1, int row2, int col2) qaytarır məbləğ elementlərindən matrix ilə müəyyən edilmiş düzbucaqlı daxilində yuxarı sol künc (row1, col1) və sağ alt künc (row2, col2).

misal

Range Sum Query 2D - Dəyişməz Leetcode HəlliPin

Input

["NumMatrix", "sumRegion", "sumRegion", "sumRegion"]
[[[[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]], [2, 1, 4, 3], [1, 1, 2, 2], [1, 2, 2, 4]]

Buraxılış

[null, 8, 11, 12]

Izahat

NumMatrix numMatrix = new NumMatrix([[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (i.e sum of the red rectangle)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (i.e sum of the green rectangle)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (i.e sum of the blue rectangle)

Məhdudiyyətlər

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 200
  • -105 <= matrix[i][j] <= 105
  • 0 <= row1 <= row2 < m
  • 0 <= col1 <= col2 < n
  • Ən çoxu 104 -yə zənglər ediləcək sumRegion.

Yanaşma

Fikir

Burada əsas fikir hər bir düzbucaqlı üçün cəmini yuxarı sol (0,0) və sağ alt tərəfi (i, j) üzərində saxlamaqdır, burada 1<=i<=m, 1<=j<=n.

Bu məbləğləri prefiksSum-da hesablamaq və saxlamaq üçün matris, münasibətindən istifadə edirik.prefixSum[i][j] = prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1] + mat[i-1][j-1];.Biz alt problemlərin həlli üzərində qurarkən, anlayışından istifadə edirik Dinamik proqramlaşdırma burada.

Bu əlaqəni təsəvvür etmək üçün şəkil də əlavə olunur.

Range Sum Query 2D - Dəyişməz Leetcode HəlliPin

Sonra O(1) zamanında hər bir məbləği sorğulamaq üçün əlaqədən istifadə edirik prefixSum[r2][c2] - prefixSum[r1-1][c2] - prefixSum[r2][c1-1] + prefixSum[r1-1][c1-1];Alt problemlərin həlli üzərində qurarkən, konsepsiyasından istifadə edirik Dinamik proqramlaşdırma burada.

Bu əlaqəni təsəvvür etmək üçün şəkil də əlavə olunur.

Range Sum Query 2D - Dəyişməz Leetcode HəlliPin

Kodu

C++ Range Sum Query 2D Proqramı – Dəyişməz

typedef vector<int> VI;
typedef vector<VI> VVI;
class NumMatrix {
private:
        int prefixSum[200+3][200+3];
public:
    NumMatrix(vector<vector<int>>& mat) {
        int n = mat.size(), m = mat[0].size();
        memset(prefixSum, 0, sizeof(prefixSum));
        
        for(int i = 1;i<=n;i++){
            for(int j = 1;j<=m;j++){
                prefixSum[i][j] = prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1] + mat[i-1][j-1];
            }
        }
    }
    
    int sumRegion(int r1, int c1, int r2, int c2) {
        r1++, c1++, c2++, r2++;
        return prefixSum[r2][c2] - prefixSum[r1-1][c2] - prefixSum[r2][c1-1] + prefixSum[r1-1][c1-1];
    }
};

Range Sum Query 2D Java Proqramı – Dəyişməz

class NumMatrix {
    long[][] prefixSum;
    
    public NumMatrix(int[][] mat) {
        int n = mat.length, m = mat[0].length;
        prefixSum = new long[n+1][m+1];
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                prefixSum[i][j] = mat[i-1][j-1] + prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1];
    }
    
    public int sumRegion(int R1, int C1, int R2, int C2) {
        R1+=1;C1+=1;R2+=1;C2+=1;
        return (int)(prefixSum[R2][C2] - prefixSum[R2][C1-1] - prefixSum[R1-1][C2] + prefixSum[R1-1][C1-1]);
    }
}

Python3 Proqramı Range Sum Query 2D – Dəyişməz

class NumMatrix:
    def __init__(self, mat: List[List[int]]):
        n, m = len(mat), len(mat[0])
        self.prefixSum = [[0] * (m+1) for _ in range(n+1)]
        for i in range(1, n+1):
            for j in range(1, m+1):
                self.prefixSum[i][j] = mat[i-1][j-1] + self.prefixSum[i-1][j] + self.prefixSum[i][j-1] - self.prefixSum[i-1][j-1]

    def sumRegion(self, R1: int, C1: int, R2: int, C2: int) -> int:
        return self.prefixSum[R2+1][C2+1] - self.prefixSum[R2+1][C1] - self.prefixSum[R1][C2+1] + self.prefixSum[R1][C1]

Range Sum Query 2D üçün mürəkkəblik təhlili – Dəyişməz Leetcode Həlli

Zamanın mürəkkəbliyi

Hər sorğu üçün O(1).

PrefiksSum 2D matrisini qurmaq üçün O(m*n).

Kosmik Mürəkkəblik

O(m*n) prefiksSum 2D matrisini saxlamaq üçün.

Crack Sistemi Dizayn Müsahibələri
Translate »