C++ 前缀和

目录

例1

例2

例3

例4

例5

例6

例7

例8

例1

DP34 【模板】前缀和

分析：dp和arr的大小并不是固定的，就是有没有偏移量，这里的n是从1开始，不如直接放到下标1处，在最后的减法时，如果用第一个参考代码会下标越界到-1，所以说这里的方法并不是固定的，思路，偏移量理清了静下心就可以上手写

注意：a[i] 的最大值是INT_MAX，所以创建long long 类型的dp表

参考代码:dp[n + 1],arr[n + 1]

#include <iostream>
using namespace std;
#include <vector>
int main() {
    int n = 0, q = 0;
    cin >> n >> q;
    vector<int> arr(n + 1);
    for(int i = 1; i < n + 1; i++)
        cin >> arr[i];
    vector<long long> dp(n + 1);
    for(int i = 1; i < n + 1; i++)
        dp[i] = dp[i - 1] + arr[i];
    int l = 0, r = 0;
    while(q--)
    {
        cin >> l >> r;
        cout << dp[r] - dp[l - 1] << endl;
    }
    return 0;
}
// 64 位输出请用 printf("%lld")

参考代码: dp[n],arr[n]

#include <iostream>
using namespace std;
#include <vector>
int main() {
    int n = 0, q = 0;
    cin >> n >> q;
    vector<int> arr(n);
    for(int i = 0; i < n; i++)
        cin >> arr[i];
    vector<long long> dp(n);
    dp[0] = arr[0];
    for(int i = 1; i < n; i++)
        dp[i] = dp[i - 1] + arr[i];
    
    int l = 0, r = 0;
    while(q--)
    {
        cin >> l >> r;
        cout << dp[r - 1] - dp[l - 1] + arr[l - 1] << endl;
    }
    return 0;
}
// 64 位输出请用 printf("%lld")

参考代码：dp[n],arr[n + 1]

#include <iostream>
using namespace std;
#include <vector>
int main() {
    int n = 0, q = 0;
    cin >> n >> q;
    vector<int> arr(n + 1);
    for(int i = 1; i <= n; i++)
        cin >> arr[i];
    vector<long long> dp(n);
    dp[0] = arr[1];
    for(int i = 1; i < n; i++)
        dp[i] = dp[i - 1] + arr[i + 1];
    
    int l = 0, r = 0;
    while(q--)
    {
        cin >> l >> r;
        cout << dp[r - 1] - dp[l - 1] + arr[l] << endl;
    }
    return 0;
}
// 64 位输出请用 printf("%lld")

例2

DP35 【模板】二维前缀和

 

dp和原数组对齐了，就没有偏移量

注意：a[i][j] 的最大值是INT_MAX，所以创建long long 类型的dp表

参考代码

#include <iostream>
using namespace std;
#include <vector>
int main() {
    int n = 0, m = 0, q = 0;
    cin >> n >> m >> q;
    vector<vector<int>> arr(n + 1, vector<int>(m + 1));
    for(int i = 1; i < n + 1; i++)
        for(int j = 1; j < m + 1; j++)
            cin >> arr[i][j];
    vector<vector<long long>> dp(n + 1, vector<long long>(m + 1));
    for(int i = 1; i < n + 1; i++)
        for(int j = 1; j < m + 1; j++)
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + arr[i][j];
    while(q--)
    {
        int x1 = 0, y1 = 0, x2 = 0, y2 = 0;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1] << endl; 
    }
    return 0;
}

例3

724. 寻找数组的中心下标

 要点：f[i] = f[i - 1] + nums[i - 1];就是看后面的nums，如果是i - 1，就是不包括自己的前缀和，f[0]自然是0，这题包不包括都可以，包括就是等式两边同时加上自己这个元素，

参考代码

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n), g(n);
        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];
        for(int i = 0; i < n; i++)
            if(f[i] == g[i])
                return i;
        return -1;
    }
};

例4

238. 除自身以外数组的乘积

注意点：f[0] = 1， g[n - 2] = 1

参考代码

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n), g(n), ret(n);
        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];
        for(int i = 0; i < n; i++)
            ret[i] = f[i] * g[i];
        return ret;
    }
};

例5

560. 和为 K 的子数组

