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

面试题 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.length100000

分析:前缀和 + 哈希表

我们可以将 字母看作是 +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 题目描述 给定一个放有字母和数字的数组&#xff0c;找到最长的子数组&#xff0c;且包含的字母和数字的个数相同。 返回该子数组&#xff0c;若存在多个最长子数组&#xff0c;返回左端点下标值最小的子数组。若不存在这样的数组&…...

解决Win10图片/文件右键单击自动退出并刷新桌面问题

问题描述 这两天开始不知道怎么回事儿&#xff0c;右键选择图片时候&#xff0c;电脑黑屏且资源管理器自动重启。然后我就开始找很多方法去解决。 我试了很多种复杂的简单的方法&#xff0c;但是只有一种解决了我的问题。 解决方案【解决我的问题】 这个方法如下&#xff1…...

【代码随想录训练营】【Day39】第九章|动态规划|62.不同路径|63. 不同路径 II

不同路径 题目详细&#xff1a;LeetCode.62 有点简单呀&#xff0c;做类似这种题型时&#xff0c;最好就是先画图&#xff1a; 可以像题目一样&#xff0c;画一个二维表格&#xff0c;表格内的值代表到达这个格子的不同路径总数那么已知&#xff0c;如果图的大小为m 1 || n…...

【Linux】linux | 修改系统编码 |  增加字体处理 | 图片处理字体变成方块

一、说明1、CentOS7二、修改系统编码编辑文件vi /etc/locale.conf修改编码并保存LANGzh_CN.UTF-8配置生效source /etc/locale.conf1&#xff09;修改系统编码&#xff0c;只是让系统支持中文编码2&#xff09;不解决文字不显示的问题&#xff1b;往后看三、解决字体不显示问题非…...

R语言介绍及安装教程

R语言是一种免费的开源编程语言和环境&#xff0c;主要用于数据分析、统计建模和可视化。它可以运行在不同的操作系统上&#xff0c;如Windows、MacOS和Linux。R语言具有以下特点&#xff1a;丰富的数据处理和统计分析函数库&#xff1b;易于学习和使用&#xff1b;可以生成高质…...

Linux 练习九 (IPC 消息队列)

文章目录消息队列有亲缘关系的进程使用消息队列通信无亲缘关系的进程使用消息队列通信使用环境&#xff1a;Ubuntu18.04 使用工具&#xff1a;VMWare workstations &#xff0c;xshell作者在学习Linux的过程中对常用的命令进行记录&#xff0c;通过思维导图的方式梳理知识点&am…...

在Win 11下使用Visual Studio 2019和cygwin编译JBR(Java SDK 17)源码

很多文章介绍了JDK 8和JDK11源码在Linux编译&#xff0c;很少有人介绍了JDK 17在windows的编译过程&#xff0c;所以写了这篇文章&#xff0c;为什么选用JBR 17版本&#xff0c;因为JBR17 版本集成了HotSwapAgent功能&#xff0c;具体HotSwapAgent有什么用&#xff0c;请看我前…...

java基础学习 day51 (匿名内部类)

1. 什么是匿名内部类&#xff1f; 隐藏了名字的内部类&#xff0c;实际名字为&#xff1a;外部类名$序号可以写在成员位置&#xff0c;为没有名字的成员内部类也可以写在局部位置&#xff0c;为没有名字的局部内部类 2. 匿名内部类的格式&#xff1f; new 类名/接口名() { 重…...

Spring MVC程序开发(三大功能)

文章目录一、什么是Spring MVC?1.MVC定义2.MVC与Spring MVC的关系3.创建方式二、Spring MVC的核心功能1.连接功能浏览器获取前端接口和后端程序连接功能实现get和post的区别Spring Boot热部署2.获取参数&#xff08;1&#xff09;传递单个参数&#xff08;2&#xff09;传递对…...

stack,queue

stack,queuestack的介绍和使用介绍使用模拟实现queue的介绍和使用介绍使用模拟实现priority_queue的介绍和使用介绍使用模拟实现容器适配器概念标准库中stack&#xff0c;queue的底层结构介绍deque原理缺陷deque作为stack,queue底层默认容器stack的介绍和使用 介绍 stack是适…...

shiro反序列化

shiro550反序列化 | 清风的博客这个看着更舒服点 环境搭建 JDK&#xff1a;1.7 Tomcat&#xff1a;8.5.83 shiro源码&#xff1a;下载地址&#xff1a;https://codeload.github.com/apache/shiro/zip/shiro-root-1.2.4 shiro war包&#xff1a;下载地址SHIRO-550/samples-…...

【GoF 23 概念理解】IoC/DI(控制反转/依赖注入)

