304. Range Sum Query 2D - Immutable - CPP - Solution


  • 0
    Y
    // 304. Range Sum Query 2D - Immutable
    // https://leetcode.com/problems/range-sum-query-2d-immutable/
    #include <iostream>
    #include <vector> // required for vector container
    #include <unordered_map> // required for unordered_map container
    using namespace std;
    class NumMatrix {
    public:
    	NumMatrix(const vector<vector<int>>& matrix) {
    		for (size_t i = 0; i < matrix.size(); ++i) {
    			for (size_t j = 0; j < matrix.front().size(); ++j) {
    				if (!i && !j) {
    					this->hashMap[0][0] = matrix[0][0];
    				}
    				else if (!i && j) {
    					this->hashMap[i][j] = this->hashMap[i][j - 1] + matrix[i][j];
    				}
    				else if (i && !j) {
    					this->hashMap[i][j] = this->hashMap[i - 1][j] + matrix[i][j];
    				}
    				else if (i && j) {
    					this->hashMap[i][j] = this->hashMap[i - 1][j] + this->hashMap[i][j - 1] - this->hashMap[i - 1][j - 1] + matrix[i][j];
    				}
    			}
    		}
    	}
    public:
    	int sumRegion(const size_t& row1, const size_t& col1, const size_t& row2, const size_t& col2) {
    		int result = 0;
    		if (!row1 && !col1) {
    			result = this->hashMap[row2][col2];
    		}
    		else if (!row1 && col1) {
    			result = this->hashMap[row2][col2] - this->hashMap[row2][col1 - 1];
    		}
    		else if (row1 && !col1) {
    			result = this->hashMap[row2][col2] - this->hashMap[row1 - 1][col2];
    		}
    		else if (row1 && col1) {
    			result = this->hashMap[row2][col2] - this->hashMap[row2][col1 - 1] - this->hashMap[row1 - 1][col2] + this->hashMap[row1 - 1][col1 - 1];
    		}
    		return result;
    	}
    private:
    	unordered_map<size_t, unordered_map<size_t, int>> hashMap;
    };
    
    int main(int argc, const char** argv) {
    	vector<vector<int>> matrix = 
    	//{
    	//	{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}
    	//};
    	{
    		{-4, -5}
    	};
    	NumMatrix numMatrix(matrix);
    	size_t row1 = 0;
    	size_t col1 = 0;
    	size_t row2 = 0;
    	size_t col2 = 1;
    	cout << numMatrix.sumRegion(row1, col1, row2, col2) << '\n';
    	getchar();
    	return 0;
    }
    
    // Your NumMatrix object will be instantiated and called as such:
    // NumMatrix numMatrix(matrix);
    // numMatrix.sumRegion(0, 1, 2, 3);
    // numMatrix.sumRegion(1, 2, 3, 4);

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.