电脑怎做单页网站,如何建微信公众号,企业宣传画册设计公司,家装公司装修Leetcode 3035. Maximum Palindromes After Operations 1. 解题思路2. 代码实现 题目链接#xff1a;3035. Maximum Palindromes After Operations
1. 解题思路
这一题的话因为可以任意交换#xff0c;因此事实上要考察回文的最大个数#xff0c;我们只需要统计所有单词当…Leetcode 3035. Maximum Palindromes After Operations 1. 解题思路2. 代码实现 题目链接3035. Maximum Palindromes After Operations
1. 解题思路
这一题的话因为可以任意交换因此事实上要考察回文的最大个数我们只需要统计所有单词当中字符出现的频次看看他们能组成多少回文即可。
而这部分我们只需要统计所有的字符频次当中pair的个数和独立元素的个数即可且需要注意的是如果独立元素不够用了我们可以将成对的元素拆分为两个独立元素即可满足使用需求。
另外要使得能组成的回文尽可能的多我们应该优先匹配较短的单词这样才能够确保能够组成最多的回文。
2. 代码实现
给出python代码实现如下
class Solution:def maxPalindromesAfterOperations(self, words: List[str]) - int:cnt defaultdict(int)for w in words:for ch in w:cnt[ch] 1odd, even 0, 0for v in cnt.values():odd v % 2even v // 2ans 0lengths sorted([len(w) for w in words])for l in lengths:if l % 2 odd and l // 2 even:ans 1odd - l % 2even - l // 2elif l % 2 odd and l // 2 even:ans 1odd 1even - (l1) // 2return ans提交代码评测得到耗时130ms占用内存17.3MB。
