409. 最长回文串
- 题号:力扣409
- 知识点:贪心,哈希,字符串
- 目标完成度:44/150
- 总结
题干:
文章图片
- 1.回文字符串的样式:
BAB
- 2.我的想法是,首先要构成回文字符串,除了中间的那个类的字母数量可以是奇数个,其他的都必须是偶数个。
- 3.如果
s
中的某类字母的个数是偶数2n
个,则这2n
个在构造回文字符串时都可以用上。 - 4.如果
s
中的某类字母的个数是奇数2n+1
个,则除了回文字符串中间位置可以允许放奇数个字符,其他位置用上2n
个。 - 5.那么放在中间的字母是哪一类呢?根据贪心思想,放奇数次字母中出现次数最多的那类字母,可以使最终的回文字符串长度最长
- 6.实现方法:先建立一个字典,根据value(出现次数)的值,提取处奇数次的字母
odd
,偶数次的字母直接加到ans
中 - 7.对
odd
排个序,把最大的那个奇数直接加到ans
上,其他的出现次数减一再加到ans
上。减一目的是为了凑成偶数次,构造回文字符串的对称结构。
class Solution:
def longestPalindrome(self, s: str) -> int:
dic = collections.Counter(s)
odd = []
ans = 0
for key, value in dic.items():
if value%2 == 1:
odd.append([key, value])
else:
ans += value
odd.sort(key=lambda arr:arr[1])
odd = odd[::-1]
for i in range(len(odd)):
if i == len(odd):
# odd[0][1] 是出现奇数次的字母中出现次数最多的那个字母的字数,这个放在中间位置
ans += odd[i][1]
else:
ans += (odd[i][1]-1)
return ans
推荐阅读
- leetcode|415. 字符串相加
- 二叉树|leetcode系列-199.二叉树的右视图
- #|求解热电联产经济调度问题的改进遗传与粒子群算法
- python|python编写冒泡算法
- 单调栈进阶-接雨水-最大矩形
- 算法|【前沿】陈丹琦团队最新论文(受GPT-3启发,用小样本学习给语言模型做微调,性能最高提升30%...)
- 一起刷好题|《力扣每日一题》—— 合并两个有序链表
- 一起刷好题|《牛客每日一题》链表分割、输出链表的倒数第k个结点
- 一起刷好题|力扣每日一题(环形链表II)