LeetCode Hot 100 精练🥸(3)
记忆中的东西一定会消退，真正留下的才是学到的，一定要及时回顾。
(41) 309. 买卖股票的最佳时机含冷冻期
给定一个整数数组prices，其中第 prices[i] 表示第 *i* 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
- 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
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. 删除无效的括号
题目大意：
给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。
回溯
实现思路：
-
统计无效括号数量：
- 首先遍历字符串s，统计左括号和右括号的数量l和r，其中l表示未匹配的左括号数量，r表示需要删除的右括号数量。
-
回溯算法：
- 编写回溯算法来尝试删除不同位置的括号，使得字符串有效。
- 回溯过程中需要注意以下情况：
- 已经匹配的括号数量ln和rn，以及当前位置i。
- 遍历字符串s的每个字符，当遇到重复的字符时跳过，以避免重复结果。
- 如果当前字符为左括号并且ln不为0，则递归调用删除当前左括号的情况，ln减一，否则继续。
- 如果当前字符为右括号并且rn不为0，则递归调用删除当前右括号的情况，rn减一，否则继续。
-
检查字符串有效性：
- 编写辅助函数
check来检查字符串是否有效，即左右括号数量是否匹配。
- 编写辅助函数
-
返回结果：
- 将所有有效的字符串结果添加到结果列表ret中，并返回。
class Solution:
def removeInvalidParentheses(self, s: str) -> List[str]:
l, r = 0, 0
ret = []
n = len(s)
for c in s:
if c=='(':
l+=1
elif c==')':
if l==0:
r+=1
else:
l-=1
def check(st):
cnt=0
for c in st:
if c=='(':
cnt+=1
elif c==')':
cnt-=1
if cnt<0:
return False
return (cnt==0)
def backtrace(st, start, ln, rn):
if ln==0 and rn==0 and check(st):
ret.append(st[:])
return
for i in range(start, len(st)):
if i>start and st[i]==st[i-1]:
continue
if ln+rn>n-1-i+1:
break
if ln and st[i]=='(':
backtrace(st[:i]+st[i+1:], i, ln-1, rn)
elif rn and st[i]==')':
backtrace(st[:i]+st[i+1:], i, ln, rn-1)
backtrace(s, 0, l, r)
return ret
广搜
这个实现使用了广度优先搜索（BFS）的思路来解决问题。
-
BFS搜索：
- 使用一个集合
cur来存储当前层的所有字符串，初始时将输入的字符串s加入集合cur中。 - 在每一轮循环中，遍历当前集合
cur中的所有字符串，如果其中有字符串是有效的，则将其加入结果列表ret中。 - 如果结果列表
ret不为空，则跳出循环，表示已经找到了所有有效的字符串。 - 如果结果列表
ret为空，则需要继续进行下一轮搜索，将当前集合cur中的每个字符串，通过删除一个括号的方式，生成所有可能的下一层字符串，加入到集合nxt中。 - 更新当前集合
cur为nxt，继续下一轮搜索。
- 使用一个集合
-
检查字符串有效性：
- 定义一个辅助函数
check，用于检查字符串是否有效。 - 遍历字符串中的每个字符，遇到左括号时增加计数器
cnt，遇到右括号时如果cnt为0则返回False（表示右括号没有匹配的左括号），否则减少cnt。 - 最终判断
cnt是否为0，如果为0表示字符串有效。
- 定义一个辅助函数
-
返回结果：
- 返回结果列表
ret，其中存储了所有有效的字符串。
- 返回结果列表
class Solution:
def removeInvalidParentheses(self, s: str) -> List[str]:
ret = []
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):
ret.append(st)
if len(ret):
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 ret
(43)300. 最长递增子序列
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
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. 二叉树的序列化与反序列化
不止第一次遇到了。
题目大意：序列化是将一个数据结构或对象转换为连续的比特位的操作，从而可以存储在文件或内存中，并且通过网络传输到另一个计算机环境中。本题要求设计一个算法来实现二叉树的序列化和反序列化，即将二叉树转换为字符串并将字符串转换回原始的二叉树结构。
实现思路：
- 序列化：使用递归将二叉树转换为字符串，根节点值与左右子树序列化结果之间使用空格分隔，空节点用 ‘#’ 表示。
- 反序列化：使用递归将字符串转换为二叉树。首先定义一个辅助函数 DerWork()，用于递归构建二叉树。在该函数中，按照前序遍历的顺序，依次提取字符串中的节点值，并根据节点值构建二叉树节点。如果节点值为 ‘#’，表示空节点，返回 None。否则，创建节点并递归构建其左右子树。
- 在反序列化过程中，使用一个全局变量 self.s 来记录当前待处理的字符串，每次递归处理后，将字符串中已经处理过的部分剔除，继续处理剩余部分。
- 最终返回根节点即可。
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. 寻找重复数
给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
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. 移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
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
func moveZeroes(nums []int) {
i, j := 0, 0
for j < len(nums) {
if nums[j] != 0 {
if i != j {
nums[i], nums[j] = nums[j], nums[i]
}
i++
}
j++
}
}
(47)279. 完全平方数
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
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
描述
给定一系列的会议时间间隔intervals，包括起始和结束时间[[s1,e1],[s2,e2],...] (si < ei)，找到所需的最小的会议室数量。
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
}
(49)240. 搜索二维矩阵 II
编写一个高效的算法来搜索 *m* x *n* 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
- 每行的元素从左到右升序排列。
- 每列的元素从上到下升序排列。
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. 滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
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. 括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
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. 字母异位词分组
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
d = defaultdict(list)
for s in strs:
sort_s = sorted(list(s))
d["".join(sort_s)].append(s)
return list(d.values())
(53)48. 旋转图像
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在** 原地** 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
n = len(matrix)
newmat = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
newmat[i][j] = matrix[n - 1 - j][i]
matrix[:] = newmat
(54)46. 全排列
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
vis = [False] * (n)
res, ls = [], []
def dfs(i):
if len(ls) == n:
res.append(ls[:])
return
for j in range(n):
if not vis[j]:
vis[j] = True
ls.append(nums[j])
dfs(j + 1)
ls.pop()
vis[j] = False
dfs(1)
return res
(55)42. 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
class Solution:
def trap(self, height: List[int]) -> int:
res = 0
stk = []
for i, h in enumerate(height):
while stk and height[stk[-1]] < h:
cur = stk.pop()
if not stk:
break
left = stk[-1]
curW = i - 1 - left
curH = min(h, height[left]) - height[cur]
res += curH * curW
stk.append(i)
return res
(56)39. 组合总和
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
n = len(candidates)
candidates.sort()
res, ls, = [], []
def dfs(i, s):
if s >= target:
if s == target:
res.append(ls[:])
return
for j in range(i, n):
ls.append(candidates[j])
dfs(j, s + candidates[j])
ls.pop()
dfs(0, 0)
return res
(57)543. 二叉树的直径
给你一棵二叉树的根节点，返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
res = 0
def dfs(root):
nonlocal res
if not root:
return 0
ls = dfs(root.left)
rs = dfs(root.right)
res = max(res, ls + rs)
return max(ls, rs) + 1
dfs(root)
return res
(58)34. 在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def bs(nums, target):
l, r = 0, len(nums) - 1
while l < r:
mid = l + r >> 1
if nums[mid] >= target:
r = mid
else:
l = mid + 1
return l
if not nums:
return [-1, -1]
left = bs(nums, target)
if nums[left] != target:
return [-1, -1]
right = bs(nums, target + 1)
if nums[right] != target:
right -= 1
return [left, right]
(59)33. 搜索旋转排序数组
题目大意：
给定一个按升序排列的整数数组 nums，数组中的值互不相同。该数组经过未知的某个下标旋转，即原本排在数组开头的一部分元素被移动到数组末尾。给定一个目标值 target，如果该目标值存在于旋转后的数组中，则返回其下标，否则返回 -1。要求设计一个时间复杂度为 O(log n) 的算法解决此问题。
实现思路：
- 使用二分查找算法来解决此问题，以满足 O(log n) 的时间复杂度要求。
- 初始化左右指针
l和r分别指向数组的首尾元素。 - 在循环中，计算中间位置
mid，判断nums[mid]是否等于目标值target，若是则直接返回mid。 - 若
nums[0] <= nums[mid]，说明左半段是有序的，此时判断目标值是否在左半段范围内，若是则将右指针移到mid-1，否则将左指针移到mid+1。 - 若
nums[0] > nums[mid]，说明右半段是有序的，此时判断目标值是否在右半段范围内，若是则将左指针移到mid+1，否则将右指针移到mid-1。 - 若循环结束仍未找到目标值，则返回 -1。
class Solution:
def search(self, nums: List[int], target: int) -> int:
if not nums:
return -1
n = len(nums)
l, r = 0, n - 1
while l <= r:
mid = l + r >> 1
if nums[mid] == target:
return mid
if nums[0] <= nums[mid]:
if nums[0] <= 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 -1
(60)32. 最长有效括号
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号 子串 的长度。
左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如 "(()())"。
class Solution:
def longestValidParentheses(self, s: str) -> int:
n = len(s)
stk = [-1]
res = 0
for i in range(n):
if s[i] == "(":
stk.append(i)
else:
stk.pop()
if stk:
res = max(res, i - stk[-1])
else:
stk.append(i)
return res