Solutions CS101

Appearance

第 438 场周赛-20250223 ​

中国时间：2025-02-23 10:30 1 小时 30 分

https://leetcode.cn/contest/weekly-contest-438/

3461.判断操作后字符串中的数字是否相等I ​

https://leetcode.cn/problems/check-if-digits-are-equal-in-string-after-operations-i/

给你一个由数字组成的字符串 s 。重复执行以下操作，直到字符串恰好包含 两个 数字：

  • 从第一个数字开始，对于 s 中的每一对连续数字，计算这两个数字的和 模 10。
  • 用计算得到的新数字依次替换 s 的每一个字符，并保持原本的顺序。

如果 s 最后剩下的两个数字 相同 ，返回 true 。否则，返回 false。

示例 1：

输入： s = "3902"

输出： true

解释：

  • 一开始，s = "3902"
  • 第一次操作：
    • (s[0] + s[1]) % 10 = (3 + 9) % 10 = 2
    • (s[1] + s[2]) % 10 = (9 + 0) % 10 = 9
    • (s[2] + s[3]) % 10 = (0 + 2) % 10 = 2
    • s 变为 "292"
  • 第二次操作：
    • (s[0] + s[1]) % 10 = (2 + 9) % 10 = 1
    • (s[1] + s[2]) % 10 = (9 + 2) % 10 = 1
    • s 变为 "11"
  • 由于 "11" 中的数字相同，输出为 true。

示例 2：

输入： s = "34789"

输出： false

解释：

  • 一开始，s = "34789"。
  • 第一次操作后，s = "7157"。
  • 第二次操作后，s = "862"。
  • 第三次操作后，s = "48"。
  • 由于 '4' != '8'，输出为 false。

提示：

  • 3 <= s.length <= 100
  • s 仅由数字组成。
python
class Solution:
    def hasSameDigits(self, s: str) -> bool:
        q = [int(i) for i in s]
        
        while len(q) > 1:
            if len(set(q)) == 1:  # 如果所有数字相同，直接返回True
                return True
            
            if len(q) == 2:
                return q[0] == q[1]
            
            new_q = []
            for i in range(len(q) - 1):
                tmp = (q[i] + q[i + 1]) % 10
                new_q.append(tmp)
            
            q = new_q
        
        return False

if __name__ == "__main__":
    sol = Solution()
    print(sol.hasSameDigits("3902"))  # True
    print(sol.hasSameDigits("34789")) # False

3462.提取至多K个元素的最大总和 ​

data structures, https://leetcode.cn/problems/maximum-sum-with-at-most-k-elements/

给你一个大小为 n x m 的二维矩阵 grid ，以及一个长度为 n 的整数数组 limits ，和一个整数 k 。你的目标是从矩阵 grid 中提取出 至多 k 个元素，并计算这些元素的最大总和，提取时需满足以下限制：

  • 从 grid 的第 i 行提取的元素数量不超过 limits[i] 。

返回最大总和。

示例 1：

输入：grid = [[1,2],[3,4]], limits = [1,2], k = 2

输出：7

解释：

  • 从第 2 行提取至多 2 个元素，取出 4 和 3 。
  • 至多提取 2 个元素时的最大总和 4 + 3 = 7 。

示例 2：

输入：grid = [[5,3,7],[8,2,6]], limits = [2,2], k = 3

输出：21

解释：

  • 从第 1 行提取至多 2 个元素，取出 7 。
  • 从第 2 行提取至多 2 个元素，取出 8 和 6 。
  • 至多提取 3 个元素时的最大总和 7 + 8 + 6 = 21 。

提示：

  • n == grid.length == limits.length
  • m == grid[i].length
  • 1 <= n, m <= 500
  • 0 <= grid[i][j] <= 10^5
  • 0 <= limits[i] <= m
  • 0 <= k <= min(n * m, sum(limits))
python
from typing import List
import heapq

class Solution:
    def maxSum(self, grid: List[List[int]], limits: List[int], k: int) -> int:
        hqs = []
        n = len(grid)
        for i in range(n):
            row = grid[i]
            limit = limits[i]
            largest_k = sorted(row, reverse=True)
            if limit < len(largest_k):
                largest_k = largest_k[:limit]
            hq = [-val for val in largest_k]
            heapq.heapify(hq)

            if hq:
                hqs.append(hq)

        print(hqs)
        sum_v = 0
        for i in range(k):
            max_v = float('-inf')
            max_idx = -1

            for j, hq in enumerate(hqs):
                if hq and -hq[0] > max_v:
                    max_v = -hq[0]
                    max_idx = j

            if max_idx != -1:
                sum_v += max_v
                heapq.heappop(hqs[max_idx])
                if not hqs[max_idx]:
                    del hqs[max_idx]

        return sum_v

