算法综合篇专题四:前缀和

这篇具有很好参考价值的文章主要介绍了算法综合篇专题四:前缀和。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

算法综合篇专题四:前缀和,综合算法篇,算法,数据结构,c++

"回忆里的我,比国王富有。奢侈的快乐~" 


 1、前缀和【模板】

(1) 题目解析

算法综合篇专题四:前缀和,综合算法篇,算法,数据结构,c++

(2) 算法原理         

#include <iostream>
using namespace std;

const int N = 100010;
// 可能出现溢出
long long arr[N],dp[N];
int n,q;

int main() {
    cin >> n >> q;
    // 初始化数组
    for(int i=1;i<=n;++i) cin >> arr[i];

    // 创建dp
    for(int i = 1; i <= n; i++) dp[i] = dp[i - 1] + arr[i];

    // 查询
    while(q--){
        int l,r;
        cin >> l >> r;
        // 计算区间和
        cout << dp[r] - dp[l - 1] << endl;
    }

    return 0;
}

 2、DP35 【模板】二维前缀和

(1) 题目解析

算法综合篇专题四:前缀和,综合算法篇,算法,数据结构,c++

        同一维前缀和类似,这类题型都需要预处理出前缀和数组,再求和。

(2) 算法原理         

算法综合篇专题四:前缀和,综合算法篇,算法,数据结构,c++

#include <iostream>
using namespace std;
const int N = 1010;
int main() {
    int n, m, q;
    long long arr[N][N], dp[N][N];
    cin >> n >> m >> q;
    // 输入数组
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            cin >> arr[i][j];

    // 预处理前缀和
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + arr[i][j] - dp[i - 1][j - 1];

    // 查询
    int x1,y1,x2,y2;
    while(q--)
    {
        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;
}

3、寻找数组的中心下标

(1) 题目解析

算法综合篇专题四:前缀和,综合算法篇,算法,数据结构,c++

        本题的核心在于,存在一个mid,使得sum(0,mid-1) == sum(mid+1,end)。所以,我们只需要求得 (0,mid-1) 区间的值 是否等于 (mid+1,end)的值,就可以判断该mid 是否是中心下标。

(2) 算法原理         

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

        // 初始化前缀和
        f[0] = g[n-1] = 0;
        for(int i =1;i<=n;++i) f[i] = f[i-1] + nums[i-1];
        for(int i =n-2;i>=0;--i) g[i] = g[i+1] + nums[i+1];

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

4、除自身以外数组的乘积

(1) 题目解析        

        

(2) 算法原理        

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

        // 初始化前缀和
        f[0] = g[n-1] = 1;
        for(int i=1;i<=n;++i) f[i] = f[i-1]*nums[i-1];
        for(int i=n-2;i>=0;--i) g[i] = g[i+1]*nums[i+1];

        // 判断
        vector<int> ret;
        for(int i=0;i<n;++i)
        {   
           ret.push_back(f[i] * g[i]);
        }
        return ret;
    }
};

5、和为 K 的子数组

(1) 题目解析

算法综合篇专题四:前缀和,综合算法篇,算法,数据结构,c++

        什么是子数组? 子数组一定是连续的 --> 这本质对应的是前缀和因为前缀和就是连续区间。

(2) 算法原理         

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) { 
        unordered_map<int,int> hash; 
        hash[0] = 1;  // 细节处理
        int sum = 0; // 模拟前缀和
        int count = 0;
        for(auto& num:nums)
        {
            sum += num;
            if(hash.count(sum-k)){
                // 该元素存在
                // 有多少个这个元素 就能找出多少个k
                count += hash[sum-k];
            }  
            // 该元素值个数++
            hash[sum]++;
        }
        return count;
    }
};

6、和可被 K 整除的子数组

(1) 题目解析        

         相比于上题,这道题无非条件做了些改变,在数组里找到能被k整除的前缀和。不过在开始这道题之前,我们得补充另外一个知识。

