leetcode biweekly contest 493

leetcode contest 493

本周的题目确实没啥太大难度，前 $3$ 题基本都是简单题目，t4 确实比较简单的题目，t3反而有一些难度。

Q1. 统计范围内的逗号

给你一个整数 n。

返回将所有从 [1, n]（包含两端）范围内的整数以标准数字格式书写时所用到的 逗号总数。

在标准格式中：

从右边开始，每三位数字后插入一个逗号。
位数 少于四位 的数字不包含逗号。

示例 1：

输入： n = 1002

输出： 3

解释：

数字 "1,000"、"1,001" 和 "1,002" 每个都包含一个逗号，总计 3 个逗号。

示例 2：

输入： n = 998

输出： 0

解释：

从 1 到 998 的所有数字位数都少于四位，因此没有使用逗号。

提示：

1 <= n <= 105

地址

https://leetcode.cn/contest/weekly-contest-493/problems/count-commas-in-range/

题意

模拟

思路

由于 $n$ 的取值范围为 $[1,10^5]$，此时我们可以知道 $[1000,100000]$ 范围内的所有元素均含有 $1$ 个逗号，此时我们直接统计处于该范围内的元素即可。
复杂度分析：

时间复杂度：$O(1)$。
空间复杂度：$O(1)$。

代码

class Solution:
    def countCommas(self, n: int) -> int:
        return max(0, n - 999)

Q2. 统计范围内的逗号 II

给你一个整数 n。

返回将所有从 [1, n]（包含两端）范围内的整数以标准数字格式书写时所用到的 逗号总数。

在标准格式中：

从右边开始，每三位数字后插入一个逗号。
位数 少于四位 的数字不包含逗号。

示例 1：

输入： n = 1002

输出： 3

解释：

数字 "1,000"、"1,001" 和 "1,002" 每个都包含一个逗号，总计 3 个逗号。

示例 2：

输入： n = 998

输出： 0

解释：

从 1 到 998 的所有数字位数都少于四位，因此没有使用逗号。

提示：

1 <= n <= 1015

地址

https://leetcode.cn/contest/weekly-contest-493/problems/count-commas-in-range-ii/description/

题意

模拟

思路

根据提议可知，每三位需要插入一个逗号，少于三位则无需逗号，此时我们可以得到如下结论：
- 处于 $[10^3,10^6)$ 的元素包含 $1$ 个逗号；
- 处于 $[10^6,10^9)$ 的元素包含 $2$ 个逗号；
- 处于 $[10^9,10^{12})$ 的元素包含 $3$ 个逗号；
- 处于 $[10^{12},10^{15})$ 的元素包含 $4$ 个逗号；
- 处于 $[10^{15},10^{18})$ 的元素包含 $5$ 个逗号；
我们依次检测给定范围 $[1,n]$ 有多少个元素处在上述区间内，并计算即可。
复杂度分析：

时间复杂度：$O(1)$；
空间复杂度：$O(1)$；

代码

class Solution:
    def countCommas(self, n: int) -> int:
        ranges = [
            (10**3, 10**6 - 1, 1),
            (10**6, 10**9 - 1, 2),
            (10**9, 10**12 - 1, 3),
            (10**12, 10**15 - 1, 4),
            (10**15, 10**18 - 1, 5),
        ]
        
        res = 0
        for low, high, commas in ranges:
            if n >= low:
                res += commas * (min(n, high) - low + 1)
        return res

Q3. 替换最多一个元素后的最长等差子数组

给你一个整数数组 nums。

如果子数组中相邻元素的差值是一个常数，那么这个子数组被称为 等差子数组。

你可以将 nums 中的 最多一个元素替换为任意一个整数。然后，从 nums 中选择一个等差子数组。

返回一个整数，该整数表示你可以选择的最长等差子数组的长度。

子数组 是数组中一段连续的元素序列。

示例 1：

输入： nums = [9,7,5,10,1]

输出： 5

解释：

将 nums[3] = 10 替换为 3，数组变为 [9, 7, 5, 3, 1]。
选择子数组 [**9, 7, 5, 3, 1**]，它是等差数组，相邻元素的公差为 -2。

示例 2：

输入： nums = [1,2,6,7]

输出： 3

解释：

将 nums[0] = 1 替换为 -2，数组变为 [-2, 2, 6, 7]。
选择子数组 [**-2, 2, 6**, 7]，它是等差数组，相邻元素的公差为 4。

提示：

4 <= nums.length <= 105
1 <= nums[i] <= 105

地址

https://leetcode.cn/contest/weekly-contest-493/problems/longest-arithmetic-sequence-after-changing-at-most-one-element/description/

题意

枚举

思路

