LeetCode

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

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

每日一题（202502） 0201 81. 搜索旋转排序数组 II 题目大意 给定一个旋转排序数组 nums 和一个目标值 target，判断目标值是否存在于数组中。需要尽可能减少操作步骤。 解题思路 旋转数组特点：旋转后数组分为两部分，其中一部分是有序的。 使用二分查找： 判断左半部分是否有序，如果有序，判断目标值是否在这部分。 否则，判断右半部分是否有序，并进行类似操作。 处理重复元素：如果 nums[left] == nums[mid] == nums[right]，无法确定哪部分有序，直接移动指针。 代码实现 class Solution: def search(self, nums: List[int], target: int) -> bool: if not nums: return False n = len(nums) if n == 1: return nums[0] == target l, r = 0, n - 1 while l <= r: mid = l + r >> 1 if nums[mid] == target: return True if nums[l] == nums[mid] and nums[mid] == nums[r]: l += 1 r -= 1 elif nums[l] <= nums[mid]: if nums[l] <= target < nums[mid]: r = mid - 1 else: l = mid + 1 else: if nums[mid] < target <= nums[n - 1]: l = mid + 1 else: r = mid - 1 return False 0202 MarsCode 每日一题 红色格子染色方案数计算 1. 题目大意 有一个长度为 n 的格子，一部分已染红，剩余格子未染色。通过特定的规则（红色格子可以染色左右邻居），我们需要计算将所有格子染红的不同染色顺序。最终返回结果对 10^9 + 7 取模。 ...

每日一题（202501） 0124 2944. 购买水果需要的最少金币数 1. 题目大意 给定一个整数数组 prices，其中 prices[i] 表示购买第 i 个水果所需的金币数。每购买一个水果后，可以根据一定的规则免费获得后续水果。规则是：购买第 i 个水果后，可以免费获得下标在 [i+1, i+i] 范围内的水果。你的目标是通过选择购买一些水果，最小化总花费，同时确保获得所有水果。 ...

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 Hot 100 精练🥸(2) 记忆中的东西一定会消退，真正留下的才是学到的，一定要及时回顾。 215. 数组中的第K个最大元素 题目大意： 给定一个整数数组 nums 和一个整数 k，要求返回数组中排序后的第 k 个最大的元素。你必须设计一个时间复杂度为 O(n) 的算法来解决此问题。 ...

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。目标是使数组中所有元素相等，返回需要的最小开销之和。 ...