[閒聊] LeetCode 409

[sustainer123 (caster )]

409. Longest Palindrome
給你一個包含大小寫的字串，請運用字串的字母建立一個最長回文字串，
最後回報回文字串的長度。
請注意字母有大小寫區別，如Aa不被視為回文字串。

Example 1:

Input: s = "abccccdd"
Output: 7
Explanation: One longest palindrome that can be built is "dccaccd", whose
length is 7.
Example 2:

Input: s = "a"
Output: 1
Explanation: The longest palindrome that can be built is "a", whose length is
1.

思路:
這題可以使用map的概念，分析每個字元的數量。如為偶數個，必能組成回文；
如為奇數個，則-1組成回文。所以，我們要找出共有多少個奇數數量的字元。
找出共有多少奇數數量字元後，因為回文字串中間能放一個奇數，
所以假如奇數數量字元>0，則length+1。
最後長度扣掉奇數個數即為答案。

C Code
---------------------
int longestPalindrome(char * s){
    int i = 0;
    int array[128]={0};
    int length =strlen(s);
    int odd = 0;
    while(i < length){
        array[s[i]]++;
        i++;
    }
    for(int j =0; j<128; j++){
        if(array[j] %2 == 1){
            odd++;
        }
    }
    if( odd > 0 ){
        length = length+1;
    }
    return length - odd;
}
---------------------
補記:這題放在貪婪，不過看不出來跟貪婪有啥關係，姆咪。


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.43.90.169 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1673593800.A.41F.html
→ Rushia: 每次都拿局部最佳解而且每次拿不影響後面結果就是貪婪阿
推 abcd991276: 大師
→ mpyh12345: 大師
推 dannyko: 貪婪是有定義的 不是第一直覺想的解叫貪婪
推 MurasakiSion: 大師
→ sustainer123: 大師能不能解釋一下貪婪 我覺得我還是不懂他在幹嘛
推 Mustafar: Longest palindrome substring 一定直接 Manacher's Al
→ Mustafar: gorithm 吧
推 SecondRun: 大師