leetcode weekly contest 412

最近周赛难度确实加强了，题目质量缺少高了不少，今天的 t3,t4 总体来说还算是不错的题目，值得思考的题目，只做出来了 t4 没有做出来 t3, t3 确实值得思考的题目。国服登不上去，试着用美服打了下比赛，感觉美服的速度比国服快好多。

3264. K 次乘运算后的最终数组 I

给你一个整数数组 nums ，一个整数 k 和一个整数 multiplier 。

你需要对 nums 执行 k 次操作，每次操作中：

• 找到 nums 中的 最小 值 x ，如果存在多个最小值，选择最 前面 的一个。
• 将 x 替换为 x * multiplier 。

请你返回执行完 k 次乘运算之后，最终的 nums 数组。

示例 1：

输入：nums = [2,1,3,5,6], k = 5, multiplier = 2

输出：[8,4,6,5,6]

解释：

示例 2：

输入：nums = [1,2], k = 3, multiplier = 4

输出：[16,8]

解释：

提示：

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100
• 1 <= k <= 10
• 1 <= multiplier <= 5

地址

https://leetcode.cn/contest/weekly-contest-412/problems/final-array-state-after-k-multiplication-operations-i/

题意

模拟

思路

1. 优先对模拟即可，每次从队列中弹出最小的元素，并乘以 multiplier ，再将其压入到队列中，一共执行 $k$ 次即可。
2. 复杂度分析：

• 时间复杂度：$O((n + k) \log n)$，其中 $n$ 表示数组的长度， $k$ 表示给定的数字 $k$。
• 空间复杂度：$O(n)$。

代码

class Solution:
    def getFinalState(self, nums: List[int], k: int, multiplier: int) -> List[int]:
        pq = []
        for i, x in enumerate(nums):
            heapq.heappush(pq, [x, i])
        for _ in range(k):
            [x, i] = heapq.heappop(pq)
            heapq.heappush(pq, [x * multiplier, i])
        for x, i in pq:
            nums[i] = x
        return nums

3265. 统计近似相等数对 I

给你一个正整数数组 nums 。

如果我们执行以下操作 至多一次 可以让两个整数 x 和 y 相等，那么我们称这个数对是 近似相等 的：

• 选择 x 或者 y 之一，将这个数字中的两个数位交换。

请你返回 nums 中，下标 i 和 j 满足 i < j 且 nums[i] 和 nums[j] 近似相等 的数对数目。

注意 ，执行操作后一个整数可以有前导 0 。

示例 1：

输入：nums = [3,12,30,17,21]

输出：2

解释：

近似相等数对包括：

• 3 和 30 。交换 30 中的数位 3 和 0 ，得到 3 。
• 12 和 21 。交换12 中的数位 1 和 2 ，得到 21 。

示例 2：

输入：nums = [1,1,1,1,1]

输出：10

解释：

数组中的任意两个元素都是近似相等的。

示例 3：

输入：nums = [123,231]

输出：0

解释：

我们无法通过交换 123 或者 321 中的两个数位得到另一个数。

提示：

• 2 <= nums.length <= 100
• 1 <= nums[i] <= 106

地址

https://leetcode.cn/contest/weekly-contest-412/problems/count-almost-equal-pairs-i/

题意

排序 + 哈希表

思路

1. 在这个题目上纠结的事件太多了，当然最简单的就是 $o(n^2)$ 直接比较任意两个数对是否相近即可，比较简单。题目中有两点不好处理：

   • 前导 $0$ 相近的问题，比如 $(1,10), (30, 3)$ 都属于近似相等的，在这里我们统一可以从小到大排序，只需要处理较大的数造成前导 $0$ 的问题，避免比较不带前导 $0$ 的数字比较前导 $0$ 的数字，这样就比较好处理；
   • 任意变换时可能存在重复的问题，此时我们可以用哈希表来解决该问题，枚举所有的相似变换，即交换元素中的任意两位；

   在以上处理后，这个题目就变得比较简单了，我们用哈希表统计当前数组中已经出现数字的次数，遍历到 $nums[i]$ 时，找到 $nums[i]$ 所有相似的数字，并统计这些数字出现的和即可。

2. 复杂度分析：

