算法之前缀和

题目1: 【模板】一维前缀和(easy)

方法一: 暴力解法, 时间复杂度O(n*q), 当n=10^5, q = 10^5, 时间复杂度为O(10^10), 会超时.

方法二:

前缀和: 快速求出数组中某一段连续区间的和.

第一步: 预处理出来一个前缀和数组dp:

1. dp[i]表示区间[1,i]里所有元素的和

2. dp[i] = dp[i-1] + arr[i]

 为什么还有一个前缀和数组? 

使用暴力解法是先把arr存进去, 再遍历一次arr求和.

但是 求和 在存入原始数据的时候就能一起完成 O(n), 而区间[l,r]的和就是dp[r] - dp[l-1], 直接取出数据即可 O(q), 最终时间复杂度是O(n) + O(q), 实际上求前l项数据的和求前r项数据的和 本质是同一类问题,  可以把同一类问题抽象成一种状态表示, 进而用动态规划思想去解决.

 细节问题:

我们的数组都要像题目一样表示, 也就是下标从1开始计数, 为什么?

因为 dp[i] = dp[i-1] + arr[i] 这个公式, 当 i==0 的时候会出现dp[-1]越界访问, 而下标从1开始, 第一个数据是dp[1] = dp[0] + arr[1], 对于dp[0]保证其初始化的时候为0即可.

#include <iostream>
using namespace std;

int main() 
{
    int n,q;
    long long arr[100001]= {0};
    long long dp[100001] = {0};

    cin >> n >> q;

    //O(n)
    for(int i = 1; i <= n; i++)
    {
        cin >> arr[i];
        dp[i] = arr[i] + dp[i-1];
    }

    //O(q)
    for(int j = 0; j < q; j++)
    {
        long long l,r;
        cin >> l >> r;
        
        cout << dp[r] - dp[l-1] << endl;
    }

    return 0;
}
// 64 位输出请用 printf("%lld")

题目2: 【模板】二维前缀和(medium)

方法1: 暴力求解,时间复杂度O(m*n*q) 

方法2:前缀和 

2.1 利用一维前缀和: 

相当于x2x1+1个一维的前缀和相加, 只需要:
1. 确定好每次区间的起始坐标为y1+(x1-1)*m, 则终止坐标为起始坐标+(y2-y1), 
2. 起始坐标+=m, 重复循环计算 

#include <iostream>
using namespace std;

int main()
{
    int n, m, q;
    long long arr[1000001] = { 0 };
    long long dp[1000001] = { 0 };

    cin >> n >> m >> q;

    //O(n)
    for (int i = 1; i <= n * m; i++)
    {
        cin >> arr[i];
        dp[i] = arr[i] + dp[i - 1];
    }

    //O(q)
    for (int j = 0; j < q; j++)
    {
        long long x1, x2, y1, y2, sum = 0;
        cin >> x1 >> y1 >> x2 >> y2;
        long long start = y1 + ((x1 - 1) * m);
        long long gap = y2 - y1;

        for (int i = 0; i < x2 - x1 + 1; i++)
        {
            sum += dp[start+gap] - dp[start- 1];
            start += m;
        }
        cout << sum << endl;
    }

    return 0;
}
// 64 位输出请用 printf("%lld")

 2.2 二维的前缀和

a. 预处理一个前缀和矩阵

dp[i][j]表示: 从 [1][1] 位置到 [i][j] 位置这个矩阵的元素和.

可以把矩阵 i*j 沿 i 和 j 分为四块, 分别标记为A,B,C,D, 因为这样划分A+B 和 A+C 的面积可以分别用dp[i-1][j]和dp[i][j-1]表示, 而D的面积就是arr[i][j], 所以dp[i][j] = A+B  + A+C + D - A = dp[i-1][j] + dp[i][j-1] + dp[i-1][j] + arr[i][j] - dp[i-1][j-1]

b.使用这个前缀和矩阵 

将矩阵沿x1 y1划分成四份, D的面积推导同上:

#include <iostream>
using namespace std;

int main()
{
    int n, m, q;
    long long arr[1001][1001] = { 0 };
    long long dp[1001][1001] = { 0 };

    cin >> n >> m >> q;

    //O(n)
    for (int i = 1; i <= n; i++)
    {
        for(int j = 1; j<=m;j++)
        {
            cin >> arr[i][j];
            dp[i][j] = dp[i-1][j] + dp[i][j-1] + arr[i][j] - dp[i-1][j-1];
        }
    }

    //O(q)
    for (int j = 0; j < q; j++)
    {
        long long x1, x2, y1, y2, sum = 0;
        cin >> x1 >> y1 >> x2 >> y2;
        cout<< dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1] << endl;
    }

    return 0;
}
// 64 位输出请用 printf("%lld")

