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

面试经典150题——单词规律

"Don't wait. The time will never be just right." - Napoleon Hill

snow covered mountain under blue sky

1. 题目描述

2.  题目分析与解析

首先还是得把题目先读懂,我们直接来看看示例:

根据上面的示例,我们可以看出pattern其实就是表示单词出现的规律,每一种pattern中的字符表示一个单词。

就比如上面的示例一:

pattern="abba",对应于s,就可以发现 a = dogb = cat,这样pattern(abba)实际上就是对应了

(a=)dog(b=)cat(b=)cat(a=)dog

而这种映射关系是不可更改的,比如看示例二,开始a对应dog,b对应cat,但是当我们走到pattern的最后一个字符发现a等于 fish,而之前我们已经将 a=dog,所以此时映射失败就返回false。

2.1 思路一——hash映射表

根据上面的读题以及上一篇文章,我想大家应该能很快想出来其实还是映射关系,映射怎么办?那就用一个hashMap解决呗。尝试将pattern中的字符不断向映射表中存放,其实和上一篇文章基本数一摸一样,

  • 当发现pattern中某一个字符在映射表中不存在,就将该字符作为键,对应的s中的单词作为值,放入映射表。

  • 当发现pattern中某一个字符在映射表中存在,查看对应的值是否与s中对应位置的单词匹配,匹配成功继续匹配,匹配失败则返回false。

  • 当走完整个pattern,都没返回false,那么就说明映射成功!

  • 但是我们需要先把s字符串按照空格切割成单词

    //2. 将字符串s按空格分割成字符串数组String[] words = s.split(" ");

这就造成了大量的额外空间的浪。

2.2 思路二——优化

由于在思路一将字符串s按空格分割成字符串数组String[] words = s.split(" ");浪费了一个和s接近一样大小的字符串数组,我们想一下怎么把这部分空间优化掉。

我们之所有将s字符串分割,就是因为我们向方便后续根据pattern的第几个字符就可以找到words中对应的第几个单词。

如果不使用额外的数组空间,我们就得想办法找到pattern字符对应的位置的单词。但是注意我要找的单词不是乱序的,是从前往后找的,pattern从第一个字符走到最后一个字符,对应s中的单词也是从第一个单词走到最后一个单词(先不考虑s中单词数量和pattern中字符数不相等的情况,因为如果不相等的话把短的那个遍历结束发现另外一个没遍历完就可以直接返回false)。

而且题目也告诉我们:

  • s 中每个单词都被 单个空格 分隔

  • s 不包含 任何前导或尾随对空格

所以如果要截取对应的单词,只需要指定两个指针,来截取对应位置的单词就可以了。

所以整体思路同思路一,只不过在使用words[i]时我们使用一个双指针,用来截取单词,减少额外的空间开销。(代码有注释)

但是我们需要注意:

  • 我们需要考虑某一个先遍历完的情况,因为任何一个先遍历完(我指的是映射),就需要返回false,比如下图:

3. 代码实现

3.1 思路一——hash映射表

3.2 思路二——优化空间

4. 相关复杂度分析

思路一:使用split方法

  • 时间复杂度

    • 分割字符串sO(M),其中M是字符串s的长度。

    • 遍历pattern字符串:O(N),其中Npattern的长度(同时也是分割后的单词数组的长度)。

    • 每次迭代中检查映射关系:O(1)平均时间复杂度,但包含对containsValue的调用,这在最坏情况下的时间复杂度为O(k)k是映射中的元素数量。

    • 综合时间复杂度:O(M + Nk),这里假设k在最坏情况下与N相等。

  • 空间复杂度

    • 存储单词数组:O(M),因为需要存储分割后的单词。

    • 使用HashMap存储映射:O(N),在最坏情况下,每个字符映射一个唯一的单词。

    • 综合空间复杂度:O(M + N)

思路二:使用双指针法

  • 时间复杂度

    • 直接在s上使用双指针寻找单词,避免了split的使用:O(M),其中M是字符串s的长度。

    • 遍历patternO(N),其中Npattern的长度。

    • 检查映射关系的时间复杂度与思路一相同,因此综合时间复杂度为:O(M + Nk)

  • 空间复杂度

    • 不需要存储单词数组,直接在s上操作:O(1)额外空间(不计入输出结果的空间)。

    • 使用HashMap存储映射:O(N),在最坏情况下,每个字符映射一个唯一的单词。

    • 综合空间复杂度:O(N)

总结

第一种方法在空间复杂度上会稍高一些,因为它需要存储分割后的单词数组。

第二种方法在处理大文本时可能更优,因为它直接在原字符串上操作,避免了额外的存储开销。

相关文章:

面试经典150题——单词规律

