这是悦乐书的第 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 + 篇, 公众号对话框回复 [数据结构与算法] ,[算法] ,[数据结构] 中的任一关键词, 获取系列文章合集.
以上就是全部内容, 如果大家有什么好的解法思路, 建议或者其他问题, 可以下方留言交流, 点赞, 留言, 转发就是对我最大的回报和支持!
来源: http://www.jianshu.com/p/1a786e0ec18e