同余定理:

        给定一个正整数m,如果两个整数a和b满足a-b能够被m整除,即(a-b)/m得到一个整数,那么就称整数a与b对模m同余,记作a≡b(mod m)。对模m同余是整数的一个等价关系。

        简单来说,就是这样:

算法综合篇专题四:前缀和,综合算法篇,算法,数据结构,c++

        有了上述的基础,我们再来认识认识这道题。

(2) 算法原理        

算法综合篇专题四:前缀和,综合算法篇,算法,数据结构,c++

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        unordered_map<int, int> hash;
        hash[0 % k] = 1; // 0 这个数的余数

        int sum = 0,ret = 0;
        for(auto& n:nums)
        {
            sum += n;
            int r = (sum % k + k) % k; // 修正后的余数
            if(hash.count(r)) ret += hash[r];
            hash[r]++;
        }
        return ret;
    }
};

7、连续数组

(1) 题目解析

算法综合篇专题四:前缀和,综合算法篇,算法,数据结构,c++

    我们可以根据1,-1的性质,因为题目是要找到能够匹配相同数量的0,1数字。当我们将0替换为-1时,如果存在长度相同的0,1数对,那么它们的和为0。反过来,本题就是要找最长子数组元素和为0的长度。     

(2) 算法原理         

算法综合篇专题四:前缀和,综合算法篇,算法,数据结构,c++

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int,int> hash;
        hash[0] = -1;
        int sum = 0;
        int len = 0;
        for(int i = 0; i < nums.size(); i++)
        {
            sum += nums[i] == 0 ? -1 : 1;   // 计算前缀和
            if(hash.count(sum)) len = max(len,i - hash[sum]);
            else hash[sum] = i; // 存储下标
        }
        return len;
    }
};

8、矩阵区域和

(1) 题目解析        

算法综合篇专题四:前缀和,综合算法篇,算法,数据结构,c++

        矩阵和同二维前缀和是相差无几的,都是求区域内的面积。例如上述例子,虽然是求整个矩阵的元素和,但是可以化解为从下标[1,1] 到 下标[3,3] 的前缀和矩阵。

(2) 算法原理

计算前缀和:

算法综合篇专题四:前缀和,综合算法篇,算法,数据结构,c++      

使用前缀和:

算法综合篇专题四:前缀和,综合算法篇,算法,数据结构,c++

class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int m = mat.size();
        int n = mat[0].size();

        // 初始化前缀和
        vector<vector<int>> dp(m+1,vector<int>(n+1));
        for(int i=1;i<=m;++i)
            for(int j=1;j<=n;++j) dp[i][j] = dp[i-1][j] + dp[i][j-1] + mat[i-1][j-1] - dp[i-1][j-1];

        // 使用前缀和
        vector<vector<int>> ret(m,vector<int>(n));
        for(int i=0;i<m;++i)
            for(int j=0;j<n;++j)
            {
                int x1 = max(0, i - k) + 1, y1 = max(0, j - k) + 1;
                int x2 = min(m - 1, i + k) + 1, y2 = min(n - 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;
    }
};

本篇到此结束,感谢你的阅读。

祝你好运,向阳而生~

算法综合篇专题四:前缀和,综合算法篇,算法,数据结构,c++文章来源地址https://www.toymoban.com/news/detail-733166.html