可以不用前缀和，因为这里不需要用到下标随机访问，这里只需要顺序访问

这里不可以用滑动窗口：因为没有单调性

把有的sum都放到哈希表里就行，先判断 : hash.count(sum)   再放入哈希表

注意：这里有个hash[0] = 1，sum = k时候也是符合条件，但是哈希表里没有hash[0]，(但是之后是会可能会添加上hash[0]，就是中间有个地方前缀和为0)，总的来说就是少了一个起点0

参考代码

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        // int n = nums.size(), ret = 0;
        // vector<int> dp(n);
        // dp[0] = nums[0];
        // for(int i = 1; i < n; i++)
        //     dp[i] = dp[i - 1] + nums[i];
        
        // unordered_map<int, int> hash;
        // hash[0] = 1;
        // for(auto e : dp)
        // {
        //     if(hash.count(e - k)) ret += hash[e - k];//hash[e - k]
        //     hash[e]++;
        // }
        // // for(int i = 0; i < n; i++)
        // // {
        // //     if(hash.count(dp[i] - k)) ret += hash(dp[i] - k);
        // //     hash[dp[i]]++;
        // // }
        // return ret;

        unordered_map<int, int> hash;
        hash[0] = 1;
        int sum = 0, ret = 0;
        for(int i = 0; i < nums.size(); i++)
        {
            sum += nums[i];
            if(hash.count(sum - k)) ret += hash[sum - k];
            hash[sum]++;
        }
        return ret;
    }
};

例6

974. 和可被 K 整除的子数组

参考代码

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

例7

525. 连续数组

题解：把0 改成 -1，之后求和为0的最长子数组，有负数，自然不能用滑动窗口

因为求的是长度吗，那么这里就是最短索引和前缀和的映射，<前缀和，最小索引>

因为是顺序遍历 ，那么不存在就添加进哈希表，这样就可以得到最小索引，既可以不用dp表，也直接找到最小索引

注意：这样就可以理解为什么是i - hash[sum]

参考代码

class Solution 
{
public:
    int findMaxLength(vector<int>& nums) 
    {
        unordered_map<int, int> hash;
        int sum = 0, ret = 0;
        hash[0] = -1;
        // for(auto e : nums)
        // {
        //     sum += e == 0 ? -1 : e;
        //     if(hash.count(sum)) ret = max(ret, );
        //     else hash[sum]++;
        // }
        for(int i = 0; i < nums.size(); i++)
        {
            sum += nums[i] == 0 ? -1 : 1;
            if(hash.count(sum)) ret = max(ret, i - hash[sum]);
            else hash[sum] = i;
        }

        return ret;
    }
};

例8

1314. 矩阵区域和

分析：涉及偏移量，和对越界的处理，如果二维dp不是 行列 + 1那么边界情况就麻烦了，一维dp若不是n + 1 只有开头或者结尾处理，

偏移：mat 到dp 的偏移，dp 到 ret的偏移

注意：int x2 = min(i + k, m - 1) + 1, y2 = min(j + k, n - 1) + 1;我在写的时候错在不是m - 1

参考代码

class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for(int i = 1; i < m + 1; i++)
            for(int j = 1; j < n + 1; j++)
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[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(i - k, 0) + 1, y1 = max(j - k, 0) + 1;
                int x2 = min(i + k, m - 1) + 1, y2 = min(j + k, n - 1) + 1;
                ret[i][j] = dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1];
            }
        return ret;
    }
};

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

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

相关文章

单调栈的理解

单调栈的理解

单调栈的理解 核心代码场景思考 完整代码环形数组循环数组 单调栈&#xff1a; 单调递增或 单调递减的栈 核心代码 while (!s.empty()&&s.peek()<nums[i]){s.pop(); } s.push(nums[i]);将要放入的元素&#xff0c;与栈内元素依个比较&#xff0c;小于的都出栈&am…
阅读更多...
设计模式（含7大原则）面试题

设计模式（含7大原则）面试题

目录 主要参考文章 设计模式的目的 设计模式的七大原则 设计模式的三大分类及关键点 1、创建型模式&#xff08;用于解耦对象的实例化过程&#xff09; 2、结构型模式 3、行为型模式 23种设计模式&#xff08;乱序--现学现写&#xff0c;不全面--应付面试为主&#xff…
阅读更多...
BUUCTF------[HCTF 2018]WarmUp

