跳到主要内容

第 302 场周赛

Problem A - 数组能形成多少数对​

方法一：暴力​

  • 时间复杂度 O(N)\mathcal{O}(N)。
  • 空间复杂度 O(N)\mathcal{O}(N)。
参考代码（Python 3）
class Solution:
    def numberOfPairs(self, nums: List[int]) -> List[int]:
        cnt = collections.Counter(nums)
        prs = sum(cnt[key] // 2 for key in cnt)
        return [prs, len(nums) - prs * 2]

Problem B - 数位和相等数对的最大和​

方法一：暴力​

  • 时间复杂度 O(Nlog⁡N)\mathcal{O}(N\log N)。
  • 空间复杂度 O(N)\mathcal{O}(N)。
参考代码（Python 3）
class Solution:
    def maximumSum(self, nums: List[int]) -> int:
        v = collections.defaultdict(list)
        for num in nums:
            v[sum(map(int, str(num)))].append(num)
        ans = -1
        for num in v:
            if len(v[num]) >= 2:
                v[num].sort(reverse=True)
                ans = max(ans, v[num][0] + v[num][1])
        return ans

Problem C - 裁剪数字后查询第 K 小的数字​

方法一：暴力​

  • 时间复杂度 O(Q∑∣Wi∣log⁡∑∣Wi∣)\mathcal{O}(Q\sum |W_i|\log\sum |W_i|) 。
  • 空间复杂度 O(∑∣Wi∣)\mathcal{O}(\sum |W_i|) 。
参考代码（Python 3）
class Solution:
    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:
        m = len(nums[0])
        ans = []
        for k, trim in queries:
            clipped = [(num[-trim:], i) for i, num in enumerate(nums)]
            clipped.sort()
            ans.append(clipped[k - 1][1])
        return ans

方法二：基数排序（略）​

Problem D - 使数组可以被整除的最少删除次数​

方法一：数学​

  • 时间复杂度 O(Nlog⁡N)\mathcal{O}(N\log N) 。
  • 空间复杂度 O(1)\mathcal{O}(1) 。
参考代码（Python 3）
from math import gcd

class Solution:
    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:
        g = 0
        for num in numsDivide:
            g = gcd(g, num)
        nums.sort()
        for i in range(len(nums)):
            if g % nums[i] == 0:
                return i
        return -1