Leetcode 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] += 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。

相关推荐

  1. Leetcode 3035. Maximum Palindromes After Operations

    2024-02-12 13:06:01       38 阅读
  2. Leetcode 3033. Modify the Matrix

    2024-02-12 13:06:01       39 阅读
  3. leetcode303--区域和检索

    2024-02-12 13:06:01       23 阅读
  4. leetcode 303 前缀和 区域和检索

    2024-02-12 13:06:01       16 阅读
  5. Leetcode 3036. Number of Subarrays That Match a Pattern II

    2024-02-12 13:06:01       50 阅读
  6. Leetcode 3085. Minimum Deletions to Make String K-Special

    2024-02-12 13:06:01       25 阅读

最近更新

  1. TCP协议是安全的吗?

    2024-02-12 13:06:01       19 阅读
  2. 阿里云服务器执行yum,一直下载docker-ce-stable失败

    2024-02-12 13:06:01       19 阅读
  3. 【Python教程】压缩PDF文件大小

    2024-02-12 13:06:01       20 阅读
  4. 通过文章id递归查询所有评论(xml)

    2024-02-12 13:06:01       20 阅读

热门阅读

  1. Ubuntu搭建计算集群

    2024-02-12 13:06:01       42 阅读
  2. 装箱问题+宠物小精灵之收服+数字组合——01背包

    2024-02-12 13:06:01       29 阅读
  3. 龙芯安装Docker

    2024-02-12 13:06:01       28 阅读
  4. 学习数据结构和算法的第7天

    2024-02-12 13:06:01       34 阅读
  5. JVM调优的一些常用技术

    2024-02-12 13:06:01       28 阅读
  6. 缓存雪崩问题与应对策略

    2024-02-12 13:06:01       37 阅读
  7. vue3学习——router-view 过渡动画

    2024-02-12 13:06:01       33 阅读