[閒聊] LeetCode 409

作者: sustainer123 (caster)   2023-01-13 15:09:56
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
作者: Rushia (みけねこ的鼻屎)   2023-01-13 15:11:00
每次都拿局部最佳解而且每次拿不影響後面結果就是貪婪阿
作者: abcd991276 (QQ)   2023-01-13 15:11:00
大師
作者: mpyh12345 (嘉義金城武)   2023-01-13 15:13:00
大師
作者: dannyko (dannyko)   2023-01-13 15:16:00
貪婪是有定義的 不是第一直覺想的解叫貪婪
作者: MurasakiSion (紫咲シオン)   2023-01-13 15:17:00
大師
作者: sustainer123 (caster)   2023-01-13 15:22:00
大師能不能解釋一下貪婪 我覺得我還是不懂他在幹嘛

Links booklink

Contact Us: admin [ a t ] ucptt.com