基础算法(4)——前缀和

ops/2024/9/24 4:13:09/

1. 前缀和

题目描述:

解法一:暴力解法

直接模拟实现题目流程即可

时间复杂度为O(N*q),根据题目给出的条件q <= 10^{5},肯定会超时

解法二:前缀和(适用题型:快速 求出数组中某一个 连续区间 的 

时间复杂度:O(q)+O(n)

算法思路:

细节问题:为什么数组下标从 1 开始

当数组下标从 0 开始,dp[l - 1] 就成了 dp[-1] 造成数组越界异常

因此数组下标从 1 开始,若是数组下标从 0 开始时,需要处理边界情况

代码实现:

import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
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 + 1; i++) {arr[i] = in.nextInt();}//2.预处理一个前缀和数组long[] dp = new long[n + 1]; //防溢出dp[1] = arr[1];for (int j = 2; j < n + 1; j++) {dp[j] += dp[j - 1] + arr[j];}//3.使用前缀和数组while (q > 0) {int l = in.nextInt();int r = in.nextInt();System.out.println(dp[r] - dp[l - 1]);q--;}}
}

2. 二维前缀和

题目描述:

解法一:暴力解法(模拟)

时间复杂度:O(n*m*q),会超时

解法二:前缀和

时间复杂度:O(m*n)+O(q)

算法思路:

代码实现:

import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);//1.读入数据int n = in.nextInt();int m = in.nextInt();int 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();}}//2.预处理一个前缀和矩阵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 - 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--;}}
}

3. 寻找数组的中心下标

题目描述:

解法:前缀和

算法思路:

从中心下标的定义可知,除中心下标的元素外,该元素左边的【前缀和】等于该元素右边的【后缀和】

因此我们可以先预处理出来两个数组,一个表示前缀和,一个表示后缀和

然后用一个 for 循环枚举可能的中心下标,判断每一个位置的【前缀和】以及【后缀和】,如果二者相等,就返回当前下标

代码实现:

