【字符串】最长公共前缀 最长回文子串
文章目录
- 14. 最长公共前缀
- 解题思路:模拟
- 5. 最长回文子串
- 解题思路一:动态规划
- 解题思路二:中心扩散法
14. 最长公共前缀
14. 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 ""。
示例 1:
输入:strs = ["flower","flow","flight"]
输出:"fl"
示例 2:
输入:strs = ["dog","racecar","car"]
输出:""
解释:输入不存在公共前缀。
提示:
1 <= strs.length <= 2000 <= strs[i].length <= 200strs[i]仅由小写英文字母组成
解题思路:模拟
这道题模拟的思路有两种,第一种就是每次比较每个字符串同一位置的字符,判断是否相等,如果不相等则返回前面匹配的位置,可以使用 substr() 函数直接实现这块!
另一种思路就是两两字符串进行比较,得到一个最长公共前缀之后,将其与第三个字符串比较,以此类推直到比较了所有字符串之后,得到的结果就是最长的公共前缀了!
两种思路的时间复杂度都是 O(n*m),其中 n 表示的是字符串的个数,m 表示字符串平均字符个数,下面代码我们采用的是第一种思路!
class Solution {
public:string longestCommonPrefix(vector<string>& strs) {// 每次比较每个字符串同一位置的字符for(int i = 0; i < strs[0].size(); ++i){char tmp = strs[0][i];for(int j = 1; j < strs.size(); ++j){// 如果某个字符串越界了,或者字符不相等,则直接返回前面匹配的位置if((i == strs[j].size()) || (strs[j][i] != tmp))return strs[0].substr(0, i);}}return strs[0];}
};
5. 最长回文子串
5. 最长回文子串
给你一个字符串 s,找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。
示例 1:
输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。
示例 2:
输入:s = "cbbd"
输出:"bb"
提示:
1 <= s.length <= 1000s仅由数字和英文字母组成
解题思路一:动态规划
这道题的动态规划解法之前在学动态规划的时候就已经讲过了,这里就不再赘述了,具体可以参考之前的笔记!
class Solution {
public:string longestPalindrome(string s) {// 定义dp二维数组,dp[j][i]表示从[j, i]区间是否为回文字符串bool dp[1000][1000] = { 0 };int maxlen = 0, maxindex = 0;for(int i = 0; i < s.size(); ++i){for(int j = 0; j <= i; ++j){// 状态转移方程if(s[i] == s[j]){if(i == j || j + 1 == i)dp[j][i] = true;elsedp[j][i] = dp[j + 1][i - 1];if(dp[j][i] && i - j + 1 > maxlen) // 是回文字符串并且长度更长了再更新{maxlen = i - j + 1;maxindex = j;}}}}return s.substr(maxindex, maxlen);}
};
解题思路二:中心扩散法
之前我们在动态规划笔记中提到,字符串的常见题解方法还有一个中心扩散法(至于一个马拉车算法就不讲了,学习成本高,使用率太低),它其实借助的就是回文字符串的特性,由中心自发的向外扩散寻找回文字符串,直到不符合要求!
假设此时我们遍历到字符串的 i 位置,然后定义两个指针 left 和 right 指向该位置,两指针从该位置分别向左和向右出发,每次走一格,判断 s[left] 是否等于 s[right],是的话说明此时就是 [left, right] 区间就是一个回文字符串,则判断是否需要更新最大长度以及回文字符串的起始位置,一直重复上述动作直到判断不符合或者越界了为止!
但是上面操作有个问题,就是只考虑到了区间是奇数的情况,如果是偶数情况比如字符串 "abbc" 的话,此时 "bb" 这种情况就被忽略了,所以我们 需要判断偶数个字符的情况!
class Solution {
public:string longestPalindrome(string s) {int n = s.size();int maxlen = 0, maxindex = 0;for(int i = 0; i < n; ++i){// 判断奇数情况int left = i, right = i;while(left >= 0 && right < n && s[left] == s[right]){left--;right++;}if(right - left - 1 > maxlen){maxlen = right - left - 1;maxindex = left + 1;}// 判断偶数情况(就起始位置不一样,剩下的操作逻辑都是一样的)left = i, right = i + 1;while(left >= 0 && right < n && s[left] == s[right]){left--;right++;}if(right - left - 1 > maxlen){maxlen = right - left - 1;maxindex = left + 1;}}return s.substr(maxindex, maxlen);}
};

相关文章:
【字符串】最长公共前缀 最长回文子串
文章目录 14. 最长公共前缀解题思路:模拟5. 最长回文子串解题思路一:动态规划解题思路二:中心扩散法 14. 最长公共前缀 14. 最长公共前缀 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀,返回空字符…...
Linux提权之详细总结版(完结)
这里是我写了折磨多提权的指令的总结 我这里毫无保留分享给大家哦 首先神魔是提权 我们完整的渗透测试的流程是(个人总结的) 首先提升权限是我们拿到webshell之后的事情,如何拿到webshell,怎末才能拿到webshell,朋友们等我更新,持续更新中,下一篇更新的是windows提权 好了 废…...
week 3 - More on Collections - Lecture 3
一、Motivation 1. Java支持哪种类型的一维数据结构? Java中用于在单一维度中存储数据的数据结构,如arrays or ArrayLists. 2. 如何在Java下创建一维数据结构?(1-dimensional data structure) 定义和初始化这些一…...
Pwntools 的详细介绍、安装指南、配置说明
Pwntools:Python 开源安全工具箱 一、Pwntools 简介 Pwntools 是一个由 Security researcher 开发的 高效 Python 工具库,专为密码学研究、漏洞利用、协议分析和逆向工程设计。它集成了数百个底层工具的功能,提供统一的 Python API 接口&am…...
PLC(电力载波通信)网络机制介绍
1. 概述 1.1 什么是PLC 电力载波通讯即PLC,是英文Power line Carrier的简称。 电力载波是电力系统特有的通信方式,电力载波通讯是指利用现有电力线,通过载波方式将模拟或数字信号进行高速传输的技术。最大特点是不需要重新架设网络…...
Qt监控系统远程回放/录像文件远程下载/录像文件打上水印/批量多线程极速下载
一、前言说明 在做这个功能的时候,着实费了点心思,好在之前做ffmpeg加密解密的时候,已经打通了极速加密保存文件,主要就是之前的类中新增了进度提示信号,比如当前已经处理到哪个position位置,发个信号出来…...
自学微信小程序的第八天
DAY8 1、使用动画API即可完成动画效果的制作,先通过wx.createAnimation()方法获取Animation实例,然后调用Animation实例的方法实现动画效果。 表40:wx.createAnimation()方法的常用选项 选项 类型 说明 duration number 动画持续时间,单位为毫秒,默认值为400毫秒 timing…...
【java】@Transactional导致@DS注解切换数据源失效
最近业务中出现了多商户多租户的逻辑,所以需要分库,项目框架使用了mybatisplus所以我们自然而然的选择了同是baomidou开发的dynamic.datasource来实现多数据源的切换。在使用初期程序运行都很好,但之后发现在调用com.baomidou.mybatisplus.ex…...
003 SpringBoot集成Kafka操作
4.SpringBoot集成Kafka 文章目录 4.SpringBoot集成Kafka1.入门示例2.yml完整配置3.关键配置注释说明1. 生产者优化参数2. 消费者可靠性配置3. 监听器高级特性4. 安全认证配置 4.配置验证方法5.不同场景配置模板场景1:高吞吐日志收集场景2:金融级事务消息…...
Android SystemUI开发(一)
frameworks/base/packages/SystemUI/src/com/android/systemui/SystemUI.java frameworks/base/packages/SystemUI/src/com/android/systemui/SystemUIService.java 关键文件 SystemUI 关键服务 简介 Dependency.class:处理系统依赖关系,提供资源或服…...
C#贪心算法
贪心算法:生活与代码中的 “最优选择大师” 在生活里,我们常常面临各种选择,都希望能做出最有利的决策。比如在超市大促销时,面对琳琅满目的商品,你总想用有限的预算买到价值最高的东西。贪心算法,就像是一…...
Vue程序下载
Vue是一个基于JavaScript(JS)实现的框架,想要使用它,就得先拿到Vue的js文件 Vue官网 Vue2:Vue.js Vue3:Vue.js - 渐进式 JavaScript 框架 | Vue.js 下载并安装vue.js 第一步:打开Vue2官网&a…...
【UCB CS 61B SP24】Lecture 17 - Data Structures 3: B-Trees学习笔记
本文以 2-3-4 树详细讲解了 B 树的概念,逐步分析其操作,并用 Java 实现了标准的 B 树。 1. 2-3 & 2-3-4 Trees 上一节课中讲到的二叉搜索树当数据是随机顺序插入的时候能够使得树变得比较茂密,如下图右侧所示,时间复杂度也就…...
机器学习决策树
一、香农公式 熵: 信息增益: 信息增益信息熵-条件熵 前者是初始信息熵大小,后者是因为条件加入后带来的确定性增加 信息增益表示得知特征X的信息而使得类Y的信息的不确定性减少的程度 信息增益越大说明影响越大 二、代码 ""&…...
Spring Boot + MyBatis 实现 RESTful API 的完整流程
后端开发:Spring Boot 快速开发实战 引言 在现代后端开发中,Spring Boot 因其轻量级、快速开发的特性而备受开发者青睐。本文将带你从零开始,使用 Spring Boot MyBatis 实现一个完整的 RESTful API,并深入探讨如何优雅地处理异…...
通过 ANSYS Discovery 进行 CFD 分析,增强工程设计
概括 工程师使用计算流体动力学 (CFD) 分析来研究和优化各种应用中的流体流动和传热分析。ANSYS Discovery 是一个用户友好的软件平台,使工程师能够轻松设置和解决 CFD 模型,并能够通知设计修改 在这篇博文中,我们将重点介绍在 Ansys Disc…...
家用可燃气体探测器——家庭燃气安全的坚实防线
随着社会的发展和变迁,天然气为我们的生活带来了诸多便利,无论是烹饪美食,还是温暖取暖,都离不开它的支持。然而,燃气安全隐患如影随形,一旦发生泄漏,可能引发爆炸、火灾等严重事故,…...
ListControl双击实现可编辑
为Edit Control控件添加丢失输入焦点事件,可见设为false 为List Control控件添加双击事件 控件和成员变量之间交换数据 CListCtrl ListPrint1; //列表输出 CEdit...
ave-form.vue 组件中 如何将产品名称发送给后端 ?
如何将产品名称发送给后端。 在这段代码中,产品名称(productName)的处理和发送主要发生在 save() 方法中。让我逐步分析: 产品ID的选择: <w-form-selectv-model"form.productId"label"涉及产品&q…...
DeepSeek行业应用实践报告-智灵动力【112页PPT全】
DeepSeek(深度搜索)近期引发广泛关注并成为众多企业/开发者争相接入的现象,主要源于其在技术突破、市场需求适配性及生态建设等方面的综合优势。以下是关键原因分析: 一、技术核心优势 开源与低成本 DeepSeek基于开源架构…...
ubuntu搭建nfs服务centos挂载访问
在Ubuntu上设置NFS服务器 在Ubuntu上,你可以使用apt包管理器来安装NFS服务器。打开终端并运行: sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享,例如/shared: sudo mkdir /shared sud…...
Day131 | 灵神 | 回溯算法 | 子集型 子集
Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣(LeetCode) 思路: 笔者写过很多次这道题了,不想写题解了,大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...
江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命
在华东塑料包装行业面临限塑令深度调整的背景下,江苏艾立泰以一场跨国资源接力的创新实践,重新定义了绿色供应链的边界。 跨国回收网络:废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点,将海外废弃包装箱通过标准…...
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* …...
tree 树组件大数据卡顿问题优化
问题背景 项目中有用到树组件用来做文件目录,但是由于这个树组件的节点越来越多,导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多,导致的浏览器卡顿,这里很明显就需要用到虚拟列表的技术&…...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
基于TurtleBot3在Gazebo地图实现机器人远程控制
1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...
如何更改默认 Crontab 编辑器 ?
在 Linux 领域中,crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用,用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益,允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...
iview框架主题色的应用
1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题,无需引入,直接可…...
Web中间件--tomcat学习
Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机,它可以执行Java字节码。Java虚拟机是Java平台的一部分,Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...