• 时间复杂度：$O(n \log n + n \log^2 U)$，其中 $n$ 表示给定数组的长度. $U$ 表示数字中的最大值 。
• 空间复杂度：$O(n)$；

代码

class Solution:
    def countPairs(self, nums: List[int]) -> int:
        n = len(nums)
        cnt = Counter()
        nums.sort()
        res = 0
        for x in nums:
            s = list(str(x))
            res += cnt[x]
            for i in range(len(s)):
                for j in range(i + 1, len(s)):
                    if s[i] == s[j]:
                        continue
                    s[i], s[j] = s[j], s[i]
                    res += cnt[int("".join(s))]
                    s[i], s[j] = s[j], s[i]
            cnt[x] += 1
        
        return res

3266. K 次乘运算后的最终数组 II

给你一个整数数组 nums ，一个整数 k 和一个整数 multiplier 。

你需要对 nums 执行 k 次操作，每次操作中：

• 找到 nums 中的 最小 值 x ，如果存在多个最小值，选择最 前面 的一个。
• 将 x 替换为 x * multiplier 。

k 次操作以后，你需要将 nums 中每一个数值对 109 + 7 取余。

请你返回执行完 k 次乘运算以及取余运算之后，最终的 nums 数组。

示例 1：

输入：nums = [2,1,3,5,6], k = 5, multiplier = 2

输出：[8,4,6,5,6]

解释：

示例 2：

输入：nums = [100000,2000], k = 2, multiplier = 1000000

输出：[999999307,999999993]

解释：

提示：

• 1 <= nums.length <= 104
• 1 <= nums[i] <= 109
• 1 <= k <= 109
• 1 <= multiplier <= 106

地址

https://leetcode.cn/contest/weekly-contest-412/problems/final-array-state-after-k-multiplication-operations-ii/

题意

优先队列 + 数学

思路

1. 当 $k$ 比较小时，我们直接使用优先队列即可，题目就非常简单与常规的题目，本题重点在于如何讨论 $k$ 比较大的时候该怎么处理。由于 $k$ 的取值范围为 $[1,10^9]$, 此时肯定无法枚举了，就需要我们使用数学技巧来处理，假设当前数组 $nums$ 有序，排序如下：
   $$
   [a_0,a_1,a_2,\cdots,a_{n-1}],a_i \le a_{i+1}
   $$
   此时我们首先是将 $a’0 = a_0 \times multiplier $ 加入到新的数组中，如果 $a’_0 \le a{n-1}$, 则此时它一定仍然排序在前 $n-1$ 个位置中，但是如果满足 $a’0 > a{n-1}$, 此时数组变成了如下：
   $$
   [a_1,a_2,\cdots,a_{n-1},a_0 \times multiplier ]
   $$
   继续下一个最小的元素乘以 $multiplier$, 由于 $a_0 \le a_1$，此时 $a_1 \times multiplier > a_{n-1}$, 则此时数组一定变成了如下：
   $$
   [a_2,\cdots,a_{n-1},a_0 \times multiplier,a_1 \times multiplier]
   $$
   我们继续重复 $n$ 次后发现得到如下队列：
   $$
   [a_0 \times multiplier ,a_1 \times multiplier ,a_2 \times multiplier ,\cdots,a_{n-1} \times multiplier ],a_i \le a_{i+1}
   $$
   这说明每经过 $n$ 次，数组又回到了原来的排序，属于 $n$ 循环节，此时我们去除掉所有的 $n$ 循环节的部分，中间的计算都是重复且可以忽略的，我们只需要计算循环节之外的那部分即可。这个是本题的解题关键；

2. 我们先找到循环节开始的位置，此时我们通过优先级队列模拟找到当前最小的元素乘以 $multiplier$ 大于数组中最大值的开始部分，后续则是利用循环节，找到循环节剩余的部分，期间需要用到快速幂的部分，本身倒也没有太大难度。

3. 复杂度分析：

• 时间复杂度：$𝑂(𝑛log⁡ 𝑛+ n \log U)$，其中 𝑛 表示给定数组的长度. 𝑈 表示数字中的最大值 。
• 空间复杂度：$𝑂(𝑛)$；

代码