到了这里,关于算法综合篇专题四:前缀和的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法专题四:前缀和

    一维前缀和 1.输入数组长度n和查询次数q。 2.使用一个一维数组保存数据。 3.使用一个循环获取q次需要查询范围的数据。 4.遍历r-l+1次进行一个范围求和然后输出。 5.时间复杂度:O(n^2) 6.通过不了所有的测试用例。 1.输入数组长度n和查询次数q。 2.使用一个一维数组保存数据。

    2024年02月01日
    浏览(36)
  • 【算法优选】前缀和专题——叁

    含义 : 前缀和实际上就是对于长度为n的数组, 我们新建立一个数组长度为n+1,第i个元素的值为前i个元素的和(包括第i个元素) 。 特点 : 前缀和数组比原数组多一个长度。 前缀和的第0个元素的值为0。 根据前缀和数组的特点,求前缀和时。我们只需要用第i个元素的值

    2024年02月06日
    浏览(42)
  • 【尚硅谷】数据结构和算法——前缀、中缀、后缀表达式规则

    跟着B站的尚硅谷学习数据结构与算法,语言为java,目前是第七个代码内容——前缀、中缀、后缀表达式 课程传送门:尚硅谷——前缀、中缀、后缀表达式 1)前缀表达式又称波兰式, 前缀表达式 的运算符位于操作符之前。 2)举例说明:(3+4)*5-6 对应的前缀表达式就是 - *

    2024年02月03日
    浏览(56)
  • 数据结构和算法专题---3、失效算法与应用

    本章我们会对失效算法做个简单介绍,包括常用的失效算法(先来先淘汰(FIFO)、最久未用淘汰(LRU)、最近最少使用(LFU))的概述、实现方式、典型场景做个说明。 失效算法常见于缓存系统中。因为缓存往往占据大量内存,而内存空间是相对昂贵,且空间有限的,那么

    2024年02月04日
    浏览(44)
  • 数据结构和算法专题---4、限流算法与应用

    本章我们会对限流算法做个简单介绍,包括常用的限流算法(计数器、漏桶算法、令牌桶案发、滑动窗口)的概述、实现方式、典型场景做个说明。 限流是对系统的一种保护措施。即限制流量请求的频率(每秒处理多少个请求)。一般来说,当请求流量超过系统的瓶颈,则丢

    2024年02月04日
    浏览(49)
  • 【数据结构与算法】【12】前缀表达式、中缀表达式、后缀表达式

    什么是前缀表达式、中缀表达式、后缀表达式 前缀表达式、中缀表达式、后缀表达式,是通过树来存储和计算表达式的三种不同方式 以如下公式为例 ( a + ( b − c ) ) ∗ d ( a+(b-c) )*d ( a + ( b − c ) ) ∗ d 通过树来存储该公式,可以表示为 那么问题就来了,树只是一种抽象的数据

    2024年02月08日
    浏览(44)
  • 每天一道算法练习题--Day18 && 第一章 --算法专题 --- ----------前缀树

    字典树也叫前缀树、Trie。它本身就是一个树型结构,也就是一颗多叉树,学过树的朋友应该非常容易理解,它的核心操作是插入,查找。删除很少使用,因此这个讲义不包含删除操作。 截止目前(2020-02-04) 前缀树(字典树) 在 LeetCode 一共有 17 道题目。其中 2 道简单,8 个

    2024年02月02日
    浏览(51)
  • 链表综合算法设计(c++数据结构)

      一、设计内容 已知简单的人事信息系统中职工记录包含职工编号(no)、职工姓名(name)、部门名称(depname)、职称(title)和工资数(salary)等信息(可以增加其他信息),设计并完成一个简单的人事信息管理系统,要求完成但不限于以下功能: (1)    增加一个职工信息

    2024年02月02日
    浏览(55)
  • 【算法数据结构专题】「延时队列算法」史上手把手教你针对层级时间轮(TimingWheel)实现延时队列的开发实战落地(下)

    承接上一篇文章【算法数据结构专题】「延时队列算法」史上手把手教你针对层级时间轮(TimingWheel)实现延时队列的开发实战落地(上)】我们基本上对层级时间轮算法的基本原理有了一定的认识,本章节就从落地的角度进行分析和介绍如何通过Java进行实现一个属于我们自

    2023年04月08日
    浏览(41)
  • 数据结构课程设计题目——链表综合算法设计、带头双向循环链表、插入、显示、删除、修改、排序

      课程设计题目1–链表综合算法设计   一、设计内容   已知简单的人事信息系统中职工记录包含职工编号(no)、职工姓名(name)、部门名称(depname)、职称(title)和工资数(salary)等信息(可以增加其他信息),设计并完成一个简单的人事信息管理系统,要求完成但不

    2024年02月08日
    浏览(61)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包