LeetCode题练习与总结：最长回文串--409
一、题目描述
给定一个包含大写字母和小写字母的字符串 s ，返回 通过这些字母构造成的 最长的 回文串 的长度。
在构造过程中，请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。
示例 1:
输入:s = "abccccdd" 输出:7 解释: 我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
示例 2:
输入:s = "a" 输出:1 解释：可以构造的最长回文串是"a"，它的长度是 1。
提示:
1 <= s.length <= 2000s只由小写 和/或 大写英文字母组成
二、解题思路
- 首先，我们需要统计字符串中每个字符出现的次数。
- 对于每个字符，如果它的出现次数是偶数，那么我们可以将所有的这些字符都用于构造回文串。
- 如果某个字符的出现次数是奇数，那么我们可以使用其中的偶数部分（即次数减一）来构造回文串，并且我们可以选择一个字符作为回文串的中心（如果还没有选择中心字符的话）。
- 最后，我们将所有偶数出现次数的字符的总数加上一个可能的中心字符（如果存在的话）的个数，就是可以构造的最长回文串的长度。
三、具体代码
class Solution {
public int longestPalindrome(String s) {
// 用于统计字符出现次数的数组，大小为128，足以覆盖ASCII码中的所有大写和小写字母
int[] count = new int[128];
for (char c : s.toCharArray()) {
// 统计每个字符出现的次数
count[c]++;
}
int result = 0;
boolean hasOdd = false; // 用于标记是否已经有一个奇数出现次数的字符被用作中心字符
for (int val : count) {
// 如果字符出现次数是偶数，则全部加入结果
if (val % 2 == 0) {
result += val;
} else {
// 如果字符出现次数是奇数，则加入偶数部分，并标记存在奇数
result += val - 1;
hasOdd = true;
}
}
// 如果存在奇数出现次数的字符，则可以在回文串中心放置一个字符
if (hasOdd) {
result++;
}
return result;
}
}
这段代码首先统计了每个字符的出现次数，然后计算了可以构成的最长回文串的长度，最后返回这个长度。在计算过程中，如果遇到出现次数为奇数的字符，则将偶数部分加到结果中，并标记可以放置一个中心字符。如果所有字符的出现次数都是偶数，则直接返回所有字符的总数。如果至少有一个字符的出现次数是奇数，则在最后的结果上加一，表示可以放置一个中心字符。
四、时间复杂度和空间复杂度
1. 时间复杂度
-
统计字符出现次数的循环：我们遍历了字符串
s中的所有字符，假设字符串的长度为n，则这一步的时间复杂度为 O(n)。 -
遍历统计数组
count的循环：由于count的大小是固定的，为128（ASCII码中大小写字母的数量），因此这一步的时间复杂度为 O(1)，可以认为是常数时间复杂度。
综合以上两步，整体的时间复杂度为 O(n)，其中 n 是字符串 s 的长度。
2. 空间复杂度
-
统计字符出现次数的数组
count：这是一个大小为128的固定大小的数组，因此这一步的空间复杂度为 O(1)，可以认为是常数空间复杂度。 -
变量
result和hasOdd：这些是几个基本数据类型的变量，它们占用的空间是固定的，因此这一步的空间复杂度也是 O(1)。
综合以上两步，整体的空间复杂度为 O(1)，即算法使用了固定大小的额外空间，与输入字符串的长度无关。
五、总结知识点
-
字符数组统计：使用一个固定大小的数组
count来统计字符串中每个字符出现的次数。数组的索引对应字符的ASCII码值，而数组的值则是对应字符出现的次数。 -
遍历字符串：使用增强型
for循环（for-each循环）来遍历字符串中的每个字符。 -
ASCII码：代码中使用的数组大小为128，这是因为ASCII码表中的字符总数为128，包括了所有的大写和小写英文字母以及一些特殊字符。
-
取模运算：使用
%运算符来检查一个数字是否为偶数，即val % 2 == 0。 -
逻辑判断：使用
if-else语句来根据字符出现次数的奇偶性来决定如何累加到结果中。 -
布尔变量：使用布尔变量
hasOdd来标记是否有字符的出现次数为奇数，这个标记用于最后决定是否可以在回文串中心放置一个字符。 -
整型累加：使用整型变量
result来累加可以构成回文串的字符数量。 -
数组遍历：使用增强型
for循环来遍历count数组，以统计可以构成回文串的字符数量。 -
条件语句：在最后，使用
if语句来检查hasOdd变量，如果为true，则在结果中加一，表示可以放置一个中心字符。 -
方法返回值：使用
return语句来返回最终计算出的最长回文串的长度。
以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。
原文地址：https://blog.csdn.net/weixin_62860386/article/details/143899017
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！