LeetCode算法题-Longest Palindrome(Java实现-五种解法)
这是悦乐书的第220次更新,第232篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第87题(顺位题号是409)。给定一个由小写或大写字母组成的字符串,找到可以用这些字母构建的最长的回文长度。这是区分大小写的,例如“Aa”在这里不被视为回文。例如:
输入:“abccccdd”
输出:7
说明:可以建造的最长的回文是“dccaccd”,其长度为7。
注意:假设给定字符串的长度不超过1,010。
本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。
02 第一种解法
给定的字符范围是大小写字母,因此使用一个长度为256的整型数组,来存储字符串s中每个字符出现的次数。想要构成回文,字符串中的各个字符出现的次数分为两种情况:一是该字符出现偶数次,二是该字符出现奇数次。出现偶数次可以直接拿来使用,只要放在对称位置即可;出现奇数次时,如果是1次,那么该字符只能当做回文的中心且只能用一次,如果大于1次,则其偶数次部分可以直接使用,并且多余的1次可以当做回文的中心且只能使用一次。
此解法的时间复杂度是O(n),空间复杂度是O(1)。
public int longestPalindrome(String s) {
int[] arr = new int[256];
for (int i=0; i<s.length(); i++) {
arr[s.charAt(i)]++;
}
int count = 0;
int single = 0;
for (int j=0; j<arr.length; j++) {
if (arr[j]%2 == 0) {
count += arr[j];
} else {
count += arr[j]-1;
single = 1;
}
}
return count+single;
}
03 第二种解法
此解法的思路和第一种解法一致,只是在计数判断那里有点区别。对数组中当前元素直接除以2得到商,再乘以2,得到当前字符可以使用的次数,但是同样需要判断奇数次元素,如果当前元素是奇数,并且count是偶数,即count之前没遇到奇数,那么count自加1,并且只会执行一次,因为回文字符串中心只能是一次。
此解法的时间复杂度是O(n),空间复杂度是O(1)。
public int longestPalindrome2(String s) {
int[] arr = new int[256];
for (int i=0; i<s.length(); i++) {
arr[s.charAt(i)]++;
}
int count = 0;
for (int j=0; j<arr.length; j++) {
count += (arr[j]/2)*2;
if (arr[j]%2 == 1 && count%2 == 0) {
count++;
}
}
return count;
}
04 第三种解法
此解法思路和第二种解法一致,有区别的是判断出现奇数次字符并且count加1的逻辑从循环体中抽出来了,放在了最后。如果count和字符串s的长度做比较时,相等则说明s中的字符都是出现偶数次,不相等则说明s中有出现奇数次的字符,count就需要加1,且只能加1次。
此解法的时间复杂度是O(n),空间复杂度是O(1)。
public int longestPalindrome3(String s) {
int[] arr = new int[256];
for (int i=0; i<s.length(); i++) {
arr[s.charAt(i)]++;
}
int count = 0;
for (int j=0; j<arr.length; j++) {
count += (arr[j]/2)*2;
}
return count == s.length() ? count : count+1;
}
05 第四种解法
使用HashSet,如果当前字符已经在set中存在,那么count加2,并且要移除当前字符;如果不存在,就add进set中。最后判断set是否为空,如果不为空,则说明有些字符出现了奇数次,就只能当做回文字符组中心来用,且只能用一次。
此解法的时间复杂度是O(n),虽然使用了contains方法,但是HashSet内存储的数据不会达到O(n)规模,因此遍历判断是否包含当前字符需要的最多判断次数为52次,即O(52*n),也即O(n)。
空间复杂度是O(1),虽然使用了HashSet,但是字符的范围只是大小写字母,最大长度是52,可以看做是一个常量。
public int longestPalindrome4(String s) {
Set<Character> set = new HashSet<Character>();
int count = 0;
for (int i=0; i<s.length(); i++) {
if (set.contains(s.charAt(i))) {
count = count + 2;
set.remove(s.charAt(i));
} else {
set.add(s.charAt(i));
}
}
if (!set.isEmpty()) {
count = count + 1;
}
return count;
}
06 第五种解法
参照第四种解法的思路,我们同样可以使用数组来操作。数组的长度控制在58,因为a到z是从97到122,A到Z是从65到90,中间相隔58个数。将s变为字符数组,如果当前字符表示的十进制数,在数组中对应的元素为0就自加1,否则就自减1,然后count加2,最后再去判断数组中的元素有没有大于0的存在,如果存在即表示有字符出现了奇数次,然后count需要加1,且只用加一次。
public int longestPalindrome5(String s) {
int[] arr = new int[58];
int count = 0;
for (char ch : s.toCharArray()) {
if (arr[ch-'A'] == 0) {
arr[ch-'A']++;
} else {
arr[ch-'A']--;
count += 2;
}
}
for (int j=0; j<arr.length; j++) {
if (arr[j] > 0) {
count += 1;
break;
}
}
return count;
}
07 小结
算法专题目前已连续日更超过两个月,算法题文章87+篇,