前缀和部分题目
前缀和
前缀和指数组的前 N项之和,是个比较基础的算法
例题
面试题 17.05. 字母与数字
给定一个放有字母和数字的数组,找到最长的子数组,且包含的字母和数字的个数相同。
返回该子数组,若存在多个最长子数组,返回左端点下标值最小的子数组。若不存在这样的数组,返回一个空数组。
示例 1:
输入: [“A”,“1”,“B”,“C”,“D”,“2”,“3”,“4”,“E”,“5”,“F”,“G”,“6”,“7”,“H”,“I”,“J”,“K”,“L”,“M”]
输出: [“A”,“1”,“B”,“C”,“D”,“2”,“3”,“4”,“E”,“5”,“F”,“G”,“6”,“7”]
示例 2:
输入: [“A”,“A”]
输出: []
提示:
array.length <= 100000
思路
使用前缀和+哈希
为字母则取1,数字为-1,即要求和为0的最大子数组。
前缀和表示第i个数及之前的所有数的和。哈希存储前缀和c第一次出现的位置i,循环时维护一个maxlen表示最大的子数组长度,start表示最长子数组起始下标。
初始化时,前缀和为0,下标为-1。遍历到i时,前缀和为sum,如果此时哈希表中没有关于前缀和为sum的记录,则更新indices[sum]=i。如果已有,则对比maxlen和i-indices[sum],如果i-indices[sum]较大,则maxlen更新为i-indices[sum],start更新为indices[sum]+1。
如果maxlen不为0,返回array中array[start]到array[start+maxlen]的部分。
代码
class Solution {
public:vector<string> findLongestSubarray(vector<string>& array) {int n=array.size();int sum=0;int maxlen=0;int start=-1;unordered_map<int,int> indices;indices[0]=-1;for(int i=0;i<n;i++){if(isalpha(array[i][0])){sum++;}else{sum--;}if(indices.find(sum)==indices.end()){indices[sum]=i;}else{if(i-indices[sum]>maxlen){maxlen=i-indices[sum];start=indices[sum]+1;}}}if(maxlen==0) return {};return vector<string>(array.begin()+start,array.begin()+start+maxlen);}
};
209. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。
示例 1:
输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2:
输入:target = 4, nums = [1,4,4]
输出:1
示例 3:
输入:target = 11, nums = [1,1,1,1,1,1,1,1]
输出:0
提示:
1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105
进阶:
如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。
思路
首先计算前缀和,presum[i]表示从0加到i-1的和,
对于遍历每个子数组的起始点nums[i],用二分搜索找到presum[j]-presum[i]大于或等于target的第一个下标j,遍历过程中维护最短子数组的长度minlen。
或者用滑动窗口做
代码
//前缀和+二分搜索
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int n=nums.size();int minlen=n+1;vector<int> presum(n+1,0);//presum[i]是从0加到i-1for(int i=0;i<n;i++){presum[i+1]=presum[i]+nums[i];}for(int i=0;i<n;i++){int l=i+1,r=n;while(l<r){int m=(l+r)/2;if(presum[m]-target<presum[i]){l=m+1;}else{r=m;}}if(presum[l]-target>=presum[i]){minlen=min(l-i,minlen);}}if(minlen>n) return 0;else return minlen;}
};
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int n=nums.size();int l=0,r=0;int sum=nums[0],minlen=n+1;while(r<n){while(sum<target&&r<n){if(++r<n) sum+=nums[r];}if(sum>=target){minlen=min(minlen,r-l+1);sum-=nums[l];l++;}else break;}return minlen<=n?minlen:0;}
};
相关文章:
前缀和部分题目
前缀和 前缀和指数组的前 N项之和,是个比较基础的算法 例题 面试题 17.05. 字母与数字 给定一个放有字母和数字的数组,找到最长的子数组,且包含的字母和数字的个数相同。 返回该子数组,若存在多个最长子数组,返回左…...
三天吃透MySQL面试八股文
本文已经收录到Github仓库,该仓库包含计算机基础、Java基础、多线程、JVM、数据库、Redis、Spring、Mybatis、SpringMVC、SpringBoot、分布式、微服务、设计模式、架构、校招社招分享等核心知识点,欢迎star~ Github地址:https://github.com/…...
Giving You A guide to learning any topic faster than 95% of people
A guide to learning any topic faster than 95% of people: Richard Feynman was a physician who won the Nobel Prize in 1965. But he became known for his great lectures. Why? He was able to explain complex concepts in simple terms with these 4 steps: 1 • E…...
(七十七)大白话MySQL是如何根据成本优化选择执行计划的?(中)
上次我们讲完了全表扫描的成本计算方法,相信大家应该都理解了,其实还是比较简单的,今天我们来讲一下索引的成本计算方法,因为除了全表扫描之外,还可能多个索引都可以使用,但是当然同时一般只能用一个索引&a…...
原来CSS 也可以节流啊
Ⅰ、前言 「节流」 是为了减少请求的触发频率,不让用户点的太快,达到节省资源的目的 ;通常 我们采用 JS 的 定时器 setTimeout ,来控制点击多少秒才能在触发;其实 通过 CSS 也能达到 「节流」 的目的,下面…...
UE官方教程笔记03-功能、术语、操作简介
对官方教程视频[官方培训]03-UE功能、术语、操作简介 | 徐良安 Epic的笔记这一部分基本都是走马观花的简单介绍功能世界创建建模Mesh editingtool是一个全新的建模工具,具备大多数的主流建模软件的核心功能HOUDINI ENGINE FOR UNREALHoudini编辑器,可以用…...
BN,LN,IN,GN的理解和用法
绿色区域表示将该区域作用域(四种方法都贯穿了w,h维度),即将该区域数值进行归一化,变为均值为0,标准差为1。BN的作用区域时N,W,H,表示一个batch数据的每一个通道均值为0,标准差为1;LN则是让每个数据的所有channel的均值…...
Linux:epoll模式web服务器代码,代码debug
源码: https://blog.csdn.net/weixin_44718794/article/details/107206136 修改的地方: 修改后代码: #include <stdio.h> #include <unistd.h> #include <stdlib.h> //#include “epoll_server.h” #ifndef _EPOLL_SER…...
SpringSecurity学习(四)密码加密、RememberMe记住我
文章目录密码加密一、简介密码为什么要加密常见的加密解决方案PasswordEncoder详解DelegatingPasswordEncoder二、自定义加密方式1. 使用灵活的密码加密方案(BCryptPasswordEncoder)加密验证(推荐)需要在密码前指定加密类型{bcryp…...
vue专项练习
一、循环实现一个列表的展示及删除功能 1.1 列表展示 1、背景: 完成一个这样的列表展示。使用v-for 循环功能 id接口名称测试人员项目名项目ID描述信息创建时间用例数1首页喵酱发财项目a1case的描述信息2019/11/6 14:50:30102个人中心张三发财项目a1case的描述信…...
【笔试题】百度+美团
发工资 链接:https://www.nowcoder.com/questionTerminal/e47cffeef25d43e3b16c11c9b28ac7e8 来源:牛客网 小度新聘请了一名员工牛牛, 每个月小度需要给牛牛至少发放m元工资(给牛牛发放的工资可以等于m元或者大于m元, 不能低于m)。 小度有一些钞票资金…...
【8.索引篇】
索引分类 索引和数据就是位于存储引擎中: 按「数据结构」分类:Btree索引、Hash索引、Full-text索引。按「物理存储」分类:聚簇索引(主键索引)、二级索引(辅助索引)。按「字段特性」分类&#…...
MySQL InnoDB存储引擎锁与事务实现原理解析(未完成)
InnoDB MySQL存储引擎是基于表的,也就是说每张表可以选择不同的存储引擎。 InnoDB存储引擎的表是索引组织的,也就是数据即索引。 存储引擎文件 InnoDB引擎会包含RedoLog重做日志文件和TableSpace表空间文件。 表空间文件 默认表空间文件(…...
P1683 入门(洛谷)JAVA
题目描述: 不是任何人都可以进入桃花岛的,黄药师最讨厌像郭靖一样呆头呆脑的人。所以,他在桃花岛的唯一入口处修了一条小路,这条小路全部用正方形瓷砖铺设而成。有的瓷砖可以踩,我们认为是安全的,而有的瓷砖…...
yocto编译烧录和脚本解析
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录前言一、初始化构建目录二、imx-setup-release.sh脚本解析三、编译单独编译内核四、烧录总结前言 本篇文章主要讲解如何在下载好源码之后进行编译和yocto的脚本解析…...
Proteus 8.15安装包安装教程
Proteus介绍Proteus的介绍Proteus8.15安装包Proteus8.15安装教程Proteus的介绍 Proteus是英国著名的EDA工具(仿真软件),从原理图布图、代码调试到单片机与外围电路协同仿真,一键切换到PCB设计,真正实现了从概念到产品的完整设计。是世界上唯…...
Spring——AOP工作流程
AOP就是代理模式的开发简化 1.Spring容器启动 因为AOP是要将通知类作为一个bean对象交给spring进行管理的,还有经过通知类被增强的类。 此时还没有创建bean对象 2.读取所有切面配置中的切入点 在下面这段代码中,定义了两个切入点,但是只…...
c++11多线程之condition_variable、wait()、notify_one()、notify_all()的使用。
系列文章目录 文章目录系列文章目录前言一、基本概念1.1 std::condition_variable1.2 wait()函数1.2.1 wait()带第二个参数1.2.2 wait()不带第二个参数1.2.3 当其他线程用notify_one()或notify_all()1.3 notify函数二、代码实例总结前言 C11多线程&…...
skywalking扩展实现 —— 监控数据的动态上报
把标题名整高大上一些,来掩盖需求的奇葩。 0. 目录1. 需求背景2. 需求描述3. 优势4. 实现4.1 扩展点4.2 配置项5. 优化6. 提醒7. 补充 - 关于微服务8. 参考1. 需求背景 过去一段时间,接手了一个迭代了数年的"基于微服务架构"搭建的产品。 自…...
【GoF 23】23种设计模式与OOP七大原则概述
1. 什么是GoF 23? GoF 23也就是23种设计模式。1995年GoF(Gang of Four,四人组/四人帮)合作出版了《设计模式:可复用面向对象软件的基础》一书,一共收录了23种设计模式,从此梳理了软件设计模式领…...
在软件开发中正确使用MySQL日期时间类型的深度解析
在日常软件开发场景中,时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志,到供应链系统的物流节点时间戳,时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库,其日期时间类型的…...
【Linux】shell脚本忽略错误继续执行
在 shell 脚本中,可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行,可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令,并忽略错误 rm somefile…...
【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密
在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...
Go 语言接口详解
Go 语言接口详解 核心概念 接口定义 在 Go 语言中,接口是一种抽象类型,它定义了一组方法的集合: // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的: // 矩形结构体…...
为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?
在建筑行业,项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升,传统的管理模式已经难以满足现代工程的需求。过去,许多企业依赖手工记录、口头沟通和分散的信息管理,导致效率低下、成本失控、风险频发。例如&#…...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...
C++ 基础特性深度解析
目录 引言 一、命名空间(namespace) C 中的命名空间 与 C 语言的对比 二、缺省参数 C 中的缺省参数 与 C 语言的对比 三、引用(reference) C 中的引用 与 C 语言的对比 四、inline(内联函数…...
sqlserver 根据指定字符 解析拼接字符串
DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...
关键领域软件测试的突围之路:如何破解安全与效率的平衡难题
在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件,这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下,实现高效测试与快速迭代?这一命题正考验着…...
Spring是如何解决Bean的循环依赖:三级缓存机制
1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间互相持有对方引用,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...
