【刷题】前缀和入门

在这里插入图片描述

送给大家一句话:
既然已经做出了选择,最好还是先假定自己是对的。焦虑未来和后悔过去,只经历一个就够了。 – 张寒寺 《不正常人类症候群》

☆ミヾ(∇≦((ヾ(≧∇≦)〃))≧∇)ノ彡☆
☆ミヾ(∇≦((ヾ(≧∇≦)〃))≧∇)ノ彡☆
☆ミヾ(∇≦((ヾ(≧∇≦)〃))≧∇)ノ彡☆


前缀和入门

  • 1 前言
    • 1.1 算法步骤
    • 1.2 使用场景
    • 1.3 时间复杂度分析
    • 1.4 空间复杂度分析
  • 2 牛客 DP35 【模板】二维前缀和
    • 题目描述
    • 算法思路
  • 3 牛客 DP35 【模板】二维前缀和
    • 题目描述
    • 算法思路
  • Leetcode 724. 寻找数组的中心下标
    • 题目描述
    • 算法思路
  • Leetcode 238. 除自身以外数组的乘积
    • 题目描述
    • 算法思路
  • Thanks♪(・ω・)ノ谢谢阅读!!!
  • 下一篇文章见!!!

1 前言

今天我学习了一个新算法:前缀和算法。
前缀和算法是一种高效处理数组区间和查询问题的算法。它的核心思想是在 O(n) 的时间复杂度内对输入数组进行预处理,从而使得后续每次查询数组中任意区间内元素和的时间复杂度降低到 O(1)。

1.1 算法步骤

  1. 初始化前缀和数组:创建一个新数组 dp,一般多开一位。
  2. 计算前缀和:遍历原数组 A,根据题目更新状态。
  3. 查询区间和:更加区间得到答案。

1.2 使用场景

  1. 频繁区间和查询:当需要对一个数组进行多次区间和查询时,前缀和可以大幅提高查询效率。
  2. 动态数据更新:在某些情况下,数组中的元素可能会动态更新,前缀和也能有效处理这种情况下的区间和查询。
  3. 多维数组处理:前缀和可以扩展到多维数组,用于处理多维数据区间和的问题。

1.3 时间复杂度分析

  • 预处理时间复杂度:O(n),其中 n 是原数组 A 的长度。
  • 查询时间复杂度:O(1),对于每次区间和查询。

1.4 空间复杂度分析

  • 空间复杂度:O(n),用于存储前缀和数组 dp。

前缀和算法在处理数组区间和问题时非常高效,适用于需要频繁查询和高效处理大量数据的场景。通过前缀和的预处理,可以显著减少计算成本,提高程序的运行效率,也就是 空间换时间

2 牛客 DP35 【模板】二维前缀和

上链接!!! DP34 一维前缀和

题目描述

在这里插入图片描述
根据题目描述,我们大概知道我们是求一个区间上的和。题目很好理解奥,接下来我们就来通过这道题来入门前缀和算法!!!

算法思路

首先最好想的就是暴力算法,求指定区间的和那么直接暴力求不就可以了?!但是毋庸置疑的是这样一定一定会超时,毕竟是O(n^2)的暴力算法。

那么来看前缀和算法,这是一个解决这个问题的优秀算法。前缀和的思想很简单,就是对数组进行一遍预处理,得到每个数组位置之前所有数的和,然后在通过减法求得数据。

  1. 创建一个大小为 n + 1 的数组(大小为 n + 1可以避免一些边界情况)
  2. 从 下标 1 开始读入数据
  3. 创建一个大小为 n + 1 的 dp 数组
  4. 从 下标 1 开始预处理数据
  5. 得到答案
#include <iostream>
#include <vector>
using namespace std;int main() {int n , q;cin >> n >> q;//读入数据vector<long long > nums(n + 1);for(int i = 1 ; i < n + 1 ; i++ ){cin >> nums[i];}//预处理数据vector<long long > sum(n + 1);for(int i = 1 ;  i < nums.size() ;i++ ){//i 位置的和等于 i - 1 位置的和 加上 i 位置的值//如果数组大小为n 那 i 从 0开始 那么就会读入 nums[-1]就会报错sum[i] = sum[i - 1] + nums[i];}//得出结果while(q--){int n1 , n2;cin >> n1 >> n2;cout <<sum[n2] - sum[n1 - 1] << endl;}return 0;
}

