[Leet Code] Range Sum Query 2D - Immutable

こんにちは!
今日、5月の2週目の5番目のアルゴリズムRange Sum Query 2D - Immutableプールについて書きます.

質問する

サマリ
与えられたmatixにおいて、与えられた範囲の左上隅のrow、columnおよび右下隅のrow、columnが与えられた場合、その範囲の数字の和を求めることによって問題が返される.

試し方

今回、私たちは最初の考えですぐにあなたの招待を受け入れました.(本当に進歩したそうです)matrixが与えられた場合、rowで蓄積される.
例えば、[[1, 2, 3], [4, 5, 6]]の形態のmatrixであれば、[[1, 3, 6], [4, 9, 15]]に置き換えることができる.
与えられた範囲の和を求めると、rowのcol2元素からcol1 - 1元素が減算される.

コードの説明

int[][] numMatrix;

public NumMatrix(int[][] matrix) {
    numMatrix = matrix;
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 1; j < matrix[i].length; j++) {
            numMatrix[i][j] = numMatrix[i][j - 1] + matrix[i][j];
        }
    }
}

for文を巡回すると、積算値を行順に保存し、numMatrixを生成します.

int result = 0;

返されるresult変数を初期化します.

for (int row = row1; row <= row2; row++) {
      if (col1 > 0) {
          result += numMatrix[row][col2] - numMatrix[row][col1 - 1];
      } else {
          result += numMatrix[row][col2];
      }
  }

col1が0の場合、col1 - 1を除外する必要はありません.
だから必ず分岐処理を行いますcol1が0の場合、row当たりの累積合計はresultである.col1が0でない場合、row星積算からcol1 - 1の元素を減算し、resultに加算する.
また,row1とrow2が連続していなければ,中間のrowも加算されるのでfor文を巡回する.

完全なコード

class NumMatrix {
    int[][] numMatrix;

    public NumMatrix(int[][] matrix) {
        numMatrix = matrix;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 1; j < matrix[i].length; j++) {
                numMatrix[i][j] = numMatrix[i][j - 1] + matrix[i][j];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int result = 0;

        for (int row = row1; row <= row2; row++) {
            if (col1 > 0) {
                result += numMatrix[row][col2] - numMatrix[row][col1 - 1];
            } else {
                result += numMatrix[row][col2];
            }
        }

        return result;
    }
}class NumMatrix {
    int[][] numMatrix;

    public NumMatrix(int[][] matrix) {
        numMatrix = matrix;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 1; j < matrix[i].length; j++) {
                numMatrix[i][j] = numMatrix[i][j - 1] + matrix[i][j];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int result = 0;

        for (int row = row1; row <= row2; row++) {
            if (col1 > 0) {
                result += numMatrix[row][col2] - numMatrix[row][col1 - 1];
            } else {
                result += numMatrix[row][col2];
            }
        }

        return result;
    }
}

の最後の部分

これは2 Dレイアウトで、明確なソリューションはありませんが、簡潔なソリューションのようです.
今回の位置付けを読んでいただき、ありがとうございました:)