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) 记忆中的东西一定会消退，真正留下的才是学到的，一定要及时回顾。 (21)139. 单词拆分 1、题目大意 给定字符串 s 和单词字典 wordDict，判断是否能用字典中的单词（可重复使用、无需全部使用）按顺序拼接得到 s。 ...

LeetCode Hot 100 精练🥸(2) 记忆中的东西一定会消退，真正留下的才是学到的，一定要及时回顾。 (41) 309. 买卖股票的最佳时机含冷冻期 class Solution: def maxProfit(self, prices: List[int]) -> int: n = len(prices) prices = [0] + prices f = [[-inf] * 3 for _ in range(n + 2)] # f[i][j] 第i天 距离上次卖出后第j天 f[1][2] = 0 # 入口，合法的情况 for i in range(1, n + 1): f[i][0] = max(f[i - 1][0], f[i][2] - prices[i]) # 第i天持有 f[i][1] = f[i - 1][0] + prices[i] # 今天买入，进入冷冻期 f[i + 1][2] = max(f[i - 1][1], f[i][2]) # 明天能达到非冷冻期的状态 return max(f[n][1], f[n + 1][2]) # 买股票后第一天，买股票后第大于等于2天 func maxProfit(prices []int) int { n := len(prices) f := make([][]int, n+2) inf := 0x3f3f3f3f for i := 0; i <= n+1; i += 1 { f[i] = make([]int, 3) for j := 0; j < 3; j += 1 { f[i][j] = -inf } } f[1][2] = 0 for i, p := range prices { f[i+1][0] = max(f[i][0], f[i+1][2]-p) f[i+1][1] = f[i][0] + p f[i+2][2] = max(f[i+1][2], f[i][1]) } return max(f[n][1], f[n+1][2]) } func max(a, b int) int { if a > b { return a } return b } (42)301. 删除无效的括号 class Solution: def removeInvalidParentheses(self, s: str) -> List[str]: res = [] def check(st): cnt = 0 for c in st: if c == "(": cnt += 1 elif c == ")": if cnt == 0: return False cnt -= 1 return cnt == 0 cur = set([s]) while True: for st in cur: if check(st): res.append(st) if len(res): break nxt = set() for st in cur: for i in range(len(st)): if i > 0 and st[i] == st[i - 1]: continue if st[i] == "(" or st[i] == ")": nxt.add(st[:i] + st[i + 1 :]) cur = nxt return res (43)300. 最长递增子序列 class Solution: def lengthOfLIS(self, nums: List[int]) -> int: n = len(nums) f = [1] * (n + 1) for i in range(n): for j in range(i, n): if nums[j] > nums[i]: f[j] = max(f[j], f[i] + 1) return max(f) (44)297. 二叉树的序列化与反序列化 class Codec: def serialize(self, root): if not root: return "#" return ( str(root.val) + " " + self.serialize(root.left) + " " + self.serialize(root.right) ) def deserialize(self, data): self.s = data return self.DerWork() def DerWork(self): if len(self.s) == 0: return None try: idx = self.s.index(" ") except: idx = -1 node = self.s if idx == -1 else self.s[:idx] self.s = "" if idx == -1 else self.s[idx + 1 :] if node == "#": return None t = TreeNode(int(node)) t.left = self.DerWork() t.right = self.DerWork() return t (45)287. 寻找重复数 class Solution: def findDuplicate(self, nums: List[int]) -> int: l, r = 0, len(nums) - 1 while l < r: mid = l + r >> 1 s = 0 for num in nums: if num > mid and num <= r: s += 1 if s > r - mid: l = mid + 1 else: r = mid return l (46)283. 移动零 class Solution: def moveZeroes(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ i, j = 0, 0 while j < len(nums): if nums[j]: if i != j: nums[i], nums[j] = nums[j], nums[i] i += 1 j += 1 (47)279. 完全平方数 class Solution: def numSquares(self, n: int) -> int: ls = [] i = 1 while True: if i**2 > n: break ls.append(i**2) i += 1 l = len(ls) f = [0] + [inf] * n for i in range(l): for j in range(ls[i], n + 1): f[j] = min(f[j], f[j - ls[i]] + 1) return f[n] (48)会议室 II class Solution: """ @param intervals: an array of meeting time intervals @return: the minimum number of conference rooms required """ def min_meeting_rooms(self, intervals: List[Interval]) -> int: # Write your code here d = defaultdict(int) #diff差分数组 for inter in intervals: s, e = inter.start, inter.end d[s] += 1 d[e] -= 1 s, res = 0, 0 for k, v in sorted(d.items()): s += v res = max(res, s) return res (49)240. 搜索二维矩阵 II class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: m, n = len(matrix), len(matrix[0]) i, j = 0, n - 1 while i < m and j >= 0: if matrix[i][j] == target: return True if matrix[i][j] > target: j -= 1 elif matrix[i][j] < target: i += 1 return False (50)239. 滑动窗口最大值 class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: n = len(nums) q = deque() res = [] for i in range(n): while q and i - q[0] + 1 > k: q.popleft() while q and nums[q[-1]] <= nums[i]: q.pop() q.append(i) if i + 1 >= k: res.append(nums[q[0]]) return res (51)22. 括号生成 class Solution: def generateParenthesis(self, n: int) -> List[str]: res = [] ls = [] n *= 2 def dfs(i, l, r): if l > n // 2 or r > n // 2: return if i == n and l == r: res.append("".join(ls)) return ls.append("(") dfs(i + 1, l + 1, r) ls.pop() if r < l: ls.append(")") dfs(i + 1, l, r + 1) ls.pop() dfs(0, 0, 0) return res (52)49. 字母异位词分组 (53)48. 旋转图像 (54)46. 全排列 (55)42. 接雨水 (56)39. 组合总和 (57)543. 二叉树的直径 (58)34. 在排序数组中查找元素的第一个和最后一个位置 (59)33. 搜索旋转排序数组 (60)32. 最长有效括号 class Solution: """ @param intervals: an array of meeting time intervals @return: the minimum number of conference rooms required """ def min_meeting_rooms(self, intervals: List[Interval]) -> int: # Write your code here d = defaultdict(int) #diff差分数组 for inter in intervals: s, e = inter.start, inter.end d[s] += 1 d[e] -= 1 s, res = 0, 0 for k, v in sorted(d.items()): s += v res = max(res, s) return res func MinMeetingRooms(intervals []*Interval) int { // 差分数组：key 是时间点，value 是变化量 diff := make(map[int]int) for _, inter := range intervals { diff[inter.Start]++ diff[inter.End]-- } // 把时间点取出来排序 times := make([]int, 0, len(diff)) for t := range diff { times = append(times, t) } sort.Ints(times) cur, res := 0, 0 for _, t := range times { cur += diff[t] if cur > res { res = cur } } return res } 11. 盛最多水的容器 题目大意：给定一个长度为n的整数数组height，数组中的每个元素代表一条垂直线的高度。找出其中的两条线，使得它们与x轴构成的容器可以容纳最多的水。 ...

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。操作分为两种： ...