【每日一题Day143】面试题 17.05. 字母与数字 | 前缀和+哈希表
面试题 17.05. 字母与数字
给定一个放有字母和数字的数组,找到最长的子数组,且包含的字母和数字的个数相同。
返回该子数组,若存在多个最长子数组,返回左端点下标值最小的子数组。若不存在这样的数组,返回一个空数组。
和昨天的很像呀,但是我在数组拷贝的时候 写成了res[i]=array[i],然后一直越界,找了半天bug,真的有被自己蠢到。。。。
-
思路:
将字符串数组转化为前缀和数组,为字母的记为1分,为数字的记为-1分,那么当连续子数组的总分为0时,该子数组包含的字母和数字的个数相同。
-
实现
- 统计前缀和数组,对于每一个右边界,此时的前缀和记为
sum,寻找合法的左边界,当左边界的前缀和也为sum时,子数组array[left,right]中字母和数字的个数相同,记录最长合法子数组的左右边界
class Solution {public String[] findLongestSubarray(String[] array) {int n = array.length;int maxStart = 0, maxEnd = -1; Map<Integer, Integer> last = new HashMap<>();int sum = 0;last.put(0, 0);for (int i = 0; i < n; i++){if (Character.isLetter(array[i].charAt(0))){sum += 1;}else{sum -= 1; } if (last.containsKey(sum)){int j = last.get(sum);if (i + 1 - j > maxEnd - maxStart){maxEnd = i + 1;maxStart = j;} }else{last.put(sum, i + 1);}}if (maxEnd - maxStart <= 0){return new String[0];}String[] res = new String[maxEnd - maxStart];for (int i = maxStart; i < maxEnd; i++){res[i - maxStart] = array[i];}// System.arraycopy(array, maxStart, res, 0, maxEnd - maxStart);// return Arrays.copyOfRange(array, maxStart, maxEnd);return res;} }- 复杂度
- 时间复杂度:O(n)O(n)O(n)
- 空间复杂度:O(n)O(n)O(n)
- 统计前缀和数组,对于每一个右边界,此时的前缀和记为
相关文章:
【每日一题Day143】面试题 17.05. 字母与数字 | 前缀和+哈希表
面试题 17.05. 字母与数字 给定一个放有字母和数字的数组,找到最长的子数组,且包含的字母和数字的个数相同。 返回该子数组,若存在多个最长子数组,返回左端点下标值最小的子数组。若不存在这样的数组,返回一个空数组。…...
Go 内置运算符 if for switch
算数运算符fmt.Println("103", 103) //103 13 fmt.Println("10-3", 10-3) //10-3 7 fmt.Println("10*3", 10*3) //10*3 30 //除法注意:如果运算的数都是整数,那么除后,去掉小数部分,保留整数部分 f…...
C语言指针数组实际应用(嵌入式)
C语言指针数组详细学习 指针是C语言中非常重要的概念之一,它可以让我们直接访问内存中的数据。指针数组则是由多个指针组成的数组,每个指针都可以指向内存中的某个位置。以下是一些指针数组的实际代码应用: 字符串数组 char* names[] {&q…...
常用的Java注解详解
Java是一种常用的编程语言,而注解是Java语言中非常重要的一部分。在这篇文章中,我们将介绍一些常用的Java注解,以及它们的作用和使用方法。 Override override注解是用于表示一个方法是被覆盖的。在Java中,如果子类要覆盖父类的方…...
华为OD机试题 - 第 K 个最小码值的字母(JavaScript)| 机考必刷
更多题库,搜索引擎搜 梦想橡皮擦华为OD 👑👑👑 更多华为OD题库,搜 梦想橡皮擦 华为OD 👑👑👑 更多华为机考题库,搜 梦想橡皮擦华为OD 👑👑👑 华为OD机试题 最近更新的博客使用说明本篇题解:第 K 个最小码值的字母题目输入输出示例一输入输出说明示例一输…...
vscode环境配置(支持跳转,阅读linux kernel)
目录 1.卸载clangd插件 2.安装C插件 3. 搜索框内输入 “intell”,将 C_Cpp:Intelli Sense Engine 开关设置为 Default。 4.ubuntu安装global工具 5.vscode安装插件 6.验证是否生效 7.建立索引 1.卸载clangd插件 在插件管理中卸载clangd插件 2.安…...
zigbee学习笔记:IO操作
1、IAR新建工程 (1)Projetc→Create New Projetc→OK→选择位置,确定 (2)新建一个c文件,保存在路径中 (3)点击工程,右键→add→加入c文件 (4)…...
华为OD机试题 - 最少数量线段覆盖(JavaScript)| 机考必刷
更多题库,搜索引擎搜 梦想橡皮擦华为OD 👑👑👑 更多华为OD题库,搜 梦想橡皮擦 华为OD 👑👑👑 更多华为机考题库,搜 梦想橡皮擦华为OD 👑👑👑 华为OD机试题 最近更新的博客使用说明本篇题解:最少数量线段覆盖题目输入输出示例一输入输出说明Code解题思路版…...
python趣味编程-2048游戏
在上一期我们用Python实现了一个盒子追逐者的游戏,这一期我们继续使用Python实现一个简单的2048游戏,让我们开始今天的旅程吧~ 在 Python 免费源代码中使用 Tkinter 的简单 2048 游戏 使用 Tkinter 的简单 2048 游戏是一个用Python编程语言编码的桌面游…...
求解完全背包问题
题目描述实现一个算法求解完全背包问题。完全背包问题的介绍如下:已知一个容量为 totalweight 的背包,有不同重量不同价值的物品,问怎样在背包容量限制下达到利益最大化。完全背包问题的每个物品可以无限选用背包问题求解方法的介绍如下&…...
我们为什么使用docker 优点 作用
1. 我们为什么使用Docker? 当我们在工作中,一款产品从开发设计到上线运行,其中需要开发人员和运维工程师,开发人员负责代码编写,开发产品,运维工程师需要测试环境,产品部署。这之间就会有分歧。 就好比我…...
Python每日一练(20230311)
目录 1. 合并两个有序数组 2. 二叉树的右视图 3. 拼接最大数 🌟 每日一练刷题专栏 C/C 每日一练 专栏 Python 每日一练 专栏 1. 合并两个有序数组 给你两个有序整数数组 nums1 和 nums2,请你将 nums2 合并到 nums1 中,使 nums1 成为…...
202109-3 CCF 脉冲神经网络 66分题解 + 解题思路 + 解题过程
解题思路 根据题意,脉冲源的阈值大于随机数时,会向其所有出点发送脉冲 神经元当v>30时,会向其所有出点发送脉冲,unordered_map <int, vector > ne; //存储神经元/脉冲源的所有出点集合vector 所有脉冲会有一定的延迟&am…...
Aurora简介
Amazon Aurora是一种兼容MySQL和PostgreSQL的商用级别关系数据库,它既有商用数据库的性能和可用性(比如Oracle数据库),又具有开源数据库的成本效益(比如MySQL数据库)。 Aurora的速度可以达到MySQL数据库的…...
【python实操】用python写软件弹窗
文章目录前言组件label 与 多行文本复选框组件Radiobutton单选组件Frame框架组件labelframe标签框架列表框Listboxscrollbar滚动条组件scale刻度条组件spinbox组件Toplevel子窗体组件PanedWindow组件Menu下拉菜单弹出菜单总结针对组件前言 python学习之路任重而道远࿰…...
Ubuntu 常用操作
版本22.04 1、开启 root # 输入新密码 sudo passwd rootUbuntu以root账号登录桌面 默认情况是不允许用root帐号直接登录图形界面的。 Ubuntu 默认使用 GNOME,GNOME 使用 GDM 显示管理器。 为了允许以 root 身份登录到 GNOME,你需要对位于 /etc/…...
井字棋--课后程序(Python程序开发案例教程-黑马程序员编著-第7章-课后作业)
实例2:井字棋 井字棋是一种在3 * 3格子上进行的连珠游戏,又称井字游戏。井字棋的游戏有两名玩家,其中一个玩家画圈,另一个玩家画叉,轮流在3 * 3格子上画上自己的符号,最先在横向、纵向、或斜线方向连成一条…...
谷粒学院开发(三):统一日志、异常及前端准备工作
特定异常处理 ControllerAdvice public class GlobalExceptionHandler {ExceptionHandler(Exception.class) // 指定出现什么异常会被处理ResponseBody // 为了能够返回数据public R error(Exception e) {e.printStackTrace();return R.error().message("执行了全局异常…...
华为OD机试题 - 招聘(JavaScript)| 机考必刷
更多题库,搜索引擎搜 梦想橡皮擦华为OD 👑👑👑 更多华为OD题库,搜 梦想橡皮擦 华为OD 👑👑👑 更多华为机考题库,搜 梦想橡皮擦华为OD 👑👑👑 华为OD机试题 最近更新的博客使用说明本篇题解:招聘题目输入输出示例一输入输出说明示例二输入输出说明示例三输…...
关于SQL优化的几点说明
1. ORACLE DBA是如何进行SQL优化的 作为一个Oracle数据库管理员(DBA),SQL优化是他们的日常工作之一,主要目标是优化查询性能,减少查询时间,并提高数据库的整体性能。 以下是Oracle DBA如何进行SQL优化的一般流程: 监控…...
HTML 语义化
目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案: 语义化标签: <header>:页头<nav>:导航<main>:主要内容<article>&#x…...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...
centos 7 部署awstats 网站访问检测
一、基础环境准备(两种安装方式都要做) bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats࿰…...
STM32标准库-DMA直接存储器存取
文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA(Direct Memory Access)直接存储器存取 DMA可以提供外设…...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...
C++.OpenGL (10/64)基础光照(Basic Lighting)
基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...
【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)
骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术,它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton):由层级结构的骨头组成,类似于人体骨骼蒙皮 (Mesh Skinning):将模型网格顶点绑定到骨骼上,使骨骼移动…...
多模态大语言模型arxiv论文略读(108)
CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题:CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者:Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...
《C++ 模板》
目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板,就像一个模具,里面可以将不同类型的材料做成一个形状,其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式:templa…...
Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)
引言 在人工智能飞速发展的今天,大语言模型(Large Language Models, LLMs)已成为技术领域的焦点。从智能写作到代码生成,LLM 的应用场景不断扩展,深刻改变了我们的工作和生活方式。然而,理解这些模型的内部…...
