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

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

文章目录

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

1.一维前缀和

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

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

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

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

image-20241029090359847

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

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

image-20241028211405840

下面的这个实现的代码:

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.二维前缀和

image-20241029081309678

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

image-20241028215935682

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

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.移动零问题

image-20241019154955303

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

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

image-20241019155022493

4.颜色的分类问题

Leetcode75题:颜色的分类;

image-20241029085145085

这个 题目主要是要设置两个标志位

image-20241029084557560

当我们的这个cur指向的元素是0的时候,就和left指向的元素进行交换,指向1的时候,不动,指向2的时候,就和我们的right指向的元素进行交换;

其中这个cur是0的时候,我们交换完成之后,这个index和我们的这个left都是需要++的,因为我们的这个时候的left左边的这个元素其实都是0,因此这个时候我们的left是可以移动的;

但是指向1的时候,这个时候的1本来就是应该放到中间的,因此这个时候的index++即可;

指向2的时候,和右边的这个进行交换,这个时候因为交换过来的这个数值的不确定性,因此只让这个right–即可,这个时候的right指向位置右边一定都是2,因此这个right是可以进行–操作的;

应该放到中间的,因此这个时候的index++即可;

指向2的时候,和右边的这个进行交换,这个时候因为交换过来的这个数值的不确定性,因此只让这个right–即可,这个时候的right指向位置右边一定都是2,因此这个right是可以进行–操作的;

image-20241029085107263


http://www.kler.cn/a/371146.html

相关文章:

  • 宠物空气净化器哪个牌子好?有没有噪音低的宠物空气净化器推荐?
  • 【架构-36】常见的各类锁的特点
  • 17 Docker容器存储架构:docker存储持久化-bind mount
  • 软件测试学习笔记丨Selenium学习笔记:css定位
  • App Inventor 2 列表显示框能否实现多选?
  • 如何将原本打开Edge呈现出的360浏览器,更换成原本的Edge页面或者百度等其他页面
  • 【ComfyUI】手动安装部署ComfyUI的运行环境
  • QML旋转选择器组件Tumbler
  • 第十一章 Shiro会话管理和加密
  • 《Web性能权威指南》-WebRTC-读书笔记
  • 【GL08】STM32--ADC/DAC
  • spring-boot(入门)
  • 深入探索:深度学习在时间序列预测中的强大应用与实现
  • 编程解决有趣的智力题
  • 17、电话号码的字母组合-cangjie
  • 中阳智能投资系统:量化科技引领未来投资之路
  • gbase8s之spring框架用druid中间件报语法错误
  • Linux安装es和kibana
  • git下载和配置
  • 探索Python与Excel的无缝对接:xlwings库的神秘面纱
  • GPT-Sovits-2-微调模型
  • 内网穿透之网络层ICMP隧道
  • CSS 修改图片颜色
  • 2024年10月HarmonyOS应用开发者基础认证全新题库
  • Objective-C 音频爬虫:实时接收数据的 didReceiveData_ 方法
  • 利用 Direct3D 绘制几何体—9.流水线状态对象