前缀和代码解析
前缀和是指数组一定范围的数的总和,常见的有两种,一维和二维,我会用两道题来分别解析
一维
DP34 【模板】前缀和
题目:

题目解析:

暴力解法
直接遍历数组,遍历到下标为 l 时,开始进行相加,直到遍历到下标为 r ,最后返回总和.这样做的时间复杂度为: O(n)
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别//接收数据int n = in.nextInt(),q=in.nextInt();int[] arr = new int[n+1];arr[0]=0;for(int i=1;i<=n;i++){arr[i]=in.nextInt();}while(q>0){int l=in.nextInt(),r=in.nextInt();int sum = 0;for(int i =l;i<=r;i++){sum+=arr[i];}System.out.println(sum);q--;}}
}
虽然代码本身是没有问题的,但是在某些情况下会运行超时

优化
对于前缀和来说,我们可以使用动态规划的部分知识来进行解决,总共分为两步
1.预处理前缀和数组
我们创建一个新的数组,数组的规模和原数组保持一致,如图:

但是在我们求dp数组时,难免会对原数组重复计算,这样会增加代码的耗时,有没有简洁的方法呢?
当然是有的,从dp的获得式中我们可以发现, dp[i] = dp[i-1]+arr[i]
2.使用数组
最后我们就可以返回值, 也就是上文提到的 dp[r]-dp[l-1]
代码
public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别//接收数据int n = in.nextInt(),q=in.nextInt();int[] arr = new int[n+1];arr[0] = 0;for(int i=1;i<arr.length;i++){arr[i] = in.nextInt();}//计算动态数组long[] dp = new long[n+1];dp[0] = 0;for(int i=1;i<dp.length;i++){dp[i]=dp[i-1]+arr[i];}//处理结果while(q>0){int l=in.nextInt(),r=in.nextInt();System.out.println(dp[r]-dp[l-1]);q--;}
}
在代码中我们可以看到,我们为数组增加了辅助节点,也就是 arr[0] 和 dp[0] ,那么为什么要增加这个辅助节点呢?或者为什么在使用数组的时候,下标要从1开始计算呢?
因为如果我们没有辅助节点或者从0开始计算,那么当 l (求前缀和的起点) 为 0 时,那么 dp[l-1] 就会越界
运行结果

二维
二维数组也就是矩阵,在计算矩阵的前缀和时,我们需要更注意一些细节
例题: DP35 【模板】二维前缀和

这道题大致与上一道题相似,所以就不进行暴力解法了,直接开始解析

也就是说,这里我们已经得到了用于动态规划的数组 dp ,我们只要再将dp中的值进行计算,就可以得到最后的值了

所以,最后要得出的答案就是 D = dp[x2][y2] -dp[x1-1][y1] -dp[x1][y1-1] +dp[x1-1][y1-1]
代码:
public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别//获取数据int n = in.nextInt(),m=in.nextInt(),q=in.nextInt();int[][] arr = new int[n+1][m+1];for(int i=1;i<n+1;i++){for(int j=1;j<m+1;j++){arr[i][j] = in.nextInt();}}//设置动态矩阵long[][] dp = new long[n+1][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]+arr[i][j]-dp[i-1][j-1];}}//得出答案while(q>0){int x1=in.nextInt(),y1=in.nextInt(),x2=in.nextInt(),y2=in.nextInt();System.out.println(dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1]);q--;}
}
运行结果:

相关文章:
前缀和代码解析
前缀和是指数组一定范围的数的总和,常见的有两种,一维和二维,我会用两道题来分别解析 一维 DP34 【模板】前缀和 题目: 题目解析: 暴力解法 直接遍历数组,遍历到下标为 l 时,开始进行相加,直到遍历到下标为 r ,最后返回总和.这样做的时间复杂度为: O(n) public class Main …...
Windows 环境下安装 Anaconda 并配置
安装Anaconda 1. 下载安装包 官网下载:https://www.anaconda.com/download/success 也可以从国内镜像仓库下载: 中国科学技术大学 https://mirrors.ustc.edu.cn/ 清华大学开源软件镜像站 https://mirrors.tuna.tsinghua.edu.cn/ 2. 安装过程 双…...
大模型在尿潴留风险预测及围手术期方案制定中的应用研究
目录 一、引言 1.1 研究背景与意义 1.2 研究目的 1.3 研究方法与数据来源 二、大模型预测尿潴留的原理与方法 2.1 相关大模型介绍 2.2 模型构建与训练 2.3 模型评估指标与验证 三、术前尿潴留风险预测及方案制定 3.1 术前风险因素分析 3.2 大模型预测结果分析 3.3 …...
JavaScript 简单类型与复杂类型
在JavaScript中,根据数据存储的方式不同,变量可以分为两大类:简单类型(也称为基本数据类型或原始类型)和复杂类型(也称为引用数据类型)。理解这两者的区别对于编写高效且无误的代码至关重要。本…...
AI绘画软件Stable Diffusion详解教程(1):Windows系统本地化部署操作方法(专业版)
一、事前准备 1、一台配置不错的电脑,英伟达显卡,20系列起步,建议显存6G起步,安装win10或以上版本,我的显卡是40系列,16G显存,所以跑大部分的模型都比较快; 2、科学上网࿰…...
大白话Vue 双向数据绑定的实现原理与数据劫持技术
咱们来好好唠唠Vue双向数据绑定的实现原理和数据劫持技术,我会用特别通俗的例子给你讲明白。 啥是双向数据绑定 你可以把双向数据绑定想象成一个神奇的“同步器”。在网页里有两部分,一部分是数据,就像你记在小本本上的信息;另一…...
VUE 获取视频时长,无需修改数据库,前提当前查看视频可以得到时长
第一字段处 <el-table-column label"视频时长" align"center"> <template slot-scope"scope"> <span>{{ formatDuration(scope.row.duration) }}</span> </template> </el-ta…...
antv G6绘制流程图
效果图(优点:可以自定义每一条折线的颜色,可以自定义节点的颜色,以及折线的计算样式等): 代码: <!-- 流程图组件 --> <template><div id"container"></div>…...
完美隐藏滚动条方案 (2024 最新验证)
完美隐藏滚动条方案 (2024 最新验证) css /* 全局隐藏竖直滚动条但保留滚动功能 */ html {overflow: -moz-scrollbars-none; /* Firefox 旧版 */scrollbar-width: none; /* Firefox 64 */-ms-overflow-style: none; /* IE/Edge */overflow-y: overlay; …...
单片机的串口(USART)
Tx - 数据的发送引脚,Rx - 数据的接受引脚。 串口的数据帧格式 空闲状态高电平,起始位低电平,数据位有8位校验位,9位校验位,停止位是高电平保持一位或者半位,又或者两位的状态。 8位无校验位传输一个字节…...
实现分布式限流开源项目
以下是10个可以实现分布式限流中间件的开源项目推荐,这些项目基于不同的技术栈,适用于多种应用场景: 1. **Alibaba Sentinel** Sentinel 是阿里巴巴开源的分布式限流中间件,支持多种限流策略(如QPS、并发线程数等…...
递归构建行政区域树(二)
概述 这篇博客中构建出的行政区域树利用element-ui的Tree组件展示出来。 实现 源码位于码云,欢迎点击哦。 项目结构 最后 好久没写基于element-ui的项目了,都有点生疏了。 好了,如果对你有帮助,欢迎点个免费的赞哦。...
AR技术下的电商:虚拟试穿/试用/试戴成新风尚
随着科技的日新月异,增强现实(AR)技术正悄然改变着我们的生活,尤其在电子商务领域,AR技术的融入正掀起一场前所未有的变革。那么,AR技术究竟是何方神圣?它在电商领域又展现出了哪些非凡的应用呢…...
社群团购平台的愿景构建与开源链动2+1模式S2B2C商城小程序应用探索
摘要:在数字经济背景下,社群团购作为一种新兴的商业模式,凭借其独特的互动性和便捷性,展现出巨大的市场潜力。本文旨在探讨社群团购平台愿景的构建策略,并结合开源链动21模式S2B2C商城小程序的应用,为创业者…...
笔记20250225
关于上拉电阻和下拉电阻的作用 原理 上拉电阻:在上拉电阻所连接的导线上,如果外部组件未启用,上拉电阻则“微弱地”将输入电压信号“拉高”。当外部组件未连接时,对输入端来说,外部“看上去”就是高阻抗的,…...
【项目】基于Boost自主实现搜索引擎
🔥 个人主页:大耳朵土土垚 🔥 所属专栏:Linux系统编程 这里将会不定期更新有关Linux的内容,欢迎大家点赞,收藏,评论🥳🥳🎉🎉🎉 文章目…...
使用 Open3D 批量渲染并导出固定视角点云截图
一、前言 在三维点云处理与可视化中,固定视角批量生成点云渲染截图是一个常见的需求。例如,想要将同一系列的点云(PCD 文件)在同样的视角下生成序列图片,以便后续合成为视频或进行其他可视化演示。本文将介绍如何使用…...
汽车无钥匙进入一键启动操作正确步骤
汽车智能无钥匙进入和一键启动的技术在近年来比较成熟,不同车型的操作步骤可能略有不同,但基本的流程应该是通用的,不会因为时间变化而有大的改变。 移动管家汽车一键启动无钥匙进入系统通常是通过携带钥匙靠近车辆,然后触摸门把…...
JMeter 的基础知识-安装部分
以下将从环境配置开始,为你详细介绍 JMeter 的基础知识,涵盖环境搭建、界面认知、测试计划创建、常用组件使用等方面内容。 1. 环境配置 1.1 安装 Java JMeter 是基于 Java 开发的,所以需要先安装 Java 开发工具包(JDK)。 下载 JDK:访问 Oracle 官方网站(https://www…...
解决后端跨域问题
目录 一、什么是跨域问题? 1、跨域问题的定义 2、举例 3、为什么会有跨域问题的存在? 二、解决跨域问题 1、新建配置类 2、编写代码 三、结语 一、什么是跨域问题? 1、跨域问题的定义 跨域问题(Cross-Origin Resource Sh…...
wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...
19c补丁后oracle属主变化,导致不能识别磁盘组
补丁后服务器重启,数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后,存在与用户组权限相关的问题。具体表现为,Oracle 实例的运行用户(oracle)和集…...
零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?
一、核心优势:专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发,是一款收费低廉但功能全面的Windows NAS工具,主打“无学习成本部署” 。与其他NAS软件相比,其优势在于: 无需硬件改造:将任意W…...
内存分配函数malloc kmalloc vmalloc
内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...
在rocky linux 9.5上在线安装 docker
前面是指南,后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...
Opencv中的addweighted函数
一.addweighted函数作用 addweighted()是OpenCV库中用于图像处理的函数,主要功能是将两个输入图像(尺寸和类型相同)按照指定的权重进行加权叠加(图像融合),并添加一个标量值&#x…...
第25节 Node.js 断言测试
Node.js的assert模块主要用于编写程序的单元测试时使用,通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试,通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...
相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...
ArcGIS Pro制作水平横向图例+多级标注
今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作:ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等(ArcGIS出图图例8大技巧),那这次我们看看ArcGIS Pro如何更加快捷的操作。…...
有限自动机到正规文法转换器v1.0
1 项目简介 这是一个功能强大的有限自动机(Finite Automaton, FA)到正规文法(Regular Grammar)转换器,它配备了一个直观且完整的图形用户界面,使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...