BUUCTF------[HCTF 2018]WarmUp

开局一个表情&#xff0c;源代码发现source.php <?phphighlight_file(__FILE__);class emmm{public static function checkFile(&$page){$whitelist ["source">"source.php","hint">"hint.php"];if (! isset($page) |…
阅读更多...
web坦克大战小游戏

web坦克大战小游戏

H5小游戏源码、JS开发网页小游戏开源源码大合集。无需运行环境&#xff0c;解压后浏览器直接打开。有需要的订阅后&#xff0c;私信本人&#xff0c;发源码&#xff0c;含60小游戏源码。如五子棋、象棋、植物大战僵尸、贪吃蛇、飞机大战、坦克大战、开心消消乐、扑鱼达人、扫雷…
阅读更多...
基于小红书评论的文本词语频数挖掘和词云图

基于小红书评论的文本词语频数挖掘和词云图

import pandas as pd df pd.read_csv(小红书评论.csv) # 读取小红书评论数据 text .join(df[内容].astype(str)).strip() # 将内容列所有数据合成字符串 print(text) 使用jieba库&#xff0c;对文本数据进行分词&#xff0c;并统计出现频数 import jieba from collectio…
阅读更多...
JMeter Body Data模拟10000个字符串

JMeter Body Data模拟10000个字符串

方法 **这个表达式使用了JMeter中的Groovy函数&#xff0c;目的是生成一个包含10000个字符 "s" 的字符串。在Groovy语言中&#xff0c;使用 "s" * 10000 可以生成包含10000个 "s" 的字符串。${__groovy("s" * 10000,)} 这个表达式在J…
阅读更多...
财报解读：基本盘稳定后，联想如何进一步抢占AI时代？

财报解读：基本盘稳定后，联想如何进一步抢占AI时代？

从2021年下半年开始&#xff0c;受诸多因素影响&#xff0c;消费电子行业始终处在承压状态&#xff0c;“不景气”这一关键词屡次被市场提及。 但寒气没有持续&#xff0c;可以看到&#xff0c;消费电子行业正在逐渐回暖。国金证券在今年1月的研报中就指出&#xff0c;从多方面…
阅读更多...
数字人解决方案——阿里EMO音频驱动肖像生成能说话能唱歌的逼真视频

数字人解决方案——阿里EMO音频驱动肖像生成能说话能唱歌的逼真视频

前言 数字可以分为3D数字人和2D数字人。3D数字人以虚幻引擎的MetaHuman为代表&#xff0c;而2D数字人则现有的图像或者视频做为输入&#xff0c;然后生成对口型的数字人&#xff0c;比如有SadTalker和Wav2Lip。 SadTalker&#xff1a;SadTalker是一种2D数字人算法&#xff0c;…
阅读更多...
什么是网络安全、信息安全、计算机安全，有何区别？

什么是网络安全、信息安全、计算机安全，有何区别？

这三个概念都存在&#xff0c;一般人可能会混为一谈。 究竟它们之间是什么关系&#xff1f;并列&#xff1f;交叉&#xff1f; 可能从广义上来说它们都可以用来表示安全security这样一个笼统的概念。 但如果从狭义上理解&#xff0c;它们应该是有区别的&#xff0c;区别在哪呢&…
阅读更多...
基于XTuner微调书生·浦语大模型

基于XTuner微调书生·浦语大模型

1 概述 XTuner 是一个傻瓜式、轻量级的大语言模型微调工具箱&#xff0c;由MMRazor和MMDeploy联合开发。其以配置文件的形式封装了大部分微调场景&#xff0c;0基础的非专业人员也能一键开始微调&#xff1b;对于 7B 参数量的LLM&#xff0c;微调所需的最小显存仅为 8GB。 常…
阅读更多...
day11_oop_fianl_satic_多态

day11_oop_fianl_satic_多态

今日内容 零、 复习昨日 一、final 二、static 三、多态 四、向上转型&向下转型 五、多态应用 零、 复习昨日 0 类封装步骤 属性私有private提供setget方法 1 继承关键词,继承的好处 extends减少代码重复为多态做准备 2 子类可以使用父类什么 非私有的属性和方法 3 方法重写…
阅读更多...
网络机顶盒哪个好？数码小编分享网络机顶盒排名

