算法前缀和—Java版

news/2024/3/28 18:26:02/文章来源:https://blog.csdn.net/cj151525/article/details/129171972

前缀和概念

  • 假设有数组 A=[1,2,3,4,5,6,7] 为原数组,有数组 B作为A的前缀和数组,那么B=[1,3,6,10,15,21,28];可以发现B[i] = A[0]+....+A[i],即B[i]是数组A的前面i个数的总和。可以前缀和表示如下公式:

    B[i]=∑j=0iA[j]B[i]=\sum_{j=0}^{i}{A[j]} B[i]=j=0iA[j]

  • 因此有了前缀和数组可以简化我们算法就子区间和,假设没有前缀和要求数组A区间[2,4]的总和,我们需要从 i=2 遍历 到 i=4 ,时间复杂度为O(n),通过前缀和只需要计算 B[4]-B[1]即可,因此可以将子区间和表示如下公式:B[i,j]=B[j]-B[i-1],j>=i 。但是上述子区间表示法在实际应用中会有问题,即当求区间B[0,j]的时候,会出现下标等于-1的情况,因此一般在程序中写成如下:

    B[i,j]=B[j]−B[i]+A[i]B[i,j]=B[j]-B[i]+A[i] B[i,j]=B[j]B[i]+A[i]

递推构造前缀和

  • 可以使用递推式构造前缀和,递推公式如下:

    B[i]=B[i−1]+A[i],B[0]=A[0]B[i]=B[i-1]+A[i],B[0]=A[0] B[i]=B[i1]+A[i],B[0]=A[0]

不仅仅是这些

  • 这些直接求前缀数字和的题目是前缀和最简单的题型,变换题型一般是记录前i个字符或者数组的状态,当遍历后续的i+k时求得前i+k的状态,然后比较两者之间的变化,推出中间长度k子串的状态看看是否满足题目要求。这才是前缀和的灵魂,前缀和一般和数组、子串、连续等关键字有关!!尤其是数组和字符串的问题,求最长子串,求数组满足条件的连续的最长长度!!!通过题目练习总结,尤其是最后两题!

LeetCode

