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

leetcode day4 409+5

409 最长回文串

给定一个包含大写字母和小写字母的字符串 s ,返回 通过这些字母构造成的 最长的 
回文串
 的长度。

在构造过程中,请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。

示例 1:

输入:s = "abccccdd"
输出:7
解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
示例 2:

输入:s = "a"
输出:1
解释:可以构造的最长回文串是"a",它的长度是 1。
 

提示:

1 <= s.length <= 2000
s 只由小写 和/或 大写英文字母组成

解题思路:注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。

把所有偶数的加起来,奇数的加上它-1的偶数,如果最后长度小于字符串长度,说明还可以加一个数。

int longestPalindrome(char* s) {int sz=strlen(s);int a[26]={};int b[26]={};for(int i=0;i<sz;i++){if(a[i]>='A'&&a[i]<='Z')a[s[i]-'A']++;else b[s[i]-'a']++;}int sum=0;for(int i=0;i<26;i++){if(a[i]%2==0)sum+=a[i];else sum=sum+a[i]-1;if(b[i]%2==0)sum+=b[i];else sum=sum+b[i]-1;}if(sum!=sz)sum++;return sum;
}

———————题目分割线——————

5 最长回文子串

给你一个字符串 s,找到 s 中最长的 回文子串。 

示例 1:

输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。
示例 2:

输入:s = "cbbd"
输出:"bb"
 

提示:

1 <= s.length <= 1000
s 仅由数字和英文字母组成

方法一:暴力求解

start:子串起始位置,求出最长回文子串后,s[start+len]='\0',原地修改返回

最后返回s+start

分回文子串是奇数和偶数讨论,注意考虑越界情况

(1)奇数 left=i-1,right=i+1

向两侧扩散 a[left]=a[right],left--,right++

len=right-left-1与len比大小,大于则更新len和start的值

(2)偶数,left=i.right=i+1

与奇数同理

char* longestPalindrome(char* s) {int sz=strlen(s),start=0,len=0;for(int i=0;i<sz;i++){int left=i-1,right=i+1;while(left>=0&&right<sz&&s[left]==s[right] ){left--;right++;}if(right-left-1>len){len=right-left-1;start=left+1;}}for(int i=0;i<sz;i++){int left=i,right=i+1;while(left>=0&&right<sz&&s[left]==s[right]){left--;right++;}if(right-left-1>len){len=right-left-1;start=left+1;}}s[start+len]='\0';return s+start;
}

方法二:动态规划

dp[i][j]=1表示从i到j是回文串

1、初始化,dp[i][i]=1

2、依此检测长度为2,3...s.length的字符串是否是回文串

首尾相等的两种情况

(1)字符长度为2,3,就一定是回文串

(2)字符长度>3,dp[i][j]=dp[i+1][j-1]

