मान लीजिए हमारे पास एक 2D मैट्रिक्स है जिसे matrix कहा जाता है, हमें (row1, col1) ऊपरी बाएं कोने और (row2, col2) निचले दाएं कोने द्वारा परिभाषित आयत के अंदर के तत्वों का योग ढूंढना है।
उदाहरण के लिए, यदि मैट्रिक्स है:
| 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) द्वारा परिभाषित है, इसका योग 8 है।
यदि हम sumRegion(2, 1, 4, 3), sumRegion(1, 1, 2, 2), sumRegion(1, 2, 2, 4) क्वेरी करते हैं, तो ये क्रमशः 8, 11, 12 वापस करेंगे।
हल करने के चरण
dp नामक एक मैट्रिक्स परिभाषित करें
प्रारंभिककरण:
n := पंक्तियों की संख्या, यदि n 0 है तो वापस लौटें
m := स्तंभों की संख्या
dp := n x m आकार का एक अन्य मैट्रिक्स
i को 0 से n-1 तक लूप करें
j को 0 से m-1 तक लूप करें
यदि j-1 < 0, तो dp[i][j] = matrix[i][j], अन्यथा dp[i][j] = dp[i][j-1] + matrix[i][j]
i को 1 से n-1 तक लूप करें
j को 0 से m-1 तक लूप करें
dp[i][j] में dp[i-1][j] जोड़ें
क्वेरी विधि row1, col1, row2, col2 लेती है
ret := dp[row2][col2]
sub1 := 0 यदि row1-1 < 0, अन्यथा dp[row1-1][col2]
sub2 := 0 यदि col1-1 < 0, अन्यथा dp[row2][col1-1]
यदि row1-1 < 0 या col1-1 < 0, तो add := 0, अन्यथा add := dp[row1-1][col1-1]
ret - sub1 - sub2 + add वापस करें
उदाहरण (C++)
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; class NumMatrix { public: vector < vector <int>> dp; NumMatrix(vector<vector<int>>& matrix) { int n = matrix.size(); if(!n) return; int m = matrix[0].size(); dp = vector < vector <int>>(n, vector <int> (m)); for(int i = 0; i < n; i++){ for(int j = 0 ;j < m; j++){ dp[i][j] = j - 1 < 0 ? matrix[i][j] : dp[i][j - 1] + matrix[i][j]; } } for(int i = 1; i < n; i++){ for(int j = 0; j < m; j++){ dp[i][j] += dp[i - 1][j]; } } } int sumRegion(int row1, int col1, int row2, int col2) { int ret = dp[row2][col2]; int sub1 = row1 - 1 < 0 ? 0 : dp[row1 - 1][col2]; int sub2 = col1 - 1 < 0 ? 0 : dp[row2][col1 - 1]; int add = row1 - 1 < 0 || col1 - 1 < 0 ? 0 : dp[row1 - 1][col1 - 1]; return ret - sub1 - sub2 + add; } }; main(){ vector<vector<int>> mat = {{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 ob(mat); cout << ob.sumRegion(2,1,4,3) << endl; cout << ob.sumRegion(1,1,2,2) << endl; cout << ob.sumRegion(1,2,2,4) << endl; }इनपुट
[[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]] sumRegion(2,1,4,3) sumRegion(1,1,2,2) sumRegion(1,2,2,4)
आउटपुट
8 11 12
