• LeetCode笔记：Weekly Contest 326
  • 1. 题目一
    • 1. 解题思路
    • 2. 代码实现
  • 2. 题目二
    • 1. 解题思路
    • 2. 代码实现
  • 3. 题目三
    • 1. 解题思路
    • 2. 代码实现
  • 4. 题目四
    • 1. 解题思路
    • 2. 代码实现

• 比赛链接：https://leetcode.com/contest/weekly-contest-326/

1. 题目一

给出题目一的试题链接如下：

• 2520. Count the Digits That Divide a Number

1. 解题思路

这一题的思路很直接，就是把每一位上的数字来看看是否能够被原数整除，然后统计一下可以被整除的数的数目即可。

2. 代码实现

给出python代码实现如下：

class Solution:def countDigits(self, num: int) -> int:s = str(num)cnt = 0for ch in s:if num % int(ch) == 0:cnt += 1return cnt

提交代码评测得到：耗时33ms，占用内存13.9MB。

2. 题目二

给出题目二的试题链接如下：

• 2521. Distinct Prime Factors of Product of Array

1. 解题思路

这一题我的思路就是先取出1000以下的全部质数，然后对每一个数看看有哪些质因子然后汇总一下就行。

2. 代码实现

给出python代码实现如下：

class Solution:@lru_cache(None)def get_primes(self):status = [0 for _ in range(1001)]primes = []for i in range(2, 1001):if status[i] == 0:primes.append(i)for j in range(i, 1001, i):status[j] = 1return primesdef distinctPrimeFactors(self, nums: List[int]) -> int:primes = self.get_primes()_primes = set()for x in nums:for y in primes:if y > x:breakif x % y == 0:_primes.add(y)return len(_primes)

提交代码评测得到：耗时743ms，占用内存15.9MB。

3. 题目三

给出题目三的试题链接如下：

• 2522. Partition String Into Substrings With Values at Most K

1. 解题思路

这一题我的思路比较暴力，就是一个简单地动态规划，考察每一种可行的切分即可。

2. 代码实现

给出python代码实现如下：

class Solution:def minimumPartition(self, s: str, k: int) -> int:n = len(s)@lru_cache(None)def dp(idx):if idx == n:return 0res = math.inffor i in range(idx+1, n+1):if int(s[idx:i]) > k:breakres = min(res, 1 + dp(i))return resres = dp(0)return res if res != math.inf else -1

提交代码评测得到：耗时1852ms，占用内存206.6MB。

4. 题目四

给出题目四的试题链接如下：

• 2523. Closest Prime Numbers in Range

1. 解题思路

这一题我的思路还是很直接，就是直接求出10610^6106以下的全部质数，然后找到左右边界之后看看范围内的数最小的相邻差距即可。

难度上可能就是计算质数的时候计算量还是很大的，因此就要想办法让他只计算一次，在这一点上，我用python感觉是有点取巧了，可能还有更好的做法吧。

2. 代码实现

给出python代码实现如下：

class Solution:def __init__(self, *args, **kwargs):super().__init__(*args, **kwargs)self.primes = Solution.get_primes()@staticmethod@lru_cache(None)def get_primes():status = [0 for _ in range(1000001)]primes = []for i in range(2, 1000001):if status[i] == 0:primes.append(i)for j in range(i, 1000001, i):status[j] = 1return primesdef closestPrimes(self, left: int, right: int) -> List[int]:i = bisect.bisect_left(self.primes, left)j = bisect.bisect_right(self.primes, right)res, delta = [-1, -1], math.inffor k in range(i, j-1):if self.primes[k+1] - self.primes[k] < delta:res = [self.primes[k], self.primes[k+1]]delta = self.primes[k+1] - self.primes[k]if delta == 2:breakreturn res

提交代码评测得到：耗时246ms，占用内存24.8MB。