14. 最长公共前缀
14. 最长公共前缀
一、题目描述:
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 “”。
示例 1:
输入:strs = [“flower”,“flow”,“flight”]
输出:“fl”
示例 2:
输入:strs = [“dog”,“racecar”,“car”]
输出:“”
解释:输入不存在公共前缀。
提示:
1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/longest-common-prefix
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
二、思路分析:
-
这道题考察了什么思想?你的思路是什么?
这道题目我的思路很简单,就是求字符串切片中最短的那个字符串的长度n,然后从1开始一直到n,截取前面几个字符判断是否一致,如若一致,即继续截取下一个,直到求出最长的公共前缀。
-
做题的时候是不是一次通过的,遇到了什么问题,需要注意什么细节?
不是,我的第一思路执行起来有点问题,需要多次遍历切片,时间复杂度太高了!
我们可以先求字符串切片中最前面两个字符串的最长公共前缀prefix, 之后遍历字符串数组strs时,迭代这个prefix就好了,即求prefix和下一个字符串strs[i]的最长公共前缀。特别的,如果循环中,prefix长度为0,说明strs[0:i]范围内的所有字符串最长公共前缀为空串,后续的遍历也就没有意义了,直接break退出循环。当然,还需要考虑特殊情况,如果字符串数组的长度为0,直接返回空串。
-
有几种解法,哪种解法时间复杂度最低,哪种解法空间复杂度最低,最优解法是什么?其他人的题解是什么,谁的效率更好一些?用不同语言实现的话,哪个语言速度最快?