题目似乎有些难度，但是我们具体分析如下前提：
- 长度小于等于 $3$ 的子数组在经过修改一个元素后一定可以变为等差数组；
- 我们设 $left[i]$ 表示以 $i$ 为结束位置的最长等差数组的长度，设 $right[i]$ 表示以 $i$ 为起点的等差子数组的最大长度；
我们可以依次枚举被修改的那个元素，鉴定修改的元素为 $nums[i]$，此时可以有以下几种情况构成等差数列：
- 假设从 $nums_{i+1}\cdots nums_{j}$ 为等差数组，此时 $nums[i]$ 通过修改后，区间 $[i,\cdots,j]$ 一定可以构成等差数列，此时等差数组长度最长可能为 $left[i+1] + 1$；
- 假设从 $nums_{j}\cdots nums_{i-1}$ 为等差数组，此时 $nums[i]$ 通过修改后，区间 $[j,\cdots,i]$ 一定可以构成等差数列，此时等差数组长度最长可能为 $right[i+1] + 1$；
- 当满足 $(nums[i-1] + nums[i+1]) \bmod 2 = 0$，此时通过修改 $nums[i]$ 才可能使得 $[i-1,i,i+1]$ 这个三个下标构成等差数组，此时我们分为以下三种情况：
  - 当满足 $(nums[i-1] + nums[i+1]) \bmod 2 = 0$，我们希望在子数组的左侧加入 $[nums[i-1],nums[i]]$ 两个元素构成新的等差数组，此时需要要满足数组新加入的元素公差 $d$ 相等，设以 $i+1$ 为起点的等差子数组的等差为 $d$，此时需要满足 $nums[i+1] - nums[i-1] = 2 \cdot d$，才能使得新加入两个元素 $(i-1,i)$ 后构成连续的等差数组，此时等差数组的长度可能为 $2 + right[i+1]$;
  - 当满足 $(nums[i-1] + nums[i+1]) \bmod 2 = 0$，我们希望在子数组的右侧加入 $[nums[i],nums[i+1]]$ 两个元素构成新的等差数组，此时需要要满足数组新加入的元素公差 $d$ 相等，设以 $i-1$ 为结束位置的等差子数组的等差为 $d$，此时需要满足 $nums[i+1] - nums[i-1] = 2 \cdot d$，才能使得新加入两个元素 $(i,i+1)$ 后构成连续的等差数组，此时等差数组的长度可能为 $2 + left[i-1]$;
  - 设 $i$ 左侧的连续等差子数组长度为 $left[i-1]$,右侧的等差子数组长度为 $right[i+1]$,此时我们希望加入 $nums[i]$ 后使得 $(j,\cdots,i-1),i,(i+1,\cdots,k)$ 构成连续的等差子数组，此时设左侧连续等差子数组的公差为 $d_l$,右侧连续等差子数组的公差为 $d_r$，此时需要满足 $d_l = d_r$ 且 $nums[i+1] - nums[i-1] = 2 \cdot d_l$ ，即可使得 $(j,\cdots,i-1,i,i+1,\cdots,k)$ 构成等差子数组，此时等差子数组的长度为 $left[i-1] + 1 + right[i+1]$；
复杂度分析：

时间复杂度：$𝑂(n)$，其中 𝑛 表示给定的数组的长度。
空间复杂度：$𝑂(𝑛)，其中 𝑛 表示给定的数组的长度。

代码

class Solution:
    def longestArithmetic(self, nums: List[int]) -> int:
        n = len(nums)
        left = [1] * n
        right = [1] * n

        left[1] = 2
        for i in range(2, n):
            if nums[i - 1] * 2 == nums[i - 2] + nums[i]:
                left[i] = left[i - 1] + 1
            else:
                left[i] = 2
        right[n - 2] = 2
        for i in range(n - 3, -1, -1):
            if nums[i + 1] * 2 == nums[i] + nums[i + 2]:
                right[i] = right[i + 1] + 1
            else:
                right[i] = 2

  
        res = 3
        for i in range(0, n):
            if i + 1 < n:
                # 加入到左侧
                res = max(res, 1 + right[i + 1])
            if i > 0:
                # 加入到右侧
                res = max(res, 1 + left[i - 1])
            if i > 0 and i < n - 1:
                # 右边只取 1 个
                if right[i + 1] > 1:
                    dr = nums[i + 2] - nums[i + 1]
                    if nums[i + 1] - nums[i - 1] == 2 * dr:
                        res = max(res, 2 + right[i + 1])
                # 左边只取 1 个
                if left[i - 1] > 1:
                    dl = nums[i - 1] - nums[i - 2]
                    if nums[i + 1] - nums[i - 1] == 2 * dl:
                        res = max(res, 2 + left[i - 1])
                # 两边都取
                if left[i - 1] > 1 and right[i + 1] > 1:
                    dl = nums[i - 1] - nums[i - 2]
                    dr = nums[i + 2] - nums[i + 1]
                    if dl == dr and nums[i + 1] - nums[i - 1] == 2 * dl:
                        res = max(res, left[i - 1] + right[i + 1] + 1)

        return res

Q4. 添加一个点后可激活的最大点数

给你一个二维整数数组 points，其中 points[i] = [xi, yi] 表示第 i 个点的坐标。points 中的所有坐标都 互不相同。

