查找最长的回文，代码过半测试用例

我试图找到最长回文可能，给出一个String。问题参数表明这是区分大小写，因此“A”！=“A”。下面我试图传递的本文给出的测试案例九十五分之四十九，但我不知道我要去哪里错了...查找最长的回文，代码过半测试用例

public class Solution { 
    public int longestPalindrome(String s) { 
     if (s.equals("")) { 
      return 0; 
     } 
     Map<Character, Integer> map = new HashMap<>(); 
     for (int i = 0; i < s.length(); i++) { 
      char c = s.charAt(i); 
      if (map.containsKey(c)) { 
       map.put(c, map.get(c) + 1); 
      } else { 
       map.put(c, 1); 
      } 
     } 
     int total = 0; 
     int greatestOdd = 0; 
     for (Map.Entry<Character, Integer> entry : map.entrySet()) { 
      int value = entry.getValue(); 
      if (value % 2 == 0) { 
       total += value; 
      } else { 
       if (value > greatestOdd) { 
        greatestOdd = value; 
       } 
      } 
     } 
     total += greatestOdd; 
     return total; 

    } 
}

的想法是，回文组成，其计数是连和一个字符的字符是有一个奇数（或可能有0个字符和一个奇数）。所以我跟踪了HashMap中的所有字符数。

然后我遍历HashMap中，如果他们甚至所有的值，添加到总量。我还跟踪最大单的（初始化为0的情况下，有没有字母与奇计）。

我认为这是正确的想法，但事情是关闭...

链接锻炼：https://leetcode.com/problems/longest-palindrome/?tab=Description

来源

2017-02-26 bclayman

这个心不是代码审查。你能不能给我们一些评论？它有什么作用？ – Tacolibre

有了这个逻辑，像bbadd字符串会被认为是回文？ – samson

你可以链接到锻炼; Tibial？我想自己测试一下。 – Tacolibre

你的逻辑是正确的，但一旦你计算的最大单值，你应该将其删除映射并考虑发生奇数次的所有其他字符。

我的代码：

public int longestPalindrome(String s) { 
    HashMap<Character,Integer> map = new HashMap<>(); 
    for (Character c : s.toCharArray()) { 
     if(map.containsKey(c)) { 
      map.put(c,map.get(c)+1); 
     } else { 
      map.put(c,1); 
     } 
    } 
    int maxOdd = 0; 
    char maxOddChar = Character.MIN_VALUE; 
    int palindromeLength = 0; 
    for (Character c : map.keySet()) { 
     if(map.get(c)%2==0) { 
      palindromeLength += map.get(c); 
     } else { 
      if(maxOdd<map.get(c)) { 
       maxOdd = map.get(c); 
       maxOddChar = c; 
      } 
     } 
    } 
    palindromeLength += maxOdd; 
    map.remove(maxOddChar); 
    //Considering other odd characters as well 
    for (Character c : map.keySet()) { 
     if(map.get(c)%2!=0) { 
      palindromeLength += map.get(c)-1; 
     } 
    } 
    return palindromeLength; 
}

例子：aabbbcccccdd

Hashmap -> a->2,b->3,c->5,d->2 
Greatest odd value = c->5 
Total palindrome length : a+d+c = 2+2+5 = 9 

// But you are missing b->3 can also be added 
// in the palindrome, but using only 2 b's and neglecting 1 

Total palindrome length : 9+2 = 11

来源

2017-02-26 17:46:15 poorvankBhatia

通常

你甚至应该减去1，并将其添加到您的回文长度使其，简化代码使一切如此清晰，你几乎不会有错误。例如：

List<Long> freqs = Arrays.stream(s.split("(<=.)")).stream() 
    .collect(Collectors.groupingBy(o -> o, Collectors.counting())) 
    .values(); 
long length = freq.stream().mapToLong(Long::longValue) 
    .filter(n -> n % 2 == 0).sum() - 
    freqs.stream().mapToLong(Long::longValue) 
    .filter(n -> n % 2 == 1).max().orElse(0);

只有2条（尽管很长）的线条。

_{免责声明：因为它是在翻阅我的手机上的代码可能无法编译或工作（但有一个合理的机会，将工作）}

来源

2017-02-26 20:08:24 Bohemian

查找最长的回文，代码过半测试用例

回答

相关问题