当前位置: 首页 > news >正文

【字符串】最长公共前缀 最长回文子串

文章目录

  • 14. 最长公共前缀
  • 解题思路:模拟
  • 5. 最长回文子串
  • 解题思路一:动态规划
  • 解题思路二:中心扩散法

在这里插入图片描述

14. 最长公共前缀

14. 最长公共前缀

​ 编写一个函数来查找字符串数组中的最长公共前缀。

​ 如果不存在公共前缀,返回空字符串 ""

示例 1:

输入:strs = ["flower","flow","flight"]
输出:"fl"

示例 2:

输入:strs = ["dog","racecar","car"]
输出:""
解释:输入不存在公共前缀。

提示:

  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[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 <= 1000
  • s 仅由数字和英文字母组成

解题思路一:动态规划

​ 这道题的动态规划解法之前在学动态规划的时候就已经讲过了,这里就不再赘述了,具体可以参考之前的笔记!

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 位置,然后定义两个指针 leftright 指向该位置,两指针从该位置分别向左和向右出发,每次走一格,判断 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. 最长公共前缀解题思路&#xff1a;模拟5. 最长回文子串解题思路一&#xff1a;动态规划解题思路二&#xff1a;中心扩散法 14. 最长公共前缀 14. 最长公共前缀 ​ 编写一个函数来查找字符串数组中的最长公共前缀。 ​ 如果不存在公共前缀&#xff0c;返回空字符…...

Linux提权之详细总结版(完结)

这里是我写了折磨多提权的指令的总结 我这里毫无保留分享给大家哦 首先神魔是提权 我们完整的渗透测试的流程是(个人总结的) 首先提升权限是我们拿到webshell之后的事情,如何拿到webshell,怎末才能拿到webshell,朋友们等我更新,持续更新中,下一篇更新的是windows提权 好了 废…...

week 3 - More on Collections - Lecture 3

一、Motivation 1. Java支持哪种类型的一维数据结构&#xff1f; Java中用于在单一维度中存储数据的数据结构&#xff0c;如arrays or ArrayLists. 2. 如何在Java下创建一维数据结构&#xff1f;&#xff08;1-dimensional data structure&#xff09; 定义和初始化这些一…...

Pwntools 的详细介绍、安装指南、配置说明

Pwntools&#xff1a;Python 开源安全工具箱 一、Pwntools 简介 Pwntools 是一个由 Security researcher 开发的 高效 Python 工具库&#xff0c;专为密码学研究、漏洞利用、协议分析和逆向工程设计。它集成了数百个底层工具的功能&#xff0c;提供统一的 Python API 接口&am…...

PLC(电力载波通信)网络机制介绍

1. 概述 1.1 什么是PLC 电力载波通讯即PLC&#xff0c;是英文Power line Carrier的简称。 电力载波是电力系统特有的通信方式&#xff0c;电力载波通讯是指利用现有电力线&#xff0c;通过载波方式将模拟或数字信号进行高速传输的技术。最大特点是不需要重新架设网络&#xf…...

Qt监控系统远程回放/录像文件远程下载/录像文件打上水印/批量多线程极速下载

一、前言说明 在做这个功能的时候&#xff0c;着实费了点心思&#xff0c;好在之前做ffmpeg加密解密的时候&#xff0c;已经打通了极速加密保存文件&#xff0c;主要就是之前的类中新增了进度提示信号&#xff0c;比如当前已经处理到哪个position位置&#xff0c;发个信号出来…...

自学微信小程序的第八天

DAY8 1、使用动画API即可完成动画效果的制作,先通过wx.createAnimation()方法获取Animation实例,然后调用Animation实例的方法实现动画效果。 表40:wx.createAnimation()方法的常用选项 选项 类型 说明 duration number 动画持续时间,单位为毫秒,默认值为400毫秒 timing…...

【java】@Transactional导致@DS注解切换数据源失效

最近业务中出现了多商户多租户的逻辑&#xff0c;所以需要分库&#xff0c;项目框架使用了mybatisplus所以我们自然而然的选择了同是baomidou开发的dynamic.datasource来实现多数据源的切换。在使用初期程序运行都很好&#xff0c;但之后发现在调用com.baomidou.mybatisplus.ex…...

003 SpringBoot集成Kafka操作

4.SpringBoot集成Kafka 文章目录 4.SpringBoot集成Kafka1.入门示例2.yml完整配置3.关键配置注释说明1. 生产者优化参数2. 消费者可靠性配置3. 监听器高级特性4. 安全认证配置 4.配置验证方法5.不同场景配置模板场景1&#xff1a;高吞吐日志收集场景2&#xff1a;金融级事务消息…...

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&#xff1a;处理系统依赖关系&#xff0c;提供资源或服…...

C#贪心算法

贪心算法&#xff1a;生活与代码中的 “最优选择大师” 在生活里&#xff0c;我们常常面临各种选择&#xff0c;都希望能做出最有利的决策。比如在超市大促销时&#xff0c;面对琳琅满目的商品&#xff0c;你总想用有限的预算买到价值最高的东西。贪心算法&#xff0c;就像是一…...

Vue程序下载

Vue是一个基于JavaScript&#xff08;JS&#xff09;实现的框架&#xff0c;想要使用它&#xff0c;就得先拿到Vue的js文件 Vue官网 Vue2&#xff1a;Vue.js Vue3&#xff1a;Vue.js - 渐进式 JavaScript 框架 | Vue.js 下载并安装vue.js 第一步&#xff1a;打开Vue2官网&a…...

【UCB CS 61B SP24】Lecture 17 - Data Structures 3: B-Trees学习笔记

本文以 2-3-4 树详细讲解了 B 树的概念&#xff0c;逐步分析其操作&#xff0c;并用 Java 实现了标准的 B 树。 1. 2-3 & 2-3-4 Trees 上一节课中讲到的二叉搜索树当数据是随机顺序插入的时候能够使得树变得比较茂密&#xff0c;如下图右侧所示&#xff0c;时间复杂度也就…...

机器学习决策树

一、香农公式 熵&#xff1a; 信息增益&#xff1a; 信息增益信息熵-条件熵 前者是初始信息熵大小&#xff0c;后者是因为条件加入后带来的确定性增加 信息增益表示得知特征X的信息而使得类Y的信息的不确定性减少的程度 信息增益越大说明影响越大 二、代码 ""&…...

Spring Boot + MyBatis 实现 RESTful API 的完整流程

后端开发&#xff1a;Spring Boot 快速开发实战 引言 在现代后端开发中&#xff0c;Spring Boot 因其轻量级、快速开发的特性而备受开发者青睐。本文将带你从零开始&#xff0c;使用 Spring Boot MyBatis 实现一个完整的 RESTful API&#xff0c;并深入探讨如何优雅地处理异…...

通过 ANSYS Discovery 进行 CFD 分析,增强工程设计

概括 工程师使用计算流体动力学 (CFD) 分析来研究和优化各种应用中的流体流动和传热分析。ANSYS Discovery 是一个用户友好的软件平台&#xff0c;使工程师能够轻松设置和解决 CFD 模型&#xff0c;并能够通知设计修改 在这篇博文中&#xff0c;我们将重点介绍在 Ansys Disc…...

家用可燃气体探测器——家庭燃气安全的坚实防线

随着社会的发展和变迁&#xff0c;天然气为我们的生活带来了诸多便利&#xff0c;无论是烹饪美食&#xff0c;还是温暖取暖&#xff0c;都离不开它的支持。然而&#xff0c;燃气安全隐患如影随形&#xff0c;一旦发生泄漏&#xff0c;可能引发爆炸、火灾等严重事故&#xff0c;…...

ListControl双击实现可编辑

为Edit Control控件添加丢失输入焦点事件,可见设为false 为List Control控件添加双击事件 控件和成员变量之间交换数据 CListCtrl ListPrint1; //列表输出 CEdit...

ave-form.vue 组件中 如何将产品名称发送给后端 ?

如何将产品名称发送给后端。 在这段代码中&#xff0c;产品名称&#xff08;productName&#xff09;的处理和发送主要发生在 save() 方法中。让我逐步分析&#xff1a; 产品ID的选择&#xff1a; <w-form-selectv-model"form.productId"label"涉及产品&q…...

DeepSeek行业应用实践报告-智灵动力【112页PPT全】

DeepSeek&#xff08;深度搜索&#xff09;近期引发广泛关注并成为众多企业/开发者争相接入的现象&#xff0c;主要源于其在技术突破、市场需求适配性及生态建设等方面的综合优势。以下是关键原因分析&#xff1a; 一、技术核心优势 开源与低成本 DeepSeek基于开源架构&#xf…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

oracle与MySQL数据库之间数据同步的技术要点

Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异&#xff0c;它们的数据同步要求既要保持数据的准确性和一致性&#xff0c;又要处理好性能问题。以下是一些主要的技术要点&#xff1a; 数据结构差异 数据类型差异&#xff…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战

“&#x1f916;手搓TuyaAI语音指令 &#x1f60d;秒变表情包大师&#xff0c;让萌系Otto机器人&#x1f525;玩出智能新花样&#xff01;开整&#xff01;” &#x1f916; Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制&#xff08;TuyaAI…...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...

Android第十三次面试总结(四大 组件基础)

Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成&#xff0c;用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机&#xff1a; ​onCreate()​​ ​调用时机​&#xff1a;Activity 首次创建时调用。​…...

JAVA后端开发——多租户

数据隔离是多租户系统中的核心概念&#xff0c;确保一个租户&#xff08;在这个系统中可能是一个公司或一个独立的客户&#xff09;的数据对其他租户是不可见的。在 RuoYi 框架&#xff08;您当前项目所使用的基础框架&#xff09;中&#xff0c;这通常是通过在数据表中增加一个…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP

编辑-虚拟网络编辑器-更改设置 选择桥接模式&#xff0c;然后找到相应的网卡&#xff08;可以查看自己本机的网络连接&#xff09; windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置&#xff0c;选择刚才配置的桥接模式 静态ip设置&#xff1a; 我用的ubuntu24桌…...

「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案

在移动互联网营销竞争白热化的当下&#xff0c;推客小程序系统凭借其裂变传播、精准营销等特性&#xff0c;成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径&#xff0c;助力开发者打造具有市场竞争力的营销工具。​ 一、系统核心功能架构&…...