class Solution {public int pivotIndex(int[] nums) {int n = nums.length;//f[i] 表示:[0, i - 1] 区间所有元素的和//g[i] 表示:[i + 1, n - 1] 区间所有元素的和int[] f = new int[n]; //前缀和数组int[] g = new int[n]; //后缀和数组//预处理前缀和后缀和数组(优化前)//这里当i等于0时,f[0]本来就是0,没必要多加判断,直接从1位置开始遍历即可// for (int i = 0; i < n; i++) {//     if (i == 0) {//         f[i] = 0;//     } else {//         f[i] = f[i - 1] + nums[i - 1];//     }// }//当i等于n-1时本来就是0,无需处理,直接从n-2处开始遍历即可// for (int i = n - 1; i >= 0; i--) {//     if (i == n - 1) {//         g[i] = 0;//     } else {//         g[i] = g[i + 1] + nums[i + 1];//     }// }//预处理前缀和后缀和数组(优化后)for (int i = 1; i < n; i++) {f[i] = f[i - 1] + nums[i - 1];}for (int i = n - 2; i >= 0; i--) {g[i] = g[i + 1] + nums[i + 1];}//使用前后缀和数组进行判断for (int i = 0; i < n; i++) {if (f[i] == g[i]) {return i;}}return -1;}
}

4. 除自身以外数组的乘积

题目描述:

解法:前缀积

算法思路:

根据题意,对于每一个位置的最终结果 answer[i] 都由两部分组成:

第一部分:nums[0] * nums[1] * nums[2] * ... * nums[i - 1]

第二部分:nums[i + 1] * nums[i + 2] * ... * nums[n - 1]

可以利用前缀和的思想,使用两个数组 f 和 g 分别处理出来两个信息:

代码实现:

class Solution {public int[] productExceptSelf(int[] nums) {int n = nums.length;//f[i] 表示[0, i-1] 区间内所有元素的乘积//g[i] 表示[i+1, n-1] 区间内所有元素的乘积int[] f = new int[n];int[] g = new int[n];int[] answer = new int[n];//细节问题,这两个下标处的值需设为1,设为0的话任何数乘0都得0了f[0] = 1;g[n - 1] = 1;//预处理前缀积和后缀积for (int i = 1; i < n; i++) {f[i] = f[i - 1] * nums[i - 1];}for (int i = n - 2; i >= 0; i--) {g[i] = g[i + 1] * nums[i + 1];}//处理结果数组for (int i = 0; i < n; i++) {answer[i] = f[i] * g[i];}return answer;}
}

5. 和为 K 的子数组

题目描述:

解法一:暴力枚举

时间复杂度:O(N)

算法思路:

解法二:前缀和

算法思路:

代码实现:

class Solution {public int subarraySum(int[] nums, int k) {Map<Integer, Integer> hash = new HashMap<Integer, Integer>();hash.put(0, 1); //对应整个数组元素和为 k 的情况int sum = 0; //记录上一个位置的元素和int ret = 0; //记录前缀和为 sum - k 出现的次数for (int x : nums) {sum += x; //计算当前位置的前缀和ret += hash.getOrDefault(sum - k, 0); //统计结果hash.put(sum, hash.getOrDefault(sum, 0) + 1); //把当前的前缀和放入哈希表}return ret;}
}

6. 和可被 K 整除的子数组

题目描述:

知识补充:

算法思路:

代码实现:

class Solution {public int subarraysDivByK(int[] nums, int k) {Map<Integer, Integer> hash = new HashMap<Integer, Integer>();hash.put(0 % k, 1);int sum = 0; //标记前一个位置的前缀和int ret = 0; //表示最终结果for (int x : nums) {sum += x; //计算当前位置的前缀和int r = (sum % k + k) % k;ret += hash.getOrDefault(r, 0); //统计结果hash.put(r, hash.getOrDefault(r, 0) + 1);}return ret;}
}

7. 连续数组

题目描述:

解法:前缀和 + 哈希表

代码实现:

class Solution {public int findMaxLength(int[] nums) {Map<Integer, Integer> hash = new HashMap<>();hash.put(0, -1); //默认存在一个前缀和为 0 的情况int sum = 0;int ret = 0;for (int i = 0; i < nums.length; i++) { //此处要求下标,所以不能用 foreach//计算当前位置前缀和//无需修改原数组,仅需判断当前位置为 0 时,加上 -1 即可sum += (nums[i] == 0 ? -1 : 1);if (hash.containsKey(sum)) { //判断哈希表中是否存在前缀和ret = Math.max(ret, i - hash.get(sum));} else { //若哈希表中不存在前缀和,则更新hash.put(sum, i);}}return ret;}
}

实例:

8. 矩阵区域和

题目描述:

题目解析:

解法:二维前缀和

二维前缀和递推公式推导:

使用前缀和

算法思路:

此处将 answer 简写为 ans

第一步:当我们要求 ans[i][j] 时,仅需知道其对应的 x1、y1、x2、y2

第二步:下标的映射关系

代码实现:

class Solution {public int[][] matrixBlockSum(int[][] mat, int k) {int m = mat.length;int n = mat[0].length;//1.预处理前缀和矩阵int[][] dp = new int[m + 1][n + 1]; //此处 +1 操作就是为 dp 表增加一行一列for (int i = 1; i <= m; i++) { //dp 表从(1,1)开始for (int j = 1; j <= n; j++) {dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i - 1][j - 1];}}//2.使用int[][] ret = new int[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {int x1 = Math.max(0, i - k) + 1;int y1 = Math.max(0, j - k) + 1;int x2 = Math.min(m - 1, i + k) + 1;int y2 = Math.min(n - 1, j + k) + 1;ret[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];}}return ret;}
}

http://www.ppmy.cn/ops/115109.html

相关文章

SpringCloud 基于 web 的只会养老平台

摘要 首先,论文一开始便是清楚的论述了系统的研究内容。其次,剖析系统需求分析,弄明白“做什么”,分析包括业务分析和业务流程的分析以及用例分析,更进一步明确系统的需求。然后在明白了系统的需求基础上需要进一步地设计系统,主要包罗软件架构模式、整体功能模块、数据库设计…

【算法】栈与模拟

【ps】本篇有 5 道 leetcode OJ。 目录 一、算法简介 二、相关例题 1&#xff09;删除字符串中的所有相邻重复项 .1- 题目解析 .2- 代码编写 2&#xff09;比较含退格的字符串 .1- 题目解析 .2- 代码编写 3&#xff09;基本计算器 II .1- 题目解析 .2- 代码编写 4&…

Avatarify——实时面部替换工具,允许用户通过网络摄像头将自己的表情映射到虚拟人物或名人头像上

一、Avatarify介绍 Avatarify 是一款基于深度学习的实时面部动画生成工具&#xff0c;它允许用户使用 AI 技术将自己的面部表情实时映射到虚拟角色、静态图片或视频上&#xff0c;进而使这些角色看起来像是在模仿用户的表情。该工具在娱乐、社交媒体以及虚拟会议等场景中应用广…

【人工智能】在大型活动中的应用案例

人工智能在娱乐大型活动中的应用 ## 作者主页: 知孤云出岫 目录 **人工智能在娱乐大型活动中的应用****1. 引言****2. 智能票务与入场管理****2.1 动态定价与票务预测****2.2 生物识别技术快速入场****2.3 区块链技术防伪票务管理** **3. 智能观众互动与个性化体验****3.1 个性…

Rocky Linux 9 中添加或删除某个网卡的静态路由的方法

使用ip命令配置临时路由 添加静态路由 ip route add <目的网络> via <下一跳IP> dev <网卡接口名称>例: 给eth0网卡添加一个到达 192.168.2.0/24 网络&#xff0c;下一跳为 192.168.1.254 的路由 ip route add 192.168.2.0/24 via 192.168.1.254 dev eth0…

ERNIESpeed-128K在线智能聊天机器人项目(附源码)

本项目是基于百度千帆的智能聊天模型ERNIESpeed-128K开发的 一、技术栈 后端&#xff1a;java8springboot2.6.13 数据库&#xff1a;MongoDB 前端&#xff1a;vue2element-uimarked&#xff08;md格式&#xff09; 二、MongoDB与对话存储的设计 使用MongoDB来储存对话&am…

基于JAVA+SpringBoot+Vue的医院资源管理系统

基于JAVASpringBootVue的医院资源管理系统 前言 ✌全网粉丝20W,csdn特邀作者、博客专家、CSDN[新星计划]导师、java领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末附源码下载链接&#x1f345; 哈…

[Simpfun游戏云1]搭建MC Java+基岩互通生存游戏服务器

众所周知&#xff0c;MC有多个客户端&#xff0c;像常见的比如Java Edition和基岩等&#xff0c;这就导致&#xff0c;比如我知道一个超级好玩的JE服务器&#xff0c;但我又想使用基岩版来玩&#xff0c;肯定是不行的&#xff0c;因为通讯协议不一样。 这就有一些人才发明了多…