【Python3】【力扣题】409. 最长回文串

【力扣题】题目描述：

（题意理解）统计如下：

① 字母个数本身是偶数。

② 字母个数是奇数，统计奇数中的偶数部分，例如：字母个数为3，统计其中的2。

③ 中间可以有一个奇数字母。即只要有奇数，不论多少奇数，最终总和再加一个1。

【Python3】代码：

解题思路：先统计出各字符总共出现次数，加和偶数部分（包括奇数的偶数部分），若有奇数最后再加1。用变量isodd记录是否有奇数。

知识点：{ }：空字典。字典：键值对的序列。

              字典[键]：获取或修改键对应的值。

             字典.values()：返回字典中所有值。

             b % 2 == 0：判断数值是否为偶数。

class Solution:def longestPalindrome(self, s: str) -> int:# 遍历字符串中每个字符，用字典统计出现个数adict = {}for a in s:if a not in adict: adict[a] = 1 else: adict[a] += 1# 遍历字典的所有值，所有偶数加和（含奇数的偶数部分）isodd = 0      # 用于记录是否有奇数total = 0for b in adict.values():if b % 2 == 0: total += belse: total += b - 1isodd = 1# 最多一个奇数在中间，若有奇数最后再加1return total + 1 if isodd == 1 else total

可以在用字典统计个数时，加总偶数，最后总和小于字符串长度，则表示有奇数，最后加1。

class Solution:def longestPalindrome(self, s: str) -> int:# 遍历字符串所有字符，用字典统计个数，统计到偶数个，加入总和，字典中恢复为0total = 0adict = {}for a in s:if a not in adict: adict[a] = 1 else: adict[a] += 1# 若个数是偶数即2，则总和+2，字典中对应值恢复为0if adict[a] % 2 == 0:total += 2adict[a] = 0# 若总和小于字符串长度（即有奇数），则总和加1return total + 1 if total < len(s) else total

python的collections库中Counter类可直接统计各元素出现个数。类似字典。

class Solution:def longestPalindrome(self, s: str) -> int:# 统计各字母出现次数adict = collections.Counter(s)# 遍历各字母的个数，偶数部分加和total = 0for b in adict.values():if b % 2 == 0: total += belse: total += b - 1# 若有奇数，最后总和加1return total + 1 if total < len(s) else total 

（官方题解）贪心

统计各字母出现次数，遍历各字母个数，加总偶数部分，若有奇数只加一次1。

知识点： b // 2：除法取整。例如：3 // 2 = 1。

                b % 2 == 1：判断数值是否是奇数。

class Solution:def longestPalindrome(self, s: str) -> int:# 统计各字母出现次数adict = collections.Counter(s)# 遍历各字母个数，偶数部分加和，若有奇数且总和为偶数则加1total = 0for b in adict.values():total += b // 2 * 2# 字母个数为奇数，总和为偶数，即确保只有一个奇数在中间位置if b % 2 == 1 and total % 2 == 0:total += 1return total