文档章节

Longest Palindrome(leetcode409)

woshixin
 woshixin
发布于 01/18 19:52
字数 429
阅读 0
收藏 0

Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.

This is case sensitive, for example "Aa" is not considered a palindrome here.

Note:
Assume the length of given string will not exceed 1,010.

Example:

Input:
"abccccdd"

Output:
7

Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.
//自然想到的正向思维 偶数的数量肯定可以组成回文,奇数只要获取其中的偶数个 如果可以中间还可以放一个
public static int longestPalindrome(String s) {

    int result = 0;
    Map<Character,Integer> map = new HashMap<>();
    for (int i =0;i<s.length();i++){
        if(map.containsKey(s.charAt(i))){
             Integer count = map.get(s.charAt(i));
             count ++;
             map.put(s.charAt(i),count);
        }else{
            map.put(s.charAt(i),1);
        }
    }
    int jishu =0;
    for (Map.Entry<Character, Integer> entry : map.entrySet()) {
        if(entry.getValue()%2==0){
            result+=entry.getValue();
        }else{
            result = entry.getValue()+result-1;
            jishu++;
        }
    }
    if(jishu> 0){
        result++;
    }

    return result;
}

//这个加加减减的方式 也是可以的
public static int longestPalindrome2(String s) {
    if(s==null || s.length()==0) {
        return 0;
    }
    HashSet<Character> hs = new HashSet<Character>();
    int count = 0;
    for(int i=0; i<s.length(); i++){
        if(hs.contains(s.charAt(i))){
            hs.remove(s.charAt(i));
            count++;
        }else{
            hs.add(s.charAt(i));
        }
    }
    if(!hs.isEmpty()) {
        return count*2+1;
    }
    return count*2;
}

//这里用整型数量的特性 除以2乘以2  就没有奇数偶数的问题
public static int longestPalindrome3(String s) {
    int[] lowercase = new int[26];
    int[] uppercase = new int[26];
    int res = 0;
    for (int i = 0; i < s.length(); i++){
        char temp = s.charAt(i);
        if (temp >= 97) {
            lowercase[temp-'a']++;
        } else {
            uppercase[temp-'A']++;
        }
    }
    for (int i = 0; i < 26; i++){
        res+=(lowercase[i]/2)*2;
        res+=(uppercase[i]/2)*2;
    }
    return res == s.length() ? res : res+1;

}

//与上面的不同  这是获取奇数的数量
public static int longestPalindrome4(String s) {
    int[] chars = new int[128];
    char[] t = s.toCharArray();
    for(char c:t){
        chars[c]++;
    }
    int single = 0;
    for(int n:chars){
        if(n%2!=0){
            single++;
        }
    }
    return single>1?t.length-single+1:t.length;
}

git:https://github.com/woshiyexinjie/leetcode-xin

 

© 著作权归作者所有

共有 人打赏支持
woshixin
粉丝 27
博文 317
码字总数 252471
作品 0
杭州
程序员
私信 提问
[leetcode] Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring. ht......

jdflyfly
2014/06/24
614
0
【LeetCode】409. Longest Palindrome (java实现)

原题链接 https://leetcode.com/problems/longest-palindrome/ 原题 Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that......

BookShu
2016/11/04
145
0
[LeetCode] Shortest Palindrome 最短回文串

Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this tran......

机器的心脏
2017/12/02
0
0
LeetCode Question Difficulty Distribution 问题难度和频率分布

Leetcode问题难度和频率分布表 引用自: https://zephyrusara.blogspot.jp/2014/07/leetcode-question-difficulty.html LeetCode Question Difficulty Distribution : Sheet1......

xidiancoder
2017/09/10
0
0
topcoder题目及我的程序(4)——find reversed string (算法1)

Problem Statement ???? You are given a String input. You are to find the longest substring of input such that the reversal of the substring is also a substring of input. In case......

晨曦之光
2012/03/09
265
0

没有更多内容

加载失败,请刷新页面

加载更多

RabbitMQ入门

RabbitMQ是一个由erlang开发的基于AMQP(Advanced Message Queue)协议的开源实现。用于在分布式系统中存储转发消息,在易用性、扩展性、高可用性等方面都非常的优秀。是当前最主流的消息中间...

watermelon11
今天
15
0
今天的学习

自动加载:方法一 function __autoload( $className ){在这里,完成加载B这个类文件的工作。}class A{} //这是一个类$a1 = new A(); //这里没有自动加载的发生,因为A这个类...

墨冥
今天
2
0
印刷工艺步骤

印刷厂从收到订单到交付整个流程,一般涉及到以下步骤 1.设计(经过软件如cdr,psd,ai等等设计需要印刷的名片,宣传单,画册等物料); 2.排版拼版(在电脑软件这区域完成); 3.出版、出硫...

focusone
昨天
4
0
virtualbox中安装ubuntu

virtualbox+ubuntu 安装virtualbox,当前版本是6.0.4 下载ubuntu安装盘,建议lubuntu,链接是http://mirrors.ustc.edu.cn/ubuntu-cdimage/lubuntu/releases/18.04.2/release/lubuntu-18.04.......

chuqq
昨天
5
0
exists 谓词的子查询

https://blog.csdn.net/qq_19782019/article/details/78730882

仟昭
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部