当涂网站建设,学做窗帘要下载哪个网站,中职高一网站建设试题,昆明营销型网站建设一、一维前缀和
① 什么是一维前缀和#xff1f;
#x1f4da; 其实通过名字就能知道 一维前缀和 的意思#xff1a;
通过一个一维数组arr1而创建的另一个一维数组arr2#xff0c;arr2的每一个元素都是arr1 其实通过名字就能知道 一维前缀和 的意思
通过一个一维数组arr1而创建的另一个一维数组arr2arr2的每一个元素都是arr1的对应下标元素再加上该下标之前所有元素的和。 简单的讲可以理解为每个位置的值是数组中该位置前的值的和。
让我们通过这个图片来看一下 而一维前缀和一般都应用在什么地方呢让我们看一道例题 给定一个长度为n的序列a再给定q组查询对于每次查询
给定一对lr你需要输出a数组中的l下标~r下标之间的和
让我们看一下没有学过一维差分的暴力解题思想解题
import java.util.*;public class Test {public static void main(String[] args) {Scanner scan new Scanner(System.in);int n scan.nextInt();int q scan.nextInt();int[] arr new int[n 10];for(int i 1;i n;i) {arr[i] scan.nextInt();}while(q-- 0) {int l scan.nextInt();int r scan.nextInt();int num 0;for(int i l; i r;i) {num arr[i];}System.out.println(num);}}
} 那让我们来分析一下这样解题的时间复杂度 数组的长度为n进行q次查询若考虑最坏的情况每次查询遍历整个数组那么时间复杂度最坏的情况是O(nq)。
而该题中n和q最大为1e5那么O(nq)便能够达到可怕的(1e10)而我们要知道正常情况下我们的编译器运算速度一秒也就是2e8而1e10则是远远的超过了2e8 果不其然这是一定会超时的。
② 一维前缀和的使用
那么如果我们使用一维前缀和来进行解题就能够大大的提高代码性能
(为了使数组下标对应 l 和 r 我们通常会从数组的1下标开始赋值) 由图我们可以看出在查询内部我们之前的时间复杂度为O(r-l)而使用一维前缀数组后将时间复杂度提升到了O(1)!!!这是非常大的提升~
用公式表示大概就是l ~ r 的区间和等于一维前缀和数组 arr2[r] - arr2[l - 1] 一维前缀和解题代码
import java.util.*;public class Test {public static void main(String[] args) {Scanner scan new Scanner(System.in);int n scan.nextInt();int q scan.nextInt();int[] arr1 new int[n 10];int[] arr2 new int[n 10];for(int i 1;i n;i) {//原数组arr1[i] scan.nextInt();//一维前缀和数组arr2[i] arr1[i] arr2[i - 1];}while(q-- 0) {int l scan.nextInt();int r scan.nextInt();System.out.println(arr2[r] - arr2[l - 1]);}}
} 经过改良后也成功通过啦~
小练习区间次方和(⭐)
问题描述 给定一个长度为 n 的整数数组 a 以及 m 个查询。 每个查询包含三个整数 l,r,k 表示询问 l∼r 之间所有元素的 k 次方和。 请对每个查询输出一个答案答案对 1e97 取模。 输入格式 第一行输入两个整数 n,m 其含义如上所述。 第二行输入 n 个整数 a[1],a[2],...,a[n]。 接下来 m 行每行输入三个整数 l,r,k 表示一个查询。 输出格式 输出 m 行每行一个整数表示查询的答案对1e97取模的结果 思路提示
首先看到对数组区间进行操作我们就应该下意识地想到去使用前缀和/差分的方法来解题~
而每次操作求对 l ~ r 之间所有元素的 k 次方求和就很自然的应该去想到使用前缀和方法~ 对元素的次方k只有1~5数据并不庞大也就意味着我们通过将1~5次方的数据全部求出来放进一个前缀和数组中然后通过输入的k来获取k次方l~r代表访问的下标~ 代码实现
import java.util.*;public class Main {public static void main(String[] args) {Scanner scan new Scanner(System.in);int n scan.nextInt();int m scan.nextInt();//储存原数组long[] a new long[n 10];//储存1~5次方前缀和数组long[][] s new long[10][n 10];//i代表第i个元素for (int i 1; i n; i) {a[i] scan.nextInt();//j代表j次方for(int j 1; j 5; j) {//(1 ~ 5次方和)s[j][i] (long)Math.pow(a[i],j) s[j][i - 1];}}while(m-- 0) {int l scan.nextInt();int r scan.nextInt();int k scan.nextInt();long num s[k][r] - s[k][l - 1];System.out.println(num % 1000000007);}}
} 没什么问题也是成功通过啦~
(该题是一道基础题但需要注意一点别忘了最后答案要对 1e97 取模哦~) 一维前缀和的作用 一维前缀和的应用非常广泛特别是在处理数组区间和的问题时非常有用 通过计算数组的前缀和我们可以在O(1)的时间复杂度内获得任意区间的和
二、一维差分
① 什么是一维差分 一维差分的定义
一维差分是指对一个一维数组进行变换使得原数组中连续元素之间的差值保存在另一个数组中这个数组称为差分数组。
用图表示 那么一维差分的作用又是什么呢同样的让我们看一个小例题
问题描述
给定一个长度为n的序列a再给定m组操作
每次操作给定3个正整数lrd表示对a(l~r)中的所有数增加d
最终输出操作结束后的序列 a
同样的让我们看一下暴力解法 暴力解法的思路大概就是
进行m组操作每次操作都使用for循环对(l~r)的区间进行遍历并且依次将区间内的元素d。 代码实现
import java.util.*;public class Test {public static void main(String[] args) {Scanner scan new Scanner(System.in);int n scan.nextInt();int m scan.nextInt();int[] a new int[n 10];for(int i 1;i n;i) {a[i] scan.nextInt();}while(m-- 0) {int l scan.nextInt();int r scan.nextInt();int d scan.nextInt();for(int i l;i r;i) {a[i] d;}}for(int i 1;i n;i) {System.out.print(a[i] );}}
} 同样的和一维前缀和的例题一样使用暴力解法会导致超时。
那么让我们来一起分析一下暴力解法的时间复杂度 进行了m组操作每次操作都对l~r的区间进行操作我们假设最坏的情况每次操作都遍历整个数组也就是说时间复杂度等于O(mn)最大的时候也是能够到达1e10仍然远远大于编译器一秒钟的运算(2e8)
② 一维差分的使用 那么我们该如何改进呢
让我们来看一下一维差分的实现
定义差分数组的公式arr2[i] arr1[i] - arr1[i - 1];
这个应该还是很好理解的只需要前一项减去后一项就是两者之差~
而求差分数组是为了对差分数组的首尾进行修改然后再还原数组从而达到将m次操作中的时间复杂度O(n)减小成O(1)~
具体我们还是看图 由此我们将之前的从l~r位置进行遍历改变成了首尾进行操作使O(nm)的时间复杂度减少成了O(m)。 代码实现
import java.util.*;
//1:无需package
//2: 类名必须Main, 不可修改public class Test {public static void main(String[] args) {Scanner scan new Scanner(System.in);int i 0;int a scan.nextInt();int b scan.nextInt();int[] arr1 new int[a 3];int[] arr2 new int[a 3];int[] arr3 new int[a 3];for(i 1;i a;i){arr1[i] scan.nextInt();arr2[i] arr1[i] - arr1[i - 1];}for(i 0;i b;i){int n1 scan.nextInt();int n2 scan.nextInt();int n scan.nextInt();arr2[n1] arr2[n1] n;arr2[n2 1] arr2[n2 1] - n;}for(i 1;i a;i){arr2[i] arr2[i] arr2[i - 1];//c1 a1 c0(0)//c2 a2 c1(a1)//c3 a3 c2(a1 a2)}for(i 1;i a;i){System.out.print(arr2[i] );}}
} 也是成功通过了所有测试用例~并无超时现象~
小练习小蓝的操作(⭐⭐)
问题描述 一个数组 a 中共包含 n 个数问最少多少次操作可以让 a 数组所有数都变成 1 。 操作的内容是 每次操作可以任选一个区间使得区间内的所有数字减 1 。 数据保证一定有解。 思路分析
同样的看到对数组区间进行操作下意识想到使用(前缀和/差分)进行求解而此题问需要多少次操作使得a[]数组中所有数变成1显然是对数组内容进行了操作于是便选择使用差分。
想要使得所有的数都变成1那么最后我们得到的差分数组一定就是 这样的一个数组其原理是
第一个数字为1而后面的元素每一位都与前一位相等也就是相当于全为1。 我们来用他的样例输入进行一下讲解 代码实现
import java.util.*;public class Main {public static void main(String[] args) {Scanner scan new Scanner(System.in);int a scan.nextInt();int num 0;int[] arr1 new int[a 5];int[] arr2 new int[a 5];for (int i 1; i a; i) {arr1[i] scan.nextInt();arr2[i] arr1[i] - arr1[i - 1];}for(int i 1;i a;i) {if(arr2[i] 0) {num arr2[i];}}System.out.println(num - 1);}那么这次关于一维前缀和与差分就为大家分享到这里啦~有什么讲解不清楚或者需要修正的地方还请大家多多在评论区指出我这个小白也会虚心改正的~那我们下次再见啦
