前缀和专题——一维模版+二维模版力扣实战应用

目录

1、模版

1.1【模版】一维前缀和

1.1.1 算法思想 

1.1.2 算法代码

1.2【模版】二维前缀和

1.2.1 算法思想

1.2.2 算法代码

2、算法应用【leetcode】

2.1 题一:寻找数组的中心下标

2.1.1 算法思想

2.1.2 算法代码

2.2 题二:除自身以外数组的乘积

2.2.1 算法思想

2.2.2 算法代码

2.3 题三:和为k的子数组

2.3.1 算法思想

2.3.2 算法代码

2.4 题四:和可被k整除的子数组 ★★★蓝桥杯竞赛原题

2.4.1 算法思想

2.4.2 算法代码

2.5 题五:连续数组

2.5.1 算法思想

2.5.2 算法代码

2.6 题六: 矩阵区域和

2.6.1 算法思想

2.6.2 算法代码


1、模版

1.1【模版】一维前缀和

一维前缀和模版,通过下方例题讲解。

【模板】前缀和_牛客题霸_牛客网

1.1.1 算法思想 

本题我们可以通过前缀和高效求解。

  1. 首先,预处理出一个前缀和数组,利用前缀和数组保存原数组数值之和。
  2. 接着,使用前缀和数组:dp[r] - dp[l-1] 得出arr[l~r]的和。

1.1.2 算法代码

import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int q = in.nextInt();long[] arr = new long[n+1];for (int i = 1; i < arr.length; i++) {arr[i] = in.nextInt();}//预处理一个前缀和数组long[] dp = new long[n+1];for (int i = 1; i < arr.length; i++) {dp[i] = dp[i-1] + arr[i];}//使用前缀和数组while (q != 0) {int l = in.nextInt(), r = in.nextInt();System.out.println(dp[r] - dp[l - 1]);q--;}}
}

1.2【模版】二维前缀和

二维前缀和模版,我们同样通过例题讲解。

【模板】二维前缀和_牛客题霸_牛客网

1.2.1 算法思想

  1. 首先,同样预处理出前缀和矩阵,但是二维矩阵中存的数值为原数组arr[0,0]~arr[i,j]整个区域之和。通过画图我们可以得出公式。
  2. 接着,使用前缀和矩阵,因为我们求的是arr[x1][y1]~arr[x2][y2]之和,我们依然可以通过画图清晰明了的得出公式。
  3. 矩阵的下标依然是从1开始,为避免数组越界及计算错误,我们仍将i==0或者j==0位置的值设为0

1.预处理得出前缀和矩阵:

2.使用前缀和矩阵求值 

1.2.2 算法代码

import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt(), m = in.nextInt(), q = in.nextInt();int[][] arr = new int[n + 1][m + 1];for (int i = 1; i < n + 1; i++) {for (int j = 1; j < m + 1; j++) {arr[i][j] = in.nextInt();}}//预处理一个前缀和矩阵//long防溢出long[][] dp = new long[n + 1][m + 1];for (int i = 1; i < n + 1; i++) {for (int j = 1; j < m + 1; j++) {dp[i][j] = dp[i][j - 1] + dp[i - 1][j] + arr[i][j] - dp[i - 1][j - 1];}}while (q != 0) {int x1 = in.nextInt(), y1 = in.nextInt();int x2 = in.nextInt(), y2 = in.nextInt();long val = dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1];System.out.println(val);q--;}}
}

注意:

模版仅仅为模版,并非前缀和算法的固定形式!!!算法的具体使用要就题论题,要学会举一反三!!!


2、算法应用【leetcode】

2.1 题一:寻找数组的中心下标

. - 力扣(LeetCode)

2.1.1 算法思想

  1. 已知中心下标左右两侧值的和相等,所以我们可以预处理一个前缀和数组和一个后缀和数组解决该题。
  2. 前缀和数组i位置处存的是arr[0]~arr[i-1]之和(不包含arr[i])
  3. 后缀和数组i位置处存的是arr[i-1]~arr[n-1]之和(不包含arr[i])
  4. 最后,同时遍历前后缀和数组,当前缀和数组f[i] == 后缀和数组g[i]时,则说明原数组i下标左右两侧值之和相等,i就为中心下标。

2.1.2 算法代码

class Solution {public int pivotIndex(int[] nums) {int len = nums.length;int[] f = new int[len];//前缀和数组int[] g = new int[len];//后缀和数组//预处理前缀和数组//f[0] = 0;下标0位置的左侧数据和为0for(int i = 1; i < len; i++) {f[i] = f[i - 1] + nums[i - 1];}//预处理后缀和数组//g[len - 1] = 0;下标len-1位置的右侧数据和为0for(int i = len - 2; i >= 0; i--) {g[i] = g[i + 1] + nums[i + 1];}for(int i = 0; i < len; i++) {if(f[i] == g[i]) return i;}return -1;}
}

2.2 题二:除自身以外数组的乘积

. - 力扣(LeetCode)

2.2.1 算法思想

本题思路与上题基本一致,只不过本题使用“积”的形式:

