LeetCode 12/07 12/08 周赛/双周赛
LeetCode 12/07 12/08 周赛/双周赛 双周赛 T3 3377. 使两个整数相等的数位操作 题目总结： 给定两个整数 n 和 m，要求将 n 转变为 m，转变过程中需要满足以下条件： n 和 m 的数位长度相同； 可以对 n的数位执行以下操作： 将 n 中的任意一个 不是 9 的数位 增加 1； 将 n 中的任意一个 不是 0 的数位 减少 1； 转变过程中，n 任何中间状态都 不能是质数； 需要返回从 n 变为 m 的最小代价，代价为转变过程中所有 n 的值之和； 如果无法将 n 变为 m，返回 -1。 实现思路： 质数筛选： 使用线性筛法生成 1~10000 范围内的质数表，用布尔数组 st 标记每个数是否为质数，避免重复计算质数判断。 判断是否是质数： 定义函数 isPrime(x)，通过 st[x] 快速判断一个数是否为质数。 特殊情况过滤： 如果 n 或 m 本身是质数，则直接返回 -1，因为无法满足条件。 最短路径求解： 使用 Dijkstra 算法 求解最小代价。 用优先队列（堆）存储当前的值和路径代价，起点为 n，终点为 m。 遍历当前数的每一位，分别尝试将该位增加或减少 1，生成新的数字 new_n： 如果 new_n 不为质数，并且更新的代价比当前已知代价更小，则将其加入堆中。 重复以上过程直到找到从 n 到 m 的最小代价。 返回结果： 如果在搜索中找到路径，返回最小代价；否则返回 -1 表示无法转换。 class Solution: def minOperations(self, n: int, m: int) -> int: N = 10000 primes = [] st = [False] * (N + 1) st[1] = True def sieve(n): for i in range(2, n + 1): if not st[i]: primes.append(i) for prime in primes: if i * prime > n: break st[i * prime] = True if i % prime == 0: break sieve(N) def isPrime(x): return not st[x] if isPrime(n) or isPrime(m): return -1 dis = [inf] * (N + 1) def dijkstra(): h = [(n, n)] dis[n] = n while h: dist, ver = heappop(h) if ver == m: return dist if dist > dis[ver]: continue str_n = list(str(ver)) for i in range(len(str_n)): ch = str_n[i] for delta in [-1, 1]: new_ch = chr(ord(ch) + delta) if '0' <= new_ch <= '9': new_n = int("".join(str_n[:i] + [new_ch] + str_n[i+1:])) if not isPrime(new_n) and dist + new_n < dis[new_n]: dis[new_n] = dist + new_n heappush(h, (dis[new_n], new_n)) return dis[m] res = dijkstra() return res if res < inf else -1 T4 3378. 统计最小公倍数图中的连通块数目 题目大意 题目给定一个整数数组 nums 和一个正整数 threshold，定义一张由 nums 的元素组成的图。如果两个节点对应的值 nums[i] 和 nums[j] 的最小公倍数（LCM）小于等于 threshold，则在图中将两个节点相连。要求返回图中 连通块的数量，即所有相互连通的节点组成的独立子图的数量。 ...