网络机顶盒哪个好？数码小编分享网络机顶盒排名

每次在挑选网络机顶盒的时候&#xff0c;很多朋友会咨询我的意见&#xff0c;最近每天都会收到相关的咨询&#xff0c;不知道网络机顶哪个好&#xff0c;我这次要分享的就是业内公认网络机顶盒排名&#xff0c;入围的几个品牌都是非常出色的&#xff0c;想买网络机顶盒的可以从…
阅读更多...
亚信安慧AntDB：数智化转型的可持续动能

亚信安慧AntDB：数智化转型的可持续动能

AntDB致力于为企业提供可持续发展的数据支持&#xff0c;其使命在于助力企业更好地适应不断变化的数智化时代。作为一款性能出色、可靠稳定的分布式数据库系统&#xff0c;AntDB为企业打造了一个高效、安全、灵活的数据管理平台&#xff0c;不仅拥有强大的数据处理和分析能力&a…
阅读更多...
谁才是“内卷”之王？众多洗地机品牌哪家清洁力最强？清洁最干净？

谁才是“内卷”之王？众多洗地机品牌哪家清洁力最强？清洁最干净？

在如今快节奏的生活中&#xff0c;家庭清洁工作愈发显得繁琐而耗时。添可洗地机凭借其高效的一体化清洁功能和智能化操作&#xff0c;为现代家庭生活带来了极大的便利。面对众多款品牌洗地机型号&#xff0c;消费者不禁会问&#xff1a;哪家洗地机清洁力最强&#xff1f;在性能…
阅读更多...
IO（Linux）

IO（Linux）

文件系统 前言1. 回顾关于C文件部分函数2. 一些文件知识的共识3. 相对路径4. fwrite中的\0 一、文件描述符fd1. 概念2. 系统调用① open 和 close② write③ read 和 lseek 3. 缺省打开的fd 二、重定向1. 原理2. 系统调用dup23. stdout和stderr的区别4. 进程替换和原来进程文件…
阅读更多...
百度AI，能否“投”出未来？

百度AI，能否“投”出未来？

图片&#xff5c;freeflo.ai ©自象限原创 作者丨程心、罗辑 2月28日&#xff0c;百度发布了2023年四季度财报及全年未经审计的财务报告&#xff0c;AI大模型带来的收入和利润成为最大的亮点。 财报显示&#xff0c;2023年百度集团总营收达1345.98亿元&#xff0c;同比增…
阅读更多...
java数据结构与算法刷题-----LeetCode337. 打家劫舍 III

java数据结构与算法刷题-----LeetCode337. 打家劫舍 III

java数据结构与算法刷题目录&#xff08;剑指Offer、LeetCode、ACM&#xff09;-----主目录-----持续更新(进不去说明我没写完)&#xff1a;https://blog.csdn.net/grd_java/article/details/123063846 文章目录 1. 动态规划深度优先1.1 解题思路和细节2.2 代码实现 很多人觉得…
阅读更多...
告别信息搜寻烦恼：用fastgpt快速部署国内大模型知识库助手

告别信息搜寻烦恼：用fastgpt快速部署国内大模型知识库助手

Docker Compose 快速部署 使用 Docker Compose 快速部署 FastGPT 推荐配置 环境最低配置&#xff08;单节点&#xff09;推荐配置测试2c2g2c4g100w 组向量4c8g 50GB4c16g 50GB500w 组向量8c32g16c64g 200GB 部署架构图 1. 准备好代理环境&#xff08;国外服务器可忽略&…
阅读更多...
web游戏-飞机大战

web游戏-飞机大战

H5小游戏源码、JS开发网页小游戏开源源码大合集。无需运行环境&#xff0c;解压后浏览器直接打开。有需要的订阅后&#xff0c;私信本人&#xff0c;发源码&#xff0c;含60小游戏源码。如五子棋、象棋、植物大战僵尸、贪吃蛇、飞机大战、坦克大战、开心消消乐、扑鱼达人、扫雷…
阅读更多...
STM32自学☞I2C

STM32自学☞I2C

这里只是大体介绍&#xff0c;具体的可参考STM32数据手册
阅读更多...
最新文章

Copyright @ 2022~2023