"Dont wait. The time will never be just right." - Napoleon Hill 1. 题目描述 2. 题目分析与解析 首先还是得把题目先读懂,我们直接来看看示例: 根据上面的示例,我们可以看出pattern其实就是表示单词出现的规律,每…...

RK3568平台开发系列讲解(Linux系统篇)container_of

🚀返回专栏总目录 文章目录 一、理解宏container_of二、使用案例沉淀、分享、成长,让自己和他人都能有所收获!😄 一、理解宏container_of 在代码中管理多个数据结构时,几乎总是需要将一个结构嵌入另一个结构中,并随时检索它们,而不关心有关内存偏移或边界的问题。假设…...

回显服务器

. 写一个应用程序,让这个程序可以使用网络通信,这里就需要调用传输层提供的api,传输层提供协议,主要是两个: UDP,TCP,它们分别提供了一套不同的api,socket api. UDP和TCP UDP:无连接,不可靠传输,面向数据报,全双工 TCP:有连接,可靠传输,面向字节流,全双工 一个客户端可以连接…...

c#,dotnet, DataMatrix 类型二维码深度识别,OCR,(基于 Halcon)

代码中部分调用的 c 函数参数,具体说明自行研究~(我也是参考的其他资源,还没研究透彻) 例如:HOperatorSet.GenRectangle2() , 2000, 2000, 0, 2000, 2000 这些数字应该是选取的图片解析范围、尺寸&#xff…...

亿道丨三防平板电脑厂商哪家好丨麒麟系统三防平板PAD

随着科技的飞速发展,人们对于移动设备的需求越来越高。然而,在不同的行业应用场景下,常规的智能平板往往无法满足特殊的工作要求。,亿道三防平板,将高可靠性与卓越性能高度结合,为各行各业提供卓越的移动解…...

什么是hash冲突?以及解决方案

哈希冲突是指在哈希表中,两个或更多个不同的键被映射到了同一个哈希桶的情况。这种情况可能会导致数据丢失或者检索效率下降,因为不同的键被映射到了同一个位置,需要额外的操作来处理这种冲突。 解决哈希冲突的常见方法包括: 开放…...

C# CAD交互界面-模态窗体与非模态窗体调用方式

运行环境Visual Studio 2022 c# cad2016 一、模态窗体调用方式: 当一个模态窗体打开时,它会阻塞主窗体的所有输入,直到关闭该模态窗体为止。例如,弹出一个对话框让用户必须完成某些操作后才能继续使用主程序。 [CommandMethod(&q…...

19个Web前端交互式3D JavaScript框架和库

