(数组)前缀和、前缀积及其应用
2023-09-14 09:00:36 时间
什么是前缀和、前缀积?
前缀和、前缀积也称前缀和数组,前缀积数组。
给一数组A,
前缀和:新建一数组B,数组中每一项B[i]保存A中[0…i]的和;
后缀和:新建一数组B,数组中每一项B[i]保存A中[i…n-1]的和;
前缀积:新建一数组B,数组中每一项B[i]保存A中[0…i]的积;
后缀积:新建一数组B,数组中每一项B[i]保存A中[i…n-1]的积;
前缀和、前缀积的应用(例子):
1、题目1:
给定浮点数组a,求一数组b,b[i]=a[0]*a[1]*…*a[i-1]*a[i+1]*…*a[n-1],不能使用除法,不允许新开数组。
思路:
先求“后缀积”:
for(int i=n-1;i>=0;i—) b[i]=a[i]*((i==n-1)?1:b[i+1]);
顺带求“前缀积”:
for(int i=0,j=1;i<n;j*=a[i++]) b[i]=j*((i==n-1)?1:b[i+1]);
2、题目2:
求数组中连续一段和,绝对值最小?
思路:
前缀和的性质:a[i]+a[i+1]+…+a[j]=sum[j]-sum[i-1]
前缀和排序,取最小
3、题目3:
把一个数组从中间p位置分开,使得a[0]+…+a[p-1]与a[p]+a[p+1]+…+a[n-1]差值最小?
思路:
- 前缀和-(总和-前缀和)=2*前缀和-总和,是该公式最小;
- 如果都是非负数,可以采取“两头扫”的方法,和较小的那边多加一个数;
相关文章
- 英特尔AIoT应用样机申请计划
- 【分享】在集简云上架应用如何配置一个触发动作?
- Leetcode 差分数组的应用「建议收藏」
- 基于发票增值税OCR API设计自动识别应用系统,从此解放财务双手
- 的应用MySQL中的数组应用方式及其优势(mysql中数组)
- MySQL中Int类型的应用和优势(mysqlint类型)
- MySQL客户端库:驱动程序开发及应用(mysql客户端库)
- 秦苍科技数据科学家沈赟:AI在消费金融产品优化以及风险控制中的应用(附PPT+视频) | 雷锋网公开课
- PLC在Linux系统中的应用(plclinux)
- Java应用在Linux上乱码的原因及解决方法(java linux乱码)
- C语言MySQL库数据库应用的强大工具(c mysql类库)
- 秒杀用Redis提升应用性能(秒插redis)
- 如何应用Redis存储数组(如何将数组存到redis)
- umOracle数据库中ROWNUM的应用(oracle rown)
- Pythonenumerate遍历数组示例应用
- JavaScript数组应用可依次读取的公告栏文字
- PHP获取数组中某元素的位置及array_keys函数应用