func longestCommonPrefix(strs []string) string {if len(strs) == 0 {return ""}for i := 0; i < len(strs[0]); i++ {for j := 1; j < len(strs); j++ {if i == len(strs[j]) || strs[j][i] != strs[0][i] {return strs[0][:i]}}}return strs[0] }作者:LeetCode-Solution 链接:https://leetcode.cn/problems/longest-common-prefix/solution/zui-chang-gong-gong-qian-zhui-by-leetcode-solution/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
三、AC 代码:
func LongestCommonPrefix(strs []string) string {count := len(strs)if count == 0 {return ""}prefix := strs[0]for i := 1; i < count; i++ {prefix = lcp(prefix, strs[i])if len(prefix) == 0 {break}}return prefix }func lcp(str1, str2 string) string {length := Min(len(str1), len(str2))index := 0for index < length && str1[index] == str2[index] {index++}return str1[:index] }func Min(a, b int) int {if a < b {return a}return b }
四、总结:
这道题目如果要求时间复杂度不高的话,实现起来还是需要一点技巧的,我的第一思路太暴力了,时间复杂度太高,测试点复杂一点的话,肯定是过不去的!
相关文章:
14. 最长公共前缀
14. 最长公共前缀 一、题目描述: 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀,返回空字符串 “”。 示例 1: 输入:strs [“flower”,“flow”,“flight”] 输出:“fl” 示例 2: …...
SignalR注册成Windows后台服务,并实现web前端断线重连
注意下文里面的 SignalR 不是 Core 版本,而是 Framework 下的 本文使用的方式是把 SignalR 写在控制台项目里,再用 Topshelf 注册成 Windows 服务 这样做有两点好处 传统 Window 服务项目调试时需要“附加到进程”,开发体验比较差…...
【前端笔试题二】从一个指定数组中,每次随机取一个数,且不能与上次取数相同,即避免相邻取数重复
前言 本篇文章记录下我在笔试过程中遇到的真实题目,供大家参考。 1、题目 系统给定一个数组,需要我们编写一个函数,该函数每次调用,随机从该数组中获取一个数,且不能与上一次的取数相同。 2、思路解析 数组已经有了…...
专栏关注学习
Node学习专栏(全网最细的教程) 【spring系列】 SpringCloud 前端框架Vue java学习过程 RocketMQ Spring Tomcat websocket 从头开始学Redisson 从头开始学Oracle 跟着大宇学Shiro 吃透Shiro源代码 Git基础与进阶 Java并发编程 Spring系列 手写…...
【手写 Vuex 源码】第八篇 - Vuex 的 State 状态安装
一,前言 上一篇,主要介绍了 Vuex 模块安装的实现,针对 action、mutation、getter 的收集与处理,主要涉及以下几个点: Vuex 模块安装的逻辑;Vuex 代码优化;Vuex 模块安装的实现;Vue…...
Mac下拉式终端的安装与配置 (iTerm2)
Mac下拉式终端的安装与配置 使用效果如图所示 安装前置软件 iTerm2 很可惜,如此炫酷的功能在原终端中并不能实现,我们需要借助iTerm2这个软件来实现。 官网链接:iTerm2 - macOS Terminal Replacement 我们点击download下载即可 配置 当我…...
使用 Spring 框架结合阿里云 OSS 实现文件上传的代码示例
使用 Spring 框架结合阿里云 OSS 实现文件上传的代码示例POM文件配置文件上传工具类控制层使用yaml配置文件(第二种用法,看公司要求)注入 OSSClient 对象及工具类(第二种用法,看公司要求)使用 Vue 前端代码…...
神经网络基础知识
神经网络基础知识 文章目录神经网络基础知识一、人工神经网络1.激活函数sigmod函数Tanh函数Leaky Relu函数分析2.过拟合和欠拟合二、学习与感知机1.损失函数与代价函数2. 线性回归和逻辑回归3. 监督学习与无监督学习三、优化1.梯度下降法2.随机梯度下降法(SGD)3. 批量梯度下降法…...
SpringBoot开发规范部分通用模板+idea配置【项目通用-1】
SpringBoot开发规范通用模板 1 分页插件使用 通过MybatisPlus配置分页插件拦截器 Configuration MapperScan("com.xuecheng.content.mapper") //拦截的mapper层 public class MybatisPlusConfig {//定义分页的拦截器Beanpublic MybatisPlusInterceptor getMybatisPl…...
程序的机器级表示part3——算术和逻辑操作
目录 1.加载有效地址 2. 整数运算指令 2.1 INC 和 DEC 2.2 NEG 2.3 ADD、SUB 和 IMUL 3. 布尔指令 3.1 AND 3.2 OR 3.3 XOR 3.4 NOT 4. 移位操作 4.1 算术左移和逻辑左移 4.2 算术右移和逻辑右移 5. 特殊的算术操作 1.加载有效地址 指令效果描述leaq S, DD…...
基于YOLOV5的钢材缺陷检测
数据和源码见文末 1.任务概述 数据集使用的是东北大学收集的一个钢材缺陷检测数据集,需要检测出钢材表面的6种划痕。同时,数据集格式是VOC格式,需要进行转化,上传的源码中的数据集是经过转换格式的版本。 2.数据与标签配置方法 在数据集目录下,train文件夹下有训练集数据…...
Session与Cookie的区别(三)
中场休息 让我们先从比喻回到网络世界里,HTTP 是无状态的,所以每一个 Request 都是不相关的,就像是对小明来说每一位客人都是新的客人一样,他根本不知道谁是谁。 既然你没办法把他们关联,就代表状态这件事情也不存在。…...
七大设计原则之接口隔离原则应用
目录1 接口隔离原则介绍2 接口隔离原则应用1 接口隔离原则介绍 接口隔离原则(Interface Segregation Principle, ISP)是指用多个专门的接口,而不使用单一的总接口,客户端不应该依赖它不需要的接口。这个原则指导我们在设计接口时…...
【Shell1】shell语法,ssh/build/scp/upgrade,环境变量,自动升级bmc
文章目录1.shell语法:shell是用C语言编写的程序,是用户使用Linux的桥梁,硬件>内核(os)>shell>文件系统1.1 变量:readonly定义只读变量,unset删除变量1.2 函数:shell脚本传递的参数中包含空格&…...
JavaScript HTML DOM - 改变CSS
JavaScript 是一种动态语言,它可以动态地修改网页的外观,并且使用HTML DOM(文档对象模型)可以更方便地控制HTML元素的样式。 JavaScript 通过在HTML DOM中更改CSS属性来更改样式,这些CSS属性包括颜色、位置、字体大小…...
mycat连接mysql 简单配置
mycat三个配置文件位于conf下 可通过Notepad操作 首先配置service.xml中的user标签,设置用户名,密码,查询权限,是否只读等 只是设置了root用户,有所有权限 配置schema.xml <?xml version"1.0"?&g…...
Spring常用注解
文章目录一、Bean交给Spring管理1、Component2、Bean3、Controller4、Service5、Repository6、Configuration7、ComponentScan二、作用域1、Lazy(false)Scope三、依赖注入1、Autowired2、Resource3、Qualifier四、读取配置文件值1、Value一、Bean交给Spring管理 1、Component …...
I.MX6ULL内核开发9:kobject-驱动的基石
目录 一、摘要 二、重点 三、驱动结构模型 四、关键函数分析 kobject_create_and_add()函数 kobject_create()函数 kobject_init()函数 kobject_init_internal()函数 kobject_add()函数 kobject_add_varg&am…...
Docker-harbor私有仓库
一、Harbor概述 1、Harbor的概念 • Harbor是VMware公司开源的企业级Docker Registry项目,其目标是帮助用户迅速搭建一个企业级的Docker Registry服务 • Harbor以 Docker 公司开源的Registry 为基础,提供了图形管理UI、基于角色的访问控制(Role Base…...
Java之动态规划之子序列问题
目录 0.动态规划问题 一.最长递增子序列 1.题目描述 2.问题分析 3.代码实现 二.最长递增子序列 1.题目描述 2.问题分析 3.代码实现 三.最长重复子数组 1.题目描述 2.问题分析 3.代码实现 4.代码的优化(滚动数组) 四.最长公共子序列 1.题目描述 2.问题分析 3.代…...
中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试
作者:Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位:中南大学地球科学与信息物理学院论文标题:BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接:https://arxiv.…...
Mac软件卸载指南,简单易懂!
刚和Adobe分手,它却总在Library里给你写"回忆录"?卸载的Final Cut Pro像电子幽灵般阴魂不散?总是会有残留文件,别慌!这份Mac软件卸载指南,将用最硬核的方式教你"数字分手术"࿰…...
论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)
笔记整理:刘治强,浙江大学硕士生,研究方向为知识图谱表示学习,大语言模型 论文链接:http://arxiv.org/abs/2407.16127 发表会议:ISWC 2024 1. 动机 传统的知识图谱补全(KGC)模型通过…...
《基于Apache Flink的流处理》笔记
思维导图 1-3 章 4-7章 8-11 章 参考资料 源码: https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...
初探Service服务发现机制
1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能:服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源…...
【JVM】Java虚拟机(二)——垃圾回收
目录 一、如何判断对象可以回收 (一)引用计数法 (二)可达性分析算法 二、垃圾回收算法 (一)标记清除 (二)标记整理 (三)复制 (四ÿ…...
PostgreSQL——环境搭建
一、Linux # 安装 PostgreSQL 15 仓库 sudo dnf install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-$(rpm -E %{rhel})-x86_64/pgdg-redhat-repo-latest.noarch.rpm# 安装之前先确认是否已经存在PostgreSQL rpm -qa | grep postgres# 如果存在࿰…...
图解JavaScript原型:原型链及其分析 | JavaScript图解
忽略该图的细节(如内存地址值没有用二进制) 以下是对该图进一步的理解和总结 1. JS 对象概念的辨析 对象是什么:保存在堆中一块区域,同时在栈中有一块区域保存其在堆中的地址(也就是我们通常说的该变量指向谁&…...
【Ftrace 专栏】Ftrace 参考博文
ftrace、perf、bcc、bpftrace、ply、simple_perf的使用Ftrace 基本用法Linux 利用 ftrace 分析内核调用如何利用ftrace精确跟踪特定进程调度信息使用 ftrace 进行追踪延迟Linux-培训笔记-ftracehttps://www.kernel.org/doc/html/v4.18/trace/events.htmlhttps://blog.csdn.net/…...
用js实现常见排序算法
以下是几种常见排序算法的 JS实现,包括选择排序、冒泡排序、插入排序、快速排序和归并排序,以及每种算法的特点和复杂度分析 1. 选择排序(Selection Sort) 核心思想:每次从未排序部分选择最小元素,与未排…...
