LeetCode C++ 409. Longest Palindrome【String/Hash Table】简单
发布日期:2021-07-01 02:52:55
浏览次数:2
分类:技术文章
本文共 1595 字,大约阅读时间需要 5 分钟。
Given a string s
which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters.
Letters are case sensitive, for example, "Aa"
is not considered a palindrome here.
Example 1:
Input: s = "abccccdd"Output: 7Explanation:One longest palindrome that can be built is "dccaccd", whose length is 7.
Example 2:
Input: s = "a"Output: 1
Example 3:
Input: s = "bb"Output: 2
Constraints:
1 <= s.length <= 2000
- s consits of lower-case and/or upper-case English letters only.
题意:给定一个包含大写字母和小写字母的字符串 s
,找到通过这些字母构造成的最长的回文串(大小写敏感)。
思路
利用回文串的特征——串中每个字符出现的次数为偶数次,或者只有奇数长度回文串中心位置的字符出现次数为奇数次。因此,我们记录字符串 s
中每个字母的出现次数,然后找到其中最大的奇数出现次数:
- 如果没有奇数次数,全是偶数次数,则能够构成的回文串长度就是
s
的长度; - 不然就找到了最大的奇数出现次数,然后加上其他偶数出现次数或者奇数出现次数减一,就是最长的回文串长度。
代码如下:
class Solution { public: int longestPalindrome(string s) { int charset[52] = { 0}; for (const char &c : s) { if (islower(c)) ++charset[c - 'a']; //小写字母 else ++charset[c - 'A' + 26]; //大写字母 } int even = 0, odd = 0; //最大的奇数次出现次数 bool isMaxOdd = true; for (int i = 0; i < 52; ++i) if (charset[i] & 1) odd = max(odd, charset[i]); for (int i = 0; i < 52; ++i) { if ((charset[i] & 1)) { //出现次数是奇数 if (charset[i] == odd && isMaxOdd) isMaxOdd = false; //避免重复计算最大的奇数次出现次数 else even += charset[i] - 1; } else even += charset[i]; } return odd + even; }};
提交后效率如下:
执行用时:8 ms, 在所有 C++ 提交中击败了46.88% 的用户内存消耗:6.4 MB, 在所有 C++ 提交中击败了89.87% 的用户
转载地址:https://memcpy0.blog.csdn.net/article/details/108908852 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年05月04日 12时26分56秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
HP-UX oracle RAC 双机实践
2019-05-02
解决SHELL脚本中的export无法生效的问题【转】
2019-05-02
linux中的sh脚本语法【转】
2019-05-02
区别数据结构中的堆栈与内存中的堆栈的个人总结【转】
2019-05-02
c++中冒号(:)和双冒号(::)的用法【转】
2019-05-02
《计算机视觉-一种现代方法(第2版)》读书笔记三:早期视觉(一幅图像)
2019-05-02
如何撰写高水平的学术论文
2019-05-02
谭浩强《C++面向对象程序设计》知识点总结
2019-05-02
分享一个关于介绍TextCNN和TextRNN的文章
2019-05-02
关于CNN中感受野的理解和计算方法
2019-05-02
java基础----RandomAccessFile
2019-05-02
__attribute__((packed))
2019-05-02
Android深入浅出之Binder机制
2019-05-02
linux查看硬件信息
2019-05-02
linux支持大于4G内存
2019-05-02
WM_GETINFO相关
2019-05-02
填入空隙(setbkcolor,setbkmode)
2019-05-02
[收藏] FC交换机基础知识详解
2019-05-02
关于数据中台系统,需要了解哪些技术?
2019-05-02
Linux调试工具
2019-05-02