JavaScript (JS) 是一种轻量级的解释(或即时编译)编程语言,是世界上最流行的编程语言。JavaScript 是一种基于原型的多范式、单线程的动态语言,支持面向对象、命令式和声明式(例如函数式编程&am…...

PaddleSeg分割框架解读[01] 核心设计解析

文章目录 PaddleSeg分割框架解读[01] 核心设计解析tools/train.pypaddleseg/cvlibs/config.pypaddleseg/cvlibs/builder.pypaddleseg/cvlibs/manager.pyPaddleSeg分割框架解读[01] 核心设计解析 tools/train.py import argparse import random import numpy as np import cv2…...

新鲜出炉:小巧优雅的 css-in-js库StyledFc

StyledFc 一个简单的运行时css-in-js库&#xff0c;用于封装react组件 零依赖非常小&#xff0c;< 3kb.运行时生成css支持css变量支持类似less的嵌套css样式支持props动态css支持typescript 演示 安装 pnpm add styledfc # or npm install styledfc # or yarn add styl…...

Python编程实验四:函数的使用

目录 一、实验目的与要求 二、实验内容 三、主要程序清单和程序运行结果 第1题 第2题 第3题 第4题 第5题 四、实验结果分析与体会 一、实验目的与要求 &#xff08;1&#xff09;通过本次实验&#xff0c;学生应掌握函数的定义与调用的基本语法&#xff0c;能根据需要…...

SVN服务备份

hotcopy备份 window批处理 保存以下内容到svn_buckup.bat&#xff0c;确保内容的路径正确&#xff0c;最后双击bat文件进行备份即可 echo offrem SVN安装路径 set svn"C:\Program Files\VisualSVN Server\bin"rem 仓库根目录 set homeE:\Repositories\WorkSpacere…...

FIDO2入门以及相关概念 Client to Authenticator Protocol

​ 本文根据官方文档的定义以及我疑惑的问题做出的相关整理的问答&#xff0c;可能会有偏差&#xff0c;请以官网为准。 官网文档网址&#xff1a;Client to Authenticator Protocol (CTAP) ​ FIDO是什么 FIDO&#xff08;Fast Identity Online&#xff09;是一组开放标准和…...

Linux系统入门:嵌入式系统的操作系统选型

&#xff08;本文为简单介绍&#xff0c;内容来源网络和AI模型生成&#xff09; Linux是一种开源的操作系统,它建立在Unix操作系统的基础之上,采用了Unix的很多理念和设计思想。与商业操作系统如Windows相比,Linux系统资源占用少,运行高效稳定,且Linux系统免费开源,使用和传播…...

数据结构——时间复杂度

前言&#xff1a; 当谈到数据结构和算法时&#xff0c;时间复杂度是一个至关重要的概念。时间复杂度是衡量算法执行时间随输入规模增长而变化的度量&#xff0c;它指示了算法的效率和性能。在本篇博客中&#xff0c;我们将深入探讨时间复杂度的相关知识&#xff0c;并结合C语言…...

《剑指Offer》笔记题解思路技巧优化 Java版本——新版leetcode_Part_5

《剑指Offer》笔记&题解&思路&技巧&优化_Part_5 &#x1f60d;&#x1f60d;&#x1f60d; 相知&#x1f64c;&#x1f64c;&#x1f64c; 相识&#x1f622;&#x1f622;&#x1f622; 开始刷题&#x1f7e2;1. LCR 158. 库存管理 II——数组中出现次数超过一…...

ubuntu上安装docker

在 Ubuntu 上安装 Docker&#xff0c;可以按照以下步骤进行操作&#xff1a; 更新软件包列表&#xff1a;运行以下命令来更新系统的软件包列表&#xff1a; sudo apt update安装必要的依赖项&#xff1a;运行以下命令来安装 Docker 所需的依赖项&#xff1a; sudo apt install …...

【Docker】Linux主机部署Docker

Docker部署 1.二进制文件部署 到如下地址&#xff0c;下载二进制包。 Docker官网&#xff1a;https://docs.docker.com/engine/install/binaries/ 网易镜像源&#xff1a;https://mirrors.163.com/docker-ce/linux/static/stable/x86_64/ 下载好的二进制包上传到主机&#xf…...

vue前端docx库生成word表格 并合并单元格的例子

Vue.js 是一个流行的前端JavaScript框架&#xff0c;用于构建用户界面和单页应用程序。在Vue中生成Word表格并合并单元格&#xff0c;通常需要使用额外的库&#xff0c;如docx&#xff0c;它是一个用于创建和修改Word文档&#xff08;.docx&#xff09;的JavaScript库。 …...

FastGPT配置文件及OneAPI程序:

FastGPT配置文件及OneAPI程序&#xff1a;百度网盘 请输入提取码 提取码&#xff1a;wuhe 创建fastgpt目录&#xff1a;mkdir fastgpt 切换到fastgpt目录&#xff1a;cd fastgpt 下载docker-compose文件&#xff1a;curl -O https://raw.githubusercontent.com/labring/Fast…...

三维GIS开发cesium智慧地铁教程(5)Cesium相机控制

一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点&#xff1a; 路径验证&#xff1a;确保相对路径.…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

CMake 从 GitHub 下载第三方库并使用

有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...

Rapidio门铃消息FIFO溢出机制

关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系&#xff0c;以下是深入解析&#xff1a; 门铃FIFO溢出的本质 在RapidIO系统中&#xff0c;门铃消息FIFO是硬件控制器内部的缓冲区&#xff0c;用于临时存储接收到的门铃消息&#xff08;Doorbell Message&#xff09;。…...

OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 在 GPU 上对图像执行 均值漂移滤波&#xff08;Mean Shift Filtering&#xff09;&#xff0c;用于图像分割或平滑处理。 该函数将输入图像中的…...

SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)

上一章用到了V2 的概念&#xff0c;其实 Fiori当中还有 V4&#xff0c;咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务)&#xff0c;代理中间件&#xff08;ui5-middleware-simpleproxy&#xff09;-CSDN博客…...

CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)

漏洞概览 漏洞名称&#xff1a;Apache Flink REST API 任意文件读取漏洞CVE编号&#xff1a;CVE-2020-17519CVSS评分&#xff1a;7.5影响版本&#xff1a;Apache Flink 1.11.0、1.11.1、1.11.2修复版本&#xff1a;≥ 1.11.3 或 ≥ 1.12.0漏洞类型&#xff1a;路径遍历&#x…...

算法打卡第18天

从中序与后序遍历序列构造二叉树 (力扣106题) 给定两个整数数组 inorder 和 postorder &#xff0c;其中 inorder 是二叉树的中序遍历&#xff0c; postorder 是同一棵树的后序遍历&#xff0c;请你构造并返回这颗 二叉树 。 示例 1: 输入&#xff1a;inorder [9,3,15,20,7…...