贪心算法：LeetCode 409 最长回文串双 100 题解

这篇文章分享如何借助位的思想将 LeetCode 409——最长回文串的题解优化到双 100。 题目 题目本身是 easy 级别的，原题目是： 给定一个包含大写字母和小写字母的字符串 s ，返回 通过这些字母构造成的 最长的回文串 。 在构造过程中，请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。 思路分析 基本的思路是遍历字符串中的所有字符，并且统计每个字符出现的次数，最后求和 length： 如果字符出现次数为偶数，则将结果 length 直接加 2； 如果字符出现次数为奇数，则进一步判断： 如果 length 未曾加过奇数，则将结果 length 直接加上这个奇数； 如果 length 已经加过奇数，则将结果 length 直接加上这个奇数-1。 这个思路的基本原则是所有出现次数为偶数的字符可以刚好位于回文中心的两侧，而最多只能有一个长度为奇数的回文中心，超过的子串就只能舍弃掉一个字符使其变成偶数长度。 对应代码 func longestPalindrome(s string) int { stats := map[rune]int{} for _, b := range s { if _, found := stats[b]; !found { stats[b] = 0 } stats[b]++ } length := 0 hasOdd := false for _, count := range stats { if count % 2 == 0 { length += count continue } if !hasOdd { length += count hasOdd = true continue } length += (count - 1) } return length } 这个题解得到的结果是 100% 时间优势，39% 空间优势，空间占用看来有比较大的优化空间。 优化思路分析 第一遍的算法思路，为了统计，我们用了一个字典来存储各个字符的出现次数，并且需要在统计完成后再一次遍历统计得到的字典。最明显的问题是空间的消耗，每个字符都需要一个 int 类型的数据结构，一般涉及字典以及计数，我都会在优化的时候想一下能不能用位来标记。 因为题目中给定字符串中所有可能的字符均为大小写字母，而参考 ASCII 码中，'A' 的码值为 65，最大码值的 'z' 为 122，相差 57，如果我们用一个 uint64 类型的变量来表示，则刚好可以容纳所有字母的表示，因为 57 < 64。 而改为位标记之后，因为一个位只能表示 0 或者 1，则我们需要考虑一个字符出现次数超过 1 次之后的处理。根据回文的特点，只要一个字符两两出现，则一定可以添加到回文串中，于是我们考虑每次用一个位表示某个字符是否已经出现过，如果是，再遇到一个时，该位置为 0，length 加 2；如果某个字符未曾出现或者之前已经因为偶数置为0，再遇到一个相同字符时，该字符所对应的位置为 1。 算法的整体思路描述： 初始化 uint64 类型变量 stats 初始化 int 类型变量 length 遍历字符串 s 中的每个字符 查找该字符在 stats 中对应的位的值 bit 如果 bit 为 0，将该 bit 置为 1，继续下一个字符 如果 bit 为 1，将该 bit 置为 0，length 加 2 最后遍历 stats 中的每一个位 如果某位不为 0，则 length 加 1，同时退出遍历 对应代码： func longestPalindrome(s string) int { var stats uint64 var length int for i := 0; i < len(s); i++ { bits := s[i] - 'A' if stats >> bits & 1 == 1 { length += 2 stats &= (math.MaxUint64 - 1<<bits) continue } stats |= 1<<bits } for i := 0; i < 64; i++ { if stats >> i & 1 == 1 { length++ break } } return length } 这个新的思路里，一方面使用一个 uint64 代替了原来的字典，空间复杂度变成 O(0)，另外使用了位操作，逻辑稍微复杂了一点。最终提交结果为双 100。 LeetCode 409 提交结果