程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> leetcode筆記:Range Sum Query 2D

leetcode筆記:Range Sum Query 2D

編輯:關於C++

一. 題目描述

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

這裡寫圖片描述

The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.<喎?/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxwPjxzdHJvbmc+tv4uIMzixL+31s72PC9zdHJvbmc+PC9wPg0KPHA+zOLEv7Tz0uLKx6OsuPi2qNK7uPa2/s6svtjV86OsvMbL47TTz8Kx6jxjb2RlPihyb3cxLCBjb2wxKTwvY29kZT4gtb3PwrHqo7ogPGNvZGU+KHJvdzIsIGNvbDIpPC9jb2RlPrXE19O+2NXztcS6zaGjzOLEv7j4s/bBy7y4uPay4srU08PA/aGjPC9wPg0KPHA+16LS4srCz+7W0Mzhtb2jujwvcD4NCrzZyei+2NXzsru74bjEseSjuyBzdW1SZWdpb26jqLLp0a+jqbqvyv274bX308O63LbgtM6juyC82cnoPGNvZGU+cm93MSAmbGU7IHJvdzI8L2NvZGU+o6wgsqLH0iA8Y29kZT5jb2wxICZsZTsgY29sMjwvY29kZT6how0KPHA+uMPM4rXE1ti148rHyrm1sbbgtM6199PDc3VtUmVnaW9uuq/K/cqxo6zL47eoxNyxo7PWuN/Qp6Os0vK0y9fu1rG527XEt723qMrHyrnTw7/VvOS7u8ihyrG85KOszai5/bm51Oy4qNb6yv3X6Txjb2RlPnN1bVJlY29yZDwvY29kZT6jrDxjb2RlPnN1bVJlY29yZFtpXVtqXTwvY29kZT6x7cq+tNPPwrHqPGNvZGU+KDAsIDApPC9jb2RlPrW9PGNvZGU+KHgsIHkpPC9jb2RlPrXE19O+2NXztcS6zaOov7zCx7W9sd+9587KzOKjrLio1vrK/dfpPGNvZGU+c3VtUmVjb3JkPC9jb2RlPrTz0KHJ6M6qPGNvZGU+KG0gKyAxKSAqIChuICsgMSk8L2NvZGU+o6zG5NbQPGNvZGU+bTwvY29kZT66zTxjb2RlPm48L2NvZGU+t9ax8M6qyv3X6Txjb2RlPm1hdHJpeDwvY29kZT61xNDQyv26zcHQyv2jqaOsyrm1w8zixL/XqruvzqrH88ihvtjQzrHfvee1xM7KzOKjrMjnz8LD5sv5yr6hozwvcD4NCjxwPsO709DK1ravu63NvKOs0v3Tw834yc+1xM+1wdDNvMasvfjQ0L3iys2jujwvcD4NCjxwcmUgY2xhc3M9"brush:java;"> +-----+-+-------+ +--------+-----+ +-----+---------+ +-----+--------+ | | | | | | | | | | | | | | | | | | | | | | | | | | +-----+-+ | +--------+ | | | | +-----+ | | | | | = | | + | | | - | | +-----+-+ | | | +-----+ | | | | | | | | | | | | | | | | | | | +---------------+ +--------------+ +---------------+ +--------------+ sumRecord[i][j] = sumRecord[i-1][j] + sumRecord[i][j-1] - sumRecord[i-1][j-1] + matrix[i-1][j-1]

這是小學學過的簡單的矩形求面積方法,對於本題正好適用。

三. 示例代碼

class NumMatrix {
public:
    NumMatrix(vector> &matrix) {
        int m = matrix.size();
        int n = m > 0 ? matrix[0].size() : 0;
        sumRecord = vector>(m + 1, vector(n + 1, 0));
        // 由於sumRegion函數可能被調用多次,因此使用輔助數組sumRecord用於
        // 記錄matrix中坐標(0,0)到任一下標(i,j)之間矩形框內元素的值,這樣
        // 每次調用sumRegion函數時只需查詢sumRecord裡的值並進行簡單運算即可
        for (int i = 1; i <= m; ++i)
            for (int j = 1; j <= n; ++j)
                sumRecord[i][j] = matrix[i - 1][j - 1] + sumRecord[i - 1][j] + sumRecord[i][j - 1] - sumRecord[i - 1][j - 1];
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        return sumRecord[row2 + 1][col2 + 1] - sumRecord[row1][col2 + 1] - sumRecord[row2 + 1][col1] + sumRecord[row1][col1];
    }

private:
    vector> sumRecord;
};


// 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);

四. 小結

在構造輔助數組時,應考慮邊界問題和下標的轉換,否則容易出現越界等錯誤。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved