且听疯吟

leetcode contest 376

2023-12-28

leetcode contest 376

T4 竟然没有做出来，不过 T3 确实是个不错的题目，非常考验思考的能力。

100149. 找出缺失和重复的数字

给你一个下标从 0 开始的二维整数矩阵 grid，大小为 n * n ，其中的值在 [1, n2] 范围内。除了 a 出现 两次，b 缺失 之外，每个整数都 恰好出现一次 。

任务是找出重复的数字a 和缺失的数字 b 。

返回一个下标从 0 开始、长度为 2 的整数数组 ans ，其中 ans[0] 等于 a ，ans[1] 等于 b 。

示例 1：

输入：grid = [[1,3],[2,2]]
输出：[2,4]
解释：数字 2 重复，数字 4 缺失，所以答案是 [2,4] 。

示例 2：

输入：grid = [[9,1,7],[8,9,2],[3,4,6]]
输出：[9,5]
解释：数字 9 重复，数字 5 缺失，所以答案是 [9,5] 。

提示：

  • 2 <= n == grid.length == grid[i].length <= 50
  • 1 <= grid[i][j] <= n * n
  • 对于所有满足1 <= x <= n * n 的 x ，恰好存在一个 x 与矩阵中的任何成员都不相等。
  • 对于所有满足1 <= x <= n * n 的 x ，恰好存在一个 x 与矩阵中的两个成员相等。
  • 除上述的两个之外，对于所有满足1 <= x <= n * n 的 x ，都恰好存在一对 i, j 满足 0 <= i, j <= n - 1 且 grid[i][j] == x 。

地址

https://leetcode.cn/contest/weekly-contest-376/problems/find-missing-and-repeated-values/

题意

模拟

思路

  1. 经典题目，找到一个出现一次和未出现的元素，直接模拟哈希统计就是非常简单的问题，当然还可以用异或之类的技巧解法。找到未出现的元素与出现两次的元素即可。
  2. 复杂度分析：
  • 时间复杂度：$O(n^2)$，其中 $n$ 表示给定矩阵的行数。
  • 空间复杂度：$O(n^2)$, 其中 $n$ 表示给定矩阵的行数。

代码

class Solution:
    def findMissingAndRepeatedValues(self, grid: List[List[int]]) -> List[int]:
        n = len(grid)
        arr = []
        for row in grid:
            arr += row
        cnt = Counter(arr)
        res = [0, 0]
        for i in range(1, n * n + 1):
            if i not in cnt:
                res[1] = i
            if cnt[i] == 2:
                res[0] = i
        return res

100161. 划分数组并满足最大差限制

给你一个长度为 n 的整数数组 nums，以及一个正整数 k 。

将这个数组划分为一个或多个长度为 3 的子数组，并满足以下条件：

  • nums 中的 每个 元素都必须 恰好 存在于某个子数组中。
  • 子数组中 任意 两个元素的差必须小于或等于 k 。

返回一个 二维数组 ，包含所有的子数组。如果不可能满足条件，就返回一个空数组。如果有多个答案，返回 任意一个 即可。

示例 1：

输入：nums = [1,3,4,8,7,9,3,5,1], k = 2
输出：[[1,1,3],[3,4,5],[7,8,9]]
解释：可以将数组划分为以下子数组：[1,1,3]，[3,4,5] 和 [7,8,9] 。
每个子数组中任意两个元素的差都小于或等于 2 。
注意，元素的顺序并不重要。

示例 2：

输入：nums = [1,3,3,2,7,3], k = 3
输出：[]
解释：无法划分数组满足所有条件。

提示：

  • n == nums.length
  • 1 <= n <= 105
  • n 是 3 的倍数
  • 1 <= nums[i] <= 105
  • 1 <= k <= 105

地址

https://leetcode.cn/contest/weekly-contest-376/problems/divide-array-into-arrays-with-max-difference/

题意

数学问题 + 贪心