题目3: 寻找数组的中心下标

直接利用前缀和:

同之前一样, 利用递推公式求出dp[i], 来表示前i个数的和:

 而后缀和可以用前缀和来表示: dp[n]-dp[i+1]

class Solution {
public:
    int pivotIndex(vector<int>& nums) 
    {
        int n = nums.size();

        vector<int> dp(n+1);
        dp[0] = 0;
        for(int i = 1; i <= n;i++)
        {
            dp[i] = dp[i-1] + nums[i-1];
        }

        for(int i = 0; i < n;i++)
        {
            if(dp[i] == dp[n]-dp[i+1])
                return i;
        }
        return -1;
    }
};

也可以用f[i]表示题意中的前缀和, g[i]表示题中的后缀和, 注意f[i]要从前向后初始化, 而g[i]要从后向前初始化, 最后用f[i] == g[i]进行比较即可:

class Solution {
public:
    int pivotIndex(vector<int>& nums) 
    {
        int n = nums.size();
        vector<int> f(n);
        vector<int> g(n);

        //初始化dp数组
        f[0] = 0;
        g[n-1] = 0;
        for(int i = 1; i < n;i++)
        {
            f[i] = f[i-1] + nums[i-1];
            g[n-1-i] = g[n-i] + nums[n-i];
        }

        //判断
        for(int i = 0; i < n;i++)
        {
            if(f[i] == g[i])
                return i;
        }
        return -1;
    }
};

题目4: 除自身以外数组的乘积

"前缀和"的思路和上一题几乎一模一样, 只是前缀和变成了前缀积, 注意把 f[0] 和 g[n-1] 设置为1:

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) 
    {
        int n = nums.size();
        vector<int> f(n), g(n), answer(n);

        //初始化dp数组
        f[0] = 1;
        g[n-1] = 1;
        for(int i = 1; i < n;i++)
        {
            f[i] = f[i-1] * nums[i-1];
            g[n-1-i] = g[n-i]* nums[n-i];
        }
        for(int i = 0; i < n; i++)
            answer[i] = f[i]*g[i];

        return answer;
    }
};

 前缀和思路实际上是一种空间换时间的做法, 此题时间复杂度空间复杂度都是O(N)

优化一下上面的前缀积, 改成空间复杂度为O(1):

由于输出数组不算在空间复杂度内, 那么我们可以将用answer数组计算出前缀积, 然后再动态构造 后缀积得到结果, 最后的answer[i]从后向前计算, 即可很巧妙的利用到上次存放的answer[i]前缀积:

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) 
    {
        int n = nums.size();
        vector<int> answer(n);

        //初始化dp数组
        answer[0] = 1;
        for(int i = 1; i < n;i++)
            answer[i] = answer[i-1] * nums[i-1];//此时answer[i]还是前缀积

        int R = 1;//动态更新后缀积
        for(int i = n-1; i >= 0; i--)
        {
            answer[i] = answer[i] * R;//最终结果,answer[i]为前缀积*后缀积
            R *= nums[i];//后缀积动态更新
        }

        return answer;
    }
};

题目5: 和为 k 的子数组(medium)

此时是连续的子数组, 看上去可以用滑动窗口解决, 但是不能, 因为 数据范围中有0和负数, 滑动窗口滑到和为k时不能停下来, 还要继续往后滑, 因为不确定后面有没有负数和0, 不具备单调性, 所以不能用滑动窗口

 前缀和+哈希表:

当下标为i时, 要找一段和为K的子数组, 只需要在[0, i-1]区间内找, 找有多少个前缀和等于sum[i] - k的子数组, 怎么去找呢?

每次求出sum[i]之后然后遍历一遍0~i-1, 这样时间复杂度还是O(n^2+n), 而暴力解法时间复杂度是O(n^2), 所以不能这样去找.

用一个哈希表去存放 前缀和等于sum[i]-k 出现的次数, 这样每次只需要 +=sum[i-k] 对应的值即可, 因为默认值是0.

注意: 

1.前缀和加入哈希表的时机? 

    在计算sum[i]之前, 只保存 [0,i-1] 位置的前缀和.

2. 如果 sum[i] 等于k, 那么它本身就是一个要找的子数组, 在哈希表中所对应的应该是sum[i]-k=0, 但是这个0相当于在[0,-1]区间内, 并不会被加入进哈希表, 所以在哈希表初始化时要令hash[0]=1, 避免这种情况被遗漏

