栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

3分钟学会前缀和

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

3分钟学会前缀和

前缀和,顾名思义是一种求出数组前n项的和的方法,本质为对数组进行预处理然后对问题求解:

主要分为1维前缀和和多维前缀和:

1.1维前缀和求解方法:

1.前缀和公式s[i] = s[i - 1] + a[i]

2.进行直接查找

例题:

链接:活动 - AcWing

答案:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

public class TheTotalOfFront {
    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);
        //将读取的数进行转化
        int n = scanner.nextInt(),m = scanner.nextInt();
        //记录前n项的前缀和
        int [] arr = new int[n + 1];
        int temp;//记录临时数字
        for(int i = 1; i <= n; i++){
            temp = scanner.nextInt();
            arr[i] = arr[i - 1] + temp;
        }
        while(m-- > 0){
            //临时变量记录区间范围
            int x = scanner.nextInt(),y = scanner.nextInt();
            System.out.println(arr[y] - arr[x - 1]);
        }
    }
}

2.二维前缀和求解:

1.找出前缀和公式

2.直接运算

例题:

链接:活动 - AcWing

题解如下:

import java.util.Arrays;
import java.util.Scanner;

public class TheSumOfJuZhen {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(),m = scanner.nextInt(),q = scanner.nextInt();
        //创建数组存储前n,m行的和
        long [][] arr = new long[n + 1][m + 1];
        //运算前n项和
        for(int i = 1; i <= n ; i++){
            for(int j = 1; j <= m ; j++){
                //求前缀和
                int temp = scanner.nextInt();
                arr[i][j] = arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1] + temp;
            }
        }
//        for (long[] a:arr) {
//            System.out.println(Arrays.toString(a));
//        }
        //循环求值
        while(q-- > 0){
            //边界赋值
            int a,b,c,d;
            a = scanner.nextInt();
            b = scanner.nextInt();
            c = scanner.nextInt();
            d = scanner.nextInt();
            //输出前缀和
            System.out.println(arr[c][d] - arr[c][b - 1] - arr[a - 1][d] + arr[a - 1][b - 1]);
        }
    }
}

前缀和知识点比较简单,算法思维也不难,就是推公式和注意细节

注:前面关于快速选择算法的代码错误,正确代码如下:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;

public class QuickChoose {
    static int n;
    static int k;
    public static void main(String[] args) throws IOException {
        final BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        final Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        k = scanner.nextInt();
        int [] arr = new int[n];
        //读入数据
//        final String s1 = new Scanner(System.in).nextLine();
//        String[] s = bufferedReader.readLine().split(" ");
        for (int i = 0 ; i < n; i++){
            arr[i] = scanner.nextInt();
        }
//        System.out.println(Arrays.toString(arr));
        System.out.println(quickChoose(0,n - 1,arr,k));
        bufferedReader.close();
    }

    //快速选择方法,该方法用于求出l到r区间范围内的第k个数
    public static int quickChoose(int l,int r,int [] arr,int k){
        //如果当前只有一个数存在
        if(l == r){
           return arr[l];
        }
        //否则进行排序和查找
        int i = l - 1,j = r + 1,pivot = arr[l];
        //修正本次必须返回j,j + 1
        //当前元素区间不止为一个数时
        while(i < j){
            while(arr[++i] < pivot);
            while(arr[--j] > pivot);
            //如果满足区间元素不为1
            if(i < j){
                int t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
            }
        }
        //如果在左半部分,直接排序左边求解
        int s1 = j - l + 1;
        if(s1 >= k){
            return quickChoose(l,i - 1,arr,k);
        }else{
            //否则排序右边数组
            k = k - s1;
            return quickChoose( i,r,arr,k);
        }
    }

}


 

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/940827.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号