前缀和算法:算法秘籍下的数据预言家

✨✨✨学习的道路很枯燥,希望我们能并肩走下来!

文章目录

目录

文章目录

前言

一. 前缀和算法的介绍

二、前缀和例题

2.1 【模版】前缀和

2.2 【模板】二维前缀和

 2.3 寻找数组的中间下标

 2.4 除自身以外数组的乘积

 2.5 和为k的子数组

2.6 和可被k整除的子数组

 2.7 连续数组

 2.8 矩阵区域和

总结


前言

本篇详细介绍了前缀和算法的使用,让使用者了解前缀和,而不是仅仅停留在表面, 文章可能出现错误,如有请在评论区指正,让我们一起交流,共同进步!


一. 前缀和算法的介绍

前缀和算法是一种用空间换时间的算法,他常常用于解决某些题目或者作为某些高级算法的组成部分。

例如:让你求某个矩阵(一维)的子矩阵的最大值,如果使用暴力解法它的时间复杂度将会是O(n^2) ,但如果使用该算法就可以使其时间复杂度降低一个维度也就是O(N).

前缀和 是从 nums 数组中的第 0 位置开始累加,到第 𝑖位置的累加结果,我们常把这个结果保存到数组 Sum 中,记为 Sum[i]。 

前缀和算法的本质是一个简单动态规划

 接下来我们使用一些例题来介绍一下

二、前缀和例题

2.1 【模版】前缀和

牛客网—【模版】前缀和

 

#include <iostream>
#include<vector>
using namespace std;int main() {//1.读入数据int n ,q;cin>>n>>q;vector<int> arr(n+1);for(int i = 1;i<=n;i++) cin>>arr[i];//2. 预处理出来个前缀和数组vector<long long> dp(n+1); //防止溢出for(int i = 1;i<=n;i++) dp[i] = dp[i-1]+arr[i];//3.使用前缀和数组int l = 0, r = 0;while(q--){cin>>l>>r;cout<<dp[r]-dp[l-1]<<endl;}return 0;}

2.2 【模板】二维前缀和

牛客网—【模版】二维前缀和

 

#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));for(int i = 1;i<=n;i++){for(int j = 1;j<=m;j++){cin>>arr[i][j];}}vector<vector<long long>> dp(n+1,vector<long long>(m+1));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 = 0,y1 = 0,x2 = 0 ,y2 = 0;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;
}

 2.3 寻找数组的中间下标

724. 寻找数组的中心下标 - 力扣(LeetCode) 

 

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

 2.4 除自身以外数组的乘积

238. 除自身以外数组的乘积 - 力扣(LeetCode) 

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

 2.5 和为k的子数组

560. 和为 K 的子数组 - 力扣(LeetCode)

 

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&x : nums){sum+=x; //计算当前位置的前缀和if(hash.count(sum-k)) ret+=hash[sum-k]; //统计个数hash[sum]++;}return ret;}
};

2.6 和可被k整除的子数组

974. 和可被 K 整除的子数组 - 力扣(LeetCode) 

 

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& x : nums){sum+=x; //算出当前位置的前缀和if(hash.count((sum%k+k)%k)) ret+=hash[(sum%k+k)%k]; //修正后的余数+统计结果hash[(sum%k+k)%k]++;}return ret;}
};

 2.7 连续数组

525. 连续数组 - 力扣(LeetCode) 

 

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

 2.8 矩阵区域和

1314. 矩阵区域和 - 力扣(LeetCode)

 

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;i++)for(int j = 1;j<=n;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>> answer(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;int y1 = max(0,j-k)+1;int x2 = min(m-1,i+k)+1;int y2 = min(n-1,j+k)+1;answer[i][j] = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1];}return answer;}
};

总结

✨✨✨各位读友,本篇分享到内容是否更好的让你理解前缀和算法,如果对你有帮助给个👍赞鼓励一下吧!!
🎉🎉🎉世上没有绝望的处境,只有对处境绝望的人。
感谢每一位一起走到这的伙伴,我们可以一起交流进步!!!一起加油吧!!

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

