LeetCode 12/07 12/08 周赛/双周赛

双周赛

T3 3377. 使两个整数相等的数位操作

题目总结：

给定两个整数 n 和 m，要求将 n 转变为 m，转变过程中需要满足以下条件：

  1. n 和 m 的数位长度相同；
  2. 可以对 n的数位执行以下操作：
    • 将 n 中的任意一个 不是 9 的数位 增加 1；
    • 将 n 中的任意一个 不是 0 的数位 减少 1；
  3. 转变过程中，n 任何中间状态都 不能是质数；
  4. 需要返回从 n 变为 m 的最小代价，代价为转变过程中所有 n 的值之和；
  5. 如果无法将 n 变为 m，返回 -1。

实现思路：

  1. 质数筛选： 使用线性筛法生成 1~10000 范围内的质数表，用布尔数组 st 标记每个数是否为质数，避免重复计算质数判断。
  2. 判断是否是质数： 定义函数 isPrime(x)，通过 st[x] 快速判断一个数是否为质数。
  3. 特殊情况过滤： 如果 n 或 m 本身是质数，则直接返回 -1，因为无法满足条件。
  4. 最短路径求解：
    • 使用 Dijkstra 算法 求解最小代价。
    • 用优先队列（堆）存储当前的值和路径代价，起点为 n，终点为 m。
    • 遍历当前数的每一位，分别尝试将该位增加或减少 1，生成新的数字 new_n：
      • 如果 new_n 不为质数，并且更新的代价比当前已知代价更小，则将其加入堆中。
    • 重复以上过程直到找到从 n 到 m 的最小代价。
  5. 返回结果： 如果在搜索中找到路径，返回最小代价；否则返回 -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，则在图中将两个节点相连。要求返回图中 连通块的数量，即所有相互连通的节点组成的独立子图的数量。

解题思路

为了实现题目的要求，我们需要解决以下问题：

  1. 构建图的连通性：
    • 我们不用显式构建图，而是利用并查集（Union-Find）来动态合并满足条件的节点。
    • 如果两个值 nums[i] 和 nums[j] 满足 LCM 的条件，则合并对应的连通块。
  2. 优化最小公倍数的计算：
    • 对于任意两个数 a 和 b，它们的最小公倍数（LCM）可以通过公式计算： lcm(a, b) = a * b / gcd(a, b) 由于 nums 中元素互不相同，可通过因数来进行筛选而避免直接计算 LCM。
  3. 通过因数优化连接过程：
    • 从小到大遍历所有的因数 g（从 1 到 threshold），对于 nums 中能被 g 整除的所有数，将这些数通过并查集进行合并。
    • 这样可以避免逐一检查任意两数间的 LCM，极大地优化性能。
  4. 并查集维护连通性：
    • 使用路径压缩和按秩合并优化的并查集，保证查找和合并操作的时间复杂度接近 O(1)。
