【力扣题】题目描述:
(题意理解)统计如下:
① 字母个数本身是偶数。
② 字母个数是奇数,统计奇数中的偶数部分,例如:字母个数为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