今日学习记录
1. 统计全为 1 的正方形子矩阵leetcode.1277
关键词：动态规划
问题分析：
- 给你一个
m * n的矩阵,矩阵中的元素不是0就是1，请你统计并返回其中完全由1组成的 正方形 子矩阵的个数.没啥好说
核心思路
- 刚学完矩阵的二维前缀和,这道题就太简单了,但是与前缀和没有半毛钱关系,最最主要的是分析从主问题分解为子问题(思考方向),再从子问题收集答案向主问题靠齐(动态规划)
- 主问题是目前的区域内最大的正方形的边是多少,不就是看围绕其的数是否为 1 么,若都为 1,则右下角的数也为一的话,不就是一个 2x2 的正方形么,总的来说就是求边的问题,看右下角这个数能组成什么样的正方形
- 于是得到状态方程 dp{i+1,j+1} = min({dp{i+1,j},dp{i,j+1},dp{i,j}})+1;
- 累加 dp{i+1,j+1}即为答案;
**最终代码：
int countSquares(vector<vector<int>>& matrix) {
int r = matrix.size(),c = matrix[0].size();
int ans = 0;
for(int i = 0;i<r;i++){
for(int j = 0;j<c;j++){
if(matrix[i][j]){
if(i==0||j==0) ans++;
else{
matrix[i][j] = min({matrix[i-1][j],matrix[i][j-1],matrix[i-1][j-1]})+1;
ans += matrix[i][j];
}
}
}
}
return ans;
}学到的点：
- 动态规划
2. 二维区域和检索 - 矩阵不可变leetcode.304
关键词：前缀和 数组
问题分析：
- 就是给出一个矩阵,然后给出左上和右下坐标,求这个子矩阵内元素的总和
核心思路
- 直接暴力做肯定超时,因为每次都要遍历矩阵
- 对于范围的和,我们想到前缀和,但这个是二维的,我只能提供大概思路,要结合图片才能懂,跟一维数组前缀和一样的思路,先求怎么累加到最后一位,先求出整个的总和,初始化前缀和数组,再求子数组范围和
最终代码：
vector<vector<int>> arr;
NumMatrix(vector<vector<int>>& matrix) {
int r = matrix.size(),c = matrix[0].size();
arr.resize(r+1,vector<int>(c+1));
for(int i = 0;i<r;i++){
for(int j = 0;j<c;j++){
arr[i+1][j+1] = arr[i][j+1]+arr[i+1][j]-arr[i][j]+matrix[i][j];
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
return arr[row2+1][col2+1] - arr[row1][col2+1]-arr[row2+1][col1]+arr[row1][col1];
}学到的点：
- 二维数组的前缀和
- 求子矩阵总和