maven编译【-Dmaven.test.skip=true和-DskipTests=true的区别】

1、背景 我在执行maven编译时&#xff0c;遇到下面情况&#xff1a; 1、当执行命令为下面&#xff1a; mvn clean compile package install -Dmaven.wagon.http.ssl.insecuretrue -Dmaven.wagon.http.ssl.allowalltrue -Dmaven.wagon.http.ssl.ignore.validity.datestrue -Dra…

红队内网攻防渗透:内网渗透之Linux内网权限提升技术:udf提权Capability权限LD_PRELOAD环境变量

红队内网攻防渗透 1. 内网权限提升技术1.1 Linux系统提权-Web&用户-数据库udf提权1.1.1 信息收集1.1.2 Web权限获取1.1.3 MYSQL-UDF提权1.1.4 下载到目标上1.1.5 连接确认是否有条件进行导出调用1.1.6 开始进行写入导出调用1.2 Linux系统提权-Web&用户-Capability能力1…

Java语言+前端框架html+Thymeleaf +后端框架springboot开发的UWB智能定位系统源码 UWB三维可视化人员定位系统源码

Java语言前端框架htmlThymeleaf 后端框架springboot开发的UWB智能定位系统源码 UWB三维可视化人员定位系统源码 UWB定位系统基于B/S架构的软件和嵌入式硬件都具有很好的扩展性和兼容性&#xff0c;可以与其他系统接口&#xff08;比如&#xff1a;围界、AB门、高压电网、报警、…

怎么图片转excel表格?推荐三个方法

怎么图片转excel表格&#xff1f;在信息化高速发展的今天&#xff0c;图片转Excel表格的需求日益凸显&#xff0c;尤其是在职场办公中&#xff0c;这一需求更是显得尤为迫切。为了满足广大用户的需求&#xff0c;市面上涌现出了众多图片转Excel的软件。今天&#xff0c;就为大家…

QT 使用资源文件的注意点

不要存放没有使用的资源文件 即使在代码中没有使用到的资源文件&#xff0c;也会编译到执行文件或者DLL里面去这样会增大它的体积。如下 在代码没有使用这个资源文件(10.4M的2k图片)&#xff0c;但是编译出来的程序有 12M左右的大小

java写一个验证码

生成验证码 内容&#xff1a;可以是小写字母&#xff0c;也可以是大写字母&#xff0c;还可以是数字 规则 长度为5 内容中是四位字母&#xff0c;1位数字。 其中数字只有1位&#xff0c;但是可以出现在任意的位置。 package User;import java.util.ArrayList; import jav…

Android Studio Jellyfish版本修改project使用特定jdk版本的步骤

android studio总是把这些东西改来改去让人十分恼火&#xff0c;IDE本身改来改去就让人无法上手就立即工作&#xff0c;很多时间浪费在IDE和gradle的配置和奇奇怪怪现象的斗智斗勇上&#xff0c;搞Android是真的有点浪费生命。一入此坑深不见底 jellyfish版安卓studio已经无法通…

LeetCode | 434.字符串中的单词数

这道题直接使用语言内置的 split 函数可直接分离出字符串中的每个单词&#xff0c;但是要注意区分两种情况&#xff1a;1、空串&#xff1b;2、多个空格连续&#xff0c;分割后会出现空字符的情况&#xff0c;应该舍弃 class Solution(object):def countSegments(self, s):&qu…

接口测试之用Fiddler对手机app进行抓包

Fiddler是一款非常流行并且实用的http抓包工具&#xff0c;它的原理是在本机开启了一个http的代理服务器&#xff0c;然后它会转发所有的http请求和响应&#xff0c;因此&#xff0c;它比一般的firebug或者是chrome自带的抓包工具要好用的多。不仅如此&#xff0c;它还可以支持…

202478读书笔记|《人间小满》——小满,才是最好的人生状态,养身先养心,知世故而不世故,历圆滑而弥天真