class Solution:
    def getFinalState(self, nums: List[int], k: int, multiplier: int) -> List[int]:
        if multiplier == 1:
            return nums
        n = len(nums)
        maxVal = max(nums)
        pq = []
        for i, x in enumerate(nums):
            heapq.heappush(pq, [x, i])
        while k > 0:
            if pq[0][0] * multiplier > maxVal:
                break
            [x, i] = heapq.heappop(pq)
            heapq.heappush(pq, [x * multiplier, i])
            k -= 1
        
        rest = k % n
        mod = 10**9 + 7
        tot = pow(multiplier, k // n, mod)
        for i in range(n):
            [val, j] = heapq.heappop(pq)
            nums[j] = val * tot % mod
            if i < rest:
                 nums[j] = nums[j] * multiplier % mod
        return nums

3267. 统计近似相等数对 II

注意：在这个问题中，操作次数增加为至多 两次 。

给你一个正整数数组 nums 。

如果我们执行以下操作 至多两次 可以让两个整数 x 和 y 相等，那么我们称这个数对是 近似相等 的：

• 选择 x 或者 y 之一，将这个数字中的两个数位交换。

请你返回 nums 中，下标 i 和 j 满足 i < j 且 nums[i] 和 nums[j] 近似相等 的数对数目。

注意 ，执行操作后得到的整数可以有前导 0 。

示例 1：

输入：nums = [1023,2310,2130,213]

输出：4

解释：

近似相等数对包括：

• 1023 和 2310 。交换 1023 中数位 1 和 2 ，然后交换数位 0 和 3 ，得到 2310 。
• 1023 和 213 。交换 1023 中数位 1 和 0 ，然后交换数位 1 和 2 ，得到 0213 ，也就是 213 。
• 2310 和 213 。交换 2310 中数位 2 和 0 ，然后交换数位 3 和 2 ，得到 0213 ，也就是 213 。
• 2310 和 2130 。交换 2310 中数位 3 和 1 ，得到 2130 。

示例 2：

输入：nums = [1,10,100]

输出：3

解释：

近似相等数对包括：

• 1 和 10 。交换 10 中数位 1 和 0 ，得到 01 ，也就是 1 。
• 1 和 100 。交换 100 中数位 1 和从左往右的第二个 0 ，得到 001 ，也就是 1 。
• 10 和 100 。交换 100 中数位 1 和从左往右的第一个 0 ，得到 010 ，也就是 10 。

提示：

• 2 <= nums.length <= 5000
• 1 <= nums[i] < 107

地址

https://leetcode.cn/contest/weekly-contest-412/problems/count-almost-equal-pairs-ii/

题意

排序哈希表

思路

1. 与 t2 一样的技巧，只不过变换一次改成了至多可以交换两次，我们直接枚举所有两次变换的可能即可, 这里需要用哈希表去重即可，感觉 t4 比 t3 简单多了，没有什么复杂技巧，反正竟然一把就过了。

2. 复杂度分析：

• 时间复杂度：$𝑂(𝑛log⁡ 𝑛+ n \log^4 U)$，其中 𝑛 表示给定数组的长度. 𝑈 表示数字中的最大值 。
• 空间复杂度：$𝑂(𝑛)$；

代码

class Solution:
    def countPairs(self, nums: List[int]) -> int:
        n = len(nums)
        cnt = Counter()
        nums.sort()
        res = 0
        for x in nums:
            s = list(str(x))
            arr = set([x])
            for i in range(len(s)):
                for j in range(i + 1, len(s)):
                    if s[i] == s[j]:
                        continue
                    s[i], s[j] = s[j], s[i]
                    arr.add(int("".join(s)))
                    for a in range(len(s)):
                        for b in range(a + 1, len(s)):
                            if s[a] == s[b]:
                                continue
                            s[a], s[b] = s[b], s[a]
                            arr.add(int("".join(s)))
                            s[a], s[b] = s[b], s[a]
                    s[i], s[j] = s[j], s[i]
            res += sum(cnt[v] for v in list(arr))
            cnt[x] += 1
        
        return res

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

• 关注我的博客: https://mike-box.github.io/

• 关注我的知乎：https://www.zhihu.com/people/da-hua-niu

• 关注我的微信公众号: 哪些奋斗者