【刷题8】连续数组、矩阵区域和
一、连续数组
题目:
思路:前缀和+哈希表
- 问题转换:子数组要0和1的个数相同,把0变成-1,-1和1的数量相同,不就是这个子数组的元素和为0,即和为k的子数组=》和为0的子数组。找与sum-k相同的数=》找与sum-0相同的数=》sum
- 哈希表:一个是前缀和,一个是下标
- hash[0] = -1,前缀和为0,下标设置为-1
- 计算长度:i-hash[sum],hash[sum]表示的是下标,i是当前的下标,能到这步,说明存在哈希表中
- 前缀和填充哈希表,注意,这里是if else的关系,因为要防止重复填入。比如此时前缀和都是0,原来已经有hash[0]=-1了,再hash[0]=1或者其他的下标就错了。还有为什么hash[0]=-1?因为只要这时的前缀和为0,说明i下标前面的所有元素(包括i指向的元素)和为0,这时候是目前最长的(因为可能i指向后面也有为0,就更长了),然后 i 是下标,下标是从0开始的,所以与长度相比少1,根据公式,i-hash[0],即i-(-1),刚好就是+1,就变成长度了。
- 更新结果:max函数
代码:
class Solution {
public:
int findMaxLength(vector<int>& nums) {
int n = nums.size();
int sum = 0, ret = 0;
unordered_map<int, int> hash;
hash[0] = -1;
for(int i=0; i<n; i++)
{
if(nums[i] == 0) nums[i] = -1;
}
for(int i=0; i<n; i++)
{
sum += nums[i];
if(hash.count(sum)) ret = max(ret, i-hash[sum]);
else hash[sum] = i;
}
return ret;
}
};
二、矩阵区域和
题目:
思路:二维前缀和
- 用二维前缀和模板的公式,最后加原数组的值时下标要-1,因为原数组的下标是从0开始,dp数组是从1开始
- x1 y1 x2 y2的下标不要越界,根据公式填到返回的数组中。下标各+1是因为从dp中获取,dp是从1开始的
代码:
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));
vector<vector<int>> dp(n+1, vector<int>(m+1));
// 预处理
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1] + mat[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;
int y1 = max(0, j-k) + 1;
int x2 = min(n-1, i+k) + 1;
int y2 = min(m-1, j+k) + 1;
ans[i][j] = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1];
}
}
return ans;
}
};
原文地址:https://blog.csdn.net/2301_77459845/article/details/142819075
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!