-
Leetcode 3035. Maximum Palindromes After Operations
- 1. 解题思路
- 2. 代码实现
- 题目链接:3035. Maximum Palindromes After Operations
1. 解题思路
这一题的话因为可以任意交换,因此事实上要考察回文的最大个数,我们只需要统计所有单词当中字符出现的频次,看看他们能组成多少回文即可。
而这部分,我们只需要统计所有的字符频次当中pair的个数和独立元素的个数即可,且需要注意的是,如果独立元素不够用了,我们可以将成对的元素拆分为两个独立元素,即可满足使用需求。
另外,要使得能组成的回文尽可能的多,我们应该优先匹配较短的单词,这样才能够确保能够组成最多的回文。
2. 代码实现
给出python代码实现如下:文章来源:https://www.toymoban.com/news/detail-827867.html
class Solution:
def maxPalindromesAfterOperations(self, words: List[str]) -> int:
cnt = defaultdict(int)
for w in words:
for ch in w:
cnt[ch] += 1
odd, even = 0, 0
for v in cnt.values():
odd += v % 2
even += v // 2
ans = 0
lengths = sorted([len(w) for w in words])
for l in lengths:
if l % 2 <= odd and l // 2 <= even:
ans += 1
odd -= l % 2
even -= l // 2
elif l % 2 > odd and l // 2 < even:
ans += 1
odd += 1
even -= (l+1) // 2
return ans
提交代码评测得到:耗时130ms,占用内存17.3MB。文章来源地址https://www.toymoban.com/news/detail-827867.html
到了这里,关于Leetcode 3035. Maximum Palindromes After Operations的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!