3. 我们不用真的创建一个前缀和数组, 用一个sum变量去标记前一个前缀和即可.

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) 
    {
        unordered_map<int,int> hash;
        hash[0] = 1;

        int sum = 0, ret = 0;
        for(auto e: nums)
        {
            sum += e;
            ret += hash[sum-k];
            hash[sum]++;
        }
        return ret;
    }
};

题目6: 和可被 K 整除的子数组

前置知识: 

1. 同余定理:
如果 (a - b) % n == 0 , 那么我们可以得到一个结论:  a % n == b % n 。用文字叙述就是, 如果两个数相减的差能被 n 整除, 那么这两个数对 n 取模的结果相同.

2. c++ 中负数取模的结果, 以及如何修正「负数取模」的结果
        a. c++ 中关于负数取模运算, 因为c++整除是向零取整(余数符号和被除数一样), 而不是向下取整(余数符号和除数相等), 所以我们来推导一下上面的结论, 因为(a - b) % n == 0 , 所以a = b+kn,  两边同时取余即可得到上面的结论, 但是这里两边同时取余是有条件的, 假如以c++的取余规则, a是正数, b是负数, 这就导致a是向下取整(实际是向零取整, 但是方向都相同)得到的余数, 而b是向上取整(实际是向零取整, 方向是向上取整)得到的余数, 取余是不等价的, 所以需要把负数的取余操作进行修正, 以(a % n + n) % n 的形式输出保证为正.

了解了这些再来看这道题:假如一段区间和能被k整除, 也就是(sum-k)%k = 0, 根据同余定理, sum%k = x%k, 所以对于每一个sum, 只需找去找[0, i-1]区间里前缀和(x) = sum%k的次数即可, 又回归到了上一道题, 思路同上一道题, 注意当k==sum的时候, 需要找0, 所以hash[0]要初始化为1:

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) 
    {
        unordered_map<int,int> hash;
        hash[0] = 1;
        
        int sum = 0, ret = 0;
        for(auto e : nums)
        {
            sum += e;
            ret += hash[(sum%k+k)%k];
            hash[(sum%k+k)%k]++;
        }
        return ret;
    }
};

题目7: 连续数组(medium)

 此题如果直接去统计区间0和1的个数会发现很困难, 可以转化一下, 把所有的0看作-1, 含有相同数量的0和1的子数组的和就为0, 问题转化为求 和为0的子数组, 和之前的那道题类似.

前缀和 + 哈希:

1. 哈希表中存什么?

这题不是求和为k的子数组的数目, 而是求区间长度, 所以哈希表应该存 hash<前缀和, 下标>

2. 什么时候存入哈希表?

和之前一样, 判断完再存入 

3. 出现重复的<sum,i>, 该如何处理?

因为是从前向后遍历数组的, 所以下标i越小, 求出的区间就越长, 所以只存入第一个前缀和为sum的i即可. 

4. 区间长度怎么算?

如图, i-j 即为区间长度

5. hash[0]该如何初始化?

同之前一样, 可能当前的sum和就为0, 要去区间 [0,-1] 寻找0, 所以hash[0] = - 1

class Solution {
public:
    int findMaxLength(vector<int>& nums)
    {
        unordered_map<int, int> hash;
        hash[0] = -1; //默认有一个前缀和为0的情况

        int sum = 0, ret = 0, n = nums.size();
        for(int i = 0; i < n; i++)
        {
            sum += nums[i] == 0 ? -1 : 1;//计算当前前缀和
            if(hash.count(sum)) 
                ret = max(ret,i-hash[sum]);
            else //找不到sum才存下标
                hash[sum] = i;
        }
        return ret;
    }
};

题目8 : 矩阵区域和(medium)

题目的描述是让我们求出一个矩阵, 矩阵里每个元素answer[i][j] 是 mat[i][j]  周围k格内元素的和, 如果越界则以边界为界限.

解法: 利用二维前缀和

a. dp[i][j]表示: dp[i][j] = A+B  + A+C + D - A = dp[i-1][j] + dp[i][j-1] + dp[i-1][j] + arr[i][j] - dp[i-1][j-1]

b.使用这个前缀和矩阵 

所以只要我们给定两个点x1,y1 和 x2,y2, 对应矩阵的和可以求出来,  所以对于每一个answer[i][j], 我们只需要确定好x1,y1,x2,y2即可, 由题意, x1 = i-k, y1 = j-k, x2 = i+k, y2=j+k,  但是还要考虑越界情况, 所以x1 = max(i-k,0),  y1 = max(j-k,0), x2 = min(i+k, n-1), y2 = min(j+k, m-1)