char* longestPalindrome(char* s) {int sz=strlen(s),start=0,maxl=1;int dp[sz][sz]={};for(int i=0;i<sz;i++){dp[i][i]=1;}for(int len=2;len<=sz;len++){for(int i=0;i<sz;i++){int j=i+len-1;if(j>=sz)break;//注意越界情况if(s[i]==s[j]){if(len<=2)dp[i][j]=1;else dp[i][j]=dp[i+1][j-1];}if(dp[i][j]==1&&len>maxl){maxl=len;start=i;}}}s[start+maxl]='\0';return s+start;
}

相关文章:

leetcode day4 409+5

409 最长回文串 给定一个包含大写字母和小写字母的字符串 s &#xff0c;返回 通过这些字母构造成的 最长的 回文串 的长度。 在构造过程中&#xff0c;请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。 示例 1: 输入:s "abccccdd" 输出:7 解…...

英语语法学习框架(考研)

一、简单句 英语都是由简单句构成&#xff0c;简单句共有五种基本句型&#xff1a;①主谓&#xff1b;②主谓宾&#xff1b;③主谓宾宾补&#xff1b;④主谓宾间宾&#xff08;间接宾语&#xff09;&#xff1b;⑤主系表&#xff1b; 其中谓语是句子最重要的部分&#xff0c;谓…...

基于neo4j的学术论文关系管理系统

正在为毕业设计头疼&#xff1f;又或者在学术研究中总是找不到像样的工具来管理浩瀚的文献资料&#xff1f;今天给大家介绍一款超实用的工具——基于Neo4j的学术论文关系管理系统&#xff0c;让你轻松搞定学术文献的管理与展示&#xff01;&#x1f389; 系统的核心是什么呢&a…...

C#中的委托、匿名方法、Lambda、Action和Func

委托 委托概述 委托是存有对某个方法的引用的一种引用类型变量。定义方法的类型&#xff0c;可以把一个方法当作另一方法的参数。所有的委托&#xff08;Delegate&#xff09;都派生自 System.Delegate 类。委托声明决定了可由该委托引用的方法。 # 声明委托类型 委托类型声…...

IDEA关联Tomcat——最新版本IDEA 2024

1.链接Tomcat到IDEA上 添加Tomcat到IDEA上有两种方式&#xff1a; 第一种&#xff1a; &#xff08;1&#xff09;首先&#xff0c;来到欢迎界面&#xff0c;找到左侧的Customize选项 &#xff08;2&#xff09;然后找到Build、Execution、Deployment选项 &#xff08;3&am…...

【如何获取股票数据18】Python、Java等多种主流语言实例演示获取股票行情api接口之沪深A股解禁限售数据获取实例演示及接口API说明文档

最近一两年内&#xff0c;股票量化分析逐渐成为热门话题。而从事这一领域工作的第一步&#xff0c;就是获取全面且准确的股票数据。因为无论是实时交易数据、历史交易记录、财务数据还是基本面信息&#xff0c;这些数据都是我们进行量化分析时不可或缺的宝贵资源。我们的主要任…...

NVR小程序接入平台/设备EasyNVR多品牌NVR管理工具/设备的多维拓展与灵活应用

在数字化安防时代&#xff0c;NVR批量管理软件/平台EasyNVR作为一种先进的视频监控系统设备&#xff0c;正逐步成为各个领域监控解决方案的首选。NVR批量管理软件/平台EasyNVR作为一款基于端-边-云一体化架构的国标视频融合云平台&#xff0c;凭借其部署简单轻量、功能多样、兼…...

GPT-4o 和 GPT-4 Turbo 模型之间的对比

GPT-4o 和 GPT-4 Turbo 之间的对比 备注 要弄 AI &#xff0c;不同模型之间的对比就比较重要。 GPT-4o 是 GPT-4 Turbo 的升级版本&#xff0c;能够提供比 GPT-4 Turbo 更多的内容和信息&#xff0c;但成功相对来说更高一些。 第三方引用 在 2024 年 5 月 13 日&#xff0…...

gin入门教程(10):实现jwt认证

使用 github.com/golang-jwt/jwt 实现 JWT&#xff08;JSON Web Token&#xff09;可以有效地进行用户身份验证,这个功能往往在接口前后端分离的应用中经常用到。以下是一个基本的示例&#xff0c;演示如何在 Gin 框架中实现 JWT 认证。 目录结构 /hello-gin │ ├── cmd/ …...

Python 基础语法 - 数据类型

顾名思义&#xff0c;计算机就是用来做数学计算的机器&#xff0c;因此&#xff0c;计算机程序理所当然的可以处理各种数值。但是&#xff0c;计算机能处理的远远不止数值&#xff0c;还可以处理文本&#xff0c;图形&#xff0c;音频&#xff0c;视频&#xff0c;网页等各种各…...

自托管无代码数据库Undb

什么是 Undb &#xff1f; Undb 是一个无代码平台&#xff0c;也可以作为后端即服务 (BaaS)。它基于 SQLite&#xff0c;可以使用 Bun 打包成二进制文件用于后端服务。此外&#xff0c;它可以通过 Docker 部署为服务&#xff0c;提供表管理的 UI。 软件特点&#xff1a; ⚡ 无…...

正则的正向前瞻断言和负向前瞻断言

正则的正向前瞻断言和负向前瞻断言 一. 正向前瞻断言二. 负向前瞻断言三. 总结 这是我在这个网站整理的笔记,有错误的地方请指出&#xff0c;关注我&#xff0c;接下来还会持续更新。 作者&#xff1a;神的孩子都在歌唱 正向前瞻断言和负向前瞻断言是正则表达式中用于检查后续字…...

大厂物联网(IoT)高频面试题及参考答案

目录 解释物联网 (IoT) 的基本概念 物联网的主要组成部分有哪些? 描述物联网的基本架构。 IoT 与传统网络有什么区别? 物联网中常用的传感器类型有哪些? 描述物联网的三个主要层次。 简述物联网中数据安全的重要性 描述物联网安全的主要威胁 解释端到端加密在 IoT 中…...

react hook

react hook 最近实习有点忙&#xff0c;所以学习记录没来得及写。 HOC higher order components(HOC) 高阶组件是一个组件&#xff0c;接受一个参数作为组件&#xff0c;返回值也是一个组件的函数。高阶组件作用域强化组件&#xff0c;服用逻辑&#xff0c;提升渲染性能等。…...

Jetpack架构组件_LiveData组件

1.LiveData初识 LiveData:ViewModel管理要展示的数据&#xff08;VM层类似于原MVP中的P层&#xff09;&#xff0c;处理业务逻辑&#xff0c;比如调用服务器的登陆接口业务。通过LiveData观察者模式&#xff0c;只要数据的值发生了改变&#xff0c;就会自动通知VIEW层&#xf…...

Etcd 可观测最佳实践

简介 Etcd 是一个高可用的分布式键值存储系统&#xff0c;它提供了一个可靠的、强一致性的存储服务&#xff0c;用于配置管理和服务发现。它最初由 CoreOS 开发&#xff0c;现在由 Cloud Native Computing Foundation (CNCF) 维护。Etcd 使用 Raft 算法来实现数据的一致性&…...

钉钉录播抓取视频

爬取钉钉视频 免责声明 此脚本仅供学习参考&#xff0c;切勿违法使用下载他人资源进行售卖&#xff0c;本人不但任何责任! 仓库地址: GItee 源码仓库 执行顺序 poxyM3u8开启代理getM3u8url用于获取m3u8文件userAgent随机请求头downVideo|downVideoThreadTqdm单线程下载和…...

centos下面的jdk17的安装配置

文章目录 1.基本指令回顾2.jdk17的安装到这个centos上面2.1首先切换到这个root下面去2.2查看系统jdk版本2.3首先到官网找到进行下载2.4安装包的上传2.5jdk17的安装包的解压过程2.6配置环境变量2.7是否设置成功&#xff0c;查看版本 1.基本指令回顾 ls:list也就是列出来这个目录…...

【操作系统】——调度

&#x1f339;&#x1f60a;&#x1f339;博客主页&#xff1a;【Hello_shuoCSDN博客】 ✨操作系统详见 【操作系统专项】 ✨C语言知识详见&#xff1a;【C语言专项】 目录 处理机调度的概念、层次 进程调度的时机、切换与过程、方式 调度器和闲逛进程 处理机调度的概念、层…...

基于Aspose依赖添加自定义文本水印——Word、Pdf、Cell

基于Aspose依赖添加自定义文本水印——Word、Pdf、Cell 所需依赖Word水印Pdf水印——&#xff08; 注意 pdf 存在找不到字体的问题&#xff09;Excel水印 所需依赖 <dependency><groupId>com.aspose</groupId><artifactId>aspose-pdf</artifactId&g…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

SkyWalking 10.2.0 SWCK 配置过程

SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外&#xff0c;K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案&#xff0c;全安装在K8S群集中。 具体可参…...

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

QT: `long long` 类型转换为 `QString` 2025.6.5

在 Qt 中&#xff0c;将 long long 类型转换为 QString 可以通过以下两种常用方法实现&#xff1a; 方法 1&#xff1a;使用 QString::number() 直接调用 QString 的静态方法 number()&#xff0c;将数值转换为字符串&#xff1a; long long value 1234567890123456789LL; …...