LeetCode周赛

周赛250803 Q4. 三段式数组 II 1. 题目大意 给定一个整数数组 nums，请你在所有三段式子数组中找出最大和。 三段式子数组定义为一个连续子数组 nums[l...r]，满足其中存在下标 l < p < q < r，使得这三个片段满足： ...

20250329LeetCode双周赛 & 20250330LeetCode周赛 T3 - 3500. 将数组分割为子数组的最小代价 1. 题目大意 给定两个等长的整数数组 nums 和 cost，以及一个整数 k。可以将 nums 分割为若干个连续的子数组，每个子数组的代价计算方式如下： ...

LeetCode 1215 周赛 当你思路对了，等最终调出来最多差两三分钟，但是代码有错误错一次就是五分钟。 T2 3387. 两天自由外汇交易后的最大货币数 1. 题目大意 你初始拥有 1 单位的指定货币 initialCurrency。在两天内，可以按照分别提供的汇率 rates1 和 rates2 进行任意次数的货币兑换。每种货币对的汇率可以反向兑换（汇率为 1/rate1/\text{rate}1/rate）。目标是经过两天后，使得最终持有的 initialCurrency 数量最大化。 ...

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，则在图中将两个节点相连。要求返回图中 连通块的数量，即所有相互连通的节点组成的独立子图的数量。 ...

LeetCode 11/24 11/25 周赛/双周赛 太长时间不参加周赛手生了很多，有时间就打，没时间刷熟 LeetCode Hot 100 + 面试题150 + LCR 双周赛 T3 3362. 零数组变换 III 题目大意 给定一个整数数组 nums 和二维数组 queries，每个操作 [li, ri] 可以将 nums[li] 到 nums[ri] 范围内的每个元素 最多减 1。 ...

周赛250922 小号第一次AK， 题比较简单。 3295. 举报垃圾信息 题目大意 给定两个字符串数组 message 和 bannedWords，你需要判断 message 是否属于“垃圾信息”。如果 message 中至少有两个单词出现在 bannedWords 中，则该数组被视为垃圾信息，返回 true；否则返回 false。 ...

周赛250915 时隔多日再才重新开启周赛。这场DP居多。 T2-3290. 最高乘法得分 题目大意： 给定两个数组 a 和 b，数组 a 长度为 4，数组 b 长度至少为 4。需要从 b 中选择 4 个递增下标 i0 < i1 < i2 < i3，计算 a[0] * b[i0] + a[1] * b[i1] + a[2] * b[i2] + a[3] * b[i3]，并返回最大得分。 ...

LeetCode双周赛132 & 周赛401(240608/09) 3181. 执行操作可获得的最大总奖励 II周赛第四题 题目大意 给定一个整数数组 rewardValues，长度为 n，表示不同位置的奖励值。初始时，总奖励 x 为 0，所有下标都是未标记的。可以执行以下操作任意次： ...

双周赛131(240525) AK的第二场😝， 第四题是用C++ 找网上模板，套用查找最长的连0串过的， 最后两分钟才过，很惊险。赛后发现做法并不优秀，但是不需要平衡树。 3161. 物块放置查询 题目大意： ...

周赛399(240526) 这场掉分了，第四题没思路，而且罚时太多了😥 第三题3164. 优质数对的总数 II 题目大意： 给定两个整数数组nums1和nums2，以及一个正整数k。如果nums1[i]可以被nums2[j]*k整除，则称数对(i, j)为优质数对。要求计算优质数对的总数。 ...

周赛250519 终于终于AK了一场😆 第四题100298. 到达第 K 级台阶的方案数 题目大意 给定一个非负整数 k，表示目标台阶的编号。虎老师从台阶 1 开始，通过一系列操作到达台阶 k。操作分为两种： ...

周赛20240505 第四题 100288. 使数组中所有元素相等的最小开销 题目大意：给定一个整数数组 nums 和两个整数 cost1 和 cost2，可以执行两种操作来使数组中所有元素相等：1. 选择某个元素增加1，开销为cost1；2. 选择两个不同的元素同时增加1，开销为cost2。目标是使数组中所有元素相等，返回需要的最小开销之和。 ...

双周赛20230427 第三/四题3130. 找出所有稳定的二进制数组 II 题目大意：给定三个正整数 zero、one 和 limit，定义一个二进制数组 arr，要求满足以下条件：数组中 0 出现的次数为 zero，1 出现的次数为 one，并且数组中每个长度超过 limit 的子数组都同时包含 0 和 1。求稳定二进制数组的总数目。 ...

周赛20230428 第四题134. 找出唯一性数组的中位数 题目大意：给定一个整数数组nums，唯一性数组是一个按元素从小到大排序的数组，包含了nums的所有非空子数组中不同元素的个数。要求返回nums唯一性数组的中位数，即有序唯一性数组的中间元素。 ...

力扣周赛394(20240421) 第三题100290. 使矩阵满足条件的最少操作次数 题目大意：给定一个大小为 m x n 的二维矩形 grid，每次操作可以将任意格子的值修改为任意非负整数。完成所有操作后，需要确保每个格子 grid[i][j] 的值满足以下条件：如果下面相邻格子存在的话，它们的值相等；如果右边相邻格子存在的话，它们的值不相等。返回需要的最少操作次数。 记忆化 实现思路：首先，统计每一列中各个数字的出现次数。然后，使用动态规划的方法，定义函数dfs(i, pre)，表示处理到第i列时，前一列的值为pre时的最大操作次数。在dfs中，对于当前列的每个数字，考虑是否修改当前列的值，然后递归处理下一列。利用缓存来避免重复计算。最后返回总的操作次数。 class Solution: # 如果你想不出来，1、你不知道这个知识点 2、 你知道这个知识点但是方向错了 def minimumOperations(self, g: List[List[int]]) -> int: n, m = len(g), len(g[0]) cnt = [[0]*10 for _ in range(m)] for row in g: for k, v in enumerate(row): cnt[k][v]+=1 @cache def dfs(i, pre): if i<0: return 0 res = 0 for v in range(10): if v!=pre: res = max(res, dfs(i-1, v) + cnt[i][v]) return res return m*n - dfs(m-1, -1) 递推 实现思路：首先，对每一列进行遍历，并统计每列中每个数字的出现次数。然后，通过动态规划的方法，使用两个变量f0和f1分别表示当前列处理时，前一列最大能保留的个数和次大能够保留的个数。接着，通过遍历每列中的每个数字，计算当前列的最大操作次数，并更新f0和f1。最后返回总的操作次数。 class Solution: def minimumOperations(self, grid: List[List[int]]) -> int: n, m = len(grid), len(grid[0]) f0, f1, pre = 0, 0, -1 for col in zip(*grid): mx, mx2, x = f0, f1, -1 for v, c in Counter(col).items(): res = (f0 if v!=pre else f1) + c if res > mx: mx, mx2, x = res, mx, v elif res > mx2: mx2 = res f0, f1, pre = mx, mx2, x return m*n - f0 第四题100276. 最短路径中的边 题目大意：给定一个包含n个节点的无向带权图，节点编号从0到n-1，总共有m条边。对于节点0为出发点，节点n-1为结束点的所有最短路，需要返回一个长度为m的布尔数组，如果edges[i]至少在其中一条最短路上，则answer[i]为true，否则为false。 ...