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 ,返回 通过这些字母构造成的 最长的 回文串 的长度。 在构造过程中,请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。 示例 1: 输入:s "abccccdd" 输出:7 解…...
英语语法学习框架(考研)
一、简单句 英语都是由简单句构成,简单句共有五种基本句型:①主谓;②主谓宾;③主谓宾宾补;④主谓宾间宾(间接宾语);⑤主系表; 其中谓语是句子最重要的部分,谓…...
基于neo4j的学术论文关系管理系统
正在为毕业设计头疼?又或者在学术研究中总是找不到像样的工具来管理浩瀚的文献资料?今天给大家介绍一款超实用的工具——基于Neo4j的学术论文关系管理系统,让你轻松搞定学术文献的管理与展示!🎉 系统的核心是什么呢&a…...
C#中的委托、匿名方法、Lambda、Action和Func
委托 委托概述 委托是存有对某个方法的引用的一种引用类型变量。定义方法的类型,可以把一个方法当作另一方法的参数。所有的委托(Delegate)都派生自 System.Delegate 类。委托声明决定了可由该委托引用的方法。 # 声明委托类型 委托类型声…...
IDEA关联Tomcat——最新版本IDEA 2024
1.链接Tomcat到IDEA上 添加Tomcat到IDEA上有两种方式: 第一种: (1)首先,来到欢迎界面,找到左侧的Customize选项 (2)然后找到Build、Execution、Deployment选项 (3&am…...
【如何获取股票数据18】Python、Java等多种主流语言实例演示获取股票行情api接口之沪深A股解禁限售数据获取实例演示及接口API说明文档
最近一两年内,股票量化分析逐渐成为热门话题。而从事这一领域工作的第一步,就是获取全面且准确的股票数据。因为无论是实时交易数据、历史交易记录、财务数据还是基本面信息,这些数据都是我们进行量化分析时不可或缺的宝贵资源。我们的主要任…...
NVR小程序接入平台/设备EasyNVR多品牌NVR管理工具/设备的多维拓展与灵活应用
在数字化安防时代,NVR批量管理软件/平台EasyNVR作为一种先进的视频监控系统设备,正逐步成为各个领域监控解决方案的首选。NVR批量管理软件/平台EasyNVR作为一款基于端-边-云一体化架构的国标视频融合云平台,凭借其部署简单轻量、功能多样、兼…...
GPT-4o 和 GPT-4 Turbo 模型之间的对比
GPT-4o 和 GPT-4 Turbo 之间的对比 备注 要弄 AI ,不同模型之间的对比就比较重要。 GPT-4o 是 GPT-4 Turbo 的升级版本,能够提供比 GPT-4 Turbo 更多的内容和信息,但成功相对来说更高一些。 第三方引用 在 2024 年 5 月 13 日࿰…...
gin入门教程(10):实现jwt认证
使用 github.com/golang-jwt/jwt 实现 JWT(JSON Web Token)可以有效地进行用户身份验证,这个功能往往在接口前后端分离的应用中经常用到。以下是一个基本的示例,演示如何在 Gin 框架中实现 JWT 认证。 目录结构 /hello-gin │ ├── cmd/ …...
Python 基础语法 - 数据类型
顾名思义,计算机就是用来做数学计算的机器,因此,计算机程序理所当然的可以处理各种数值。但是,计算机能处理的远远不止数值,还可以处理文本,图形,音频,视频,网页等各种各…...
自托管无代码数据库Undb
什么是 Undb ? Undb 是一个无代码平台,也可以作为后端即服务 (BaaS)。它基于 SQLite,可以使用 Bun 打包成二进制文件用于后端服务。此外,它可以通过 Docker 部署为服务,提供表管理的 UI。 软件特点: ⚡ 无…...
正则的正向前瞻断言和负向前瞻断言
正则的正向前瞻断言和负向前瞻断言 一. 正向前瞻断言二. 负向前瞻断言三. 总结 这是我在这个网站整理的笔记,有错误的地方请指出,关注我,接下来还会持续更新。 作者:神的孩子都在歌唱 正向前瞻断言和负向前瞻断言是正则表达式中用于检查后续字…...
大厂物联网(IoT)高频面试题及参考答案
目录 解释物联网 (IoT) 的基本概念 物联网的主要组成部分有哪些? 描述物联网的基本架构。 IoT 与传统网络有什么区别? 物联网中常用的传感器类型有哪些? 描述物联网的三个主要层次。 简述物联网中数据安全的重要性 描述物联网安全的主要威胁 解释端到端加密在 IoT 中…...
react hook
react hook 最近实习有点忙,所以学习记录没来得及写。 HOC higher order components(HOC) 高阶组件是一个组件,接受一个参数作为组件,返回值也是一个组件的函数。高阶组件作用域强化组件,服用逻辑,提升渲染性能等。…...
Jetpack架构组件_LiveData组件
1.LiveData初识 LiveData:ViewModel管理要展示的数据(VM层类似于原MVP中的P层),处理业务逻辑,比如调用服务器的登陆接口业务。通过LiveData观察者模式,只要数据的值发生了改变,就会自动通知VIEW层…...
Etcd 可观测最佳实践
简介 Etcd 是一个高可用的分布式键值存储系统,它提供了一个可靠的、强一致性的存储服务,用于配置管理和服务发现。它最初由 CoreOS 开发,现在由 Cloud Native Computing Foundation (CNCF) 维护。Etcd 使用 Raft 算法来实现数据的一致性&…...
钉钉录播抓取视频
爬取钉钉视频 免责声明 此脚本仅供学习参考,切勿违法使用下载他人资源进行售卖,本人不但任何责任! 仓库地址: 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是否设置成功,查看版本 1.基本指令回顾 ls:list也就是列出来这个目录…...
【操作系统】——调度
🌹😊🌹博客主页:【Hello_shuoCSDN博客】 ✨操作系统详见 【操作系统专项】 ✨C语言知识详见:【C语言专项】 目录 处理机调度的概念、层次 进程调度的时机、切换与过程、方式 调度器和闲逛进程 处理机调度的概念、层…...
基于Aspose依赖添加自定义文本水印——Word、Pdf、Cell
基于Aspose依赖添加自定义文本水印——Word、Pdf、Cell 所需依赖Word水印Pdf水印——( 注意 pdf 存在找不到字体的问题)Excel水印 所需依赖 <dependency><groupId>com.aspose</groupId><artifactId>aspose-pdf</artifactId&g…...
系统设计 --- MongoDB亿级数据查询优化策略
系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log,共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题,不能使用ELK只能使用…...
vue3 定时器-定义全局方法 vue+ts
1.创建ts文件 路径:src/utils/timer.ts 完整代码: import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...
鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/
使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题:docker pull 失败 网络不同,需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...
vue3+vite项目中使用.env文件环境变量方法
vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量,这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...
【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统
目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索(基于物理空间 广播范围)2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...
C++使用 new 来创建动态数组
问题: 不能使用变量定义数组大小 原因: 这是因为数组在内存中是连续存储的,编译器需要在编译阶段就确定数组的大小,以便正确地分配内存空间。如果允许使用变量来定义数组的大小,那么编译器就无法在编译时确定数组的大…...
算法岗面试经验分享-大模型篇
文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer (1)资源 论文&a…...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...
Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战
说明:这是一个机器学习实战项目(附带数据代码文档),如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下,风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...
Netty从入门到进阶(二)
二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架,用于…...
