[閒聊] LeetCode 409

看板Marginalman作者sustainer123 (caster )時間3年前 (2023/01/13 15:10)推噓5(5推 0噓 4→)

留言9則, 8人參與討論串1/1

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

01/13 15:11, 3年前 , 1^F

01/13 15:11, 1^F

推

abcd991276

01/13 15:11, 3年前 , 2^F

01/13 15:11, 2^F

→

mpyh12345

01/13 15:13, 3年前 , 3^F

01/13 15:13, 3^F