这样提交:过啦!!!
这里有点像动态规划奥

3 牛客 DP35 【模板】二维前缀和

家人们跟上节奏!!!DP35 二维前缀和

题目描述

在这里插入图片描述

根据题目描述,这道题是刚才一维的升级版,我们需要计算一个指定矩阵的和。那么依然使用的是前缀和来进行预处理。这道题就要注意细节处理了

算法思路

首先最好想的就是暴力算法,求指定矩阵的和那么直接暴力求不就可以了?!但是毋庸置疑的是这样一定一定会超时,O(n^3)的暴力算法啊。

那么来看前缀和算法,这是一个解决这个问题的优秀算法。前缀和的思想很简单,就是对数组进行一遍预处理,得到每个数组位置之前所有数的和,然后在通过减法求得数据。

  1. 创建一个大小为 (n + 1) *( n + 1) 的矩阵(大小为 n + 1可以避免一些边界情况)
  2. 从 坐标(1,1) 开始读入数据
  3. 创建一个大小为 (n + 1) *( n + 1) 的 dp 矩阵
  4. 从 坐标(1,1)开始预处理数据
  5. 得到答案

这里的预处理就有说法了,这和线性的数组不一样,我们做一个图就可以很好理解预处理然后进行:
求(i,j)的矩阵和:
可以理解为(i-1,j)的矩阵和 加上 (i,j-1)的矩阵和,加上(i,j)的值再减去(i-1,j-1)的矩阵和(因为多加了一遍)
在这里插入图片描述
这样就可以进行预处理了:
然后我们还需要如何得到答案:
在这里插入图片描述
我们想要求以 (x1, y1) 为左上角 , (x2,y2) 为右下角的子矩阵的和。
可以通过 (x2,y2) 矩阵和 减去(x2 , y1 - 1)矩阵和 减去(x1 - 1 , y2)矩阵和 加上(x1 - 1, y1 - 1)的矩阵和(因为多减了一遍)

#include <iostream>
#include <vector>
#define int long longusing namespace std;signed main() {int n , m ,q;cin >> n >> m >> q;//创建二维数组 匿名对象构造vector<vector<int>> nums(n + 1 , vector<int>(m + 1));for(int i = 1 ; i <= n ; i++ )for(int j = 1 ; j <= m ; j++)cin>>nums[i][j];//进行前缀和计算vector<vector<int>> dp(n + 1 , vector<int>(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] - dp[i-1][j-1] + nums[i][j];int x1 , x2 , y1 ,y2;while(q--){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;
}

提交过啦!!!

Leetcode 724. 寻找数组的中心下标

跟上节奏:724. 寻找数组的中心下标

题目描述

在这里插入图片描述
这道题可谓是一维前缀和的变形了,我们来秒杀这个题目

算法思路

我们先进行一下前缀和的预处理,然后根据条件判断即可:

class Solution {
public:int pivotIndex(vector<int>& nums) {//预处理vector<int> dp(nums.size() + 1);for(int i = 1 ; i <= nums.size() ;i++){dp[i] = dp[i - 1] + nums[i - 1];}int ans = -1;//根据题目要求求得即可for(int i = 0 ; i < nums.size() ;i++){if(dp[i] == dp[nums.size()] - dp [i + 1] ){ans = i ;break;}}return ans;}
};

提交过啦!!!

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

最后一道:238. 除自身以外数组的乘积

题目描述

在这里插入图片描述
注意到题目要求,我们看来是要使用前缀和来解决问题了。

算法思路

这道题的难点在于不能不能使用除法,而且还要进行O(n)的算法
那么如何进行呢???

  1. 很简单,我们在创建一个前缀乘积数组与一个后缀乘积数组,分开进行预处理即可。
  2. 然后按照对应位置,通过n - 1 的前缀乘积与 n + 1 的后缀乘积相乘 得到 除自身以外数组的乘积,就可以了。
class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int n = nums.size();vector<int> dpfront(n + 1);vector<int> dpback(n + 1);//细节处理,不能为0哦!!!dpfront[0] = 1;dpback[n]  = 1;//预处理for(int i = 1 ; i <= n ; i++){   //一次处理两个数组,提高效率dpfront[i] = dpfront[i - 1] * nums[i - 1];dpback[n - i] = dpback[n - i + 1] * nums[n - i];}//得到答案for(int i = 0 ; i < n ; i++){nums[i] = dpfront[i] * dpback[i + 1];}return nums;}
};