class Solution:
    def countComponents(self, nums: List[int], threshold: int) -> int:
        n = len(nums)
        f = list(range(n))

        # 非递归并查集
        def find(x: int) -> int:
            while x != f[x]:
                f[x] = f[f[x]]
                x = f[x]
            return x

        # 记录每个数的下标
        idx = {x: i for i, x in enumerate(nums)}

        for g in range(1, threshold + 1):
            fi = -1

            for x in range(g, threshold + 1, g):
                if x in idx:
                    fi = find(idx[x])
                    break

            if fi < 0:
                continue

            for y in range(x + g, g * threshold // x + 1, g):
                if y in idx:
                    fj = find(idx[y])
                    if fj != fi:
                        f[fj] = fi  # 合并 idx[x] 和 idx[y]
                        n -= 1

        return n

周赛

T3 3381. 长度可被 K 整除的子数组的最大元素和

题目大意

给定一个整数数组 nums 和一个整数 k，要求找到一个非空子数组，使得其长度可以被 k 整除，同时该子数组的和最大。返回这个子数组的最大和。

解题思路

为了解决这个问题，我们可以利用前缀和的思想，结合模运算来处理子数组长度的整除性问题。

核心思想

  1. 前缀和性质：
    • 对于任意子数组 [i, j] 的和，可以用前缀和 s 表示： 子数组和 = s[j + 1] - s[i]
    • 如果子数组的长度 (j - i + 1) 可以被 k 整除，则有 (j + 1) % k == i % k。
    • 因此，我们只需要记录每个前缀和的模 k 的最小值即可，随后用当前的前缀和减去此前的最小值得到最大的子数组和。
  2. 优化存储和计算：
    • 使用一个哈希表 pre 来记录每个模值对应的最小前缀和。
    • 遍历数组时，更新当前前缀和并检查是否存在满足条件的模值，计算出可能的最大子数组和。
  3. 特殊情况处理：
    • 初始时，假设前缀和为 0 时，模值为 0（即可以整除），因此需要初始化 pre[0] = 0。
class Solution:
    def maxSubarraySum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        s = 0
        pre = {0: 0}  
        res = float('-inf')
        
        for i in range(n):
            s += nums[i]
            l_mod = (i + 1) % k # length mod 
            
            if l_mod in pre:
                res = max(res, s - pre[l_mod])
            
            if l_mod not in pre:
                pre[l_mod] = s  
            else:
                pre[l_mod] = min(pre[l_mod], s)
        
        return res

T4 3382. 用点构造面积最大的矩形 II

题目大意

在无限平面上，给定一组点 (xCoord[i], yCoord[i])，要求找到四个点组成的矩形，满足以下条件：

  1. 矩形的四个顶点必须是输入点中的点；
  2. 矩形的内部或边界上不能包含任何其他点；
  3. 矩形的边与坐标轴平行。

返回此类矩形的最大面积，如果无法形成这样的矩形，则返回 -1。

解题思路

关键点

  1. 坐标映射与排序：
    • 利用 xCoord 和 yCoord 分别构造点在横坐标和纵坐标上的分布，并记录每个点的信息。
    • 通过对横坐标和纵坐标的排序，便于枚举可能的矩形点对。
  2. 构造规则矩形：
    • 枚举每个点作为右上角 (x2, y2)，并通过预处理找到：
      • 左下角 (x1, y1)；
      • 矩形左上角 (x1, y2)；
      • 矩形右下角 (x2, y1)。
    • 通过这些点确定矩形的边界，并进行验证。
  3. 矩形内点的验证：
    • 构造树状数组（或其他数据结构）支持快速统计某个矩形范围内的点数。
    • 通过离线处理所有可能的矩形范围，利用前缀和或树状数组进行批量查询，确保效率。
  4. 记录面积：
    • 如果一个矩形满足条件且正好包含 4 个顶点，则计算其面积并与当前最大面积比较。
# 树状数组模板
class Fenwick:
    def __init__(self, n: int):
        self.tree = [0] * (n + 1)

    def add(self, i: int) -> None:
        while i < len(self.tree):
            self.tree[i] += 1
            i += i & -i

    # [1,i] 中的元素和
    def pre(self, i: int) -> int:
        res = 0
        while i > 0:
            res += self.tree[i]
            i &= i - 1
        return res

    # [l,r] 中的元素和
    def query(self, l: int, r: int) -> int:
        return self.pre(r) - self.pre(l - 1)

class Solution:
    def maxRectangleArea(self, xCoord: List[int], yCoord: List[int]) -> int:
        x_map = defaultdict(list)
        y_map = defaultdict(list)
        for i, x in enumerate(xCoord):
            y = yCoord[i]
            x_map[x].append(y)
            y_map[y].append(x)

        # 预处理每个点的正下方的点
        below = {}
        for x, ys in x_map.items():
            ys.sort()
            for y1, y2 in pairwise(ys):
                below[(x, y2)] = y1

        # 预处理每个点的正左边的点
        left = {}
        for y, xs in y_map.items():
            xs.sort()
            for x1, x2 in pairwise(xs):
                left[(x2, y)] = x1

        # 离散化用
        xs = sorted(x_map)
        ys = sorted(y_map)

        # 收集询问：矩形区域（包括边界）的点的个数
        queries = []
        # 枚举 (x2,y2) 作为矩形的右上角
        for x2, list_y in x_map.items():
            for y1, y2 in pairwise(list_y):
                # 计算矩形左下角 (x1,y1)
                x1 = left.get((x2, y2), None)
                # 矩形右下角的左边的点的横坐标必须是 x1
                # 矩形左上角的下边的点的纵坐标必须是 y1
                if x1 is not None and left.get((x2, y1), None) == x1 and below.get((x1, y2), None) == y1:
                    queries.append((
                        bisect_left(xs, x1),  # 离散化
                        bisect_left(xs, x2),
                        bisect_left(ys, y1),
                        bisect_left(ys, y2),
                        (x2 - x1) * (y2 - y1),
                    ))

        # 离线询问
        qs = [[] for _ in range(len(xs))]
        for i, (x1, x2, y1, y2, _) in enumerate(queries):
            if x1 > 0:
                qs[x1 - 1].append((i, -1, y1, y2))
            qs[x2].append((i, 1, y1, y2))

        # 回答询问
        res = [0] * len(queries)
        tree = Fenwick(len(ys))
        for i, x in enumerate(xs):
            # 把横坐标为 x 的所有点都加到树状数组中
            for y in x_map[x]:
                tree.add(bisect_left(ys, y) + 1)  # 离散化
            for qid, sign, y1, y2 in qs[i]:
                # 查询 [y1,y2] 中点的个数
                res[qid] += sign * tree.query(y1 + 1, y2 + 1)

        ans = -1
        for cnt, q in zip(res, queries):
            if cnt == 4:
                ans = max(ans, q[4])
        return ans