Leetcodeブラシ問題86-409.最长回文串(C++详细解法!!)


Come from : [https://leetcode-cn.com/problems/longest-palindrome/]
409. Longest Palindrome
  • 1.Question
  • 2.Answer
  • 3.オオカミたちの解決策
  • 4.私の収穫
  • 1.Question
    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.
    Example 1 :
    Input:
    "abccccdd"
    
    Output:
    7
    
    Explanation:
    One longest palindrome that can be built is "dccaccd", whose length is 7.
    

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

    2.Answer
    easyタイプテーマ.文字ハッシュ表を使用します.
    MACコードは以下の通りである.
    class Solution {
    public:
        int longestPalindrome(string s) {
            int a[128] = {0}; //    
            int sum = 0;
            int tag = 0;   //             
            for(int i = 0; i < s.size(); ++i)
            {
                ++a[s[i]];
            }
            for(int i = 0; i < 128; ++i)
            {
                if(a[i] % 2 == 0)
                {
                    sum += a[i];
                }
                if(a[i] %2 == 1)
                {
                    tag = 1;
                    sum += a[i] - 1;
                }
            }
            return sum + tag;
        }
    };
    

    3.オオカミたちの解決策
    方法:私のやり方と同じです.のでもスピードランキング1位ですね~
    class Solution {
    public:
        int longestPalindrome(string s) {
            
            unordered_map<char,int>tem;
            for(int i=0;i<s.size();i++){
                tem[s[i]]++;
            }
            int flag=0;
            int res=0;
            for(auto iter=tem.begin();iter!=tem.end();iter++){
                int n=iter->second;
                if(n%2!=0){
                    flag++;
                    res+=n-1;
                }else
                    res+=n;
            }
            if(flag>0)
                res++;
            return res;
        }
    };
    

    4.私の収穫
    感覚はやはり系統的に知識を身につけなければならない...例えば今回のハッシュ表...系統的に勉強してから、もっと上手に運用することができます.
    2019/5/25胡雲雲は南京で86