提交:过啦!!!

Thanks♪(・ω・)ノ谢谢阅读!!!

下一篇文章见!!!

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

信息系统项目管理师0064:软件实现(5信息系统工程—5.1软件工程—5.1.4软件实现)

点击查看专栏目录 文章目录 5.1.4软件实现1.软件配置管理2.软件编码3.软件测试记忆要点总结5.1.4软件实现 1.软件配置管理 软件配置管理通过标识产品的组成元素、管理和控制变更、验证、记录和报告配置信息,来控制产品的演进和完整性。软件配置管理与软件质量保证活动密切相关…

关于Domain的查询命令

dig: 用来执行DNS查询&#xff0c;可以获取指定域名的所有类型的DNS记录。对网络管理员和开发人员尤其有用。 host: 一个简化版的DNS查询工具&#xff0c;适合快速查询域名的IP地址或某种类型的DNS记录。 nslookup: 另一个DNS查询工具&#xff0c;既支持交互模式也支持命令行模…

简单谈谈URL过滤在网络安全中的作用

用户花在网络上的时间越来越多&#xff0c;浏览他们最喜欢的网站&#xff0c;点击电子邮件链接&#xff0c;或利用各种基于网络的 SaaS 应用程序供个人和企业使用。虽然这种不受约束的网络活动对提高企业生产力非常有用&#xff0c;但也会使组织面临一系列安全和业务风险&#…

线性代数 --- 矩阵的对角化以及矩阵的n次幂

矩阵的对角化以及矩阵的n次幂 &#xff08;特征向量与特征值的应用&#xff09; 前言&#xff1a; 在上一篇文章中&#xff0c;我记录了学习矩阵的特征向量和特征值的学习笔记&#xff0c;所关注的是那些矩阵A作用于向量x后&#xff0c;方向不发生改变的x(仅有尺度的缩放)。线…

面试ssss

响应式布局 响应式布局是一种设计和开发网页的方法&#xff0c;使网页能够适应不同的设备和屏幕尺寸&#xff0c;提供更好的用户体验。它通过使用媒体查询&#xff08;Media Queries&#xff09;和弹性布局&#xff08;Flexbox&#xff09;等技术&#xff0c;根据设备的特性和…

SSH Key生成

天行健&#xff0c;君子以自强不息&#xff1b;地势坤&#xff0c;君子以厚德载物。 每个人都有惰性&#xff0c;但不断学习是好好生活的根本&#xff0c;共勉&#xff01; 文章均为学习整理笔记&#xff0c;分享记录为主&#xff0c;如有错误请指正&#xff0c;共同学习进步。…

代码随想录算法训练营DAY32|C++贪心算法Part.2|122.买卖股票的最佳时机II、55.跳跃游戏、45.跳跃游戏II

文章目录 122.买卖股票的最佳时机II思路CPP代码 55.跳跃游戏思路CPP代码 45.跳跃游戏II思路方法一代码改善 CPP代码 122.买卖股票的最佳时机II 力扣题目链接 文章讲解&#xff1a;122.买卖股票的最佳时机II 视频讲解&#xff1a; 状态&#xff1a;本题可以用动态规划&#xff0…

构建NodeJS库--前端项目的打包发布

1. 前言 学习如何打包发布前端项目&#xff0c;需要学习以下相关知识&#xff1a; package.json 如何初始化配置&#xff0c;以及学习npm配置项&#xff1b; 模块类型type配置&#xff0c; 这是nodejs的package.json的配置main 入口文件的配置 webpack 是一个用于现代 JavaSc…

Linux加强篇-存储结构与管理硬盘(一)

目录 ⛳️推荐 从“/”开始 物理设备命名规则 文件系统与数据资料 ⛳️推荐 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。点击跳转到网站 从“/”开始 Linux系统中一切都是文件&#xff0c;都是从“…

深度解析:云计算的三宝——IaaS、PaaS和SaaS

4月22日&#xff0c;腾讯宣布旗下协作SaaS产品全面接入腾讯混元大模型&#xff0c;除去企业微信、腾讯会议、腾讯文档等“一门三杰”产品&#xff0c;腾讯乐享、腾讯电子签、腾讯问卷、腾讯云AI代码助手等协作SaaS产品也都已实现智能化升级。大模型应用落地再加速。 那么什么是…