  1. 预处理一个前缀积和一个后缀积数组
  2. 前缀积数组i位置处存的是arr[0]~arr[i-1]之积(不包含arr[i])
  3. 后缀积数组i位置处存的是arr[i-1]~arr[n-1]之积(不包含arr[i])
  4. 同时遍历前后缀积数组,将两值相乘所得值赋给ret数组中,即为除自身以外的乘积
  5. 这里需要注意一个边界细节问题:在前缀积0下标处应存入的值为1;在后缀积n-1下标处应存入的值为1

2.2.2 算法代码

class Solution {public int[] productExceptSelf(int[] nums) {int n = nums.length;int[] f = new int[n];int[] g = new int[n];//预处理前缀积数组f[0] = 1;for (int i = 1; i < n; i++) {f[i] = f[i - 1] * nums[i - 1];}//预处理后缀积数组g[n - 1] = 1;for (int i = n - 1 - 1; i >= 0; i--) {g[i] = g[i + 1] * nums[i + 1];}//使用前后缀积数组int[] ret = new int[n];for (int i = 0; i < n; i++) {ret[i] = f[i] * g[i];}return ret;}
}

2.3 题三:和为k的子数组

. - 力扣(LeetCode)

2.3.1 算法思想

2.3.2 算法代码

class Solution {public int subarraySum(int[] nums, int k) {Map<Integer,Integer> map = new HashMap<>();//当前子数组的和就为kmap.put(0,1);int sum = 0;int ret = 0;for (int i = 0; i < nums.length; i++) {sum += nums[i];ret += map.getOrDefault(sum - k,0);map.put(sum, map.getOrDefault(sum,0) + 1);}return ret;}
}

2.4 题四:和可被k整除的子数组 ★★★蓝桥杯竞赛原题

. - 力扣(LeetCode)

2.4.1 算法思想

  • 本题依然使用前缀和思想解题
  • 解决本题,我们首先需要了解同余定理以及Java/C++在[负数%正数]结果的修正(均整理好放在了下图中)
  • 依旧是查找以i结尾的子数组,当sum-x可被整除时,通过同余定理的转换,得到:查找在[0,i-1]区域中有多少个sum%k即有多少个可被整除的子数组
  • 故,我们在哈希表中存储的并非前缀和,而是前缀和的余数

2.4.2 算法代码

class Solution {public int subarraysDivByK(int[] nums, int k) {int sum = 0;Map<Integer,Integer> map = new HashMap<>();int ret = 0;map.put(0,1);for(int i = 0; i < nums.length; i++) {sum += nums[i];//同余定理 && Java中[负数 % 正数]的校正(正确结果为正数,但Java或C++中得到的是负数)int val = (sum % k + k) % k;ret += map.getOrDefault(val, 0);map.put(val, map.getOrDefault(val, 0) + 1);}return ret;}
}

2.5 题五:连续数组

. - 力扣(LeetCode)

2.5.1 算法思想

  • 哈希表+前缀和思想解题
  • 将数组中的0元素转化为-1,进而将求0和1出现次数相同的最长子数组转变为求和为0的最长子数组
  • 因为求最长的子数组,所以哈希表中不再存sum出现的次数,而是要存sum的下标
  • 查找在[0,i-1]区域上的和为sum-0(sum)的子数组的末位置,得到的末位置+1就得到和为0的子数组的起始位置,计算得出长度,进而保留最长长度。

2.5.2 算法代码

class Solution {public int findMaxLength(int[] nums) {int sum = 0;Map<Integer,Integer> map = new HashMap<>();//和为0子数组前的和为sum-0的子数组map.put(0,-1);int max = 0;for (int i = 0; i < nums.length; i++) {//将为 0 -> -1//数组和为k -> 数组和为0sum += nums[i] == 0 ? -1 : 1;if (map.containsKey(sum)) {max = Math.max(max,i - (map.get(sum) + 1) + 1);}else {map.put(sum,i);}}return max;}
}

2.6 题六: 矩阵区域和

. - 力扣(LeetCode)

2.6.1 算法思想

该题需要使用二维前缀和思想:

