面试题 17.05. 字母与数字
题目链接
面试题 17.05. 字母与数字 mid
题目描述
给定一个放有字母和数字的数组,找到最长的子数组,且包含的字母和数字的个数相同。
返回该子数组,若存在多个最长子数组,返回左端点下标值最小的子数组。若不存在这样的数组,返回一个空数组。
示例 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≤100000array.length \leq 100000array.length≤100000
分析:前缀和 + 哈希表
我们可以将 字母看作是 +1,数字看作是 -1,那么原问题就转换为 求最长的一段和 sum = 0的子数组。
我们用一个哈希表 m来记录遍历过的 前缀和 s[i]和它对应的下标 i。
如果当前遍历到了 s[j],并且 m存在 s[j]这个键。由此,我们可以得到 i = m[s[j]]。那么 (i , j]这一段就是和为 0
的子数组,我们就将答案更新即可。
我们用 idx代表最长的那段子数组的起始下标,用 len表示最长的那段子数组的长度。
最后返回 array的这一段 [idx , idx + len]即可。
时间复杂度: O(n)O(n)O(n)
C++代码:
class Solution {
public:vector<string> findLongestSubarray(vector<string>& arr) {int n = arr.size();unordered_map<int,int> m{{0,-1}};int idx = 0 , len = 0;for(int j = 0 ,s = 0;j < n;j++){s += (arr[j][0] >= 'A' ? 1 : -1);if(m.count(s)){int i = m[s];if(j - i > len){len = j - i;idx = i + 1;}}else m[s] = j;}return vector<string> (arr.begin() + idx,arr.begin() + idx + len);}
};
Python代码:
class Solution:def findLongestSubarray(self, arr: List[str]) -> List[str]:m = {0:-1}s = idx = len = 0for j,str in enumerate(arr):s += 1 if str.isalpha() else -1if s in m:i = m[s]if len < j - i:idx = i + 1len = j - ielse:m[s] = j return arr[idx:idx+len]相关文章:
面试题 17.05. 字母与数字
题目链接 面试题 17.05. 字母与数字 mid 题目描述 给定一个放有字母和数字的数组,找到最长的子数组,且包含的字母和数字的个数相同。 返回该子数组,若存在多个最长子数组,返回左端点下标值最小的子数组。若不存在这样的数组&…...
解决Win10图片/文件右键单击自动退出并刷新桌面问题
问题描述 这两天开始不知道怎么回事儿,右键选择图片时候,电脑黑屏且资源管理器自动重启。然后我就开始找很多方法去解决。 我试了很多种复杂的简单的方法,但是只有一种解决了我的问题。 解决方案【解决我的问题】 这个方法如下࿱…...
【代码随想录训练营】【Day39】第九章|动态规划|62.不同路径|63. 不同路径 II
不同路径 题目详细:LeetCode.62 有点简单呀,做类似这种题型时,最好就是先画图: 可以像题目一样,画一个二维表格,表格内的值代表到达这个格子的不同路径总数那么已知,如果图的大小为m 1 || n…...
【Linux】linux | 修改系统编码 | 增加字体处理 | 图片处理字体变成方块
一、说明1、CentOS7二、修改系统编码编辑文件vi /etc/locale.conf修改编码并保存LANGzh_CN.UTF-8配置生效source /etc/locale.conf1)修改系统编码,只是让系统支持中文编码2)不解决文字不显示的问题;往后看三、解决字体不显示问题非…...
R语言介绍及安装教程
R语言是一种免费的开源编程语言和环境,主要用于数据分析、统计建模和可视化。它可以运行在不同的操作系统上,如Windows、MacOS和Linux。R语言具有以下特点:丰富的数据处理和统计分析函数库;易于学习和使用;可以生成高质…...
Linux 练习九 (IPC 消息队列)
文章目录消息队列有亲缘关系的进程使用消息队列通信无亲缘关系的进程使用消息队列通信使用环境:Ubuntu18.04 使用工具:VMWare workstations ,xshell作者在学习Linux的过程中对常用的命令进行记录,通过思维导图的方式梳理知识点&am…...
在Win 11下使用Visual Studio 2019和cygwin编译JBR(Java SDK 17)源码
很多文章介绍了JDK 8和JDK11源码在Linux编译,很少有人介绍了JDK 17在windows的编译过程,所以写了这篇文章,为什么选用JBR 17版本,因为JBR17 版本集成了HotSwapAgent功能,具体HotSwapAgent有什么用,请看我前…...
java基础学习 day51 (匿名内部类)
1. 什么是匿名内部类? 隐藏了名字的内部类,实际名字为:外部类名$序号可以写在成员位置,为没有名字的成员内部类也可以写在局部位置,为没有名字的局部内部类 2. 匿名内部类的格式? new 类名/接口名() { 重…...
Spring MVC程序开发(三大功能)
文章目录一、什么是Spring MVC?1.MVC定义2.MVC与Spring MVC的关系3.创建方式二、Spring MVC的核心功能1.连接功能浏览器获取前端接口和后端程序连接功能实现get和post的区别Spring Boot热部署2.获取参数(1)传递单个参数(2)传递对…...
stack,queue
stack,queuestack的介绍和使用介绍使用模拟实现queue的介绍和使用介绍使用模拟实现priority_queue的介绍和使用介绍使用模拟实现容器适配器概念标准库中stack,queue的底层结构介绍deque原理缺陷deque作为stack,queue底层默认容器stack的介绍和使用 介绍 stack是适…...
shiro反序列化
shiro550反序列化 | 清风的博客这个看着更舒服点 环境搭建 JDK:1.7 Tomcat:8.5.83 shiro源码:下载地址:https://codeload.github.com/apache/shiro/zip/shiro-root-1.2.4 shiro war包:下载地址SHIRO-550/samples-…...
【GoF 23 概念理解】IoC/DI(控制反转/依赖注入)
搞清楚以下几个问题你就明白什么是 IoC/DI 了: 参与者都有谁?依赖:谁依赖于谁?为什么要依赖?注入:谁注入于谁?到底注入什么?控制反转:谁控制谁?控制什么&…...
stm32外设-GPIO
0. 写在最前 本栏目笔记都是基于stm32F10x 1. GPIO基本介绍 GPIO—general purpose intput output 是通用输入输出端口的简称,简单来说就是软件可控制的引脚, STM32芯片的GPIO引脚与外部设备连接起来,从而实现与外部通讯、控制以及数据采集的…...
AfxMessageBox 自定义封装
一般情况下AfxMessageBox是系统提供的一个对话框,若要做这种效果的,必须重写。 实例1: void test_SgxMemDialog_AutoSize() { //使用给定大小的对话框 CSgxMemDialog dlg(180, 60); dlg.SetWindowTitle(_T(" SegeX - CT&qu…...
登入vCenter显示503,证书过期解决办法
登入vCenter显示503 原因:当安全令牌服务 (STS) 证书已过期时,会出现这些问题。这会导致内部服务和解决方案用户无法获取有效令牌,从而导致无法按预期运行(证书两年后就会过期)。 解决办法&…...
设计模式(十九)----行为型模式之命令模式
1、概述 日常生活中,我们出去吃饭都会遇到下面的场景。 定义: 将一个请求封装为一个对象,使发出请求的责任和执行请求的责任分割开。这样两者之间通过命令对象进行沟通,这样方便将命令对象进行存储、传递、调用、增加与管理。命…...
【数据库】数据库基础架构
数据库架构 数据库对于后端程序员来说是每天都需要打交道的系统,因此了解并掌握MySQL底层原理是必须的。 基础架构图 MySQL内部分为两层,一个是Server层,另一个是存储引擎层,而我们常用的就是MyISAM、InnoDB,主要负…...
English Learning - L2 语音作业打卡 双元音 [ɔɪ] [ɪə] Day16 2023.3.8 周三
English Learning - L2 语音作业打卡 双元音 [ɔɪ] [ɪə] Day16 2023.3.8 周三💌发音小贴士:💌当日目标音发音规则/技巧:🍭 Part 1【热身练习】🍭 Part2【练习内容】🍭【练习感受】🍓元音 [ɔ…...
C++语法规则4(C++面向对象)
接口(抽象类) 接口描述了类的行为和功能,而不需要完成类的特定实现。C 接口是使用抽象类来实现的,抽象类与数据抽象互不混淆,数据抽象是一个把实现细节与相关的数据分离开的概念。 如果类中至少有一个函数被声明为纯虚…...
【Spring 深入学习】AOP的前世今生之后续
AOP的前世今生之后续 1. 概述 上篇文章【Spring 深入学习】AOP的前世今生之代理模式我们讲述了代理模式。而我们今天的主人公AOP就是基于代理模式实现的,所以我们今天会简单学习下AOP 2. 什么是AOP 是面向切面编程,一般可以帮助我们在不修改现有代码的情…...
使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...
CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型
CVPR 2025 | MIMO:支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题:MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者:Yanyuan Chen, Dexuan Xu, Yu Hu…...
智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql
智慧工地管理云平台系统,智慧工地全套源码,java版智慧工地源码,支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求,提供“平台网络终端”的整体解决方案,提供劳务管理、视频管理、智能监测、绿色施工、安全管…...
python/java环境配置
环境变量放一起 python: 1.首先下载Python Python下载地址:Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个,然后自定义,全选 可以把前4个选上 3.环境配置 1)搜高级系统设置 2…...
测试markdown--肇兴
day1: 1、去程:7:04 --11:32高铁 高铁右转上售票大厅2楼,穿过候车厅下一楼,上大巴车 ¥10/人 **2、到达:**12点多到达寨子,买门票,美团/抖音:¥78人 3、中饭&a…...
Python爬虫(一):爬虫伪装
一、网站防爬机制概述 在当今互联网环境中,具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类: 身份验证机制:直接将未经授权的爬虫阻挡在外反爬技术体系:通过各种技术手段增加爬虫获取数据的难度…...
Axios请求超时重发机制
Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式: 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...
大模型多显卡多服务器并行计算方法与实践指南
一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...
微信小程序云开发平台MySQL的连接方式
注:微信小程序云开发平台指的是腾讯云开发 先给结论:微信小程序云开发平台的MySQL,无法通过获取数据库连接信息的方式进行连接,连接只能通过云开发的SDK连接,具体要参考官方文档: 为什么? 因为…...
Spring数据访问模块设计
前面我们已经完成了IoC和web模块的设计,聪明的码友立马就知道了,该到数据访问模块了,要不就这俩玩个6啊,查库势在必行,至此,它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据(数据库、No…...