下标的对应关系:

此题大体思路是这样, 但是注意我们原题中给的矩阵mat是下标从0开始的, 也就是说对应的dp[i][j]如果在边界上初始化会出现越界访问, 所以我们应该给dp数组开辟一个n+1*m+1大小的空间, 其中第0行第0列全部初始化为0, 方便dp[i][j]的计算, 与之对应的, 初始化公式也要进行修改:

dp里用到mat就要减1: 

 ans里用到dp就要加1, 因为ans的下标是对应着mat的下标:

class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) 
    {
        int n = mat.size(), m = mat[0].size();
        vector<vector<int>> dp(n+1,vector<int>(m+1));//n+1 * 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] + mat[i-1][j-1] - dp[i-1][j-1];
            }
        }

        vector<vector<int>> ret(n, vector<int>(m));//n * m
        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;
                int x2 = min(n-1,i+k)+1, y2 = min(m-1,j+k)+1; 
                ret[i][j] = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1];
            }
        }
        return ret;
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/273005.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

TypeScript中的 K、T 、V

文章目录 前言泛型类型链接关系K、T、V 含义自动类型推断泛型的应用场景容器类和数据结构函数和方法接口和类类型约束和扩展常用的工具类型 前言 在 TypeScript 的泛型里经常会碰到一些字母&#xff0c;比如 K、T、V&#xff0c;是不是觉得很奇怪&#xff1f; 泛型类型 图中的…

全基因集GSEA富集分析

原文链接&#xff1a;一文完成全基因集GSEA富集分析 本期内容 写在前面 我们前面分享过一文掌握单基因GSEA富集分析的教程&#xff0c;主要使用单基因的角度进行GSEA富集分析。 我们社群的同学咨询&#xff0c;全基因集的GSEA如何分析呢&#xff1f;&#xff1f;其实&#x…

基于Andriod的连锁药店管理系统(源码|论文)

一、系统架构 前端&#xff1a;vue | uni-app 后端&#xff1a;spring | springmvc | mybatis 环境&#xff1a;jdk1.8 | mysql | maven | node 二、代码及数据库 三、功能介绍 01. 登录页 02. 管理后台-首页 03. 管理后台-个人中心-修改密码 04. 管理后台-个人中心-个…

npm WARN config init.license Use `--init-license` instead.

背景&#xff1a;近期升级本地node版本&#xff08;v14.15.4 --> v18.19.1&#xff09;&#xff0c;npm -v报警 npm WARN config init.license Use --init-license instead. npm WARN config init.author.name Use --init-author-name instead. 分析&#xff1a; npm高版本…

Python爬虫从基础到入门:script标签中的数据

上一篇文章: Python爬虫从基础到入门:script标签中的数据 1. 分析需要抓取的数据的在哪?2. 获取数据、解析数据3. 下载视频、音频文件4. 参考代码1. 分析需要抓取的数据的在哪? 本篇博文以B站视频为例,B站视频在用户没有登录的状态下,只能观看视频尺寸为360流畅,在登录…

【前缀和】100255. 成为 K 特殊字符串需要删除的最少字符数

本文涉及知识点 C算法&#xff1a;前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频 枚举 LeetCode100255. 成为 K 特殊字符串需要删除的最少字符数 给你一个字符串 word 和一个整数 k。 如果 |freq(word[i]) - freq(word[j])| < k 对于字符串中所有下标 …

BUGKU-WEB cookies

题目描述 题目截图如下&#xff1a; 进入场景看看&#xff1a; 解题思路 看源码看F12&#xff1a;看请求链接看提示&#xff1a;cookies欺骗 相关工具 插件&#xff1a;ModHeader或者hackbarbase64解密 解题步骤 看源码 就是rfrgrggggggoaihegfdiofi48ty598whrefeoia…

QT中messageBox的使用

想要实现一个注册功能&#xff0c;判断两次输入的密码是否相同&#xff0c;不同则弹出对话框 查阅了资料&#xff0c;很多都用 exec()来实现信息框的停留&#xff0c;如下 // QMessageBox mag;// mag.setText("密码错误");// mag.exec(); 但是这会导致按了确定之后将…

牛客——紫魔法师(并查集)

