结果
这里是式酱(∠・ω< )⌒☆
大家元旦快乐呀！今天就是纯粹福利场了，没有Hard题，大家在新年第一天都可以顺利AK。
6278. 统计能整除数字的位数
class Solution:
def countDigits(self, num: int) -> int:
res = 0
for x in str(num):
if num % int(x) == 0:
res += 1
return res6279. 数组乘积中的不同质因数数目
筛一下质数，用集合计数即可。
class Solution:
def distinctPrimeFactors(self, nums: List[int]) -> int:
s = set()
for i in nums:
p, x = 2, i
while p * p <= x:
while x % p == 0:
x //= p
s.add(p)
p += 1
if x > 1:
s.add(x)
return len(s)6196. 将字符串分割成值不超过 K 的子字符串
记忆化搜索 找到一个有效的切分点就切开试试，答案应该返回一个最小的有效切分次数。
class Solution:
def minimumPartition(self, s: str, k: int) -> int:
n = len(s)
t = len(str(k))
@cache
def dfs(start):
if start == n:
return 0
count = 0
ans = 10**18
for i in range(start,min(n,start + t)):
count = 10*count + int(s[i])
if count <= k:
ans = min(ans,1 + dfs(i + 1))
return ans
ans = dfs(0)
return ans if ans != 10**18 else -16280. 范围内最接近的两个质数
埃氏全局筛一遍，找出[left,right]之间的所有质数，线性遍历找出最小差值的两个质数。时间复杂度O（n）
prim = [-1]*(10**6 + 1)
for i in range(2,10**6 + 1):
if prim[i] == -1:
for j in range(i,10**6 + 1,i):
prim[j] = i
class Solution:
def closestPrimes(self, left: int, right: int) -> List[int]:
p = [i for i in range(left,right + 1) if prim[i] == i]
res = [-1,-1]
for i in range(1,len(p)):
if res[0] == -1 or p[i] - p[i-1] < res[1] - res[0]:
res[0] = p[i-1]
res[1] = p[i]
return res评论 (7)
