网站模板下载网站有哪些内容,wordpress 交流群,前端转行可以找啥工作,app制作免费官网目录
一、数组理论基础
二、前缀和
三、相关算法题目
四、总结
五、待解决问题 一、数组理论基础
数组是存放在连续内存空间上的相同类型数据的集合。
代码随想录 (programmercarl.com)
特点#xff1a;
1.下标从0开始#xff0c;内存中地址空间是连续的
2.查询快
1.下标从0开始内存中地址空间是连续的
2.查询快增删慢
3.二维数组中行为第一索引列为第二索引
4.一旦创建以后长度不能发生变化
5.元素无法删除只能被覆盖
二、前缀和
前缀和在涉及计算数组区间和问题上是常用技巧其主要思想是计算出从下标0到下标 i0 i 数组长度的数值之和p[i]存放在另一数组p中当需要计算某个区间和时即可利用数组p得出结果只需一个O1的操作无需多次遍历元素数组从而降低算法时间复杂度。
本题可以利用前缀和的思想其中需要注意求解区间。例如某一数组 array [1,2,3,4,5,6]对应p数组为 [1,3,6,10,15,21]p[0] array[0]p[1] array[0] array[1]...以此类推现在要计算数组array下标2到下标5的数值之和即3,4,5,6的和:18那么由p数组可知应为p[5] - p[1] 21-318而不是p[5] - p[2]因为p[2]是包含了下标2的p[2]p[0] p[1] p[2]具体可参考下图
图源代码随想录
三、相关算法题目
58.区间和
58. 区间和第九期模拟笔试 (kamacoder.com)
两种方法直接求和法和前缀和法
直接求和时间复杂度比较高不推荐暂不赘述。
前缀法
import java.util.Scanner;
public class Main{public static void main(String[] args){Scanner in new Scanner(System.in);int n in.nextInt();int[] Array new int[n];int[] p new int[n];int sum1 0;in.nextLine();int i 0;while(in.hasNextInt() i n){Array[i] in.nextInt();sum1 Array[i];p[i] sum1;in.nextLine();i; //否则while成死循环 ⭐️}while(in.hasNextInt()){int a in.nextInt();//in.nextLine();int b in.nextInt();int sum2;if(a 0){sum2 p[b];}else{sum2 p[b] - p[a-1];}System.out.println(sum2);}in.close();}
}四、总结
1.最后记得关掉输入流in.close();
2.第一个while循环中循环体中记得加条件控制语句i否则while成死循环或者可以换成for循环
3.可以通过按CtrlD来手动结束输入流这样程序会停止读取输入并退出;
4.本题用了ACM输入输出模式具体可见面试 | Java 算法的 ACM 模式_java acm模式-CSDN博客
五、待解决问题
in.nextLine();这行语句有什么作用为什么加不加都不影响程序的运行和in.nextInt();
