【每日刷题】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;

    }

};