本周学习情况

• 周一至周三每天进行了两轮周赛模拟，其中有五次均在40分钟内完成了三题，一次在一个半小时内完成三题。
• 周四把上次周赛的中等题过了一遍，并练习了枚举。
• 周五、周六温习图的相关算法与代码模板，并做练习。
• 周赛第一次 0 错误 AK 。

一点阶段性感想

过去两个月刷 LeetCode 的经历还是比较开心的，学到很多东西（也还有更多要学）。

差不多要进入下一个阶段的学习了。虽然不会停止算法练习，但就不每天专帖更新了。

再多立个flag，今年每日一题要全勤！（虽然12月每天都做题，但非每日一题不算……）

周赛情况

两道 M 题都涉及到质数，恰好这周刷到了质数题，对这类题目有基本了解，所以很快做出来了。

但最后能 AK 确实意料之外。算是2023年第一天的一个意外惊喜，新年新气象！

可能因为圣诞周赛太难了所以这次放放水

Problem 1 统计能整除数字的位数

思路

数字最大才9位，逐位检查即可。

代码

class Solution:
    def countDigits(self, num: int) -> int:
        value = num
        ans = 0
        while num:
            cur = num % 10
            num //= 10
            if value % cur == 0: ans += 1
        return ans

Problem 2 数组乘积中的不同质因数数目

思路

首先不能被举例迷惑，总共会有 10000 个数字，累积肯定会溢出。而显然每个因数的因数也一定是积的因数，所以检查所有数字的质因数即可。

先想分解每个数再统计，但估计会超时。然后看到数字范围，只有 1000 个，那么可以对这 1000 个数字逐个求质因数，放进单独的集合中，遍历数组时直接取用算好的质因数放到集合里即可。

最后返回集合大小。

代码

class Solution:
    def distinctPrimeFactors(self, nums: List[int]) -> int:
        def getContent(x: int) -> Set[int]:
            content = set()
            i = 2
            while i * i <= x:
                if (x % i == 0):
                    while x % i == 0:
                        content.add(i)
                        x = x // i
                i += 1
            if x > 1: content.add(x)
            return content
        mapping = [set() for _ in range(1001)]
        for num in range(2, 1001):
            mapping[num] = getContent(num)
        res = set()
        for num in nums:
            res = res.union(mapping[num])
        return len(res)

Problem 3 将字符串分割成值不超过 K 的子字符串

思路

贪心法，让当前数字尽可能大，如果超出 k ，就另起一个数字。如此可以推出全局最优：子串数目最少。

另外想到什么时候无法分割子串？在最坏的情况下，我们只能把每一位数字作为一个子串，那么当 k 小于 9 ，且字符串中有大于 k 的数字，此时一定分割不了，返回 -1 。

代码

class Solution:
    def minimumPartition(self, s: str, k: int) -> int:
        if k < 9:
            for ch in s:
                if int(ch) > k: return -1
        ans = 0
        cur = ""
        n = len(s)
        for idx in range(n):
            if int(cur + s[idx]) > k:
                cur = ""
                ans += 1
            cur += s[idx]
        return ans + 1

Problem 4 范围内最接近的两个质数

思路

看到数据范围最大到 10 的 6 次方，而上次计数质数是它的五倍，那么显然可以直接用了。

直接用埃氏筛法生成范围内质数，然后从小到大遍历找差最小的组合即可（显然组合一定相邻）。

如果生成的质数数目不足 2 ，返回 -1 。

代码

class Solution:
    def closestPrimes(self, left: int, right: int) -> List[int]:
        primes = []

        def getPrimes(n: int) -> None:
            if n < 2:  return
            nums = [1 for i in range(n + 1)]
            nums[0] = 0
            nums[1] = 0
            for num in range(2, int(sqrt(n)) + 1):
                if nums[num]:
                    for i in range(num * num, n + 1, num):
                        nums[i] = 0
            for num in range(n + 1):
                if nums[num] and left <= num <= right:
                    primes.append(num)
            return

        getPrimes(right)
        if len(primes) < 2: return [-1, -1]
        ans = [primes[0], primes[1]]
        n = len(primes)
        for i in range(1, n):
            if primes[i] - primes[i - 1] < ans[1] - ans[0]:
                ans = [primes[i - 1], primes[i]]
        return ans