C语言重构【1314】矩阵区域和

野性酷女 2022-11-06 04:47 196阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

给你一个 m * n 的矩阵 mat 和一个整数 K ，请你返回一个矩阵 answer ，其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和： 
    
    i - K <= r <= i + K, j - K <= c <= j + K 
    (r, c) 在矩阵内。
     
    
    示例 1：
    
    输入：mat = [[1,2,3],[4,5,6],[7,8,9]], K = 1
    输出：[[12,21,16],[27,45,33],[24,39,28]]
    示例 2：
    
    输入：mat = [[1,2,3],[4,5,6],[7,8,9]], K = 2
    输出：[[45,45,45],[45,45,45],[45,45,45]]
     
    
    提示：
    
    m == mat.length
    n == mat[i].length
    1 <= m, n, K <= 100
    1 <= mat[i][j] <= 100

#### 方案： ####

*  俺的思路比较直白，就是直接利用上一个值的加减（看作矩阵移动后框住的数字不同），先一个点，再一列，再扩展到全数组，有那么点dp的味道

class Solution
    { 
    public:
        vector<vector<int>> matrixBlockSum(vector<vector<int>> &mat, int K)
        { 
            //有个矩阵和
            int sum = 0;
            int m = mat.size();
            int n = mat[0].size();
            int km = min(K + 1, m), kn = min(K + 1, n);
            vector<vector<int>> res(m, vector<int>(n, 0));
            //初始化sums[0]
            for (int i = 0; i < km; i++)
            { 
                for (int j = 0; j < kn; j++)
                { 
                    sum += mat[i][j];
                }
            }
            res[0][0] = sum;
            //填充第一列
            for (int i = 1; i < m; i++)
            { 
                res[i][0] = res[i - 1][0];
                //上侧有减
                if (i - K > 0)
                { 
                    for (int j = 0; j < kn; j++)
                    { 
                        res[i][0] -= mat[i - K - 1][j];
                    }
                }
                //下侧有加
                if (i + K < m)
                { 
                    for (int j = 0; j < kn; j++)
                    { 
                        res[i][0] += mat[i + K][j];
                    }
                }
            }
            //填充每一行
            for (int i = 0; i < m; i++)
            { 
                for (int j = 1; j < n; j++)
                { 
                    res[i][j] = res[i][j - 1];
                    //左侧有减
                    if (j - K > 0)
                    { 
                        for (int x = max(0, i - K); x < min(m, i + K + 1); x++)
                        { 
                            res[i][j] -= mat[x][j - K - 1];
                        }
                    }
                    //右侧有加
                    if (j + K < n)
                    { 
                        for (int x = max(0, i - K); x < min(m, i + K + 1); x++)
                        { 
                            res[i][j] += mat[x][j + K];
                        }
                    }
                }
            }
    
            return res;
        }
    };

##### 复杂度计算 #####

*  时间复杂度：O(mn)
 *  空间复杂度：O(mn)

[Git]: https://github.com/ch98road/leetcode