Re: [闲聊] 每日LeetCode

楼主: Rushia (みけねこ的鼻屎)   2022-11-03 10:33:23
2131. Longest Palindrome by Concatenating Two Letter Words
给予很多个长度为2的字串,求出将这些字串任意拼接后可得的最长回文长度。
Exaple:
Input: words = ["lc","cl","gg"]
Output: 6
Explanation: One longest palindrome is "lc" + "gg" + "cl" = "lcggcl", of
length 6.
Note that "clgglc" is another longest palindrome that can be created.
思路:
1.任意两字串要组成回文需要满足 ab => ba 或 aa => aa 它们必须成双成对
(两边数量都大于1,并且取较小的那边)
2.其中较特别的是自己就是回文的字串(例如:aa)只有一个的时候加入字串
中间可以使回文变长(lccl中间加上gg => lcggcl)
3.所以我们就先把所有字串放进map并统计数量,对自己就是回文的字串做特殊处理
如果自己就是回文的字串统计完数量后还有剩余时,我们用一个flag纪录,并在
返回res前判断是否有多出一个自己就是回文的字串,若有则答案要再多加2。
4.这边我判断回文是奇数的时候更新flag并且把当前的数量减一就不会重复加到多个
重复回文字串,例如:(5个aa、7个bb)
JavaCode:
class Solution {
public int longestPalindrome(String[] words) {
int res = 0;
Map<String, Integer> map = new HashMap<>();
for(String word : words) {
map.put(word, map.getOrDefault(word, 0) + 1);
}
boolean middle = false;
for(String key : map.keySet()) {
if(key.charAt(0) == key.charAt(1)) {
int cnt = map.get(key);
if((cnt & 1) == 1) {
middle = true;
cnt
作者: Bill8x1229 (20分钟了还是想不到)   2022-11-03 10:34:00
大师
作者: pandix (面包屌)   2022-11-03 10:49:00
大师
作者: itoumashiro (佩可咪口爱的结晶)   2022-11-03 11:34:00
怎么没有龙

Links booklink

Contact Us: admin [ a t ] ucptt.com