LeetCode Hot 100

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 Hot 100 精练🥸(1) 记忆中的东西一定会消退，真正留下的才是学到的，一定要及时回顾。 题目表 (序号) 标题 (1) 160. 相交链表 (2) 236. 二叉树的最近公共祖先 (3) 234. 回文链表 (4) 739. 每日温度 (5) 226. 翻转二叉树 (6) 221. 最大正方形 (7) 215. 数组中的第K个最大元素 (8) 208. 实现 Trie (前缀树) (9) 207. 课程表 (10) 206. 反转链表 (11) 200. 岛屿数量 (12) 198. 打家劫舍 (13) 169. 多数元素 (14) 238. 除自身以外数组的乘积 (15) 155. 最小栈 (16) 152. 乘积最大子数组 (17) 148. 排序链表 (18) 146. LRU 缓存 (19) 142. 环形链表 II (20) 141. 环形链表 (21) 139. 单词拆分 (22) 136. 只出现一次的数字 (23) 647. 回文子串 (24) 128. 最长连续序列 (25) 124. 二叉树中的最大路径和 (26) 322. 零钱兑换 (27) 494. 目标和 (28) 461. 汉明距离 (29) 448. 找到所有数组中消失的数字 (30) 438. 找到字符串中所有字母异位词 (31) 437. 路径总和 III (32) 416. 分割等和子集 (33) 406. 根据身高重建队列 (34) 399. 除法求值 (35) 394. 字符串解码 (36) 347. 前 K 个高频元素 (37) 338. 比特位计数 (38) 337. 打家劫舍 III (39) 121. 买卖股票的最佳时机 (40) 312. 戳气球 (41) 309. 买卖股票的最佳时机含冷冻期 (42) 301. 删除无效的括号 (43) 300. 最长递增子序列 (44) 297. 二叉树的序列化与反序列化 (45) 287. 寻找重复数 (46) 283. 移动零 (47) 279. 完全平方数 (48) 253. 会议室 II (49) 240. 搜索二维矩阵 II (50) 239. 滑动窗口最大值 (51) 22. 括号生成 (52) 49. 字母异位词分组 (53) 48. 旋转图像 (54) 46. 全排列 (55) 42. 接雨水 (56) 39. 组合总和 (57) 543. 二叉树的直径 (58) 34. 在排序数组中查找元素的第一个和最后一个位置 (59) 33. 搜索旋转排序数组 (60) 32. 最长有效括号 (61) 31. 下一个排列 (62) 538. 把二叉搜索树转换为累加树 (63) 23. 合并 K 个升序链表 (64) 560. 和为 K 的子数组 (65) 21. 合并两个有序链表 (66) 20. 有效的括号 (67) 19. 删除链表的倒数第 N 个结点 (68) 17. 电话号码的字母组合 (69) 15. 三数之和 (70) 11. 盛最多水的容器 (71) 10. 正则表达式匹配 (72) 5. 最长回文子串 (73) 4. 寻找两个正序数组的中位数 (74) 3. 无重复字符的最长子串 (75) 2. 两数相加 (76) 79. 单词搜索 (77) 114. 二叉树展开为链表 (78) 621. 任务调度器 (79) 617. 合并二叉树 (80) 105. 从前序与中序遍历序列构造二叉树 (81) 104. 二叉树的最大深度 (82) 102. 二叉树的层序遍历 (83) 101. 对称二叉树 (84) 98. 验证二叉搜索树 (85) 96. 不同的二叉搜索树 (86) 94. 二叉树的中序遍历 (87) 85. 最大矩形 (88) 84. 柱状图中最大的矩形 (89) 1. 两数之和 (90) 78. 子集 (91) 76. 最小覆盖子串 (92) 75. 颜色分类 (93) 72. 编辑距离 (94) 70. 爬楼梯 (95) 581. 最短无序连续子数组 (96) 64. 最小路径和 (97) 62. 不同路径 (98) 56. 合并区间 (99) 55. 跳跃游戏 (100) 53. 最大子数组和 (1)160. 相交链表 题目大意： ...