面试题 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 是面向切面编程,一般可以帮助我们在不修改现有代码的情…...
Linux应用开发之网络套接字编程(实例篇)
服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...
渲染学进阶内容——模型
最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...
【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表
1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...
Android15默认授权浮窗权限
我们经常有那种需求,客户需要定制的apk集成在ROM中,并且默认授予其【显示在其他应用的上层】权限,也就是我们常说的浮窗权限,那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...
深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南
🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...
C++八股 —— 单例模式
文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全(Thread Safety) 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性…...
C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。
1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj,再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...
HashMap中的put方法执行流程(流程图)
1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中,其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下: 初始判断与哈希计算: 首先,putVal 方法会检查当前的 table(也就…...
NPOI操作EXCEL文件 ——CAD C# 二次开发
缺点:dll.版本容易加载错误。CAD加载插件时,没有加载所有类库。插件运行过程中用到某个类库,会从CAD的安装目录找,找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库,就用插件程序加载进…...
Linux系统部署KES
1、安装准备 1.版本说明V008R006C009B0014 V008:是version产品的大版本。 R006:是release产品特性版本。 C009:是通用版 B0014:是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存:1GB 以上 硬盘…...