搞清楚以下几个问题你就明白什么是 IoC/DI 了&#xff1a; 参与者都有谁&#xff1f;依赖&#xff1a;谁依赖于谁&#xff1f;为什么要依赖&#xff1f;注入&#xff1a;谁注入于谁&#xff1f;到底注入什么&#xff1f;控制反转&#xff1a;谁控制谁&#xff1f;控制什么&…...

stm32外设-GPIO

0. 写在最前 本栏目笔记都是基于stm32F10x 1. GPIO基本介绍 GPIO—general purpose intput output 是通用输入输出端口的简称&#xff0c;简单来说就是软件可控制的引脚&#xff0c; STM32芯片的GPIO引脚与外部设备连接起来&#xff0c;从而实现与外部通讯、控制以及数据采集的…...

AfxMessageBox 自定义封装

一般情况下AfxMessageBox是系统提供的一个对话框&#xff0c;若要做这种效果的&#xff0c;必须重写。 实例1&#xff1a; void test_SgxMemDialog_AutoSize() { //使用给定大小的对话框 CSgxMemDialog dlg(180, 60); dlg.SetWindowTitle(_T(" SegeX - CT&qu…...

登入vCenter显示503,证书过期解决办法

登入vCenter显示503 原因&#xff1a;当安全令牌服务 &#xff08;STS&#xff09; 证书已过期时&#xff0c;会出现这些问题。这会导致内部服务和解决方案用户无法获取有效令牌&#xff0c;从而导致无法按预期运行&#xff08;证书两年后就会过期&#xff09;。 解决办法&…...

设计模式(十九)----行为型模式之命令模式

1、概述 日常生活中&#xff0c;我们出去吃饭都会遇到下面的场景。 定义&#xff1a; 将一个请求封装为一个对象&#xff0c;使发出请求的责任和执行请求的责任分割开。这样两者之间通过命令对象进行沟通&#xff0c;这样方便将命令对象进行存储、传递、调用、增加与管理。命…...

【数据库】数据库基础架构

数据库架构 数据库对于后端程序员来说是每天都需要打交道的系统&#xff0c;因此了解并掌握MySQL底层原理是必须的。 基础架构图 MySQL内部分为两层&#xff0c;一个是Server层&#xff0c;另一个是存储引擎层&#xff0c;而我们常用的就是MyISAM、InnoDB&#xff0c;主要负…...

English Learning - L2 语音作业打卡 双元音 [ɔɪ] [ɪə] Day16 2023.3.8 周三

English Learning - L2 语音作业打卡 双元音 [ɔɪ] [ɪə] Day16 2023.3.8 周三&#x1f48c;发音小贴士&#xff1a;&#x1f48c;当日目标音发音规则/技巧:&#x1f36d; Part 1【热身练习】&#x1f36d; Part2【练习内容】&#x1f36d;【练习感受】&#x1f353;元音 [ɔ…...

C++语法规则4(C++面向对象)

接口&#xff08;抽象类&#xff09; 接口描述了类的行为和功能&#xff0c;而不需要完成类的特定实现。C 接口是使用抽象类来实现的&#xff0c;抽象类与数据抽象互不混淆&#xff0c;数据抽象是一个把实现细节与相关的数据分离开的概念。 如果类中至少有一个函数被声明为纯虚…...

【Spring 深入学习】AOP的前世今生之后续

AOP的前世今生之后续 1. 概述 上篇文章【Spring 深入学习】AOP的前世今生之代理模式我们讲述了代理模式。而我们今天的主人公AOP就是基于代理模式实现的&#xff0c;所以我们今天会简单学习下AOP 2. 什么是AOP 是面向切面编程&#xff0c;一般可以帮助我们在不修改现有代码的情…...

手游刚开服就被攻击怎么办?如何防御DDoS?

开服初期是手游最脆弱的阶段&#xff0c;极易成为DDoS攻击的目标。一旦遭遇攻击&#xff0c;可能导致服务器瘫痪、玩家流失&#xff0c;甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案&#xff0c;帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

GruntJS-前端自动化任务运行器从入门到实战

Grunt 完全指南&#xff1a;从入门到实战 一、Grunt 是什么&#xff1f; Grunt是一个基于 Node.js 的前端自动化任务运行器&#xff0c;主要用于自动化执行项目开发中重复性高的任务&#xff0c;例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...

无人机侦测与反制技术的进展与应用

国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机&#xff08;无人驾驶飞行器&#xff0c;UAV&#xff09;技术的快速发展&#xff0c;其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统&#xff0c;无人机的“黑飞”&…...

认识CMake并使用CMake构建自己的第一个项目

1.CMake的作用和优势 跨平台支持&#xff1a;CMake支持多种操作系统和编译器&#xff0c;使用同一份构建配置可以在不同的环境中使用 简化配置&#xff1a;通过CMakeLists.txt文件&#xff0c;用户可以定义项目结构、依赖项、编译选项等&#xff0c;无需手动编写复杂的构建脚本…...