思路

  1. 首先需要将数组排序，依次枚举，对第 $0$ 个元素，此时与 $nums[0]$ 最接近的两个元素即为 $nums[1],nums[2]$, 如果 $nums[1],nums[2]$ 与 $nums[0]$ 的差值都大于 $k$ ，则此时一定无法满足分类。然后再依次枚举 $nums[3]$, 相邻的三个元素是否可以构成合法分组。本质上是相邻的三个元素进行分组即可。
  2. 复杂度分析：
  • 时间复杂度：$O(n \times \log n)$，其中 $n$ 表示给定数组的长度。
  • 空间复杂度：$O(\log n)$。

代码

class Solution:
    def divideArray(self, nums: List[int], k: int) -> List[List[int]]:
        nums.sort()
        ans = []
        for i in range(0, len(nums), 3):
            if nums[i + 2] - nums[i] > k:
                return []
            ans.append([nums[i], nums[i + 1], nums[i + 2]])
        return ans

100151. 使数组成为等数数组的最小代价

给你一个长度为 n 下标从 0 开始的整数数组 nums 。

你可以对 nums 执行特殊操作 任意次 （也可以 0 次）。每一次特殊操作中，你需要 按顺序 执行以下步骤：

  • 从范围 [0, n - 1] 里选择一个下标 i 和一个 正 整数 x 。
  • 将 |nums[i] - x| 添加到总代价里。
  • 将 nums[i] 变为 x 。

如果一个正整数正着读和反着读都相同，那么我们称这个数是 回文数 。比方说，121 ，2552 和 65756 都是回文数，但是 24 ，46 ，235 都不是回文数。

如果一个数组中的所有元素都等于一个整数 y ，且 y 是一个小于 109 的 回文数 ，那么我们称这个数组是一个 等数数组 。

请你返回一个整数，表示执行任意次特殊操作后使 nums 成为 等数数组 的 最小 总代价。

示例 1：

输入：nums = [1,2,3,4,5]
输出：6
解释：我们可以将数组中所有元素变为回文数 3 得到等数数组，数组变成 [3,3,3,3,3] 需要执行 4 次特殊操作，代价为 |1 - 3| + |2 - 3| + |4 - 3| + |5 - 3| = 6 。
将所有元素变为其他回文数的总代价都大于 6 。

示例 2：

输入：nums = [10,12,13,14,15]
输出：11
解释：我们可以将数组中所有元素变为回文数 11 得到等数数组，数组变成 [11,11,11,11,11] 需要执行 5 次特殊操作，代价为 |10 - 11| + |12 - 11| + |13 - 11| + |14 - 11| + |15 - 11| = 11 。
将所有元素变为其他回文数的总代价都大于 11 。

示例 3 ：

输入：nums = [22,33,22,33,22]
输出：22
解释：我们可以将数组中所有元素变为回文数 22 得到等数数组，数组变为 [22,22,22,22,22] 需要执行 2 次特殊操作，代价为 |33 - 22| + |33 - 22| = 22 。
将所有元素变为其他回文数的总代价都大于 22 。

提示：

  • 1 <= n <= 105
  • 1 <= nums[i] <= 109

地址

https://leetcode.cn/contest/weekly-contest-376/problems/minimum-cost-to-make-array-equalindromic/

题意

贪心 + 数学

思路

  1. 对于一个数组来说，我们知道数组的中位数到所有元素的距离之和最小，此时我们只需要找到距离中位数最近的回文数 $x$，此时 $x$ 到所有元素的差的绝对值之和最小。此时我们可以参考力扣经典题目 寻找最近的回文数，可以得到最近的回文数一定在下属序列中：

    • 用原数的前半部分替换后半部分得到的回文整数。

    • 用原数的前半部分加一后的结果替换后半部分得到的回文整数。

    • 用原数的前半部分减一后的结果替换后半部分得到的回文整数。

    • 为防止位数变化导致构造的回文整数错误，因此直接构造 $999999\dots 999 和 100\dots 001$ 作为备选答案。

  2. 找到备选的元素后，我们直接求最小的变换数目即可。

  • 时间复杂度：$O(n)$，其中$n$ 表示给定数组的长度；
  • 空间复杂度：$O(\log U)$，其中$u$ 表示给定数组中的最大元素；

代码

