云浮哪有公司做网站的/免费永久注册顶级域名网站
前缀和
前缀和指数组的前 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种设计模式,从此梳理了软件设计模式领…...

Java 日期时间
Java 日期时间是 Java 标准库中一个非常重要的部分,它提供了丰富的 API 来处理日期、时间以及日期时间。在 Java 应用程序中,我们经常需要处理日期时间相关的操作,例如计算两个日期之间的差、将日期时间转换为不同的时区等。在本篇文章中&…...

Face Forgery Suvery
文章目录Face ForgeryFace Forgery classAttribute ManipulationExpression SwapIdentity SwapEntire Face SynthesisFace Forgery DetectionLow-levelOn the Detection of Digital Face Manipulation(CVPR2020)High-levelProtecting World Leaders Against Deep FakesDetectin…...

案例学习--016 消息队列作用和意义
简介MQ全称为Message Queue, 是一种分布式应用程序的的通信方法,它是消费-生产者模型的一个典型的代表,producer往消息队列中不断写入消息,而另一端consumer则可以读取或者订阅队列中的消息。主要产品有:ActiveMQ、RocketMQ、Rabb…...

【MySQL】MySQL的锁机制
目录 概述 MyISAM 表锁 InnoDB行锁 概述 锁是计算机协调多个进程或线程并发访问某一资源的机制(避免争抢)。 在数据库中,除传统的 计算资源(如 CPU、RAM、I/O 等)的争用以外,数据也是一种供许多用户共…...

HTML 背景
一个富有美感的背景会让站点看上去更加高级、更有吸引力。本篇为大家来的是 HTML 背景相关内容。 背景(Backgrounds) <body> 拥有两个配置背景的标签。背景可以是颜色或者图像。 背景颜色(Bgcolor) 背景颜色属性将背景设…...

Lombok
文章目录简介原理安装常用Getter、SetterToStringEqualsAndHashCodeNonNullNoArgsConstructor、RequiredArgsConstructor、AllArgsConstructorDATABuilderLogvalCleanup简介 Project Lombok is a java library that automatically plugs into your editor and build tools, spi…...

Koa源码学习
前言 koa是一个非常流行的Node.js http框架。本文我们来学习下它的使用和相关源码 来自官网的介绍: Koa 是一个新的 web 框架,由 Express 幕后的原班人马打造, 致力于成为 web 应用和 API 开发领域中的一个更小、更富有表现力、更健壮的基石。…...

一种延迟加载自定义元素的方法
您可能实际上并不需要所有这些;通常有一个更简单的方法。如果有意使用,此处显示的技术可能仍然对您的工具集有用。 为了保持一致性,我们希望我们的自动加载器也成为一个自定义元素——这也意味着我们可以通过 HTML 轻松配置它。但首先&#…...

Pytho经典面试题荟萃:第一期
目录 一、面试题 二、参考答案 解释器和编译器的区别 解释器 编译器 Python 的解释过程 Python 内存管理 Python 内存分配 引用计数 垃圾回收 其他内存管理技术 多重继承 多重继承带来的问题 命名冲突 菱形继承问题 解决多重继承带来的问题 方法重写 调用 su…...

01背包问题(大彻大悟版)
背包问题身为一个非常经典的动态规划问题,理清思路很重要,在经过多次观看y总视频和b站解析,加上CSDN的文章辅助,我终于从很多不理解到大彻大悟,下面是我对于背包问题思路的总结,有问题的话欢迎指出。谈到背…...