Java之前缀和算法
目录
一.前缀和
1.前缀和介绍
2.编程中的前缀和
二.一维数组的动态和
1.题目描述
2.问题分析
3.代码实现
三.除自身以外数组的乘积
1.题目描述
2.问题分析
3.代码实现
四.和为 K 的子数组
1.题目描述
2.问题分析
3.代码实现
五.形成两个异或相等数组的三元组数目
1.题目描述
2.问题分析
3.代码实现
一.前缀和
1.前缀和介绍
前缀和,顾名思义,就是前n项相加之和,和我们高中时候学习的数列中的一个含义
例如一个等差数组=n,那他的前n项和
=
也可知道-
=
2.编程中的前缀和
对于一个数组nums,也可以很容易求出它的前缀和数组
public int[] prefix(int[] nums) {int[] prefix = new int[nums.length];prefix[0] = nums[0];for (int i = 1; i < nums.length; ++i) {prefix[i] = prefix[i - 1] + nums[i];}return prefix;}
prefix数组的含义是: prefix[i]的值为nums数组从0到i的元素之和
其实我们这里的前缀和并不仅仅局限于前几项的和,之后我们还会涉及到乘法前缀和(后缀和),异或前缀和等等......并且还会存在后缀和的情况
二.一维数组的动态和
1.题目描述
给你一个数组
nums。数组「动态和」的计算公式为:runningSum[i] = sum(nums[0]…nums[i])。请返回
nums的动态和。
力扣:力扣
2.问题分析
这道题就是一道典型的前缀和题目,没什么特别之处,数组的动态和计算公式就是前缀和的含义,可以直接写出代码求解
3.代码实现
public int[] runningSum(int[] nums) {int[] prefix = new int[nums.length];prefix[0] = nums[0];for (int i = 1; i < nums.length; ++i) {prefix[i] = prefix[i - 1] + nums[i];}return prefix;}
三.除自身以外数组的乘积
1.题目描述
给你一个整数数组
nums,返回 数组answer,其中answer[i]等于nums中除nums[i]之外其余各元素的乘积 。题目数据 保证 数组
nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。请不要使用除法,且在
O(n)时间复杂度内完成此题。
力扣:力扣
2.问题分析
这个问题说的很明白,不能用除法来进行,我们的第一想法是使用乘法前缀和来进行计算,但是考虑到不能使用除法和数组中可能存在0,所以这样是不能够满足题意和解答问题的.
因此我们不妨再来设置一个数组,这个数组用来存储乘法后缀和,我们计算res[i]的时候就可以它的前缀和乘以它的后缀和,这样它的结果就可以求出来了
设置前缀和数组left[i]含义为:从nums数组的第0到第i-1项的叠乘所获得的结果
设置后缀和数组right[i]含义为:从nums数组的第i+1到最后一项项的叠乘所获得的结果
最后结果数组res[i]=left[i]*right[i]
3.代码实现
public int[] productExceptSelf(int[] nums) {int[] left = new int[nums.length];//left[i]:从0-i-1项相乘int[] right = new int[nums.length];//right[i]:从i+1到最后一项相乘left[0] = 1;right[nums.length - 1] = 1;for (int i = 1; i < nums.length; ++i) {left[i] = left[i - 1] * nums[i - 1];}for (int j = nums.length - 2; j >= 0; --j) {right[j] = right[j + 1] * nums[j + 1];}int[] res = new int[nums.length];for (int i = 0; i < nums.length; ++i) {res[i] = left[i] * right[i];}return res;}
四.和为 K 的子数组
1.题目描述
给你一个整数数组
nums和一个整数k,请你统计并返回 该数组中和为k的连续子数组的个数 。
力扣:力扣
2.问题分析
这一题我们不妨先暴力思考一下,暴力就是把它的所有子数组的和全部求出来,然后和k进行判断,最后统计出等于k的子数组的数量,至少也进行两层for循环,代码如下:
public int subarraySum(int[] nums, int k) {int count = 0;for (int end = 0; end < nums.length; ++end) {int sum = 0;for (int start = end; start >= 0; --start) {sum += nums[start];if (sum == k) {count++;}}}return count; }

相当于外层循环确定end,内层循环确定开始的位置start的位置
其实我们可以用一个哈希表进行优化,因为它的前缀和每次都是叠加的,其实只要统计它的每个前缀和的次数,然后prefix-k就是它从0到start的前缀和,此时start+1到end的位置就是和为k的子数组,同时map哈希表刚开始的时候还要添加key=0,value=1的键值对,因为当prefix刚好为k的时候,prefix-k=0,表示从0到end的子数组符合条件
3.代码实现
public int subarraySum(int[] nums, int k) {HashMap<Integer, Integer> map = new HashMap<>();map.put(0, 1);//此时是从0到i的前缀和int prefix = 0, count = 0;for (int end = 0; end < nums.length; ++end ) {prefix += nums[end];if (map.containsKey(prefix - k)) {count += map.get(prefix - k);}map.put(prefix, map.getOrDefault(prefix, 0) + 1);}return count; }
五.形成两个异或相等数组的三元组数目
1.题目描述
给你一个整数数组
arr。现需要从数组中取三个下标
i、j和k,其中(0 <= i < j <= k < arr.length)。
a和b定义如下:
a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]注意:^ 表示 按位异或 操作。
请返回能够令
a == b成立的三元组 (i,j,k) 的数目。
力扣:力扣
2.问题分析
首先我们想的就是需要暴力遍历i,j和k这三个值,这一题是异或前缀和,首先我们把它的异或前缀和数组求解出来,然后用异或前缀和来表达a和b,
前缀和数组prefixArr[i]的含义:nums从0到i-1的异或前缀
a=prefixArr[j]^prefixArr[i]
b=prefixArr[k+1]^prefixArr[j]
a==b 即 prefixArr[k+1]==prefixArr[i]
知道这个之后,我们就可以使用暴力的方法求解出满足条件的三元组的数量了
3.代码实现
public int countTriplets(int[] arr) {int[] prefixArr = new int[arr.length + 1];for (int i = 1; i <= arr.length; ++i) {prefixArr[i] = prefixArr[i - 1] ^ arr[i - 1];}System.out.println(Arrays.toString(prefixArr));int count = 0;for (int i = 0; i < arr.length - 2; ++i) {for (int j = i + 1; j < arr.length - 1; ++j) {for (int k = j + 1; k < arr.length; ++k) {if (prefixArr[k + 1] == prefixArr[i])count++;}}}return count;}
相关文章:
Java之前缀和算法
目录 一.前缀和 1.前缀和介绍 2.编程中的前缀和 二.一维数组的动态和 1.题目描述 2.问题分析 3.代码实现 三.除自身以外数组的乘积 1.题目描述 2.问题分析 3.代码实现 四.和为 K 的子数组 1.题目描述 2.问题分析 3.代码实现 五.形成两个异或相等数组的三元组数目…...
基于GIS计算降雨侵蚀力R因子
一、数据来源介绍 (一)行政边界数据 本文所用到的河北唐山行政边界数据来源于中国科学院资源环境科学与数据中心(https://www.resdc.cn/Default.aspx)。 (二)降水量数据 本文所用到的降水量数据来源于国家…...
大数据时代下的企业网络安全
在大数据技术迅猛发展的今天,网络安全问题已经发展成一个广受关注的热门研究方向。有人说,“大数据下,人人裸奔”,隐私保护、数据防护日益成为广大学者、企业研究的焦点。 面对这种安全威胁,企业必须实施一些有效的信…...
【跟我一起读《视觉惯性SLAM理论与源码解析》】第三章第四章 SLAM中常用的数学基础知识相机成像模型
齐次坐标能大大简化在三维空间中点、线、面表达方式和旋转、平移等操作在齐次坐标下,两个点的叉积结果可以表示一条直线l;也可以用两条直线的叉积结果表示它们的齐次坐标交点,关于叉积其实十四讲解释的还是比较清楚的,和李代数李群的关系可以…...
LeetCode 242. 有效的字母异位词
242. 有效的字母异位词 难度:easy\color{Green}{easy}easy 题目描述 给定两个字符串 sss 和 ttt ,编写一个函数来判断 ttt 是否是 sss 的字母异位词。 注意: 若 sss 和 ttt 中每个字符出现的次数都相同,则称 sss 和 ttt 互为字…...
力扣mysql刷题记录
mysql刷题记录 刷题链接https://leetcode.cn/study-plan/sql/?progressjkih0qc mysql冲!mysql刷题记录1699. 两人之间的通话次数1251. 平均售价1571. 仓库经理1445. 苹果和桔子1193. 每月交易 I1633. 各赛事的用户注册率1173. 即时食物配送 I1211. 查询结果的质量…...
Linux基础命令-lsof查看进程打开的文件
Linux基础命令-uptime查看系统负载 Linux基础命令-top实时显示系统状态 Linux基础命令-ps查看进程状态 文件目录 前言 一 命令的介绍 二 语法及参数 2.1 使用help查看命令的语法信息 2.2 常用参数 2.2.lsof命令-i参数的条件 三 命令显示内容的含义 3.1 FD 文件描述符的…...
常用电平标准
现在常用的电平标准有TTL CMOS LVTTL LVCMOS LVDS PCI等,下面简单介绍一下各自的供电电源、电平标准及注意事项数字电路中,由TTL电子元件组成电路使用的电平。电平是个电压范围。标准输出高电平(VOH): 2.4V标准输出低电平(VOL):0.4V通常输出高…...
小程序开发注意点
1.组件样式隔离注意点 2.methods方法 3.自定义组件的properties参数 4.自定义组件的事件监听 5.纯数据字段 6.插槽 单个插槽 启用多插槽 使用多个插槽 7.属性绑定实现父传子功能 例如在这里有一个组件为<one></one>,那么可以在组件当中传入参数 &l…...
自行车出口欧盟CE认证,新版自行车标准ISO 4210:2023与ISO 8098:2023发布
2023年1月,国际标准化组织ISO发布了新版“自行车以及儿童自行车的测试标准”,即ISO 4210:2023以及ISO 8098:2023,用于取代了SO 4210:2015以及ISO 8098:2015。新版标准一经发布,立即生效。欧盟标准化委员会C…...
2020蓝桥杯真题回文日期 C语言/C++
题目描述 2020 年春节期间,有一个特殊的日期引起了大家的注意:2020 年 2 月 2 日。因为如果将这个日期按 “yyyymmdd” 的格式写成一个 8 位数是 20200202,恰好是一个回文数。我们称这样的日期是回文日期。 有人表示 20200202 是 “千年一遇…...
postman入门到精通之【接口知识准备】(一)
postman入门到精通之【接口知识准备】(一) 目录:导读 前言 接口测试概念 接口测试 接口测试的原理 常用接口测试工具 接口测试基础知识 接口的定义 接口的分类 HTTP接口 Web Service接口 RESTful接口 HTTP请求 统一资源定位符&…...
【算法数据结构体系篇class07】:加强堆
一、手动改写堆(非常重要)!系统提供的堆无法做到的事情:1)已经入堆的元素,如果参与排序的指标方法变化,系统提供的堆无法做到时间复杂度O(logN)调整!都是O(N)的调整!2&am…...
Taro3.x 容易踩坑的点(阻止滚动穿透,弹框蒙层父级定位)
解决弹框滚动的时候,下层也会滚动问题》阻止滚动穿透(react,vue)案例描述:页面展示时需要滚动条才可以显示完整,但是当我们显示弹框的时候,即使不需要滚动条,但是页面仍然可以滚动,并且下层内容会随着滚动变…...
SpringBoot+ActiveMQ-发布订阅模式(消费端)
ActiveMQ消息中间件的发布订阅模式 主题 topictopic生产端案例(配合topic消费端测试):SpringBootActiveMQ Topic 生产端ActiveMQ版本:apache-activemq-5.16.5案例源码:SpringBootActiveMQ-发布订阅DemoSpringBoot集成ActiveMQ Topic消费端的pom.xml<?…...
vscode下使用arduino插件开发ESP32 Heltec WiFi_Kit_32_V3
下载vsCode 添加 arduino 插件 在Arduino IDE 中添加开发板,注意只能用右侧的开发板管理器添加,自己下载之后复制进去的IDE认,但是vsCode不认,搜索ESP32 第一个库里面只有到V2的,没有V3,要安装下面那个 H…...
吐血整理AutoSAR Com-Stack 的配置【基于ETAS】
总目录链接>> AutoSAR入门和实战系列总目录 文章目录01.软件组件和系统说明02.基本软件配置03.系统数据映射04.代码生成05.代码整合06.测试下图显示了基于 AUTOSAR 的 ECU SW 的结构。纵观BSW,大体分为三层。三层模块中,与通信相关的模块称为通信…...
面向对象进阶之元类
6. 元类 Python 中一切皆对象,对象是由类实例化产生的。那么类应该也有个类去产生它,利用 type() 函数我们可以去查看: class A:pass a1 A() print(type(a1)) print(type(A))<class __main__.A> <class type>由上可知…...
【Android AIDL之详细使用】
Android AIDL之详细使用一级目录概述使用场景语法相关编码实践服务端:java文件修改AndroidManifest客户端坑一级目录 概述 AIDL叫Android接口定义语言,是用于辅助开发者完成Android跨进程编程的工具。 从某种意义上说AIDL其实是一个模板,因…...
ASP.NET MVC | 简介
目录 前提 1.教程 2.MVC 编程模式 最后 前提 在学习学过很多课程,但是最主要学的还是ASP.NET MVC这门课程,工作也是用的ASP.NET MVC,所以写一点ASP.NET MVC的东西,大家可以来看看,我自己不会的时候也不用找别的地方…...
React hook之useRef
React useRef 详解 useRef 是 React 提供的一个 Hook,用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途,下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...
VB.net复制Ntag213卡写入UID
本示例使用的发卡器:https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...
k8s从入门到放弃之Ingress七层负载
k8s从入门到放弃之Ingress七层负载 在Kubernetes(简称K8s)中,Ingress是一个API对象,它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress,你可…...
Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件
今天呢,博主的学习进度也是步入了Java Mybatis 框架,目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学,希望能对大家有所帮助,也特别欢迎大家指点不足之处,小生很乐意接受正确的建议&…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...
新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案
随着新能源汽车的快速普及,充电桩作为核心配套设施,其安全性与可靠性备受关注。然而,在高温、高负荷运行环境下,充电桩的散热问题与消防安全隐患日益凸显,成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...
iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈
在日常iOS开发过程中,性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期,开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发,但背后往往隐藏着系统资源调度不当…...
springboot整合VUE之在线教育管理系统简介
可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生,小白用户,想学习知识的 有点基础,想要通过项…...
Redis:现代应用开发的高效内存数据存储利器
一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发,其初衷是为了满足他自己的一个项目需求,即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源,Redis凭借其简单易用、…...
如何应对敏捷转型中的团队阻力
应对敏捷转型中的团队阻力需要明确沟通敏捷转型目的、提升团队参与感、提供充分的培训与支持、逐步推进敏捷实践、建立清晰的奖励和反馈机制。其中,明确沟通敏捷转型目的尤为关键,团队成员只有清晰理解转型背后的原因和利益,才能降低对变化的…...