def getCandidates(x):
    s = str(x)
    n = len(s)
    candidates = [10 ** (n - 1) - 1, 10 ** (n) + 1]
    selfPrefix = int(s[0 : (n + 1) // 2])
    for i in [selfPrefix - 1, selfPrefix, selfPrefix + 1]:
        prefix = str(i)
        rev = prefix[::-1]
        candidate = prefix + rev[n & 1:]
        candidates.append(int(candidate))
    return candidates

class Solution:  
    def minimumCost(self, nums: List[int]) -> int:
        n = len(nums)
        nums.sort()
        mid = (nums[(n - 1) // 2] + nums[n // 2]) // 2
        psum = [0] * (n + 1)
        for i, x in enumerate(nums):
            psum[i + 1] = psum[i] + x
        
        candidates = getCandidates(mid)
        res = inf
        for x in candidates:
            a = bisect_right(nums, x)
            res = min(res, a * x - psum[a] + psum[n] - psum[a] - (n - a) * x)
        return res

100123. 执行操作使频率分数最大

显示英文描述

我的提交返回竞赛

  • 通过的用户数215
  • 尝试过的用户数451
  • 用户总通过次数248
  • 用户总提交次数936
  • 题目难度****Hard

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。

你可以对数组执行 至多 k 次操作：

  • 从数组中选择一个下标 i ，将 nums[i] 增加 或者 减少 1 。

最终数组的频率分数定义为数组中众数的 频率 。

请你返回你可以得到的 最大 频率分数。

众数指的是数组中出现次数最多的数。一个元素的频率指的是数组中这个元素的出现次数。

示例 1：

输入：nums = [1,2,6,4], k = 3
输出：3
解释：我们可以对数组执行以下操作：
- 选择 i = 0 ，将 nums[0] 增加 1 。得到数组 [2,2,6,4] 。
- 选择 i = 3 ，将 nums[3] 减少 1 ，得到数组 [2,2,6,3] 。
- 选择 i = 3 ，将 nums[3] 减少 1 ，得到数组 [2,2,6,2] 。
元素 2 是最终数组中的众数，出现了 3 次，所以频率分数为 3 。
3 是所有可行方案里的最大频率分数。

示例 2：

输入：nums = [1,4,4,2,4], k = 0
输出：3
解释：我们无法执行任何操作，所以得到的频率分数是原数组中众数的频率 3 。

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109
  • 0 <= k <= 1014

地址

https://leetcode.cn/contest/weekly-contest-376/problems/apply-operations-to-maximize-frequency-score/

题意

滑动窗口

思路

  1. 首先需要将数组排序，我们知道对于任意的窗口 $[l,r]$ 此时窗口内的所有元素到窗口的中位数差的绝对值之和最小，此时我们可以采用滑动窗口 $l$ 只想窗口的左端，$r$ 指向窗口的右端，此时计算窗口内将所有元素变为其中位数所花费的代价是否大于 $k$：
    • 如果窗口变为中位数的代价小于 $k$, 则表示该窗口符合要求，并记录当前窗口的大小；
    • 如果窗口变为中位数的代价大于 $k$，则表示当前窗口无法满足要求，此时需要将窗口左端点向右移动；
    • 题目本质即为求医 $r$ 为右端点的且满足代价小于 $k$ 的最大长度；
  2. 复杂度分析:
  • 时间复杂度：$O(n)$，其中 $n$ 表示数组的长度;
  • 空间复杂度：$O(n)$，其中 $n$ 表示数组的长度;

代码

class Solution:
    def maxFrequencyScore(self, nums: List[int], k: int) -> int:
        n = len(nums)
        nums.sort()
        psum = [0] * (n + 1)
        for i, x in enumerate(nums):
            psum[i + 1] = psum[i] + x
        
        def calc(l, r):
            return psum[r + 1] - psum[(l + r + 1) // 2] - (psum[(l + r) // 2 + 1] - psum[l])
        
        j = 0
        res = 0
        for i in range(n):
            while j <= i and calc(j, i) > k:
                j += 1
            res = max(res, i - j + 1)
        return res

欢迎关注和打赏，感谢支持！

Tags: 题解 力扣周赛赛
← leetcode contest 373 leetcode biweekly contest 120 →

扫描二维码，分享此文章