从零学算法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.一元函数…...
【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型
摘要 拍照搜题系统采用“三层管道(多模态 OCR → 语义检索 → 答案渲染)、两级检索(倒排 BM25 向量 HNSW)并以大语言模型兜底”的整体框架: 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后,分别用…...
Cursor实现用excel数据填充word模版的方法
cursor主页:https://www.cursor.com/ 任务目标:把excel格式的数据里的单元格,按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例,…...
ES6从入门到精通:前言
ES6简介 ES6(ECMAScript 2015)是JavaScript语言的重大更新,引入了许多新特性,包括语法糖、新数据类型、模块化支持等,显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var…...
VB.net复制Ntag213卡写入UID
本示例使用的发卡器:https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...
Qt Widget类解析与代码注释
#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码,写上注释 当然可以!这段代码是 Qt …...
(二)原型模式
原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...
LeetCode - 199. 二叉树的右视图
题目 199. 二叉树的右视图 - 力扣(LeetCode) 思路 右视图是指从树的右侧看,对于每一层,只能看到该层最右边的节点。实现思路是: 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...
基于 TAPD 进行项目管理
起因 自己写了个小工具,仓库用的Github。之前在用markdown进行需求管理,现在随着功能的增加,感觉有点难以管理了,所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD,需要提供一个企业名新建一个项目&#…...
08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险
C#入门系列【类的基本概念】:开启编程世界的奇妙冒险 嘿,各位编程小白探险家!欢迎来到 C# 的奇幻大陆!今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类!别害怕,跟着我,保准让你轻松搞…...
【SpringBoot自动化部署】
SpringBoot自动化部署方法 使用Jenkins进行持续集成与部署 Jenkins是最常用的自动化部署工具之一,能够实现代码拉取、构建、测试和部署的全流程自动化。 配置Jenkins任务时,需要添加Git仓库地址和凭证,设置构建触发器(如GitHub…...
