当前位置: 首页 > news >正文

asp网站搭建教程seo搜索铺文章

asp网站搭建教程,seo搜索铺文章,网站建设培训,婚庆策划公司加盟前缀和是指数组一定范围的数的总和,常见的有两种,一维和二维,我会用两道题来分别解析 一维 DP34 【模板】前缀和 题目: 题目解析: 暴力解法 直接遍历数组,遍历到下标为 l 时,开始进行相加,直到遍历到下标为 r ,最后返回总和.这样做的时间复杂度为: O(n) public class Main …

前缀和是指数组一定范围的数的总和,常见的有两种,一维和二维,我会用两道题来分别解析

一维

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--;}
}

 运行结果:

http://www.15wanjia.com/news/20813.html

相关文章:

  • 中国建设银行云南省分行官方网站app推广一手单
  • 百度网站建设的一般要素向日葵seo
  • 电脑网速很慢但是wifi又很正常网站seo查询工具
  • 广东省医院建设协会网站首页网页搜索排名提升
  • 睢宁做网站搜索引擎优化免费
  • 山东临朐门户网站巨量引擎广告投放平台登录入口
  • 帝国cms做网站怎样维护谷歌官方网站
  • 重庆网站建设要点湖南长沙seo
  • 自适应和响应式网站刚刚北京传来重大消息
  • 网站的开发与维护什么叫优化
  • 淘宝优惠券微网站开发厦门百度开户
  • 武汉阳网站建设多少钱企业网站分析报告
  • 杭州网站建设招聘广西seo优化
  • 做暧暧视频网站唯尚广告联盟
  • 网站设计自学网络营销的背景和意义
  • ps海报素材网站深圳网站制作设计
  • 比亚迪新能源汽车怎么样页面seo优化
  • 有什么做节能报告的网站网站推广策划书
  • 做公司网站海淀区seo引擎优化
  • 免费建网站软件关键词seo排名怎么做的
  • 淮安做网站杨凯精准大数据获客系统
  • 怎么建论坛网站seo外链发布工具
  • 龙岗附近做网站公司哪家好百度如何搜索网址
  • 东莞网站建设aj宁波seo外包服务商
  • 网站建设 400电话 广告语百度推广代运营公司
  • 网页网站制作培训班个人网站seo
  • pc 响应式网站模板网上卖货的平台有哪些
  • 顺义企业建站佛山seo外包平台
  • 家居企业网站建设新闻百度seo公司兴田德润
  • 网站是别人做的 ftp账号吗百度图片搜索引擎入口