【每日刷题】Day135
【每日刷题】Day135
🥕个人主页：开敲🍉
🔥所属专栏：每日刷题🍍
🌼文章目录🌼
1. LCR 011. 连续数组 - 力扣（LeetCode）
2. 【模板】二维前缀和_牛客题霸_牛客网 (nowcoder.com)
3. 1314. 矩阵区域和 - 力扣（LeetCode）
1. LCR 011. 连续数组 - 力扣（LeetCode）
//思路：前缀和+哈希表
//本题思路与 Day132 中的"和为K的子数组" 完全相似
//区别在于哈希中存储的不再是前缀和，而是每个前缀和对应的下标
//同时，还有个最为核心的思想，我们将数组中所有的 0 看作 -1，这样要找数量相同 0 和 1 的最长连续子数组问题就可以转换为最长和为 0 的连续子数组
class Solution {
public:
int findMaxLength(vector<int>& nums)
{
int sum = 0,ans = 0;
vector<int> dp;
unordered_map<int,int> hash;
for(int i = 0;i<nums.size();i++)
{
if(!nums[i]) sum--;//将数组中的 0 看作 -1
else sum++;
dp.push_back(sum);//dp数组存储前缀和
if(!dp[i]) ans = ans>i+1?ans:i+1;//找前缀和为 0 的连续子数组
else if(hash.find(sum)!=hash.end()) ans = ans>i-hash[sum]?ans:i-hash[sum];
else hash[sum] = i;//前缀和不为 0 则判断一下在前面能否找到一个前缀和使它们之前出现和为 0 的连续子数组
}
return ans;
}
};
2. 【模板】二维前缀和_牛客题霸_牛客网 (nowcoder.com)
//思路：二位前缀和模板
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n,m,q;
cin>>n>>m>>q;
vector<vector<int>> arr(n+1,vector<int>(m+1,0));
vector<vector<long long>> sum(n+1,vector<long long>(m+1,0));
for(int i = 1;i<n+1;i++)
{
for(int j = 1;j<m+1;j++)
{
cin>>arr[i][j];
sum[i][j] = sum[i][j-1]+sum[i-1][j]+arr[i][j]-sum[i-1][j-1];//创建矩阵，套用二位前缀和公式
}
}
while(q--)
{
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
cout<<sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1]<<endl;//套用子矩阵和公式
}
return 0;
}
3. 1314. 矩阵区域和 - 力扣（LeetCode）
//思路：二位前缀和
//本题的思路就是 "【模板】二位前缀和" 的思路。
//题目的意思就是：
//知道了题目意思以后，思路就很容易想了。
//想要知道这个新矩阵的和，我们只需要类比 "【模板】二位前缀和" 中的思路即可，即：确定一个起点以及一个终点，起点和终点所形成的子矩阵直接套用公式即可求出和
class Solution {
public:
vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k)
{
int n = mat.size(),m = mat[0].size();
vector<vector<int>> ans(n,vector<int>(m,0));
vector<vector<int>> sum(n+1,vector<int>(m+1,0));
for(int i = 1;i<n+1;i++)
for(int j = 1;j<m+1;j++)
sum[i][j] = sum[i][j-1]+sum[i-1][j]+mat[i-1][j-1]-sum[i-1][j-1];//套用前缀和公式
for(int i = 0;i<n;i++)
{
for(int j = 0;j<m;j++)
{
int x1 = max(0,i-k)+1,y1 = max(0,j-k)+1,x2 = min(n-1,i+k)+1,y2 = min(m-1,j+k)+1;//因为下标从0开始，因此 x1、y1、x2、y2都要+1与 sum 的起始下标对应
ans[i][j] = sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1];//确定起点与终点，这里需要仔细思考起点和终点与K的关系。
}
}
return ans;
}
};