当前位置：首页 > article >正文

蓝桥杯基本算法~~~一维/二维前缀和问题

article 2024/10/30 5:41:20

文章目录

1.一维前缀和
2.二维前缀和
3.移动零问题
4.颜色的分类问题

1.一维前缀和

问题说明：一维就是表示的是一维数组的计算，我们的这个一维前缀和是基于这个一维数组进行计算的；

什么是前缀和：就是10 20 30 40 50这个数组，13前缀和就是1~3之间的元素，这个下标是从1开始的，这个结果就是60；

如果我们的这个计算的是3~5之间的数据之和，这个就是前面的5个的和减去前面的2个的和，这个前缀和就是前面的几个数据之和；

如果不使用前缀和，我们每一次都是需要进行遍历的；

我们的这个前缀和数组就是dp表示的，dp[i]=dp[i-1]+arr[i]这个公式计算的；

我们计算这个left~right之间的数据求和的时候，[l,r]就是这个区间，我们基于这个已经计算出来的数组，使用这个dp[r]-dp[l-1]就是我们想要得到的结果；

下面的这个实现的代码：

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        //1.进行数据的读入
        int n=in.nextInt();
        int q=in.nextInt();
        int[] arr=new int[n+1];
        for(int i=1;i<=n;i++){
          arr[i]=in.nextInt();
        }
        //2.计算前缀和数组
        long[] dp=new long[n+1];
        for(int i=1;i<=n;i++){
          dp[i]=dp[i-1]+arr[i];
        }
        //3.使用前缀和数组进行计算
        while(q>0){
          int l=in.nextInt();
          int r=in.nextInt();
          System.out.println(dp[r]-dp[l-1]);
          q--;
        }
    }
}

疑问：为什么这个下标需要从1开始计数；

如果我们从是从0开始计数，这个时候的边界情况是无法进行处理的，因为我们使用前缀和对于这个连续区间的和进行计算的时候，这个是需要使用的是我们的这个dp[r]-dp[l-1]，但是如果我们的这个下标是从1开始的，如果用到这个第一个元素，这个时候的写法就是dp[0]，虽然我们的这个里面没有第0个元素，但是我们把这个dp[0]=0即可，但是如果我们的这个下标是从0开始的，这个时候的这个dp[-1]就会超出我们的这个范畴，因此使用这个1作为开始下标处理这个一维前缀和和二位前缀和问题也是为了更好的处理边界情况；

2.二维前缀和

如果上面的这个图示有些不懂，可以看下面的这个，下面的这个图形对于网格画了出来，而且可以更加清晰的看到关键的点对应的坐标，结合下面的这个图可以更好地理解我们上面的公式；

下面的这个就是我们的二位前缀和的代码：

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        //0.n表示的是我们的这个矩阵的行数，m表示的是我们的这个矩阵的列数，q表示的是我们的计算的组数
        int n=in.nextInt();
        int m=in.nextInt();
        int q=in.nextInt();
        //1.读入数据，就是我们的h行m列的数组；
        int[][] arr=new int[n+1][m+1];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                arr[i][j]=in.nextInt();
            }
        }
		//2.下面的这个就是进行的我们的这个前缀和数组的计算；
        long[][] dp=new long[n+1][m+1];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                dp[i][j]=dp[i-1][j]+dp[i][j-1]+arr[i][j]-dp[i-1][j-1];
            }
        }
		//3.根据我们计算的前缀和数组得到这个指定区间的数值；
        while(q>0){
            int x1=in.nextInt();
            int y1=in.nextInt();
            int x2=in.nextInt();
            int y2=in.nextInt();
            System.out.println(dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1]);
            q--;
        }
        in.close();
    }
}

其实上面的1,2两个是可以进行合并的，因为他们的这个循环的判断条件之类的就是一样的，因此我们可以把这个循环体进行合并，这个也是没有问题的；

3.移动零问题

这个题目，之前使用C++写过一次，但是觉得这个C++写出来这个代码确实还是比较复杂的，但是这个Java的写完之后，我觉得这个比之前的那个版本更加容易理解；

刚开始的时候我们的这个fast,slow都是执行第一个元素的，然后这个时候我们的fast开始向右边进行遍历，当遇到不是0的元素的时候，把我们的这个slow指向的这个元素替换成为这个元素，然后这个slow++,fast++,追后我们的这个slow指向的元素开始的所有的元素应该都是0了，因为我们所有的不是0的元素都是已经被替换掉得了；