HarmonyOS开发案例:【相机开发】

基本概念 相机是OpenHarmony多媒体进程提供的服务之一&#xff0c;提供了相机的录像、预览、拍照功能&#xff0c;支持多用户并发取流。 在进行应用的开发前&#xff0c;开发者应了解以下基本概念&#xff1a; 视频帧 视频流指的是将一系列图片数据按照固定时间间隔排列形成的…

牛客社区所有的表和SQL语句

文章目录 1 帖子表 discuss_post1.1 字段描述1.2 相关功能描述1.2.1 分页查询帖子1.2.2 查询帖子总数量1.2.3 插入一条帖子记录1.2.4 根据帖子ID查询某条帖子1.2.5 更新帖子评论数量1.2.6 更新帖子类型1.2.6 更新帖子状态1.2.7 更新帖子分数 2 用户表 user2.1 字段描述2.2 相关…

【七】jmeter5.5+influxdb2.0+prometheus+grafana

参考文章&#xff1a;https://blog.csdn.net/wenxingchen/article/details/126892890 https://blog.csdn.net/Zuo19960127/article/details/119726652 https://blog.csdn.net/shnu_cdk/article/details/132182858 promethus参考 由于自己下载的是infuldb2.0&#xff0c;所以按照…

云Docker部署Guacamole经frp中转远程连接Windows

安装frps sudo nohup ./frps -c frps.ini >/dev/null 2>&1 & frps.ini [common] bind_port 7000# Virtual host configuration vhost_http_port 80 vhost_https_port 443# Dashboard configuration dashboard_addr 0.0.0.0 dashboard_port 7500 dashboar…

自然语言处理 (NLP) 的技术演变史

一、简述 本文的目标是了解自然语言处理 (NLP) 的历史&#xff0c;包括 Transformer 体系结构如何彻底改变该领域并帮助我们创建大型语言模型 (LLM)。 基础模型&#xff08;如 GPT-4&#xff09;是最先进的自然语言处理模型&#xff0c;旨在理解、生成人类语言并与之交互。 要理…

FebHost:科技企业如何规划并注册.AI域名?

为确保企业使用.AI域名的方式准确反映其对人工智能技术的关注&#xff0c;企业应考虑以下步骤&#xff1a; 了解法律和合规要求&#xff1a; 第一步是了解与 .AI 域名相关的独特法律和合规要求。由于.AI域名源于安圭拉&#xff0c;企业必须遵守安圭拉的限制和法律规定。这包括…

(Oracle)SQL优化案例:组合索引优化

项目场景 项目上的ETL模型里有如下SQL语句。执行速度非常慢&#xff0c;每次只查询200条数据&#xff0c;但却需要20多秒的时间。再加上该SQL查询出的数据同步频率很高&#xff0c;这个速度是完全不能忍受的。 因为项目隐私&#xff0c;所以对表及字段做了改写。 SELECT ID…

服务器(AIX、Linux、UNIX)性能监视器工具【nmon】使用介绍

目录 ■nmon简介 1.安装 2.使用简介 3.使用&#xff08;具体使用的例子【CPU】【内存】&#xff09; 4.采集数据 5.查看log&#xff08;根据结果&#xff0c;生成报表&#xff09; 6.分析结果 ■nmon简介 nmon&#xff08;"Nigels performance Monitor"&…

Laravel 6 - 第十一章 中间件

​ 文章目录 Laravel 6 - 第一章 简介 Laravel 6 - 第二章 项目搭建 Laravel 6 - 第三章 文件夹结构 Laravel 6 - 第四章 生命周期 Laravel 6 - 第五章 控制反转和依赖注入 Laravel 6 - 第六章 服务容器 Laravel 6 - 第七章 服务提供者 Laravel 6 - 第八章 门面 Laravel 6 - …

[论文笔记] EcomGPT:COT扩充数据的电商大模型

社区供稿 | EcomGPT:基于任务链数据的电商大模型(附魔搭推理实践) - 知乎 https://arxiv.org/pdf/2312.15696.pdf EcomInstruct指令数据集构建 数据集组成 COT方式构造垂域训练数据:把原本的垂域任务分解成了原子任务,构造了基于解决原子任务的数据。这样能用类似…