Weekly Contest 399 周赛题目解析

Posted on Mon 17 June 2024 in Leetcode

Weekly Contest 399

第 399 场周赛

题目列表

3162. Find the Number of Good Pairs I 优质数对的总数 I

给定数组nums1和nums2和整数k，定义好数对为(i,j)使得nums1[i]整除nums2[j] * k，找到所有好数对的数量。

由于取值范围较小，我们直接O(n^2)暴力计算即可。

class Solution:
    def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:
        result = 0
        for i in nums1:
            for j in nums2:
                if i % (j * k) == 0:
                    result += 1

        return result

3163. String Compression III 压缩字符串 III

定义压缩算法为将最多9个连续字符压缩为数字前缀与字母后缀的字符串，给定字符word，将其进行压缩并返回最终的压缩字符串。

按照题意模拟即可。

class Solution:
    def compressedString(self, word: str) -> str:
        ns = []

        c = None
        cnt = 0

        def append_reset():
            nonlocal c
            nonlocal cnt
            if c != None:
                ns.append(str(cnt))
                ns.append(c)
            c = None
            cnt = 0

        for w in word:
            if c == None or w == c:
                c = w
                cnt += 1
                if cnt == 9:
                    append_reset()
            elif w != c:
                append_reset()
                c = w
                cnt = 1
        append_reset()

        return ''.join(ns)

3164. Find the Number of Good Pairs II 优质数对的总数 II

第三题题目与第一题一样，只是数据范围增加，因此不多赘述。

若nums1[i]可以被nums2[j] * k整除，那么nums2[j] * k一定是nums[i]的一个因数。在数据范围内，我们可以在常数范围内求得nums1的因数。此题的解法呼之欲出。即我们对于球的nums1中每一个数求所有的因数，再用nums2[j] * k进行搜索即可。

import math

def find_factors(n):
    factors = set()
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            factors.add(i)
            factors.add(n // i)
    return factors


class Solution:
    def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:
        # find all prime factors?
        d = defaultdict(int)
        for n in nums1:
            for f in find_factors(n):
                d[f] += 1

        result = 0
        for n in nums2:
            result += d[n * k]
        return result

3165. Maximum Sum of Subsequence With Non-adjacent Elements 不包含相邻元素的子序列的最大和

这题暂时不会做了，之后补充吧。

Contest