Re: [閒聊] 每日LeetCode已回收
※ 引述《Rushia (みけねこ的鼻屎)》之銘言：
: 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.
一開始想法是用雙重迴圈去跑後面有沒有可以回文的字串
前面答案都對但是遇到太大量的資料 會 Time Limit Exceeded
所以後來改用map來存取每個字串出現的次數
ones用來存連續字母 twos用來存不同字母的
然後twos的部分 使用map<string, pair<int, int>> 的形式 前面string先sort過
然後再用迴圈回去算就好 大約是O(n)吧
------
C++ 程式碼：
class Solution {
public:
int longestPalindrome(vector<string>& words) {
map<string, pair<int, int>> twos;
map<string, int> ones;
for (auto word : words) {
if (word[0] == word[1]) {
ones[word]++;
}
else {
string s = word;
sort(s.begin(), s.end());
if (s == word) {
twos[s].first++;
}
else {
twos[s].second++;
}
}
}
int res = 0;
for (auto& two : twos) {
res += min(two.second.first, two.second.second) * 4;
}
for (auto& one : ones) {
res +=( one.second / 2) * 4;
}
for (auto& one : ones) {
if ((one.second % 2) == 1) {
res += 2;
break;
}
}
return res;
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.229.103.22 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1667471602.A.A61.html
推
11/03 19:39,
3年前
, 1F
11/03 19:39, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 84 之 719 篇)：