  1. 利用上文二维前缀和模版题的思想,预处理出二维前缀和矩阵dp
  2. answer数组中元素的值,即为mat数组中的部分区域之和,可利用前缀和数组计算得出(使用前缀和数组计算得出区域之和)
  3. 本题需要额外注意mat、dp、answer数组之间的下标映射关系
  4. 其中,mat、answer数组矩阵下标是从0开始的,而我们预处理出的dp矩阵的有效数据是从1下标开始的

1.预处理出前缀和矩阵dp:

 2.确定answer数组中元素数值:

3.确定下标映射关系:

2.6.2 算法代码

class Solution {public int[][] matrixBlockSum(int[][] mat, int k) {int m = mat.length;int n = mat[0].length;int[][] dp = new int[m + 1][n + 1];for (int i = 1; i < m + 1; i++) {for (int j = 1; j < n + 1; j++) {dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + mat[i - 1][j - 1];}}int[][] answer = new int[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {//+1是为了处理下标映射关系int x1 = Math.max(0,i - k) + 1, y1 = Math.max(0,j - k) + 1;int x2 = Math.min(m - 1,i + k) + 1, y2 = Math.min(n - 1,j + k) + 1;answer[i][j] = dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1];}}return answer;}
}

END

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/415290.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

聚观早报 | 理想汽车OTA 6.2发布;京东大幅上调校招薪资

聚观早报每日整理最值得关注的行业重点事件&#xff0c;帮助大家及时了解最新行业动态&#xff0c;每日读报&#xff0c;就读聚观365资讯简报。 整理丨Cutie 9月3日消息 理想汽车OTA 6.2发布 京东大幅上调校招薪资 哪吒汽车8月销量持续破万 C919国产大飞机首航在即 现代…

怎么找TikTok代运营助力?灵感魔方怎么样?

在当今全球化的浪潮中&#xff0c;海外版抖音已然成为了品牌出海的重要阵地。然而&#xff0c;面对这个充满机遇与挑战的平台&#xff0c;如何找到专业的TikTok代运营团队来助力品牌成功出海呢&#xff1f;以下是一些关键的考量因素和方法。 首先&#xff0c;专业的TikTok代运…

【机器学习】图像处理与深度学习利器:OpenCV实战攻略全面解析

&#x1f3ac; 鸽芷咕&#xff1a;个人主页 &#x1f525; 个人专栏: 《C干货基地》《粉丝福利》 ⛺️生活的理想&#xff0c;就是为了理想的生活! 前言 OpenCV想必大家都听过跨平台计算机视觉库&#xff0c;可以运行在Linux、Windows、Android和Mac OS操作系统上。它轻量级而…

巴黎奥运会引发体育健身热潮:气膜体育馆成为新宠—轻空间

随着巴黎奥运会的成功举办&#xff0c;全球范围内掀起了一股体育健身的热潮。各地的健身场所迎来了前所未有的参与热情&#xff0c;其中&#xff0c;融合了体育、娱乐、休闲等多种业态的综合气膜体育馆因其独特的优势&#xff0c;迅速成为群众健身的新宠&#xff0c;成为了大众…

视频搬运的素材网站有哪些?打包好的视频素材在哪找?

探索短视频创作世界时&#xff0c;是不是经常碰到缺乏素材的难题&#xff1f;无需担心&#xff0c;今天我们来聊聊一些能够即刻丰富你视频内容的素材网站。无论是搬运视频还是寻找灵感&#xff0c;这些资源站都将为你的创作锦上添花。特别强调的是&#xff0c;除了国际上的珍贵…

小土堆pytorch

anaconda安装 pip list 可以看有哪些package包 nvidia-smi查看显卡的状态 安装pytorch 检验pytorch是否安装成功&#xff0c;以及是否pytorch是否可以使用gpu。 (1)查看conda版本 conda --version 或 conda -V (2)更新conda&#xff08;将conda自身更新到最新版本&#xff09; …

sqlite数据插入效率

一、程序效率测试 时间相关接口&#xff1a; int gettimeofday(struct timeval*tv, struct timezone *tz); 功能&#xff1a;得到从1970年1月1日0时0分0秒到现在的秒数。<可以利用该函数来计算一个程序的运行时间&#xff0c;只需在程序前后调用该函数&#xff0c;…

计算机网络概述(分组延时、丢失和吞吐量)

目录 分组丢失和延时是怎样发生的&#xff1f; 四种分组延时 节点延时 排队延迟 分组丢失 吞吐量 吞吐量&#xff1a;互联网场景 分组丢失和延时是怎样发生的&#xff1f; 在路由器缓冲区的分组队列 分组到达链路的速率超过了链路输出的能力分组等待排队到队头、被传输…

基于.NET6的WPF基础总结(上)

目录 一.常用属性介绍 二、 程序退出方式 三、布局样式 3.1 Panel的附加属性ZIndex 3.2 Grid(网格)布局 3.3 UniformGrid&#xff08;均分布局&#xff09; 3.4 StackPanel&#xff08;堆积面板&#xff09; 3.5 WrapPanel&#xff08;换行面板&#xff09; 3.6 Doc…

什么是I2C总线?

1.什么是I2C&#xff1f; 1.1 I2C的由来 在电视机内部电路中&#xff0c;众多功能需要用到许多集成电路IC来实现&#xff0c;包括主控器件微控制器和众多外围设备器件。这些器件相互之间要传递数据信息&#xff0c;那么就需要用导线相互连接&#xff0c;如此众多IC器件的互连&…

linux下cpu多核运行程序以及运行时间统计

一、多核心运行程序 在linux下我们可以指定线程或者进程运行在指定的cpu核心上&#xff0c;操作方法如下&#xff1a; 1&#xff09;运行进程指定cpu核心 taskset -c 2 ./app //-c指定运行的cpu核心号&#xff0c;从0计数&#xff0c;查看效果如下&#xff1a; 2&#xff09…

两句话讲清楚离线安装docker镜像

两句话讲清楚离线安装docker镜像 文章目录 两句话讲清楚离线安装docker镜像写在前面解决方案 写在前面 背景&#xff1a;银河麒麟、离线环境&#xff0c;装吧&#xff0c;一装一个不吱声。 准备&#xff1a; 首先&#xff0c;你要有个docker&#xff0c;安装好了才能搞镜像是不…

C++:构造函数与析构函数

一.类的默认成员函数 默认成员函数就是用户没有显式实现&#xff0c;编译器会自动生成的成员函数称为默认成员函数&#xff0c;如下图&#xff1a; 其中最重要的就是我们表格中的前四个函数&#xff0c;本篇文章我们主要介绍前三个。默认成员函数很重要&#xff0c;也比较复杂…

下载xhsell连接Linux系统

一、下载安装xshell 1、下载 免费版的网址&#xff1a;家庭/学校免费 - NetSarang Website 2、安装 选择自己想要下载的文件夹位置 创建一个新的文件夹即可 不想注册可以直接选择后来先进行试用 二、连接Linux虚拟机 1、点击加号新建会话 2、输入你要连接的虚拟机的IP地址…

4、Django Admin对自定义的计算字段进行排序

通常&#xff0c;Django会为模型属性字段&#xff0c;自动添加排序功能。当你添加计算字段时&#xff0c;Django不知道如何执行order_by&#xff0c;因此它不会在该字段上添加排序功能。 如果要在计算字段上添加排序&#xff0c;则必须告诉Django需要排序的内容。你可以通过在…

【综合架构】Part 5.2 Ansible

使用设备&#xff1a;管理设备-m01-10.0.0.61 1 概述 自动化运维工具&#xff1a;可实现批量管理、批量分发、批量执行、维护... Ansible 是由 Python语言 所编写 2 管理架构 Inventory 主机清单&#xff1a;被管理主机的ip列表、分类。ad-hoc模式&#xff1a;命令行批量管理…

迁移学习之领域偏移(domain shift)

实际应用中很多任务的数据的标注成本很高&#xff0c;无法获得充足的训练数据&#xff0c;这种情况可以 使用迁移学习&#xff08;transfer learning)。假设 A、B 是两个相关的任务&#xff0c;A 任务有很多训练数 据&#xff0c;就可以把从A任务中学习到的某些可以泛化知识迁移…

《信息技术 云计算 边缘云通用技术要求》国家标准发布,九州未来参编

日前&#xff0c;2024年第17号国家标准公告发布&#xff0c;由全国信标委云计算标准工作组组织制定、九州未来作为行业专家单位参编的《信息技术 云计算 边缘云通用技术要求》国家标准正式获批发布。 边缘云作为云计算技术的有效补充和拓展&#xff0c;能够实现将云计算能力拓展…

java常用类

目录 1 String类 1字符串的构造方法&#xff1a; 2.常量池 3 .字符串的比较 1 equals 2 equalsIgnorecase 3.字符串长度&#xff1a; 4.拼接字符串 5.获取单个字符&#xff1a; 6.子字符串的索引&#xff08;首个&#xff09; 7.截取字符串 8.将String的转换为数组&…

设计模式 -- 迭代器模式(Iterator Pattern)

1 问题引出 编写程序展示一个学校院系结构&#xff1a;需求是这样&#xff0c;要在一个页面中展示出学校的院系组成&#xff0c;一个学校有多个学院&#xff0c; 一个学院有多个系 传统方式实现 将学院看做是学校的子类&#xff0c;系是学院的子类&#xff0c;这样实际上是站在…