如果一个点被激活，那么所有与该点具有相同 x 坐标或 y 坐标的点也会被激活。

激活会一直持续，直到没有额外的点可以被激活为止。

你可以 额外添加 一个不在 points 数组中的整数坐标点 (x, y) 。从这个新添加的点开始激活。

返回一个整数，表示可以被激活的最大点数，包括新添加的点。

示例 1：

输入： points = [[1,1],[1,2],[2,2]]

输出： 4

解释：

添加并激活一个点，例如 (1, 3)，会导致以下激活：

(1, 3) 与 (1, 1) 和 (1, 2) 具有相同的 x = 1，因此 (1, 1) 和 (1, 2) 被激活。
(1, 2) 与 (2, 2) 具有相同的 y = 2，因此 (2, 2) 被激活。

因此，被激活的点为 (1, 3), (1, 1), (1, 2), (2, 2)，总计 4 个点。可以证明这是最大激活点数。

示例 2：

输入： points = [[2,2],[1,1],[3,3]]

输出： 3

解释：

添加并激活一个点，例如 (1, 2)，会导致以下激活：

(1, 2) 与 (1, 1) 具有相同的 x = 1，因此 (1, 1) 被激活。
(1, 2) 与 (2, 2) 具有相同的 y = 2，因此 (2, 2) 被激活。

因此，被激活的点为 (1, 2), (1, 1), (2, 2)，总计 3 个点。可以证明这是最大激活点数。

示例 3：

输入： points = [[2,3],[2,2],[1,1],[4,5]]

输出： 4

解释：

添加并激活一个点，例如 (2, 1)，会导致以下激活：

(2, 1) 与 (2, 3) 和 (2, 2) 具有相同的 x = 2，因此 (2, 3) 和 (2, 2) 被激活。
(2, 1) 与 (1, 1) 具有相同的 y = 1，因此 (1, 1) 被激活。

因此，被激活的点为 (2, 1), (2, 3), (2, 2), (1, 1)，总计 4 个点。

提示：

1 <= points.length <= 105
points[i] = [xi, yi]
-109 <= xi, yi <= 109
points 中的坐标均 互不相同。

地址

https://leetcode.cn/contest/weekly-contest-493/problems/maximum-points-activated-with-one-addition/description/

题意

并查集，贪心

思路

题目本身算是比较简单的题目，核心在于并查集，所有存在相同的 $x$ 轴坐标的点归为同一个集合，所有存在相同 $y$ 轴坐标的点归为同一个集合，分类完成后，我们依次取出元素数组最多的两个集合，设起该两个集合中元素的数目为 $s_1,s_2$，此时可以得到：
- 如果只有一个集合，此时再加入一个新的点，此时可激活的最大数目即为 $n + 1$，其中 $n$ 表示所有点的数目；
- 如果大于一个集合，此时再加入一个新的点，可以将最大的两个集合同时激活，此时最大激活数目即为 $s+$
复杂度分析：

时间复杂度：$𝑂(𝑛log⁡ 𝑛)$，其中 𝑛 表示给定数组的长度。
空间复杂度：$𝑂(𝑛)$；

代码

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.sz = [1] * n
    
    def uni(self, x, y):
        rootx = self.find(x)
        rooty = self.find(y)
        if rootx != rooty:
            if self.rank[rootx] > self.rank[rooty]:
                self.parent[rooty] = rootx
                self.sz[rootx] += self.sz[rooty]
            elif self.rank[rootx] < self.rank[rooty]:
                self.parent[rootx] = rooty
                self.sz[rooty] += self.sz[rootx]
            else:
                self.parent[rooty] = rootx
                self.rank[rootx] += 1
                self.sz[rootx] += self.sz[rooty]
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def size(self, x):
        return self.sz[self.find(x)]
    
    def connect(self, x, y):
        return self.find(x) == self.find(y)


class Solution:
    def maxActivated(self, points):
        n = len(points)
        uf = UnionFind(n)
        
        cntx = {}
        cnty = {}
        
        # Union points that share the same x or y coordinate
        for i in range(n):
            x, y = points[i]
            
            if x in cntx:
                uf.uni(i, cntx[x])
            else:
                cntx[x] = i
            
            if y in cnty:
                uf.uni(i, cnty[y])
            else:
                cnty[y] = i
        
        cnt = {}
        for i in range(n):
            root = uf.find(i)
            cnt[root] = cnt.get(root, 0) + 1
        
        arr = list(cnt.values())
        arr.sort(reverse=True)
        
        if len(arr) == 1:
            return n + 1
        else:
            return arr[0] + arr[1] + 1

欢迎关注和打赏，感谢支持！

关注我的博客: https://mike-box.github.io/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 哪些奋斗者

力扣周赛

#力扣周赛赛 #题解

leetcode biweekly contest 493

http://example.com/1970/01/01/力扣周赛题解/225/

Author

Mike Meng

Posted on

January 1, 1970

Updated on

March 16, 2026

Licensed under

leetcode biweekly contest 183 Previous

kickstart 2021 round H Next