Блог

Вопрос: https://leetcode.com/problems/matrix-block-sum /

Я пытаюсь решить эту проблему, используя 2D-префикс sum, где sum[i][j] это сумма всех элементов с левой стороны, включая элемент и его строку и столбец.

Код :

 class Solution {
public:
    int n, m;
    int getSum(int i, int j, vector<vector<int>>amp; sum) {
        if(i<0 || j<0) return 0;
        if (i >= n) i = m - 1;
        if (j >= n) j = m - 1;
        return sum[i][j];
    }
    
    vector<vector<int>> matrixBlockSum(vector<vector<int>>amp; mat, int k) {
        n = mat.size();
        m = mat[0].size();
        vector<vector<int>> sum(n, vector<int>(m, 0)), res(n, vector<int>(m, 0));
        for(int i=0; i<n; i  ) {
            for(int j=0; j<m; j  ) {
                sum[i][j] = mat[i][j]   getSum(i-1, j, sum)   getSum(i, j-1, sum) - getSum(i-1, j-1, sum);
            }
        }
        for(int i=0; i<n; i  ) {
            for(int j=0; j<m; j  ) {
                res[i][j] = getSum(i k, j k, sum) - getSum(i-k-1, j k, sum) - getSum(i k, j-k-1, sum)   getSum(i-k-1, j-k-1, sum);
            }
        }
        return res;
    }
};
  

• Ошибка, вероятно, будет в последнем цикле среди этих индексов.

                 res[i][j] = getSum(i k, j k, sum) - getSum(i-k-1, j k, sum) - getSum(i k, j-k-1, sum)   getSum(i-k-1, j-k-1, sum);
  

• Вот тот же метод с разными именами переменных, будет проходить:

 // The following block might slightly improve the execution time;
// Can be removed;
static const auto __optimize__ = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();

// Most of headers are already included;
// Can be removed;
#include <cstdint>
#include <vector>

static const struct Solution {
        static const std::vector<std::vector<int>> matrixBlockSum(
                    const std::vector<std::vector<int>>amp; mat,
                    const int K
        ) {
            const std::size_t row_len = std::size(mat);
            const std::size_t col_len = row_len ? std::size(mat[0]) : 0;

            std::vector<std::vector<int>> sums(row_len, std::vector<int>(col_len, 0));

            for (std::size_t row = 0; row < row_len;   row) {
                for (std::size_t col = 0; col < col_len;   col) {
                    sums[row][col] = mat[row][col]  
                                     getPrefixSum(row - 1, col, sums)  
                                     getPrefixSum(row, col - 1, sums) -
                                     getPrefixSum(row - 1, col - 1, sums);
                }
            }

            std::vector<std::vector<int>> res(row_len, std::vector<int>(col_len, 0));

            for (std::size_t row = 0; row < row_len;   row) {
                for (std::size_t col = 0; col < col_len;   col) {
                    res[row][col] = getPrefixSum(row   K, col   K, sums) -
                                    getPrefixSum(row   K, col - K - 1, sums) -
                                    getPrefixSum(row - K - 1, col   K, sums)  
                                    getPrefixSum(row - K - 1, col - K - 1, sums);
                }
            }

            return res;
        }

    private:

        static const int getPrefixSum(
            int row,
            int col,
            const std::vector<std::vector<int>>amp; sums
        ) {
            if (row < 0 || col < 0) {
                return 0;
            }

            if (row >= std::size(sums)) {
                row = std::size(sums) - 1;
            }

            if (col >= std::size(sums[0])) {
                col = std::size(sums[0]) - 1;
            }

            return sums[row][col];
        }
};