menu Lyanのブログ
Prifix Sum
159 浏览 | 2020-04-28 | 分类:动态规划,数据结构与算法 | 标签:

Matrix Block Sum

Summary

Given a m * n matrix mat and an integer K, return a matrix answer where each answer[i][j] is the sum of all elements mat[r][c] for i - K <= r <= i + K, j - K <= c <= j + K, and (r, c) is a valid position in the matrix.

My approuch

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        if not mat:
            return mat
        iMax = len(mat) - 1
        jMax = len(mat[0]) - 1
        prifix = [ [ 0 for _ in range(jMax + 1) ] for _ in range(iMax + 1)]
        for i, row in enumerate(prifix):
            for j, _ in enumerate(row):
                if not i and not j:
                    prifix[i][j] = mat[i][j]
                elif not i:
                    prifix[i][j] = prifix[i][j-1] + mat[i][j]
                elif not j:
                    prifix[i][j] = prifix[i-1][j] + mat[i][j]
                else:
                    prifix[i][j] = prifix[i-1][j] + prifix[i][j-1] - prifix[i-1][j-1] + mat[i][j]
        for i, row in enumerate(mat):
            for j, _ in enumerate(row):
                rMin, rMax = max(i - K, 0), min(i + K, iMax)
                cMin, cMax = max(j - K, 0), min(j + K, jMax)
                tmp1 = prifix[rMin-1][cMin-1] if rMin and cMin else 0
                tmp2 = prifix[rMin-1][cMax] if rMin else 0
                tmp3 = prifix[rMax][cMin-1] if cMin else 0
                mat[i][j] = prifix[rMax][cMax] + tmp1 - tmp2 - tmp3
        return mat
知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

发表评论

email
web

全部评论 (暂无评论)

info 还没有任何评论,你来说两句呐!