202478读书笔记|《人间小满》——小满&#xff0c;才是最好的人生状态&#xff0c;养身先养心&#xff0c;知世故而不世故&#xff0c;历圆滑而弥天真 一、画出世俗的欢喜&#xff0c;过一种平淡自由的人生二、与时舒卷&#xff0c;抵岁月荒唐三、一半是海水&#xff0c;一半是…

案例学习-存量更新规划实施探索(武汉)

案例学习-存量更新规划实施探索&#xff08;武汉&#xff09; 武汉市在早期旧城更新实践中发现零散化的更新往往导致资源配置分散、城市建设破碎化等弊病&#xff0c;特别是由于过于强调项目自身“经济平衡”&#xff0c;在实施过程中也逐步暴露出住宅占比过大、强度偏高、公服…

C++之模板

在C 中&#xff0c;模板为泛型程序设计奠定了关键的基础。使用模板需要用到两个关键字template 、typename&#xff0c;写法&#xff1a;template<typename Type> template告诉编译器&#xff0c;将要定义一个模板&#xff0c;<>中的是模板参数列表&#xff0c;类…

AGI 远不止 ChatGPT!一文入门 AGI 通识及应用开发

AI 大语言模型进入爆发阶段 2022 年 12 月 ChatGPT 突然爆火&#xff0c;原因是其表现出来的智能化已经远远突破了我们的常规认知。虽然其呈现在使用者面前仅仅只是一个简单的对话问答形式&#xff0c;但是它的内容化水平非常强大&#xff0c;甚至在某些方面已经超过人类了&am…

禁用PS/Photoshop等一系列Adobe旗下软件联网外传用户数据操作

方案一&#xff1a; 下载火绒杀毒&#xff0c;在联网请求上禁用Adobe软件的联网请求&#xff0c;甚至还可以额外发现哪些是它要想要偷偷摸摸干的。 方案二&#xff1a; 最后注意&#xff1a; 用盗版软件只是获得了使用权&#xff01;

关于element-plus中el-select自定义标签及样式的问题

关于element-plus中el-select自定义标签及样式的问题 我这天天的都遇到各种坑&#xff0c;关于自定义&#xff0c;我直接复制粘贴代码都实现不了&#xff0c;研究了一下午&#xff0c;骂骂咧咧了一下午&#xff0c;服气了。官网代码实现不了&#xff0c;就只能 “ 曲线救国 ”…

Kubernetes集群持久化部署实践

WordPress 网站持久化部署 要持久化MariaDB 可以把 Deployment 改成了 StatefulSet&#xff0c;修改 YAML添加“serviceName”“volumeClaimTemplates”这两个字段&#xff0c;定义网络标识和 NFS 动态存储卷&#xff0c;然后在容器部分用“volumeMounts”挂载到容器里的数据目…

php实现一个简单的MySQL分页

一、案例演示&#xff1a; 二、php 代码 <?php $servername "localhost"; // MySQL服务器名称或IP地址 $username "root"; // MySQL用户名 $password "123456"; // MySQL密码 $dbname "test"; // 要连接…

Character Region Awareness for Text Detection论文学习

​1.首先将模型在Synth80k数据集上训练 Synth80k数据集是合成数据集&#xff0c;里面标注是使用单个字符的标注的&#xff0c;也就是这篇文章作者想要的标注的样子&#xff0c;但是大多数数据集是成堆标注的&#xff0c;也就是每行或者一堆字体被整体标注出来&#xff0c;作者…

泛微开发修炼之旅--15后端开发连接外部数据源,实现在ecology系统中查询其他异构系统数据库得示例和源码

文章链接&#xff1a;15后端开发连接外部数据源&#xff0c;实现在ecology系统中查询其他异构系统数据库得示例和源码

大模型应用产品指北

一、试用类型 计算机视觉Computer Vision&#xff1a;Text-to-image(文生图) 二、国内产品 Aliyun通义千问 【体验】 可以替代Stable Diffusion、Midjourney;支持风格、滤镜; [传送门&#xff1a;通义万相] 【体验】Transformer架构&#xff1b;中英双语&#xff1b;开源可以…