Cpp solution which beats 100%, with detail explain


  • 0
    Y
    class NumMatrix {
    public:
      vector<vector<int>> matrix_;
      NumMatrix(vector<vector<int>> &matrix) {
        /* for example, matrix = 
         * 1  2  3
         * 4  5  6
         * 7  8  9
         */
        int m = matrix.size();
        if (m == 0)
          matrix_.push_back(vector<int>(1, 0));
        else {
          int n = matrix[0].size();
          if (n == 0) matrix_.push_back(vector<int>(1, 0));
          else {
            matrix_.push_back(vector<int>(n + 1, 0));
            for (int i = 0; i < m; i++) {
              vector<int> row;
              row.push_back(0);
              for (int j = 0; j < n; j++)
                row.push_back(matrix[i][j] + row.back() + matrix_[i][j + 1] - matrix_[i][j]);
              matrix_.push_back(row);
            }
          }
        }
        /* after constructor, matrix_ =
         * 0   0   0   0
         * 0   1   3   6
         * 0   5  12  21
         * 0   12 27  45
         */
      }
    
      /* for example, calling sumRegion(1, 1, 2, 2), which means:
       * 5 + 6 + 8 + 9 = 28
       * result is matrix_[3][3] - matrix_[3][1] - matrix_[1][3] + matrix_[1][1]
       * as 45 - 12 - 6 + 1 = 28
       */
      int sumRegion(int row1, int col1, int row2, int col2) {
        return matrix_[row2 + 1][col2 + 1] \
          - matrix_[row2 + 1][col1] \
          - matrix_[row1][col2 + 1] \
          + matrix_[row1][col1];
      }
    };

Log in to reply
 

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