当前位置: 首页 > news >正文

云浮哪有公司做网站的/免费永久注册顶级域名网站

云浮哪有公司做网站的,免费永久注册顶级域名网站,嘉兴城乡建设厅网站,建立一个网站要多久前缀和 前缀和指数组的前 N项之和,是个比较基础的算法 例题 面试题 17.05. 字母与数字 给定一个放有字母和数字的数组,找到最长的子数组,且包含的字母和数字的个数相同。 返回该子数组,若存在多个最长子数组,返回左…

前缀和

前缀和指数组的前 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项之和&#xff0c;是个比较基础的算法 例题 面试题 17.05. 字母与数字 给定一个放有字母和数字的数组&#xff0c;找到最长的子数组&#xff0c;且包含的字母和数字的个数相同。 返回该子数组&#xff0c;若存在多个最长子数组&#xff0c;返回左…...

三天吃透MySQL面试八股文

本文已经收录到Github仓库&#xff0c;该仓库包含计算机基础、Java基础、多线程、JVM、数据库、Redis、Spring、Mybatis、SpringMVC、SpringBoot、分布式、微服务、设计模式、架构、校招社招分享等核心知识点&#xff0c;欢迎star~ Github地址&#xff1a;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是如何根据成本优化选择执行计划的?(中)

上次我们讲完了全表扫描的成本计算方法&#xff0c;相信大家应该都理解了&#xff0c;其实还是比较简单的&#xff0c;今天我们来讲一下索引的成本计算方法&#xff0c;因为除了全表扫描之外&#xff0c;还可能多个索引都可以使用&#xff0c;但是当然同时一般只能用一个索引&a…...

原来CSS 也可以节流啊

Ⅰ、前言 「节流」 是为了减少请求的触发频率&#xff0c;不让用户点的太快&#xff0c;达到节省资源的目的 &#xff1b;通常 我们采用 JS 的 定时器 setTimeout &#xff0c;来控制点击多少秒才能在触发&#xff1b;其实 通过 CSS 也能达到 「节流」 的目的&#xff0c;下面…...

UE官方教程笔记03-功能、术语、操作简介

对官方教程视频[官方培训]03-UE功能、术语、操作简介 | 徐良安 Epic的笔记这一部分基本都是走马观花的简单介绍功能世界创建建模Mesh editingtool是一个全新的建模工具&#xff0c;具备大多数的主流建模软件的核心功能HOUDINI ENGINE FOR UNREALHoudini编辑器&#xff0c;可以用…...

BN,LN,IN,GN的理解和用法

绿色区域表示将该区域作用域(四种方法都贯穿了w,h维度)&#xff0c;即将该区域数值进行归一化&#xff0c;变为均值为0&#xff0c;标准差为1。BN的作用区域时N,W,H,表示一个batch数据的每一个通道均值为0&#xff0c;标准差为1&#xff1b;LN则是让每个数据的所有channel的均值…...

Linux:epoll模式web服务器代码,代码debug

源码&#xff1a; https://blog.csdn.net/weixin_44718794/article/details/107206136 修改的地方&#xff1a; 修改后代码&#xff1a; #include <stdio.h> #include <unistd.h> #include <stdlib.h> //#include “epoll_server.h” #ifndef _EPOLL_SER…...

SpringSecurity学习(四)密码加密、RememberMe记住我

文章目录密码加密一、简介密码为什么要加密常见的加密解决方案PasswordEncoder详解DelegatingPasswordEncoder二、自定义加密方式1. 使用灵活的密码加密方案&#xff08;BCryptPasswordEncoder&#xff09;加密验证&#xff08;推荐&#xff09;需要在密码前指定加密类型{bcryp…...

vue专项练习

一、循环实现一个列表的展示及删除功能 1.1 列表展示 1、背景&#xff1a; 完成一个这样的列表展示。使用v-for 循环功能 id接口名称测试人员项目名项目ID描述信息创建时间用例数1首页喵酱发财项目a1case的描述信息2019/11/6 14:50:30102个人中心张三发财项目a1case的描述信…...

【笔试题】百度+美团

发工资 链接&#xff1a;https://www.nowcoder.com/questionTerminal/e47cffeef25d43e3b16c11c9b28ac7e8 来源&#xff1a;牛客网 小度新聘请了一名员工牛牛, 每个月小度需要给牛牛至少发放m元工资(给牛牛发放的工资可以等于m元或者大于m元, 不能低于m)。 小度有一些钞票资金…...

