从零学算法14
14. 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 “”。
示例 1:
输入:strs = [“flower”,“flow”,“flight”]
输出:“fl”
示例 2:
输入:strs = [“dog”,“racecar”,“car”]
输出:“”
解释:输入不存在公共前缀。
提示:
1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成
- 最容易想到的思路就是先默认第一个字符串为结果 res,然后遍历剩下的字符串,不断根据 res 以及 str 的比较得到新的 res,这样就相当于比较了所有字符串,最终 res 就是公共前缀
-
public String longestCommonPrefix(String[] strs) {if(strs.length == 0)return "";String res = strs[0];for(int i = 1; i < strs.length; i++){res = getPre(res, strs[i]);if("".equals(res))break;}return res;}public String getPre(String s1, String s2){int min = Math.min(s1.length(), s2.length());int i = 0;while(i < min && s1.charAt(i) == s2.charAt(i)){i++;}return s1.substring(0, i);} - 既然有横向的,那么纵向的也比较容易想到,取任意一个字符串为例,从第一位开始,比较所有字符串某一位是否等于该字符的这一位,需要注意的是不仅当遇到不同字符时需要返回,当某个字符串已经被比较完也应该返回
-
public String longestCommonPrefix(String[] strs) {if(strs.length == 0)return "";for(int i = 0; i < strs[0].length(); i++){char c = strs[0].charAt(i);for(int j = 1; j < strs.length; j++){if(i == strs[j].length() || strs[j].charAt(i) != c){return strs[0].substring(0, i);}}}// 理论上来说返回什么都可以,因为上面的情况已经包含了比较完的情况// 但是 strs 只有一个字符串时就不会进入比较// 所以需要返回 strs[0]return strs[0];} - 分治:由于不管怎么样最终每个字符都会被比较,比如第一种解法就是不断更新两个字符串比较后的结果,那么其实分治也可以,不过同时比较两组字符串而已
-
public String longestCommonPrefix(String[] strs) {if(strs.length == 0)return "";return longestCommonPrefix(strs, 0, strs.length - 1);}// 分治public String longestCommonPrefix(String[] strs, int start, int end) {if(start == end)return strs[start];int mid = start + (end - start) / 2;String left = longestCommonPrefix(strs, start, mid);String right = longestCommonPrefix(strs, mid + 1, end);return commonPrefix(left, right);}// 获取两个字符串的公共前缀public String commonPrefix(String lcpLeft, String lcpRight) {int minLength = Math.min(lcpLeft.length(), lcpRight.length()); for (int i = 0; i < minLength; i++) {if (lcpLeft.charAt(i) != lcpRight.charAt(i)) {return lcpLeft.substring(0, i);}}return lcpLeft.substring(0, minLength);} - 二分法:由于最终公共前缀的长度不会大于最短字符串长度 min ,那么可以在解法 2 的基础上,使用二分法,从 left = 0 ,right = min 开始,得到最终公共前缀的长度
-
public String longestCommonPrefix(String[] strs) {if(strs.length == 0)return "";int min = Integer.MAX_VALUE;for (String str : strs) {min = Math.min(min, str.length());}int left = 0, right = min;while(left < right){int mid = left + (right - left + 1) / 2;if(isCommonPrefix(strs, mid))left = mid;else right = mid - 1;}return strs[0].substring(0, left);}// 判断 length 是否为公共前缀public boolean isCommonPrefix(String[] strs, int length) { for (int i = 0; i < length; i++) {char c = strs[0].charAt(i);for(int j = 1; j < strs.length; j++){if(strs[j].charAt(i) != c)return false;}}return true;}
相关文章:
从零学算法14
14. 最长公共前缀 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀,返回空字符串 “”。 示例 1: 输入:strs [“flower”,“flow”,“flight”] 输出:“fl” 示例 2: 输入:strs [“d…...
[入门] Unity Shader前置知识(5) —— 向量的运算
在Unity中,向量无处不在,我想很多人都使用过向量类的内置方法 normalized() 吧,我们都知道该方法是将其向量归一化从而作为一个方向与速度相乘,以达到角色朝任一方向移动时速度都相等的效果,但内部具体是如何将该向量进…...
html的i标签 “\e905“ font-family 字体没有效果
一、html的i标签 “\e905” 没有效果 在HTML和CSS中,\e905 这样的字符通常与字体图标(Font Icons)或自定义字体(Custom Fonts)中的Unicode字符相关。具体来说,\e905 是一个Unicode转义序列,但它…...
Golang reflect.MakeFunc() 的用法及示例
Golang 作为一门强类型语言,在某些场景下,我们需要动态地创建函数或者修改函数,这个时候就可以使用反射的方法去实现。在反射中,我们可以使用 reflect.MakeFunc() 方法来创建一个新的函数,本文我将介绍使用反射及其 Ma…...
深入学习和理解Django视图层:处理请求与响应
title: 深入学习和理解Django视图层:处理请求与响应 date: 2024/5/4 17:47:55 updated: 2024/5/4 17:47:55 categories: 后端开发 tags: Django请求处理响应生成模板渲染表单处理中间件异常处理 第一章:Django框架概述 1.1 什么是Django?…...
【MySQL】SQL基本知识点DDL(1)
目录 1.SQL分类: 2.DDL-数据库操作 3.DDL-表操作-创建 4.DDL-表操作-查询 5.DDL-表操作-数据类型 6.DDL-表操作-修改 1.SQL分类: 2.DDL-数据库操作 3.DDL-表操作-创建 注意:里面的符号全部要切换为英文状态 4.DDL-表操作-查询 5.DDL…...
短剧奔向小程序,流量生意如何开启?
随着移动互联网的飞速发展,小程序作为一种轻量级、易传播的应用形态,逐渐在各个领域展现出其独特的商业价值。而最近爆火的短剧小视频作为一种受众广泛的娱乐形式,与小程序结合后,不仅为观众提供了更为便捷的观看体验,…...
微服务下的技术栈架构解析
微服务是一种架构风格,它将一个复杂的应用拆分成多个独立自治的服务,每个服务负责应用程序中的一小部分功能。这些服务通过定义良好的API进行通信,通常是HTTP RESTful API或事件流。微服务架构的主要特点包括单一职责、自治性、可独立部署和扩…...
Mesa3D图形库与NIR(New Intermediate Representation)
Mesa 是一个开源图形库,为 Unix 和 Linux 系统提供了 OpenGL 和 Vulkan API 的实现。它也支持其他图形 API,如OpenCL、OpenGL ES 和 Vulkan。Mesa 项目的目标是为开源社区提供高性能的图形库,使得开源操作系统能够充分利用现代图形硬件。 Me…...
C++:模板初阶
文章目录 泛型编程函数模板概念函数模板格式函数模板的原理函数模板的实例化模板参数的匹配原则 模板类类模板的定义格式类模板实例化 泛型编程 如何实现一个通用的交换函数呢? 函数重载可以帮助我们完成 void Swap(int& left, int& right) {int temp l…...
为什么要学Python?学Python有什么用?
为什么要学Python?学Python有什么用? 在当今的数字化时代,编程已成为一项宝贵的技能。Python,作为一种流行的编程语言,因其易于学习和强大的功能而受到全球开发者的青睐。本文将探讨学习Python的原因和它的实际应用&am…...
Linux磁盘IO、网络IO、零拷贝详解
一、什么是I/O? 在计算机操作系统中,所谓的I/O就是输入(input)和输出(output),也可以理解为读(read)和写(write),针对不同的对象,I/O模式可以划分…...
工业交换机外壳材质大比拼,看看哪种外壳适合你
在工业领域里,交换机就像我们的网络心脏,时刻跳动着确保信息畅通无阻。而它的外壳,就是保护这颗“心脏”的铠甲。今天,咱们就来聊聊这些铠甲——工业交换机外壳的材质和防护等级,看看它们如何守护我们的网络世界。 首…...
智慧公厕的技术基础、保障技术和应用价值
近年来,随着信息技术的快速发展,智慧公厕逐渐成为城市管理的热点项目。智慧公厕利用物联网技术与大数据、云计算、网络通信、自动化控制等先进技术相结合,公共厕所的管理变得更加快捷高效,实现了真正的智能化使用和智慧化管理。下…...
思腾合力受邀参加VALSE 2024视觉与学习青年学者研讨会
在充满学术氛围的五月,思腾合力荣幸受邀参加了于2024年5月5-7日在重庆举行的第十四届VALSE大会。作为视觉与学习领域的顶级交流平台,VALSE大会每年都吸引着全国专家与学者的目光。 本次大会不仅延续了往届的高水平学术研讨,还进一步拓宽了研究…...
geotrust dv通配符证书800
Geotrust是成立时间较久的正规CA认证机构,在过去的几十年间颁发了无数的SSL证书,这些SSL证书被各个开发者使用,受到大多数浏览器的信任。而Geotrust旗下的DV通配符证书因其广泛的应用范围受到了用户的青睐。今天就随SSL盾小编了解Geotrust旗下…...
SpringBoot工作原理
优点:自动装配,起步依赖 起步依赖 原理就是maven的依赖传递 【A依赖B、B依赖C….,则我导入依赖A的时候,B,C都会被maven加载进来】 重点看看自动装配 概念: 当Spring容器启动后,一些配置类、…...
【Spring】Spring 整合 Junit、MyBatis
一、 Spring 整合 Junit <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation"http://maven.apache…...
【JVM基础篇】JVM入门介绍
JVM入门介绍 为什么学习JVM 岗位要求 解决工作中遇到的问题 性能调优 真实案例 导出超大文件,系统崩溃从数据库中查询超大量数据出错消费者消费来不及导致系统崩溃Mq消息队列接受消息导致的内存泄漏业务高峰期系统失去响应 初识JVM 什么是JVM? JV…...
《21天学通C++》(第二十一章)理解函数对象
什么是函数对象? 函数对象是一种特殊类型的类,它重载了函数调用操作符 operator(),使得类的实例可以像函数一样被调用。 什么是谓词? 谓词是指一个能够返回布尔值(true或false)的函数或函数对象 1.一元函数…...
工业安全零事故的智能守护者:一体化AI智能安防平台
前言: 通过AI视觉技术,为船厂提供全面的安全监控解决方案,涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面,能够实现对应负责人反馈机制,并最终实现数据的统计报表。提升船厂…...
2025年能源电力系统与流体力学国际会议 (EPSFD 2025)
2025年能源电力系统与流体力学国际会议(EPSFD 2025)将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会,EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...
练习(含atoi的模拟实现,自定义类型等练习)
一、结构体大小的计算及位段 (结构体大小计算及位段 详解请看:自定义类型:结构体进阶-CSDN博客) 1.在32位系统环境,编译选项为4字节对齐,那么sizeof(A)和sizeof(B)是多少? #pragma pack(4)st…...
【Linux】C语言执行shell指令
在C语言中执行Shell指令 在C语言中,有几种方法可以执行Shell指令: 1. 使用system()函数 这是最简单的方法,包含在stdlib.h头文件中: #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...
在rocky linux 9.5上在线安装 docker
前面是指南,后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...
基础测试工具使用经验
背景 vtune,perf, nsight system等基础测试工具,都是用过的,但是没有记录,都逐渐忘了。所以写这篇博客总结记录一下,只要以后发现新的用法,就记得来编辑补充一下 perf 比较基础的用法: 先改这…...
【HTML-16】深入理解HTML中的块元素与行内元素
HTML元素根据其显示特性可以分为两大类:块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...
k8s业务程序联调工具-KtConnect
概述 原理 工具作用是建立了一个从本地到集群的单向VPN,根据VPN原理,打通两个内网必然需要借助一个公共中继节点,ktconnect工具巧妙的利用k8s原生的portforward能力,简化了建立连接的过程,apiserver间接起到了中继节…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...
