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轴构成的容器可以容纳最多的水。
...