链接&#xff1a;登录—专业IT笔试面试备考平台_牛客网 来源&#xff1a;牛客网 题目描述 “サーヴァント、キャスター、Medea。”--紫魔法师 给出一棵仙人掌(每条边最多被包含于一个环&#xff0c;无自环&#xff0c;无重边&#xff0c;保证连通)&#xff0c;要求用最少的…

【电路笔记】-MOSFET作为开关

MOSFET 作为开关 文章目录 MOSFET 作为开关1、概述2、MOSFET特性曲线2.1 截住区域2.2 饱和区域3、MOSFET作为开关的示例4、功率MOSFET电机控制5、P沟道MOSFET作为开关6、互补MOSFET作为开关电机控制器当 MOSFET 在截止区和饱和区之间工作时,MOSFET 是非常好的电子开关,用于控…

2024年3月GESP认证Scratch图形化编程四级真题及答案

GESP 图形化四级试卷 &#xff08;满分&#xff1a;100 分 考试时间&#xff1a;120 分钟&#xff09; 学校&#xff1a; 姓名&#xff1a; ​ 一、单选题&#xff08;共 10 题&#xff0c;每题 2 分&#xff0c;共 30 分&#xff09; 题号 1 2 3 4 5 6 7 8 9 10 11 1…

(done) 解释 python3 torch.utils.data DataLoader

特别注意&#xff1a;DataLoader 返回的迭代器是无尽的&#xff0c;依据如下 (CHATGPT3.5) DataLoader 返回的迭代器默认情况下是无尽的&#xff0c;因为它会无限地循环遍历数据集&#xff0c;以提供批量的数据。在训练神经网络时&#xff0c;通常会使用无尽的迭代器来循环遍历…

第六十回 吴用智赚玉麒麟 张顺夜闹金沙渡-飞桨科学计算套件PaddleScience

吴用说我到北京让卢俊义上山&#xff0c;小菜一碟&#xff0c;但是我需要一个粗心大胆的同伴一起去。黑旋风李逵自告奋勇&#xff0c;答应了吴用三件事才被允许去&#xff1a;一、 不喝酒 二、扮做道童听吩咐 三、不说话当哑巴。 两人拜做算命的道士和道童&#xff0c;来到北京…

【送书福利!第一期】《ARM汇编与逆向工程》

&#x1f42e;博主syst1m 带你 acquire knowledge&#xff01; ✨博客首页——syst1m的博客&#x1f498; &#x1f618;《CTF专栏》超级详细的解析&#xff0c;宝宝级教学让你从蹒跚学步到健步如飞&#x1f648; &#x1f60e;《大数据专栏》大数据从0到秃头&#x1f47d;&…

【论文笔记合集】ARIMA 非平稳过程通过差分转化为平稳过程

本文作者&#xff1a; slience_me 文章目录 ARIMA 非平稳过程通过差分转化为平稳过程文章原文具体解释详解参照 ARIMA 非平稳过程通过差分转化为平稳过程 文章原文 Many time series forecasting methods start from the classic tools [38, 10]. ARIMA [7, 6] tackles the fo…

P1514 [NOIP2010 提高组] 引水入城

题目描述 在一个遥远的国度&#xff0c;一侧是风景秀美的湖泊&#xff0c;另一侧则是漫无边际的沙漠。该国的行政区划十分特殊&#xff0c;刚好构成一个 N 行 M 列的矩形&#xff0c;如上图所示&#xff0c;其中每个格子都代表一座城市&#xff0c;每座城市都有一个海拔高度。…

21-分支和循环语句_while语句(中)(初阶)

21-2 代码准备 getchar()&#xff1a;获取字符 int ch getchar(); //把获取的字符的ASCII码值放在ch中 int main() {int ch getchar();printf("%c\n", ch); //ch存的是该字符的ASCII码值&#xff0c;此处以字符形式打印ASCII码值对应的字符putchar(ch); } 运…

docker引擎

目录 一、Docker引擎发展历程 二、docker引擎架构 三、docker引擎分类 四、docker引擎安装 4.1安装条件 4.2 使用rpm存储库安装 4.2.1设置存储库 4.2.2安装docker引擎 4.2.3启动docker,并设置docker开机自启动 五、卸载docker引擎 5.1.卸载 Docker 引擎、CLI、conta…

德迅蜂巢(容器安全)全面出击

随着云计算的发展&#xff0c;以容器和微服务为代表的云原生技术&#xff0c;受到了人们的广泛关注&#xff0c;德迅云安全德迅蜂巢&#xff08;容器安全&#xff09;是企业容器运行时和容器编排的首要选择。然而&#xff0c;在应用容器过程中&#xff0c;大多数企业都遇到过不…
最新文章