if __name__ == "__main__":
    sol = Solution()
    #print(sol.maxSum([[1,2],[3,4]], [1,2], 2))
    #print(sol.maxSum([[5,3,7],[8,2,6]], [2,2], 3))
    #print(sol.maxSum([[3],[9],[1]], [1,0,0], 1))
    print(sol.maxSum([[5,3,7],[8,2,6]], [2,2], 3))

Q3.判断操作后字符串中的数字是否相等II ​

https://leetcode.cn/contest/weekly-contest-438/problems/check-if-digits-are-equal-in-string-after-operations-ii/

给你一个由数字组成的字符串 s 。重复执行以下操作，直到字符串恰好包含 两个 数字：

  • 从第一个数字开始，对于 s 中的每一对连续数字，计算这两个数字的和 模 10。
  • 用计算得到的新数字依次替换 s 的每一个字符，并保持原本的顺序。

如果 s 最后剩下的两个数字相同，则返回 true 。否则，返回 false。

示例 1：

输入： s = "3902"

输出： true

解释：

  • 一开始，s = "3902"
  • 第一次操作：
    • (s[0] + s[1]) % 10 = (3 + 9) % 10 = 2
    • (s[1] + s[2]) % 10 = (9 + 0) % 10 = 9
    • (s[2] + s[3]) % 10 = (0 + 2) % 10 = 2
    • s 变为 "292"
  • 第二次操作：
    • (s[0] + s[1]) % 10 = (2 + 9) % 10 = 1
    • (s[1] + s[2]) % 10 = (9 + 2) % 10 = 1
    • s 变为 "11"
  • 由于 "11" 中的数字相同，输出为 true。

示例 2：

输入： s = "34789"

输出： false

解释：

  • 一开始，s = "34789"。
  • 第一次操作后，s = "7157"。
  • 第二次操作后，s = "862"。
  • 第三次操作后，s = "48"。
  • 由于 '4' != '8'，输出为 false。

提示：

  • 3 <= s.length <= 10^5
  • s 仅由数字组成。

634/683超时，请优化

python
class Solution:
    def hasSameDigits(self, s: str) -> bool:
        q = [int(i) for i in s]

        while True:
            if len(set(q)) == 1:
                return True

            if len(q) == 2:
                return q[0] == q[1]

            q = [(q[i] + q[i + 1]) % 10 for i in range(len(q) - 1)]

        return False


if __name__ == "__main__":
    sol = Solution()
    #print(sol.hasSameDigits("3902"))  # True
    print(sol.hasSameDigits("34789"))  # False

Q4.正方形上的点之间的最大距离 ​

https://leetcode.cn/contest/weekly-contest-438/problems/maximize-the-distance-between-points-on-a-square/

给你一个整数 side，表示一个正方形的边长，正方形的四个角分别位于笛卡尔平面的 (0, 0) ，(0, side) ，(side, 0) 和 (side, side) 处。

同时给你一个 正整数 k 和一个二维整数数组 points，其中 points[i] = [xi, yi] 表示一个点在正方形边界上的坐标。

你需要从 points 中选择 k 个元素，使得任意两个点之间的 最小 曼哈顿距离 最大化 。

返回选定的 k 个点之间的 最小 曼哈顿距离的 最大 可能值。

两个点 (xi, yi) 和 (xj, yj) 之间的曼哈顿距离为 |xi - xj| + |yi - yj|。

示例 1：

输入： side = 2, points = [[0,2],[2,0],[2,2],[0,0]], k = 4

输出： 2

解释：

img

选择所有四个点。

示例 2：

输入： side = 2, points = [[0,0],[1,2],[2,0],[2,2],[2,1]], k = 4

输出： 1

解释：

img

选择点 (0, 0) ，(2, 0) ，(2, 2) 和 (2, 1)。

示例 3：

输入： side = 2, points = [[0,0],[0,1],[0,2],[1,2],[2,0],[2,2],[2,1]], k = 5

输出： 1

解释：

img

选择点 (0, 0) ，(0, 1) ，(0, 2) ，(1, 2) 和 (2, 2)。

提示：

  • 1 <= side <= 10^9
  • 4 <= points.length <= min(4 * side, 15 * 10^3)
  • points[i] == [xi, yi]
  • 输入产生方式如下：
    • points[i] 位于正方形的边界上。
    • 所有 points[i] 都 互不相同 。
  • 4 <= k <= min(25, points.length)
python