【8.索引篇】

索引分类 索引和数据就是位于存储引擎中&#xff1a; 按「数据结构」分类&#xff1a;Btree索引、Hash索引、Full-text索引。按「物理存储」分类&#xff1a;聚簇索引&#xff08;主键索引&#xff09;、二级索引&#xff08;辅助索引&#xff09;。按「字段特性」分类&#…...

MySQL InnoDB存储引擎锁与事务实现原理解析(未完成)

InnoDB MySQL存储引擎是基于表的&#xff0c;也就是说每张表可以选择不同的存储引擎。 InnoDB存储引擎的表是索引组织的&#xff0c;也就是数据即索引。 存储引擎文件 InnoDB引擎会包含RedoLog重做日志文件和TableSpace表空间文件。 表空间文件 默认表空间文件&#xff08…...

P1683 入门(洛谷)JAVA

题目描述&#xff1a; 不是任何人都可以进入桃花岛的&#xff0c;黄药师最讨厌像郭靖一样呆头呆脑的人。所以&#xff0c;他在桃花岛的唯一入口处修了一条小路&#xff0c;这条小路全部用正方形瓷砖铺设而成。有的瓷砖可以踩&#xff0c;我们认为是安全的&#xff0c;而有的瓷砖…...

yocto编译烧录和脚本解析

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录前言一、初始化构建目录二、imx-setup-release.sh脚本解析三、编译单独编译内核四、烧录总结前言 本篇文章主要讲解如何在下载好源码之后进行编译和yocto的脚本解析…...

Proteus 8.15安装包安装教程

Proteus介绍Proteus的介绍Proteus8.15安装包Proteus8.15安装教程Proteus的介绍 Proteus是英国著名的EDA工具(仿真软件)&#xff0c;从原理图布图、代码调试到单片机与外围电路协同仿真&#xff0c;一键切换到PCB设计&#xff0c;真正实现了从概念到产品的完整设计。是世界上唯…...

Spring——AOP工作流程

AOP就是代理模式的开发简化 1.Spring容器启动 因为AOP是要将通知类作为一个bean对象交给spring进行管理的&#xff0c;还有经过通知类被增强的类。 此时还没有创建bean对象 2.读取所有切面配置中的切入点 在下面这段代码中&#xff0c;定义了两个切入点&#xff0c;但是只…...

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&#xff08;&#xff09;1.3 notify函数二、代码实例总结前言 C11多线程&…...

skywalking扩展实现 —— 监控数据的动态上报

把标题名整高大上一些&#xff0c;来掩盖需求的奇葩。 0. 目录1. 需求背景2. 需求描述3. 优势4. 实现4.1 扩展点4.2 配置项5. 优化6. 提醒7. 补充 - 关于微服务8. 参考1. 需求背景 过去一段时间&#xff0c;接手了一个迭代了数年的"基于微服务架构"搭建的产品。 自…...

【GoF 23】23种设计模式与OOP七大原则概述

1. 什么是GoF 23&#xff1f; GoF 23也就是23种设计模式。1995年GoF&#xff08;Gang of Four&#xff0c;四人组/四人帮&#xff09;合作出版了《设计模式&#xff1a;可复用面向对象软件的基础》一书&#xff0c;一共收录了23种设计模式&#xff0c;从此梳理了软件设计模式领…...

Java 日期时间

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

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, 是一种分布式应用程序的的通信方法&#xff0c;它是消费-生产者模型的一个典型的代表&#xff0c;producer往消息队列中不断写入消息&#xff0c;而另一端consumer则可以读取或者订阅队列中的消息。主要产品有&#xff1a;ActiveMQ、RocketMQ、Rabb…...

【MySQL】MySQL的锁机制

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

HTML 背景

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

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框架。本文我们来学习下它的使用和相关源码 来自官网的介绍&#xff1a; Koa 是一个新的 web 框架&#xff0c;由 Express 幕后的原班人马打造&#xff0c; 致力于成为 web 应用和 API 开发领域中的一个更小、更富有表现力、更健壮的基石。…...

一种延迟加载自定义元素的方法

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

Pytho经典面试题荟萃:第一期

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

01背包问题(大彻大悟版)

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