稀疏矩阵搜索(两种方法解决:1.暴力+哈希 2.二分法)
题目:
有个排好序的字符串数组,其中散布着一些空字符串,编写一种方法,找出给定字符串的位置。
示例:
输入: words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ta"
输出:-1
说明: 不存在返回-1。
输入:words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ball"
输出:4
解题思路:
首先,简单的可以用暴力+哈希来实现。
创建哈希表,并建立每个字符串与其下标的映射关系;
然后找是否存在key值(字符串s),存在则返回哈希表中的value值;
否则说明不存在该字符串,返回-1。
Code:
class Solution {
public:int findString(vector<string>& words, string s) {unordered_map<string,int> map;//创建哈希表//建立每个单词与其下标的映射关系for(int i=0;i<words.size();i++){map[words[i]]=i;}//直接找字符串//找到了,直接返回value值if(map.find(s)!=map.end()){return map[s];}//没找到,返回-1return -1;}
};
再升级一下,采用二分法来实现。
思路:
1.先将数组前后的空字符串清除
2.如果mid下标遇到空字符串,统一向右靠,当mid=right时,我们直接更新右边界到mid的位置
3.剩下接着按照常规的二分查找法进行目标字符串的查找
Code:
class Solution {
public:int findString(vector<string>& words, string s) {int left = 0, right = words.size() - 1;while (left <= right) {//左边界遇到空字符串,左边界向右移if (words[left].size() == 0) {left++;continue;}//右边界遇到空字符串,右边界向左移if (words[right].size() == 0) {right--;continue;}//中间下标midint mid = (right + left) / 2;//如果遇到空字符串,统一向右靠while (words[mid].size() == 0) {mid++;//如果此时mid已经到达右边界,那么将右边界更新到中间下标mid处//这里right下标处的值会在后面判断到,不会被漏掉if (mid == right) {right = (right + left) / 2;continue;}}//这里顺便将刚刚上一步的右边界的值判断了,并没有漏掉//剩下的就是二分法常规查找if (words[mid] == s)return mid;else if (words[mid] > s) {right = mid - 1;}else {left = mid + 1;}}return -1;}
};
相关文章:
稀疏矩阵搜索(两种方法解决:1.暴力+哈希 2.二分法)
题目: 有个排好序的字符串数组,其中散布着一些空字符串,编写一种方法,找出给定字符串的位置。 示例: 输入: words ["at", "", "", "", "ball", "", &…...
NodeJS系列教程、笔记
NodeJS系列教程、笔记 点我进入专栏 Node.js安装与基本使用 NodeJS的Web框架Express入门 Node.js的sha1加密 Nodejs热更新 Nodejs配置文件 Nodejs的字节操作(Buffer) Node.js之TCP(net) Node.js使用axios进行web接口调用 …...

4.4TCP半连接队列和全连接队列
目录 什么是 TCP 半连接队列和全连接队列? TCP 全连接队列溢出 如何知道应用程序的 TCP 全连接队列大小? 如何模拟 TCP 全连接队列溢出的场景? 全连接队列溢出会发生什么 ? 如何增大全连接队列呢 ? TCP 半连接队列溢出 如何查看 TC…...

一键实现 Oracle 数据整库同步至 Apache Doris
在实时数据仓库建设或迁移的过程中,用户必须考虑如何高效便捷将关系数据库数据同步到实时数仓中来,Apache Doris 用户也面临这样的挑战。而对于从 Oracle 到 Doris 的数据同步,通常会用到以下两种常见的同步方式: OGG/XStream/Lo…...

Unity3D软件安装包分享(附安装教程)
目录 一、软件简介 二、软件下载 一、软件简介 Unity3D是一款全球知名的游戏开发引擎,由Unity Technologies公司开发。它提供了一个跨平台、多功能的开发环境,支持创建2D和3D游戏、交互式应用、虚拟现实、增强现实等多种类型的应用程序。以下是Unity3D…...

Vue2向Vue3过度Vue3组合式API
目录 1. Vue2 选项式 API vs Vue3 组合式API2. Vue3的优势3 使用create-vue搭建Vue3项目1. 认识create-vue2. 使用create-vue创建项目 4 熟悉项目和关键文件5 组合式API - setup选项1. setup选项的写法和执行时机2. setup中写代码的特点3. <script setup>语法糖 6 组合式…...

⛳ Docker 安装 MySQL
🎍目录 ⛳ Docker 安装 MySQL🚜 一、搜索 mysql , 查看版本🎨 二、拉取mysql镜像👣 三、建立容器的挂载文件🧰 四、创建mysql配置文件,my.conf🏭 五、根据镜像产生容器🎁 六、远程连…...

4.6 TCP面向字节流
TCP 是面向字节流的协议,UDP 是面向报文的协议 操作系统对 TCP 和 UDP 协议的发送方的机制不同,也就是问题原因在发送方。 UDP面向报文协议: 操作系统不会对UDP协议传输的消息进行拆分,在组装好UDP头部后就交给网络层处理&…...

uniapp返回上一页并刷新
在uniapp中,经常会有返回上一页的情况,官方提供有 uni.navigateBack 这个api来实现效果,但是此方法返回到上一页之后页面并不会更新(刷新)。 例如有这样一个场景:从地址列表页点击添加按钮进入添加地址页面…...
LRU cache的实现细节优化——伪结点的技巧
LRU cache的实现是面试常见的题目,思路比较简单,可以参考思路 这个题目在实际面试中容易出错,主要是npe和头节点与尾节点的更新,有没有办法避免这一点呢,这时可以发现伪节点的好处,永远不用更新头尾节点&am…...

【C/C++】父类指针指向子类对象 | 隐藏
创作不易,本篇文章如果帮助到了你,还请点赞 关注支持一下♡>𖥦<)!! 主页专栏有更多知识,如有疑问欢迎大家指正讨论,共同进步! 🔥c系列专栏:C/C零基础到精通 🔥 给大…...

NSSCTF——Web题目2
目录 一、[HNCTF 2022 Week1]2048 二、[HNCTF 2022 Week1]What is Web 三、[LitCTF 2023]1zjs 四、[NCTF 2018]签到题 五、[SWPUCTF 2021 新生赛]gift_F12 一、[HNCTF 2022 Week1]2048 知识点:源代码审计 解题思路: 1、打开控制台,查看…...

从零到富:探索CSGO搬砖项目的无限可能
在如今互联网时代,有一项令人惊叹的项目正悄然兴起,它就是CSGO搬砖项目。作为一个从零开始的家伙,我亲身经历了这个项目的神奇魅力,每天轻松赚取几十上百的收益,无风险,低成本。今天,我将带领大…...
Uniapp中vuex的使用
vuex的学习笔记,很多地方还都不是很懂,先记下来再说,比小程序里自带的store复杂很多,看着头大,而且方法里面很多ES6的内容,头都看到爆炸 一、初始化vuex 新建store.js,挂载到main.js 1、在根…...

SpringBoot案例-配置文件-参数配置化
前言 目前我们已经完成了部门管理和员工管理功能接口的实现,阿里云OSS工具类中,我们会设置4个参数,分别是云服务域名、云服务ID和密码、文件存储的Bucket、就会存在以下问题:参数配置分散以及参数发生变化,就需要对应…...

android系统启动流程之zygote(Native)启动分析
zygote有一部分运行在native,有一部分运行在java层,它是第一个进入java层的进程 zygote在启动时,在init.${ro.zygote}.rc脚本中,里面描述了zygote是如何被启动的, 当init进程解析到zygote.rc文件时,将根据解析出来的命…...
Win10上ffmpeg出现Invalid report file level
在win10上经常使用ffmpeg,但是最近突然ffmpeg用不了,不管ffmpeg还是ffplay,输出始终一句话: Invalid report file level 重新通过scoop装了以后还是同样的错误。 后来发现是一个环境变量设置有问题,FFREPORT。 我在w…...

Vue3 中引入液晶数字字体(通常用于大屏设计)
一、下载 .ttf 字体文件到本地,放在 src 中的 assets 文件下 下载液晶字体 DS-Digital.ttf 二、在 css 文件中引入字体 /* src/assets/fonts/dsfont.css */ font-face {font-family: electronicFont;src: url(./DS-Digital.ttf);font-weight: normal;font-styl…...
从 Future 到 CompletableFuture:简化 Java 中的异步编程
引言 在并发编程中,我们经常需要处理多线程的任务,这些任务往往具有依赖性,异步性,且需要在所有任务完成后获取结果。Java 8 引入了 CompletableFuture 类,它带来了一种新的编程模式,让我们能够以函数式编…...

【ARMv8 SIMD和浮点指令编程】NEON 乘法指令——乘法知多少?
NEON 乘法指令包括向量乘法、向量乘加和向量乘减,还有和饱和相关的指令。总之,乘法指令是必修课,在我们的实际开发中会经常遇到。 1 MUL (by element) 乘(向量,按元素)。该指令将第一个源 SIMD&FP 寄存器中的向量元素乘以第二个源 SIMD&FP 寄存器中的指定值,将…...

铭豹扩展坞 USB转网口 突然无法识别解决方法
当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

stm32G473的flash模式是单bank还是双bank?
今天突然有人stm32G473的flash模式是单bank还是双bank?由于时间太久,我真忘记了。搜搜发现,还真有人和我一样。见下面的链接:https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...
Linux链表操作全解析
Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表?1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

Xshell远程连接Kali(默认 | 私钥)Note版
前言:xshell远程连接,私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...
java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别
UnsatisfiedLinkError 在对接硬件设备中,我们会遇到使用 java 调用 dll文件 的情况,此时大概率出现UnsatisfiedLinkError链接错误,原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用,结果 dll 未实现 JNI 协…...
测试markdown--肇兴
day1: 1、去程:7:04 --11:32高铁 高铁右转上售票大厅2楼,穿过候车厅下一楼,上大巴车 ¥10/人 **2、到达:**12点多到达寨子,买门票,美团/抖音:¥78人 3、中饭&a…...

Linux-07 ubuntu 的 chrome 启动不了
文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了,报错如下四、启动不了,解决如下 总结 问题原因 在应用中可以看到chrome,但是打不开(说明:原来的ubuntu系统出问题了,这个是备用的硬盘&a…...

tree 树组件大数据卡顿问题优化
问题背景 项目中有用到树组件用来做文件目录,但是由于这个树组件的节点越来越多,导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多,导致的浏览器卡顿,这里很明显就需要用到虚拟列表的技术&…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)
参考官方文档:https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java(供 Kotlin 使用) 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

USB Over IP专用硬件的5个特点
USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中,从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备(如专用硬件设备),从而消除了直接物理连接的需要。USB over IP的…...