90
给一个括号序列，问最长的一串合法括号。
合法的一串括号一定是连续的，而且每个右括号一定是和最近的左括号配对。
拿栈存左括号，先扫一遍把所有配对的左右括号标记，再扫一遍找最长的一串标记。
class Solution: def longestValidParentheses(self, s: str) -> int: stack = [] n = len(s) v = [False] * n
for i in range(n): if s[i] == '(': stack.append(i) elif s[i] == ')' and len(stack): left = stack.pop() v[left] = v[i] = True
ans, cnt, i = 0, 0, 0 while i < n: if v[i]: cnt += 1 ans = max(ans, cnt) else: cnt = 0 i += 1
return ans89
能否把一个数组里的数字分成两个集合，每个集合的和相等。
先判奇偶。
问题变成能否从n个数里选某些数使得和为m，是背包问题。
class Solution: def canPartition(self, nums: List[int]) -> bool: s = sum(nums) if s & 1: return False
n = len(nums)
@cache def dfs(i, j) -> bool: if i == 0: return j == 0 or j == nums[0] if j < 0: return False return dfs(i - 1, j) or dfs(i - 1, j - nums[i])
return dfs(n - 1, s / 2)88
乘积最大子数组。
因为这个数组里有负数，所以要同时维护只考虑前i个数且取第i个数的最大值和最小值，可能负负得正。
class Solution: def maxProduct(self, nums: List[int]) -> int: n = len(nums) f = [float('-inf')] * n g = [float('inf')] * n
f[0] = nums[0] g[0] = nums[0] for i in range(1, n): f[i] = max(f[i - 1] * nums[i], g[i - 1] * nums[i], nums[i], f[i]) g[i] = min(g[i - 1] * nums[i], f[i - 1] * nums[i], nums[i], g[i])
return max(f)87
最长上升子序列。
最重要的是理解O(nlogn)做法的思想。
先看代码实际意味着做的事情。
想象数组是一副扑克牌，现在按以下规则分成若干堆牌堆：
为当前牌找到第一个牌堆顶部牌大于等于它的堆，放上去。
如果没找到，就以这个牌新开一个堆。
最后牌堆的数量就是LIS长度。
为什么两者等价呢？
每个牌堆，都精确对应了一个“某个长度的上升子序列”的最好结尾。
第k个牌堆顶部的牌，是目前为止，能构成"长度为k的LIS"的最小可能结尾数字。
具体例子，考虑[3, 1, 5]。
-
新建第一个堆，堆顶是
3，意味着想构成长度为1的子序列，末尾最小可以是3。 -
1 < 3，想构成长度为1的子序列，末尾最小可以是1。1比3更有潜力。 -
5比前两个数都大，无法去优化长度为1的子序列的末尾，但它带来了长度为2的子序列的想象空间，新开一个堆。
核心比喻抗遗忘：转化分牌堆，维护一个有“潜力”的结构。
class Solution: def lengthOfLIS(self, nums: List[int]) -> int: d = [] n = len(nums)
for num in nums: l, r = 0, len(d) while l < r: mid = (l + r) >> 1; if num <= d[mid]: r = mid else: l = mid + 1
if l < len(d): d[l] = num else: d.append(num)
return len(d)86
单词拆分。给定字符串和单词列表，问字符串能不能由列表内若干单词组成。
如果这里没用set，用了dict的话，不要写mp[s[j:i]]，要写s[j:i] in mp。
Python对于没有的Key会直接抛一个异常。
class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: n = len(s) dp = [False] * (n + 1) word_set = set(wordDict)
dp[0] = True for i in range(1, n + 1): for j in range(0, i): dp[i] = dp[i] or (dp[j] and s[j:i] in word_set)
return dp[n]85
零钱兑换。问某一个总额能不能由若干固定面额的零钱凑出来，每种零钱有无数个。
记忆化搜索就完了。
class Solution: def coinChange(self, coins: List[int], amount: int) -> int:
@cache def dfs(remains) -> int: if remains < 0: return float("inf") if remains == 0: return 0
res = float("inf") for coin in coins: res = min(res, dfs(remains - coin) + 1) return res
res = dfs(amount) return res if res != float("inf") else -184
一个数最少能由几个完全平方数相加得到。
简单DP。
class Solution: def numSquares(self, n: int) -> int: squares = set()
i = 1 while i * i <= n: squares.add(i * i) i += 1
@cache def dfs(x) -> int: if x <= 0: return float("inf") if x in squares: return 1
res = float("inf") for square in squares: res = min(res, dfs(x - square) + 1) return res
return dfs(n)83
打家劫舍。
不能连着抢两家相邻的。简单DP。
class Solution: def rob(self, nums: List[int]) -> int: n = len(nums) dp = [[0] * 2 for _ in range(n)]
dp[0][0] = 0 dp[0][1] = nums[0]
for i in range(1, n): dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]) dp[i][1] = dp[i - 1][0] + nums[i]
return max(dp[n - 1][0], dp[n - 1][1])82
打印杨辉三角形。
简单DP。
class Solution: def generate(self, numRows: int) -> List[List[int]]: f = [[1] for _ in range(numRows)]
for i in range(1, numRows): for j in range(1, i + 1): f[i].append(f[i - 1][j - 1]) if j < i: f[i][j] += f[i - 1][j]
return f81
爬楼梯。
简单DP。
class Solution: def climbStairs(self, n: int) -> int: dp = [0] * (n + 1) dp[0] = dp[1] = 1
for i in range(2, n + 1): dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]