1685. 有序数组中差绝对值之和

    public int[] getSumAbsoluteDifferences(int[] nums) {//使用一个规律,即数组是递增的,即后一个数的和与前一个数的和之间的关系//关系是,假设第i+1个数比第i个数大k,则i+1之后的数会在sum(i)的基础上少// (n-i+1)*k , 而i之前的数会在sum(i)的基础上多 (i-1)*kint n = nums.length;int[] res = new int[n];int sum = 0;for (int i = 0; i < n; i++) {sum+=(Math.abs(nums[i]-nums[0]))}res[0] = sum;for (int i = 1; i < n; i++) {int k = nums[i]-nums[i-1];int a = (i-1)*k;int b = (n-i-1)*k;res[i] = res[i-1]+a-b;}return res;}

1423. 可获得的最大点数

  • 一开始秒想到动态规划,但是超时,正确思路是反过来找最小的剩下的连续序列。使用滑动窗口!
public int maxscore(int[] cardPoints,int left,int right,int k){if(k==1 && left<right){int value = Math.max(cardPoints[right],cardPoints[left]);map.put(""+left+right+k,value);return value;}int a = 0;int b = 0;if(map.containsKey(""+(left+1)+right+(k-1))){a = map.get(""+(left+1)+right+(k-1))+cardPoints[left];}else {a = maxscore(cardPoints,left+1,right,k-1)+cardPoints[left];}if(map.containsKey(""+left+(right-1)+(k-1))){b = map.get(""+(left)+(right-1)+(k-1))+cardPoints[right];}else {b = maxscore(cardPoints,left,(right-1),k-1)+cardPoints[right];}return Math.max(a,b);}public int maxScore(int[] cardPoints, int k) {//动态规划map = new HashMap<>();return maxscore(cardPoints,0,cardPoints.length-1,k);}

正确解法:

public int maxScore(int[] cardPoints, int k) {int n = cardPoints.length-k;int[] B = new int[cardPoints.length];B[0] = cardPoints[0];for (int i = 1; i < cardPoints.length; i++) {B[i] = B[i-1]+cardPoints[i];}if(cardPoints.length==k){return B[cardPoints.length-1];}int minn = Integer.MAX_VALUE;for (int i = 0; i <= k; i++) {int sum = B[i+n-1]-B[i]+cardPoints[i];if(sum<minn){minn = sum;}}return B[cardPoints.length-1]-minn;}

1371. 每个元音包含偶数次的最长子字符串

525. 连续数组

  • 为什么挂这两道题,因为如果想到了这两道题的前缀和才是真的入门了,首先说525题。这道题前面已经提过,这道题需要把0变成-1,如果前i个数的和为-2,前i+7的和也是-2,那么巧了,那就意味着从i+1到i+7的和为0,即1和-1的数量一样多。这就是前缀的灵魂。那么换成1371,要求五个字母出现都是偶数的最长子字符串的长度,那么5个字符的奇偶状态就有32种,因此,同理在前i个字符如果是 ‘a’,‘e’,‘i’, ‘o’,都是偶数,'u’是奇数,而前i+9个字符前三个是偶数,后两个是奇数,那么意味着什么?意味着从i+1到i+9的子串中有奇数个 ‘o’ 。这只是一个例子,所以需要使用前i+k的状态与前i的状态对比,才知道中间这k个字符是什么状态。因此,前缀和并一定是前面数字之和,也可以是状态的变化。通过后面i+k的状态与i的状态推出中间的状态。这就是前缀和的灵魂。

  • class Solution {public int findTheLongestSubstring(String s) {int n = s.length();int[] pos = new int[1 << 5];Arrays.fill(pos, -1);int ans = 0, status = 0;pos[0] = 0;for (int i = 0; i < n; i++) {char ch = s.charAt(i);if (ch == 'a') {status ^= (1 << 0);} else if (ch == 'e') {status ^= (1 << 1);} else if (ch == 'i') {status ^= (1 << 2);} else if (ch == 'o') {status ^= (1 << 3);} else if (ch == 'u') {status ^= (1 << 4);}if (pos[status] >= 0) {ans = Math.max(ans, i + 1 - pos[status]);} else {pos[status] = i + 1;}}return ans;}
    }
    

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

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

相关文章

JAVA线程入门简介

线程入门简介什么是程序?什么是进程?什么是线程&#xff1f;单线程与多线程并发与并行线程的使用用java查看有多少个cpu创建线程的两种方式继承Thread类&#xff0c;重写run方法实现Runnable接口&#xff0c;重写run方法多线程机制为社么是start?源码解析什么是程序? 是为完…

字符串转换为二进制-课后程序(JAVA基础案例教程-黑马程序员编著-第五章-课后作业)

【案例5-4】 字符串转换为二进制 【案例介绍】 1.任务描述 本例要求编写一个程序&#xff0c;从键盘录入一个字符串&#xff0c;将字符串转换为二进制数。在转换时&#xff0c;将字符串中的每个字符单独转换为一个二进制数&#xff0c;将所有二进制数连接起来进行输出。 案…

win10下 WSL2安装及配置

目录 一. Windows中WSL2&#xff08;子系统&#xff09;安装前提条件 二. Windows中WSL2&#xff08;子系统&#xff09;安装步骤&#xff08;默认安装C盘&#xff09; 选择包安装模式(选择到其他盘安装) 三. Windows中WSL2&#xff08;子系统&#xff09;设置默认root用户登…

35-Golang中的方法

Golang中的方法方法的介绍和使用方法的声明和调用方法的调用和传参机制原理方法的声明(定义)方法注意事项和细节讨论方法和函数的区别方法的介绍和使用 在某些情况下&#xff0c;我们需要声明(定义)方法。比如person结构体&#xff0c;除了有一些字段外(年龄&#xff0c;姓名……

Apollo规划模块代码学习(1): 算法架构原理、运行机制一文详解

文章目录 1、Apllo算法框架原理2、Apollo规划模块概述3、规划模块代码框架1、重要数据结构2、运行机制1、Apllo算法框架原理 Apollo开源自动驾驶平台中,高清地图模块提供了每个在线模块都可以访问的高清地图。感知和定位模块提供了必要的动态环境信息,可以在预测模块中进一步…

优思学院:六西格玛管理的优势有哪些?

六西格玛的优势有哪些呢&#xff1f;以下我们来探讨一下。 一・降低企业整体成本 对企业而言&#xff0c;不良品要么被废弃&#xff0c;要么需要重新加工&#xff0c;或者需要在客户现场维修或更换&#xff0c;这些都会增加企业成本。根据美国的统计数据&#xff0c;执行3σ管…

Socket编程 | TCP服务器 之 并发阻塞模型(多进程实现)

TCP服务器IO模型 之 并发阻塞 1. 引言 在 Linux 环境下多进程的应用很多,其中最主要的就是网络/客户服务器。多进程服务器是当客户有请求时,服务器用一个子进程来处理客户请求。父进程继续等待其它客户的请求。这种方法的优点是当客户有请求时,服务器能及时处理客户,特别是…

docker 部署centos7.9并打包成docker

下载centos基础镜像 docker pull centos:centos7 运行镜像 docker run -itd --name centos-test -p 60001:22 --privileged centos:centos7 /usr/sbin/init 进入容器 docker exec -it ebec90068696 /bin/bash 配置容器信息 安装ssh服务和网络必须软件 yum install net-to…

MongoDB在Windows、Linux、Docker环境下的安装

MongoDB在Windows、Linux、Docker环境下的安装DockerDocker安装远程连接WindowsWindows安装服务相关命令压缩包形式安装Mac、Ubuntu、Centos一键安装MacUbuntucentos源码安装使用Atlas免费MongoDB云数据库申请云数据库连接测试Docker Docker安装 拉取镜像 docker pull mongo…

洛谷P5736 【深基7.例2】质数筛 C语言/C++

【深基7.例2】质数筛 题目描述 输入 nnn 个不大于 10510^5105 的正整数。要求全部储存在数组中&#xff0c;去除掉不是质数的数字&#xff0c;依次输出剩余的质数。 输入格式 第一行输入一个正整数 nnn&#xff0c;表示整数个数。 第二行输入 nnn 个正整数 aia_iai​&…

数据结构与算法(二)(Python版)

数据结构与算法&#xff08;一&#xff09;&#xff08;Python版&#xff09; 文章目录递归动规初识递归&#xff1a;数列求和递归三定律递归的应用&#xff1a;任意进制转换递归的应用&#xff1a;斐波那契数列递归调用的实现分治策略与递归优化问题和贪心策略找零兑换问题贪心…

系列四、多表查询

一、多表关系 项目开发中&#xff0c;在进行数据库表结构设计时&#xff0c;会根据业务需求及业务模块之间的关系&#xff0c;分析并设计表结 构&#xff0c;由于业务之间相互关联&#xff0c;所以各个表结构之间也存在着各种联系&#xff0c;基本上分为三种&#xff1a;一对多…

Sprng依赖注入(二):setter注入是如何工作的?

文章示例环境配置信息jdk版本:1.8开发工具&#xff1a;Intellij iDEA 2020.1springboot:2.3.9.RELEASE前言在Spring依赖注入&#xff08;一&#xff09;&#xff1a;字段注入的方式是如何工作的&#xff1f;中主要分享了Spring bean依赖注入方式中的字段注入方式及其工作过程&a…

基于Pytorch,从头开始实现Transformer(编码器部分)

Transformer理论部分参考知乎上的这篇文章 Transformer的Attention和Masked Attention部分参考知乎上的这篇文章 Transformer代码实现参考这篇文章&#xff0c;不过这篇文章多头注意力实现部分是错误的&#xff0c;需要注意。 完整代码放到github上了&#xff0c;链接 Trans…

联想小新 Air-14 2019IML电脑 Hackintosh 黑苹果efi引导文件

原文来源于黑果魏叔官网&#xff0c;转载需注明出处。硬件型号驱动情况主板Lenovo LNVNB161216处理器Intel Core i5-10210U / i7-10510U已驱动内存8GB DDR4 2666已驱动硬盘康佳KAK0500B128(128 GB/固志硬盘)已驱动显卡Intel UHD 620Nvidia GeForce MX250(屏蔽)无法驱动声卡Cone…

轮播图、阅读注册协议、网页时钟、随机点名、小米搜索框、轮播图点击切换——web APIs练习

目录 一、获取元素&#xff08;DOM&#xff09; 1. 随机轮播图案例 2. 阅读注册协议&#xff08;定时器间歇函数的应用&#xff09; 3. 轮播图定时器版 4. 网页时钟 二、事件基础&#xff08;DOM&#xff09; 1. 随机点名案例 2. 轮播图点击切换&#xff08;重点&#…

【计算机网络 -- 期末复习】

例题讲解 IP地址&#xff08;必考知识点&#xff09; 子网掩码 子网划分 第一栗&#xff1a; 子网划分题目的答案一般不唯一&#xff0c;我们主要采用下方的写法&#xff1a; 第二栗&#xff1a; 路由跳转 数据传输 CSMA/CD数据传输 2、比特率与波特率转换 四相位表示&am…

ElasticSearch 学习笔记总结(一)

文章目录一、 数据的 分类二、 ElasticSearch 介绍三、 ElasticSearch 搭建四、正排索引 和 倒排索引五、ES HTTP 索引 操作六、ES HTTP 文档 操作七、ES HTTP 查询数据1. 条件查询2. 分页查询3. 排序查询4. 多条件查询5. 全文检索 完全匹配 高亮显示6. 聚合查询八、 ES HTTP 映…

Scalable but Wasteful: Current State of Replication in the Cloud

文章目录ABSTRACT1 INTRODUCTION2 REPLICATION IN THE WILD3 CURRENT APPROACHES TO SCALING STATE MACHINE REPLICATION4 EFFICIENCY METRIC5 INEFFECTIVENESS OF CURRENT APPROACHES PER NEW METRIC6 CONCLUSION AND FUTURE DIRECTIONSABSTRACT 共识协议是部署在基于云的存储…

面试热点题:stl中vector与list的优缺点对比、以及list的迭代器与vector迭代器的区别

vector的优点 下标随机访问 vector的底层是一段连续的物理空间&#xff0c;所以支持随机访问尾插尾删效率高 跟数组类似&#xff0c;我们能够很轻易的找到最后一个元素&#xff0c;并完成各种操作cpu高速缓存命中率高 因为系统在底层拿空间的时候&#xff0c;是拿一段进cpu&am…