leetcode409.最长回文串

news/2024/9/20 1:55:49/ 标签: 算法, 数据结构

题目描述:

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

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

示例一:
 

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

示例二:
 

输入:s = "a"
输出:1

示例三:
 

输入:s = "aaaaaccc"
输出:7

问题解决:

回文串大家一定都了解,就是关于最中间对称的字符串,我们可以利用这一特性来向其两边来分配

元素其中必须要保持左右两边的元素关于中间对称,再次简化,我们只用统计字符个数,如果字符

个数是偶数,直接将其加到最终长度之中,应为将此字符对半放在对称的两边,该字符串一定还是

回文的,如果是奇数,就将其转换成最大的偶数在加入到最终长度之中,与上面所描述的一样,最

后考虑在对称的最中间是否可以放入元素,也就是判断是否还有元素剩余,可以将最终长度和原来

字符串的长度进行比较,如果相等,说明没有剩余元素,否则,将最终长度再加1,可以将任意一

个剩余元素加入到回文字符串的最中间。

对应的代码实现:
 

class Solution 
{
public:int longestPalindrome(string s) {//1.计数---数组模拟哈希表int hash[127] = {0};for(auto ch : s){hash[ch]++;}//2.统计结果int ret = 0;for(int x : hash){ret += x / 2 *2;}if(ret < s.size()){return ret + 1;}elsereturn ret;}
};

这道题相对来说比较简单,只要统计字符个数即可。


http://www.ppmy.cn/news/1451995.html

相关文章

STM32入门学习之DMA

1.直接存储访问DMA(Direct Memory Access)&#xff1a;DMA传输不需要CPU的参与&#xff0c;直接在内存和I/O设备间开辟了一条新的数据传输通道&#xff0c;不仅提高数据传输的速率&#xff0c;还因为不需要CPU的干预&#xff0c;从而提高了CPU的利用率。(注&#xff1a;文中的资…

Jenkins自动化搭建记录

每一份努力都是有一份期盼&#xff0c;每一份付出都是为了有更多的收获。 本文记录一次搭建Jenkins自动参数化打包APK的实现过程和碰到的问题&#xff0c;实现了在Windows和Mac系统下的自动化打包流程。 因为Jenkins的安装过程在网上的教程很多&#xff0c;这里就不在赘述。 …

华为试题之删除最少字符

题目描述 删除字符串中出现次数最少的字符 如果多个字符出现次数一样则都删除 输入描述 输入只包含小写字母 输出描述 输出删除后剩余的字符 若删除后字符串长度为0&#xff0c;则输出empty 我的思路是将字符串中的字符对应的数量和key统计后放到对应的字典中&#xff0c; 对字…

python项目==一个web项目,配置模板指定文件清洗规则,调用模板规则清洗文件

代码地址 一个小工具。 一个web项目&#xff0c;配置模板指定文件清洗规则&#xff0c;调用模板规则清洗文件 https://github.com/hebian1994/csv-transfer-all 技术栈&#xff1a; SQLite python flask vue3 elementplus 功能介绍&#xff1a; A WEB tool for cleaning…

OpenWRT有线桥接部署教程

前言 之前咱们讲到OpenWRT部署WAN实现PPPoE拨号上网和自动获取IP模式上网的办法&#xff1a; OpenWRT设置PPPoE拨号教程 OpenWRT设置自动获取IP&#xff0c;作为二级路由器 这一次&#xff0c;咱们尝试用OpenWRT有线桥接上一级路由器的教程。 可能有小伙伴敏锐地发现了&am…

阿里云API网关 产品的使用笔记

阿里云的产品虽多&#xff0c;还是一如既往的一用一个看不懂&#xff0c;该模块的文档依旧保持“稳定”发挥&#xff0c;磕了半天才全部跑通。 用阿里云API网关的原因是&#xff0c;在Agent中写插件调用API的时候&#xff0c;需要使用Https协议&#xff0c;又嫌搞备案、证书等事…

《Mask2Former》算法详解

文章地址&#xff1a;《Masked-attention Mask Transformer for Universal Image Segmentation》 代码地址&#xff1a;https://github.com/facebookresearch/Mask2Former 文章为发表在CVPR2022的一篇文章。从名字可以看出文章像提出一个可以统一处理各种分割任务&#xff08;…

望仙谷听谿涛

望仙谿涛 近来不知为何&#xff0c;染上喝咖啡的恶习&#xff0c;称为“恶”&#xff0c;是因为要花钱&#xff0c;而且非得是那种口感好的。 网络流行“人生无解&#xff0c;来杯拿铁”。 大抵是因为咖啡再苦&#xff0c;也比不过生活吧&#xff0c;至少咖啡可以加糖&#xff…

数据库管理-第179期 分库分表vs分布式(20240430

数据库管理179期 2024-04-30 数据库管理-第179期 分库分表vs分布式&#xff08;20240430&#xff09;1 分库分表1.1 分库1.2 分表1.3 组合1.4 问题 2 分布式3 常见分布式数据库4 期望总结 数据库管理-第179期 分库分表vs分布式&#xff08;20240430&#xff09; 作者&#xff1…

C++ 函数与指针

函数内部数据是地址需要传递给调用函数&#xff0c;返回的当然是指针了&#xff01;当然&#xff0c;这个返回地址也可以通过函数参数返回&#xff01; 函数的参数是指针可以输出函数多个结果&#xff0c;返回值本身就是返回数据&#xff0c;什么时候需要返回指针呢&#xff1f…

WebSocket 的封装

websocket 具体内容参考了 原文 import {ref, onUnmounted} from vue; import dayjs from "dayjs";class Socket {url;ws null;opts;reconnectAttempts 0;listeners {};heartbeatInterval null;constructor(url, opts {}) {this.url url;this.opts {// 心跳检…

Java image-processing 包依赖错误

错误的信息为&#xff1a; [ERROR] Failed to execute goal on project image-processing: Could not resolve dependencies for project com.ossez:image-processing:jar:0.0.2-SNAPSHOT: Failed to collect dependencies at org.openimaj:core-image:jar:1.3.10 -> org.op…

机器学习每周挑战——二手车车辆信息交易售价数据

这是数据集的截图 目录 背景描述 数据说明 车型对照&#xff1a; 燃料类型对照&#xff1a; 老规矩&#xff0c;第一步先导入用到的库 第二步&#xff0c;读入数据&#xff1a; 第三步&#xff0c;数据预处理 第四步&#xff1a;对数据的分析 第五步&#xff1a;模型建…

ES集群分布式查询原理

集群分布式查询 elasticsearch的查询分成两个阶段&#xff1a; scatter phase&#xff1a;分散阶段&#xff0c;coordinating node会把请求分发到每一个分片gather phase&#xff1a;聚集阶段&#xff0c;coordinating node汇总data node的搜索结果&#xff0c;并处理为最终结…

设计模式的原则与分类

一、设计模式的原则 1、单一职责原则 一个类只需要负责一种职责即可&#xff0c;一个类发生变化的原因&#xff0c;必然是所负责的职责发生变化 2、接口隔离原则 单一职责原则是接口隔离原则的基础&#xff0c;单一职责原则注重职责的划分&#xff0c;从职责角度进行类和接口…

使用docker创建rocketMQ主从结构,使用

1、 创建目录 mkdir -p /docker/rocketmq/logs/nameserver-a mkdir -p /docker/rocketmq/logs/nameserver-b mkdir -p /docker/rocketmq/logs/broker-a mkdir -p /docker/rocketmq/logs/broker-b mkdir -p /docker/rocketmq/store/broker-a mkdir -p /docker/rocketmq/store/b…

【数据结构与算法】力扣 347. 前 K 个高频元素

题目描述 给你一个整数数组 nums 和一个整数 k &#xff0c;请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。 示例 1: 输入: nums [1,1,1,2,2,3], k 2 输出: [1,2]示例 2: 输入: nums [1], k 1 输出: [1]提示&#xff1a; 1 < nums.length < …

KIE关键信息抽取——SDMG-R

https://arxiv.org/pdf/2103.14470https://arxiv.org/pdf/2103.14470 1.概述 背景:传统的关键信息提取方法依赖于模板匹配,这使它们难以泛化到未见过的模板,且对文本识别错误不够鲁棒。SDMG-R方法:提出一种端到端的双模态图推理方法,通过构建双模态图(视觉和文本特征),…

多级留言/评论的功能实现——SpringBoot3后端篇

目录 功能描述数据库表设计后端接口设计实体类entity 完整实体类dto 封装请求数据dto 封装分页请求数据vo 请求返回数据 Controller控制层Service层接口实现类 Mapper层Mybatis 操作数据库 补充&#xff1a;返回的数据结构自动创建实体类 最近毕设做完了&#xff0c;开始来梳理…

【CTF MISC】XCTF GFSJ0512 give_you_flag Writeup(图像处理+QR Code识别)

give_you_flag 菜狗找到了文件中的彩蛋很开心&#xff0c;给菜猫发了个表情包 解法 图片的最后一帧好像闪过了什么东西。 用 Photoshop 打开&#xff0c;检查时间轴。 找到一张二维码&#xff0c;但是缺了三个角&#xff08;定位图案&#xff09;&#xff0c;无法识别。 找一…