Leetcode 3035. Maximum Palindromes After Operations

这篇具有很好参考价值的文章主要介绍了Leetcode 3035. Maximum Palindromes After Operations。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

  • 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] += 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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • LeetCode2111. Minimum Operations to Make the Array K-Increasing——动态规划

    You are given a 0-indexed array arr consisting of n positive integers, and a positive integer k. The array arr is called K-increasing if arr[i-k] = arr[i] holds for every index i, where k = i = n-1. For example, arr = [4, 1, 5, 2, 6, 2] is K-increasing for k = 2 because: arr[0] = arr[2] (4 = 5) arr[1] = arr[3] (1 = 2) arr[2] = arr[4] (5 = 6) arr[3] = arr[5]

    2024年03月09日
    浏览(44)
  • LeetCode //C - 918. Maximum Sum Circular Subarray

    Given a circular integer array nums of length n, return the maximum possible sum of a non-empty subarray of nums. A circular array means the end of the array connects to the beginning of the array. Formally, the next element of nums[i] is nums[(i + 1) % n] and the previous element of nums[i] is nums[(i - 1 + n) % n]. A subarray may only include each element

    2024年02月07日
    浏览(47)
  • 【LeetCode 算法】Minimum Operations to Halve Array Sum 将数组和减半的最少操作次数-Greedy

    给你一个正整数数组 nums 。每一次操作中,你可以从 nums 中选择 任意 一个数并将它 减小 到 恰好 一半 。(注意,在后续操作中你可以对减半过的数继续执行操作) 请你返回将 nums 数组和 至少 减少一半 的 最少 操作数。 1 = n u m s . l e n g t h = 1 0 5 1 = n u m s [ i ] = 1 0 7 1 = num

    2024年02月15日
    浏览(47)
  • LeetCode --- 1710. Maximum Units on a Truck 解题报告

    You are assigned to put some amount of boxes onto  one truck . You are given a 2D array  boxTypes , where  boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi] : numberOfBoxesi  is the number of boxes of type  i . numberOfUnitsPerBoxi  is the number of units in each box of the type  i . You are also given an integer  truckSize , which is the  maximu

    2023年04月18日
    浏览(42)
  • LeetCode //C - 124. Binary Tree Maximum Path Sum

    A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root. The path sum of a path is the sum of the node’s values in the path. Given the root of a binary tree, return the maximum

    2024年02月09日
    浏览(44)
  • leetcode - 2616. Minimize the Maximum Difference of Pairs

    You are given a 0-indexed integer array nums and an integer p. Find p pairs of indices of nums such that the maximum difference amongst all the pairs is minimized. Also, ensure no index appears more than once amongst the p pairs. Note that for a pair of elements at the index i and j, the difference of this pair is |nums[i] - nums[j]|, where |x| represents th

    2024年02月13日
    浏览(43)
  • LeetCode646. Maximum Length of Pair Chain——动态规划

    You are given an array of n pairs pairs where pairs[i] = [lefti, righti] and lefti righti. A pair p2 = [c, d] follows a pair p1 = [a, b] if b c. A chain of pairs can be formed in this fashion. Return the length longest chain which can be formed. You do not need to use up all the given intervals. You can select pairs in any order. Example 1: Input: pairs = [[

    2024年02月22日
    浏览(48)
  • LeetCode 918. Maximum Sum Circular Subarray【数组,动态规划】中等

    本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,

    2024年02月15日
    浏览(52)
  • LeetCode 1921. Eliminate Maximum Number of Monsters【贪心,计数排序】1527

    本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,

    2024年02月09日
    浏览(52)
  • LeetCode //C - 2130. Maximum Twin Sum of a Linked List

    In a linked list of size n, where n is even, the i t h i^{th} i t h node (0-indexed) of the linked list is known as the twin of the ( n − 1 − i ) t h (n-1-i)^{th} ( n − 1 − i ) t h node, if 0 = i = (n / 2) - 1. For example, if n = 4, then node 0 is the twin of node 3, and node 1 is the twin of node 2. These are the only nodes with twins for n = 4. Th

    2024年01月17日
    浏览(66)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包