贪心算法
买卖股票的最佳时机
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
from typing import List
class Solution:
def maxProfit(self, prices: List[int]) -> int:
"""
使用一次遍历找到最大利润
思路：
- 遍历数组，记录遍历过的最低价格
- 对于每个价格，计算卖出能获得的利润
- 更新最大利润
- 时间 O(n)，空间 O(1)
"""
min_price = float('inf') # 记录最低价格
max_profit = 0 # 记录最大利润
for price in prices:
# 更新最低价格
if price < min_price:
min_price = price
# 计算当前价格卖出的利润，更新最大利润
profit = price - min_price
if profit > max_profit:
max_profit = profit
return max_profit
# 测试用例
assert Solution().maxProfit([7, 1, 5, 3, 6, 4]) == 5
assert Solution().maxProfit([7, 6, 4, 3, 1]) == 0
assert Solution().maxProfit([2, 4, 1]) == 2
assert Solution().maxProfit([3, 2, 6, 1, 4]) == 5
# 手动推导 [7,1,5,3,6,4]：
# min_price=7, max_profit=0
# price=1: 1<7，更新 min_price=1，profit=0，max_profit=0
# price=5: 5>1，profit=5-1=4，max_profit=4
# price=3: 3>1，profit=3-1=2，max_profit=4
# price=6: 6>1，profit=6-1=5，max_profit=5
# price=4: 4>1，profit=4-1=3，max_profit=5
# 结果：最大利润为 5（第2天买入，第5天卖出）
|
跳跃游戏
给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
from typing import List
class Solution:
def canJump(self, nums: List[int]) -> bool:
"""
使用贪心算法判断能否到达终点
思路：
- 维护一个变量 max_reach 表示当前能到达的最远位置
- 遍历数组，更新 max_reach = max(max_reach, i + nums[i])
- 如果 max_reach >= n-1，说明能到达终点
- 如果遍历过程中 i > max_reach，说明当前位置不可达，返回 False
- 时间 O(n)，空间 O(1)
"""
n = len(nums)
max_reach = 0 # 当前能到达的最远位置
for i in range(n):
# 如果当前位置不可达，返回 False
if i > max_reach:
return False
# 更新能到达的最远位置
max_reach = max(max_reach, i + nums[i])
# 如果已经能到达终点，直接返回 True
if max_reach >= n - 1:
return True
return True
# 测试用例
assert Solution().canJump([2, 3, 1, 1, 4]) == True
assert Solution().canJump([3, 2, 1, 0, 4]) == False
assert Solution().canJump([0]) == True
assert Solution().canJump([2, 0, 0]) == True
assert Solution().canJump([1, 2, 3]) == True
assert Solution().canJump([1, 0, 2]) == False
# 手动推导 [2,3,1,1,4]：
# i=0: max_reach = max(0, 0+2) = 2
# i=1: 1 <= 2（可达），max_reach = max(2, 1+3) = 4 >= 4（终点），返回 True
# 结果：True（可以到达终点）
# 手动推导 [3,2,1,0,4]：
# i=0: max_reach = max(0, 0+3) = 3
# i=1: 1 <= 3，max_reach = max(3, 1+2) = 3
# i=2: 2 <= 3，max_reach = max(3, 2+1) = 3
# i=3: 3 <= 3，max_reach = max(3, 3+0) = 3
# i=4: 4 > 3（不可达），返回 False
# 结果：False（无法到达终点）
|
跳跃游戏 II
给定一个长度为 n 的 0 索引整数数组 nums。初始位置在下标 0。
每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在索引 i 处，你可以跳转到任意 (i + j) 处：
0 <= j <= nums[i] 且
i + j < n
返回到达 n - 1 的最小跳跃次数。测试用例保证可以到达 n - 1。
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
题目保证可以到达 n - 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
from typing import List
class Solution:
def jump(self, nums: List[int]) -> int:
"""
使用贪心算法找到最小跳跃次数
思路：
- 每次在当前可达范围内，选择能跳到最远位置的那一步
- 维护三个变量：
- end：当前跳跃的边界
- max_pos：当前范围内能跳到的最远位置
- steps：跳跃次数
- 当 i 到达 end 时，需要再跳一次，steps++，end = max_pos
- 时间 O(n)，空间 O(1)
"""
n = len(nums)
if n == 1:
return 0
max_pos = 0 # 当前能跳到的最远位置
end = 0 # 当前跳跃的边界
steps = 0 # 跳跃次数
for i in range(n - 1): # 不需要遍历到最后一个位置
# 更新能跳到的最远位置
max_pos = max(max_pos, i + nums[i])
# 到达当前跳跃的边界，需要再跳一次
if i == end:
steps += 1
end = max_pos
# 如果已经能跳到最后，提前返回
if end >= n - 1:
return steps
return steps
# 测试用例
assert Solution().jump([2, 3, 1, 1, 4]) == 2
assert Solution().jump([2, 3, 0, 1, 4]) == 2
assert Solution().jump([1, 2, 1, 1, 1]) == 3
assert Solution().jump([0]) == 0
assert Solution().jump([2, 1]) == 1
# 手动推导 [2,3,1,1,4]：
# i=0: max_pos = max(0, 0+2) = 2, end=0, i==end，steps=1, end=2
# i=1: max_pos = max(2, 1+3) = 4 >= 4(终点), end=2, i==end，steps=2, end=4
# end >= n-1，返回 2
# 结果：2 步
# 手动推导 [2,3,0,1,4]：
# i=0: max_pos = max(0, 0+2) = 2, end=0, i==end，steps=1, end=2
# i=1: max_pos = max(2, 1+3) = 4, end=2, i==end，steps=2, end=4 >= 4(终点)
# 返回 2
# 结果：2 步
|
划分字母区间
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 “ababcc” 能够被分为 [“abab”, “cc”]，但类似 [“aba”, “bcc”] 或 [“ab”, “ab”, “cc”] 的划分是非法的。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
输入：s = “ababcbacadefegdehijhklij”
输出：[9,7,8]
解释：
划分结果为 “ababcbaca”、“defegde”、“hijhklij” 。
每个字母最多出现在一个片段中。
像 “ababcbacadefegde”, “hijhklij” 这样的划分是错误的，因为划分的片段数较少。
s 仅由小写英文字母组成
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
|
from typing import List
class Solution:
def partitionLabels(self, s: str) -> List[int]:
"""
使用贪心算法划分字母区间
思路：
- 第一步：统计每个字符最后出现的位置
- 第二步：遍历字符串，维护当前片段的右边界
- 当遍历到当前片段的右边界时，说明可以划分子串
- 时间 O(n)，空间 O(1)（26个字母的固定空间）
"""
# 1. 统计每个字符最后出现的位置
last = [0] * 26
for i, ch in enumerate(s):
last[ord(ch) - ord('a')] = i
# 2. 遍历字符串，划分片段
result = []
start = 0 # 当前片段的起始位置
end = 0 # 当前片段的右边界
for i, ch in enumerate(s):
# 更新当前片段的右边界（取当前位置和该字符最远出现位置的较大值）
end = max(end, last[ord(ch) - ord('a')])
# 当遍历到当前片段的右边界时，划分子串
if i == end:
result.append(end - start + 1)
start = end + 1
return result
# 测试用例
assert Solution().partitionLabels("ababcbacadefegdehijhklij") == [9, 7, 8]
assert Solution().partitionLabels("eccbbbbdec") == [10]
assert Solution().partitionLabels("abcdef") == [1, 1, 1, 1, 1, 1]
assert Solution().partitionLabels("a") == [1]
assert Solution().partitionLabels("aaaaa") == [5]
# 手动推导 "ababcbacadefegdehijhklij"：
# 1. 统计每个字符最后出现的位置：
# a:14, b:8, c:9, d:15, e:18, f:16, g:17, h:19, i:22, j:23, k:20, l:21, j:22, ...
#
# 2. 遍历字符串：
# i=0, 'a': end=max(0,14)=14, i!=14
# i=1, 'b': end=max(14,8)=14, i!=14
# ...
# i=14, 'a': end=max(14,14)=14, i==14 -> 片段长度=15-0=15？不对...
#
# 重新推导：
# start=0
# i=0 'a': end=14
# i=1 'b': end=14
# i=2 'a': end=14
# i=3 'b': end=14
# i=4 'c': end=max(14,9)=14
# i=5 'b': end=14
# i=6 'a': end=14
# i=7 'c': end=max(14,9)=14
# i=8 'b': end=14
# i=9 'a': end=max(14,14)=14
# i=10 'd': end=max(14,15)=15
# ...
# i=14 'e': end=max(15,18)=18
# ...
# i=22 'i': end=max(20,22)=22
# i=23 'j': end=max(22,23)=23
# i=24 'h': end=max(23,19)=23
# ...
#
# 正确划分：
# 片段1: 索引0-8（"ababc baca"），长度=9
# 片段2: 索引9-15（"defegde"），长度=7
# 片段3: 索引16-23（"hijhklij"），长度=8
# 结果：[9, 7, 8]
|
动态规划
爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
from typing import List
class Solution:
def climbStairs(self, n: int) -> int:
"""
使用动态规划求解爬楼梯的方法数
思路：
- 到达第 i 阶的方法数 = 到达第 i-1 阶的方法数 + 到达第 i-2 阶的方法数
- 因为可以从 i-1 阶走一步上来，或从 i-2 阶走两步上来
- dp[i] = dp[i-1] + dp[i-2]，即斐波那契数列
- 初始值：dp[1] = 1，dp[2] = 2
- 空间优化：只需要保存前两个状态
- 时间 O(n)，空间 O(1)
"""
if n == 1:
return 1
if n == 2:
return 2
# dp[i] 表示到达第 i 阶的方法数
prev1 = 2 # dp[i-1]
prev2 = 1 # dp[i-2]
for i in range(3, n + 1):
curr = prev1 + prev2 # dp[i] = dp[i-1] + dp[i-2]
prev2 = prev1
prev1 = curr
return prev1
# 测试用例
assert Solution().climbStairs(1) == 1
assert Solution().climbStairs(2) == 2
assert Solution().climbStairs(3) == 3
assert Solution().climbStairs(4) == 5
assert Solution().climbStairs(5) == 8
assert Solution().climbStairs(10) == 89
# 手动推导 n=5：
# dp[1] = 1（1种方法：1）
# dp[2] = 2（2种方法：1+1, 2）
# dp[3] = dp[2] + dp[1] = 2 + 1 = 3（3种方法：1+1+1, 1+2, 2+1）
# dp[4] = dp[3] + dp[2] = 3 + 2 = 5（5种方法）
# dp[5] = dp[4] + dp[3] = 5 + 3 = 8（8种方法）
# 结果：8 种方法
|
杨辉三角
给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
from typing import List
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
"""
生成杨辉三角的前 numRows 行
思路：
- 杨辉三角的每个元素是它左上方和右上方元素的和
- 第 i 行有 i 个元素
- 每行的首尾元素都是 1
- 中间元素：triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j]
- 时间 O(n^2)，空间 O(n^2)
"""
triangle = []
for i in range(numRows):
# 当前行有 i+1 个元素
row = [1] * (i + 1)
# 填充中间的元素（除了首尾）
for j in range(1, i):
row[j] = triangle[i - 1][j - 1] + triangle[i - 1][j]
triangle.append(row)
return triangle
# 测试用例
assert Solution().generate(5) == [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
assert Solution().generate(1) == [[1]]
assert Solution().generate(2) == [[1], [1, 1]]
assert Solution().generate(3) == [[1], [1, 1], [1, 2, 1]]
# 手动推导 numRows=5：
# 第0行: [1]
# 第1行: [1, 1] （两个1相加）
# 第2行: [1, 2, 1] （1+1=2）
# 第3行: [1, 3, 3, 1] （1+2=3, 2+1=3）
# 第4行: [1, 4, 6, 4, 1] （1+3=4, 3+3=6, 3+1=4）
# 结果: [[1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1]]
|
打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
from typing import List
class Solution:
def rob(self, nums: List[int]) -> int:
"""
使用动态规划求解能偷窃的最高金额
思路：
- 对于第 i 间房屋，有两种选择：偷或不偷
- dp[i] = max(dp[i-1], dp[i-2] + nums[i])
- dp[i-1]：不偷第 i 间房屋，最大金额就是前 i-1 间能偷的最大金额
- dp[i-2] + nums[i]：偷第 i 间房屋，加上前 i-2 间能偷的最大金额
- 初始值：dp[0] = nums[0]，dp[1] = max(nums[0], nums[1])
- 空间优化：只需要保存前两个状态
- 时间 O(n)，空间 O(1)
"""
n = len(nums)
if n == 0:
return 0
if n == 1:
return nums[0]
# dp[i] 表示偷到第 i 间房屋时能获得的最高金额
prev2 = nums[0] # dp[i-2]
prev1 = max(nums[0], nums[1]) # dp[i-1]
for i in range(2, n):
curr = max(prev1, prev2 + nums[i]) # dp[i] = max(dp[i-1], dp[i-2] + nums[i])
prev2 = prev1
prev1 = curr
return prev1
# 测试用例
assert Solution().rob([1, 2, 3, 1]) == 4
assert Solution().rob([2, 7, 9, 3, 1]) == 12
assert Solution().rob([0]) == 0
assert Solution().rob([1]) == 1
assert Solution().rob([1, 2]) == 2
assert Solution().rob([2, 1, 1, 2]) == 4
# 手动推导 [1, 2, 3, 1]：
# dp[0] = 1（只有第0间，偷1）
# dp[1] = max(1, 2) = 2（偷第1间）
# dp[2] = max(dp[1], dp[0]+3) = max(2, 1+3) = max(2, 4) = 4（偷第2间）
# dp[3] = max(dp[2], dp[1]+1) = max(4, 2+1) = max(4, 3) = 4（不偷第3间）
# 结果：4（偷第0间和第2间，或偷第1间和第3间）
# 手动推导 [2,7,9,3,1]：
# dp[0] = 2
# dp[1] = max(2, 7) = 7
# dp[2] = max(7, 2+9) = 11（偷第2间和第0间）
# dp[3] = max(11, 7+3) = 11（不偷第3间）
# dp[4] = max(11, 11+1) = 12（偷第4间）
# 结果：12（偷第0间、第2间和第4间：2+9+1=12）
|
完全平方数
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
from typing import List
class Solution:
def numSquares(self, n: int) -> int:
"""
使用动态规划求解完全平方数的最少数量
思路：
- dp[i] 表示和为 i 的完全平方数的最少数量
- 对于每个 i，遍历所有可能的完全平方数 j*j <= i
- dp[i] = min(dp[i], dp[i - j*j] + 1)
- 时间 O(n * sqrt(n))，空间 O(n)
"""
dp = [float('inf')] * (n + 1)
dp[0] = 0 # 和为0需要0个完全平方数
for i in range(1, n + 1):
# 遍历所有可能的完全平方数
j = 1
while j * j <= i:
dp[i] = min(dp[i], dp[i - j * j] + 1)
j += 1
return dp[n]
# 测试用例
assert Solution().numSquares(12) == 3
assert Solution().numSquares(13) == 2
assert Solution().numSquares(1) == 1
assert Solution().numSquares(2) == 2
assert Solution().numSquares(4) == 1
assert Solution().numSquares(5) == 2
# 手动推导 n=12：
# dp[0] = 0
# dp[1] = min(dp[0]+1) = 1
# dp[2] = min(dp[1]+1, dp[0]+1) = min(2, 1) = 2
# dp[3] = min(dp[2]+1, dp[0]+1) = min(3, 1) = 2
# dp[4] = min(dp[3]+1, dp[0]+1) = min(3, 1) = 1
# ...
# dp[12] = min(
# dp[11]+1, # 1 + 11
# dp[8]+1, # 4 + 8
# dp[3]+1 # 9 + 3
# )
# 其中 dp[8] = min(dp[7]+1, dp[4]+1, dp[0]+1) = min(2, 1, 1) = 1
# 所以 dp[12] = min(?, 2, ?) = 2？不对...
#
# 重新推导：
# dp[12] = min(dp[11]+1, dp[8]+1, dp[3]+1)
# dp[11] = min(dp[10]+1, dp[7]+1, dp[2]+1) = ...
# 最终：12 = 4 + 4 + 4，所以 dp[12] = 3
# 结果：3（12 = 4 + 4 + 4）
|
零钱兑换
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
from typing import List
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
"""
使用动态规划求解最少硬币个数
思路：
- dp[i] 表示凑成金额 i 所需的最少硬币个数
- 对于每个金额 i，遍历所有硬币
- dp[i] = min(dp[i], dp[i - coin] + 1)
- 初始值：dp[0] = 0，其他为 infinity
- 时间 O(amount * len(coins))，空间 O(amount)
"""
dp = [float('inf')] * (amount + 1)
dp[0] = 0 # 凑成金额0需要0个硬币
for i in range(1, amount + 1):
for coin in coins:
if coin <= i:
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
# 测试用例
assert Solution().coinChange([1, 2, 5], 11) == 3
assert Solution().coinChange([2], 3) == -1
assert Solution().coinChange([1], 0) == 0
assert Solution().coinChange([1], 2) == 2
assert Solution().coinChange([2, 5, 10], 14) == 2
# 手动推导 coins=[1,2,5], amount=11：
# dp[0] = 0
# dp[1] = min(dp[0]+1) = 1
# dp[2] = min(dp[1]+1, dp[0]+1) = min(2, 1) = 1
# dp[3] = min(dp[2]+1, dp[1]+1) = min(2, 2) = 2
# dp[4] = min(dp[3]+1, dp[2]+1) = min(3, 2) = 2
# dp[5] = min(dp[4]+1, dp[3]+1, dp[0]+1) = min(3, 3, 1) = 1
# dp[6] = min(dp[5]+1, dp[4]+1, dp[1]+1) = min(2, 3, 2) = 2
# dp[7] = min(dp[6]+1, dp[5]+1, dp[2]+1) = min(3, 2, 2) = 2
# dp[8] = min(dp[7]+1, dp[6]+1, dp[3]+1) = min(3, 3, 3) = 3
# dp[9] = min(dp[8]+1, dp[7]+1, dp[4]+1) = min(4, 3, 3) = 3
# dp[10] = min(dp[9]+1, dp[8]+1, dp[5]+1) = min(4, 4, 2) = 2
# dp[11] = min(dp[10]+1, dp[9]+1, dp[6]+1) = min(3, 4, 3) = 3
# 结果：3（11 = 5 + 5 + 1）
|
单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
输入: s = “leetcode”, wordDict = [“leet”, “code”]
输出: true
解释: 返回 true 因为 “leetcode” 可以由 “leet” 和 “code” 拼接成。
s 和 wordDict[i] 仅由小写英文字母组成
wordDict 中的所有字符串 互不相同
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
from typing import List
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
"""
使用动态规划判断字符串能否被拆分
思路：
- dp[i] 表示字符串 s[0:i] 能否被拆分
- dp[i] = True 当且仅当存在某个 word 在 wordDict 中，且 s[i-len(word):i] == word 且 dp[i-len(word)] == True
- 即：当前位置的子串是一个单词，且前面的子串也能被拆分
- 时间 O(n * m * L)，空间 O(n)，其中 n 是字符串长度，m 是字典大小，L 是单词平均长度
"""
n = len(s)
word_set = set(wordDict) # 转换为集合提高查找效率
max_word_len = max(len(word) for word in wordDict) # 最长单词长度，用于剪枝
dp = [False] * (n + 1)
dp[0] = True # 空字符串可以被拆分
for i in range(1, n + 1):
# 遍历所有可能的单词长度
for length in range(1, min(i, max_word_len) + 1):
if dp[i - length] and s[i - length:i] in word_set:
dp[i] = True
break
return dp[n]
# 测试用例
assert Solution().wordBreak("leetcode", ["leet", "code"]) == True
assert Solution().wordBreak("applepenapple", ["apple", "pen"]) == True
assert Solution().wordBreak("catsandog", ["cats", "dog", "sand", "and", "cat"]) == False
assert Solution().wordBreak("a", ["a"]) == True
assert Solution().wordBreak("a", ["b"]) == False
assert Solution().wordBreak("aaaaaaa", ["aaaa", "aaa"]) == True
# 手动推导 s="leetcode", wordDict=["leet", "code"]：
# dp[0] = True（空字符串）
# dp[1]: s[0:1]="l", 不在字典中
# dp[2]: s[0:2]="le", 不在字典中
# dp[3]: s[0:3]="lee", 不在字典中
# dp[4]: s[0:4]="leet", 在字典中且 dp[0]=True -> dp[4]=True
# dp[5]: s[0:5]="leetc", 不在字典中
# dp[6]: s[0:6]="leetco", 不在字典中
# dp[7]: s[0:7]="leetcod", 不在字典中
# dp[8]: s[0:8]="leetcode", 不在字典中，但 s[4:8]="code" 在字典中且 dp[4]=True -> dp[8]=True
# 结果：True
|
最长递增子序列
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
进阶：你能将算法的时间复杂度降低到 O(n log(n)) 吗?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
from typing import List
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
"""
使用二分查找优化动态规划
思路：
- dp[i] 表示长度为 i+1 的递增子序列的最小尾部值
- 遍历数组，维护一个有序的 dp 数组
- 对于每个数，用二分查找找到它应该插入的位置
- 如果它比所有尾部都大，就扩展 dp；否则替换相应的位置
- 最终 dp 的长度就是最长递增子序列的长度
- 时间 O(n log n)，空间 O(n)
关键洞察：对于相同长度的递增子序列，尾部值越小越好
"""
import bisect
dp = [] # dp[i] 表示长度为 i+1 的递增子序列的最小尾部值
for num in nums:
# 找到 num 应该插入的位置
pos = bisect.bisect_left(dp, num)
if pos == len(dp):
# num 比所有尾部都大，扩展 dp
dp.append(num)
else:
# 替换 dp[pos]，保持 dp 的有序性
dp[pos] = num
return len(dp)
# 测试用例
assert Solution().lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]) == 4
assert Solution().lengthOfLIS([0, 1, 0, 3, 2, 3]) == 4
assert Solution().lengthOfLIS([7, 7, 7, 7, 7, 7, 7]) == 1
assert Solution().lengthOfLIS([1]) == 1
assert Solution().lengthOfLIS([1, 2, 3, 4, 5]) == 5
assert Solution().lengthOfLIS([5, 4, 3, 2, 1]) == 1
# 手动推导 [10, 9, 2, 5, 3, 7, 101, 18]：
# num=10: dp=[10]
# num=9: pos=0, dp=[9]
# num=2: pos=0, dp=[2]
# num=5: pos=1, dp=[2,5]
# num=3: pos=1, dp=[2,3]
# num=7: pos=2, dp=[2,3,7]
# num=101: pos=3, dp=[2,3,7,101]
# num=18: pos=2, dp=[2,3,18,101]（替换101为18，但长度不变）
# 结果：4（[2,3,7,101] 或 [2,3,7,18]）
|
乘积最大子数组
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
请注意，一个只包含一个元素的数组的乘积是这个元素的值。
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
nums 的任何子数组的乘积都 保证 是一个 32-位 整数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
from typing import List
class Solution:
def maxProduct(self, nums: List[int]) -> int:
"""
使用动态规划，维护最大和最小乘积
思路：
- 由于负数的存在，最大乘积可能由两个负数相乘得到
- 需要同时维护：以当前位置结尾的最大乘积和最小乘积
- max_dp[i] = max(nums[i], nums[i] * max_dp[i-1], nums[i] * min_dp[i-1])
- min_dp[i] = min(nums[i], nums[i] * max_dp[i-1], nums[i] * min_dp[i-1])
- 答案就是所有 max_dp 中的最大值
- 时间 O(n)，空间 O(1)
"""
max_prod = nums[0] # 全局最大乘积
max_dp = nums[0] # 以当前位置结尾的最大乘积
min_dp = nums[0] # 以当前位置结尾的最小乘积
for i in range(1, len(nums)):
num = nums[i]
# 当前最大值和最小值候选
candidates = (max_dp * num, min_dp * num, num)
max_dp = max(candidates)
min_dp = min(candidates)
# 更新全局最大乘积
max_prod = max(max_prod, max_dp)
return max_prod
# 测试用例
assert Solution().maxProduct([2, 3, -2, 4]) == 6
assert Solution().maxProduct([-2, 0, -1]) == 0
assert Solution().maxProduct([-2, 3, -4]) == 24
assert Solution().maxProduct([0, 2]) == 2
assert Solution().maxProduct([-2]) == -2
assert Solution().maxProduct([-2, -3, -4]) == 12
# 手动推导 [2,3,-2,4]：
# i=0: max_prod=2, max_dp=2, min_dp=2
# i=1, num=3:
# candidates = (2*3=6, 2*3=6, 3) -> max_dp=6, min_dp=3
# max_prod = max(2, 6) = 6
# i=2, num=-2:
# candidates = (6*(-2)=-12, 3*(-2)=-6, -2) -> max_dp=-2, min_dp=-12
# max_prod = max(6, -2) = 6
# i=3, num=4:
# candidates = (-2*4=-8, -12*4=-48, 4) -> max_dp=4, min_dp=-48
# max_prod = max(6, 4) = 6
# 结果：6（子数组 [2,3]）
|
分割等和子集
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
from typing import List
class Solution:
def canPartition(self, nums: List[int]) -> bool:
"""
转化为背包问题：能否从数组中选取若干元素，使其和等于 sum/2
思路：
- 如果数组总和为奇数，直接返回 False
- 令 target = sum(nums) // 2
- dp[i] 表示能否凑成和为 i
- 对于每个数 num，遍历从 target 到 num 的所有位置
- dp[i] = dp[i] or dp[i - num]
- 时间 O(n * sum)，空间 O(sum)
"""
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
dp = [False] * (target + 1)
dp[0] = True # 和为0可以通过不选任何元素得到
for num in nums:
# 从后往前遍历，避免同一个元素被使用多次
for i in range(target, num - 1, -1):
dp[i] = dp[i] or dp[i - num]
# 提前返回，如果已经找到解
if dp[target]:
return True
return dp[target]
# 测试用例
assert Solution().canPartition([1, 5, 11, 5]) == True
assert Solution().canPartition([1, 2, 3, 5]) == False
assert Solution().canPartition([1, 1]) == True
assert Solution().canPartition([1, 2, 5]) == False
assert Solution().canPartition([3, 3, 3, 4, 5]) == True
# 手动推导 [1, 5, 11, 5]：
# total = 1 + 5 + 11 + 5 = 22
# target = 11
# dp[0] = True
#
# num=1: dp[1]=True, dp[2]=..., dp[11]=...
# num=5: dp[5]=True, dp[6]=True, ..., dp[11]=True
# num=11: dp[11]=True or dp[0]=True -> dp[11]=True（找到解）
# 结果：True（可以分割为 [11] 和 [1,5,5]）
|
最长有效括号
给你一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号 子串 的长度。
左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如 “(()())"。
输入：s = “(()”
输出：2
解释：最长有效括号子串是 “()”
s[i] 为 ‘(’ 或 ‘)’
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
|
class Solution:
def longestValidParentheses(self, s: str) -> int:
"""
使用动态规划求解最长有效括号长度
思路：
- dp[i] 表示以 s[i] 结尾的有效括号长度
- 如果 s[i] == ')'：
- 如果 s[i-1] == '('，则 dp[i] = dp[i-2] + 2
- 否则，如果 s[i-dp[i-1]-1] == '('，则 dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]
- 时间 O(n)，空间 O(n)
"""
n = len(s)
if n == 0:
return 0
dp = [0] * n
max_len = 0
for i in range(1, n):
if s[i] == ')':
# 情况1：s[i-1] == '('，形成 "()"
if s[i - 1] == '(':
dp[i] = (dp[i - 2] if i >= 2 else 0) + 2
# 情况2：s[i-dp[i-1]-1] == '('，形成 "(...)"
elif i - dp[i - 1] - 1 >= 0 and s[i - dp[i - 1] - 1] == '(':
dp[i] = dp[i - 1] + 2 + (dp[i - dp[i - 1] - 2] if i - dp[i - 1] - 2 >= 0 else 0)
max_len = max(max_len, dp[i])
return max_len
# 测试用例
assert Solution().longestValidParentheses("(()") == 2
assert Solution().longestValidParentheses(")()())") == 4
assert Solution().longestValidParentheses("") == 0
assert Solution().longestValidParentheses("()") == 2
assert Solution().longestValidParentheses("()()") == 4
assert Solution().longestValidParentheses("(()())") == 6
assert Solution().longestValidParentheses(")()()()") == 4
# 手动推导 "(()"：
# i=0: s[0]='('，无法形成有效括号，dp[0]=0
# i=1: s[1]=')' 且 s[0]='('，dp[1]=dp[-1]+2=2，max_len=2
# i=2: s[2]=')' 但 s[1]=')'，检查 s[0]='('？不满足 s[i-dp[i-1]-1]=s[-2]？越界
# 结果：max_len=2
# 手动推导 ")()())"：
# i=0: s[0]=')'，无法形成有效括号
# i=1: s[1]='(' 且 s[2]=')'，dp[2]=2？不对...
# 重新推导：
# i=0: s[0]=')'，dp[0]=0
# i=1: s[1]='('，dp[1]=0
# i=2: s[2]=')' 且 s[1]='('，dp[2]=dp[0]+2=2，max_len=2
# i=3: s[3]=')' 且 s[2]=')'，检查 s[3-2-1]=s[0]=')' != '('，dp[3]=0
# i=4: s[4]='('，dp[4]=0
# i=5: s[5]=')' 且 s[4]='('，dp[5]=dp[3]+2=2，max_len=2
# 结果：2？不对，应该是4...
#
# 重新分析 ")()())":
# 字符串索引: 0:')', 1:'(', 2:')', 3:'(', 4:')', 5:')'
# i=0: ')'
# i=1: '('
# i=2: ')', s[1]='(' -> dp[2] = dp[0] + 2 = 2, max=2
# i=3: ')', s[2]=')' -> 检查 s[0]=')' != '(' -> dp[3] = 0
# i=4: '(', dp[4] = 0
# i=5: ')', s[4]='(' -> dp[5] = dp[3] + 2 = 2, max=2
# 结果：2？不对
#
# 正确分析：
# ")()())"
# 有效括号是 "()()" (索引1-2和4-5) 和 "()()" 中的部分？
# 实际上是 "()()" 从索引1到4（不含）
# 让我再想想...
# ")()())" 中有效的是 "()" (索引1-2) 和 "()" (索引4-5)
# 但中间被隔断了，所以最长是 2+2=4
#
# 修正：
# ")()())"
# i=2: dp[2]=2 (匹配 "()")
# i=3: dp[3]=0
# i=4: s[4]='(', 不是右括号
# i=5: s[5]=')', s[4]='(' -> dp[5]=dp[3]+2=2
# 但索引1-2和4-5是连续的 "()()"，所以应该是 4
# 问题在于 dp[5] 应该等于 dp[1] + 2 + dp[?]？不对
# 实际上 ")()())" 从索引1到5是 "()())" = "()" + "())"，有效部分是 "()"
# 但 ")()())" 的有效括号子串是 "()()" 长度为4
# 这意味着 dp[5] 应该 = dp[3] + 2 + dp[?] 但 dp[3]=0，所以是2
# 最大长度是 dp[2]=2, dp[5]=2, max=2？不对
#
# 让我重新理解：
# ")()())"
# 索引0: )
# 索引1: (
# 索引2: )
# 索引3: (
# 索引4: )
# 索引5: )
#
# 有效括号子串：
# - 索引1-2: "()" -> 长度2
# - 索引3-5: "())" -> 包含索引3-4的 "()"，长度2
# - 索引1-5: "()())" -> 包含索引1-2和3-4的有效部分，长度4
#
# 所以最长有效括号长度是4（索引1-5）
# dp[5] = dp[1] + 2 + dp[?]？dp[1]=0，所以是2
# 这不对...
#
# 重新看代码逻辑：
# 对于 i=5, s[i]=')'
# s[i-1]='('? s[4]=')' != '('
# 所以走 elif 分支：s[i-dp[i-1]-1] = s[5-2-1] = s[2] = ')' != '('
# 所以 dp[5] = 0？不对
#
# 实际上的代码应该能处理这种情况，因为索引1-2形成"()"，索引3-4形成"()"
# 这两个是独立的有效括号子串，所以最长长度是4
#
# 在 dp 数组中：
# dp[2] = 2 (索引1-2)
# dp[4] 应该 = dp[3] + 2 = 0 + 2 = 2 (索引3-4)
# 但 dp[5] 不会连接到 dp[2]，因为它们之间有间隔
#
# 所以 dp[5] = 0，但 max_len = max(2, 2) = 2
# 结果是 2？这不对
#
# 实际上 ")()())" 的最长有效括号子串是 "()()" 长度为4
# 这说明代码逻辑应该能找到这个
# 让我再看...
#
# 可能我的分析有问题，正确理解应该是：
# dp[i] 表示以 s[i] 结尾的有效括号子串的长度
# ")()())" 中，以索引5结尾的有效括号子串是 "()())"，它包含两个 "()"，所以长度应该是4
#
# 对于 i=5, s[5]=')'
# s[4]='('，所以走第一个分支
# dp[5] = dp[3] + 2
# dp[3] = ? s[3]='(' 不是右括号，所以 dp[3]=0
# dp[5] = 0 + 2 = 2？不对
#
# 啊，问题在于 "()())" 不是连续的有效括号！
# "()" 是有效的，")" 是多余的，所以最长有效是 "()" 长度2
# 但题目说答案是4，所以 ")()())" 中 "()()" 是有效子串（索引1-4）
#
# ")()())" = 索引0:')', 索引1:'(', 索引2:')', 索引3:'(', 索引4:')', 索引5:')'
# 从索引1到4是 "()()"，是有效的！所以长度是4
#
# 对于 i=4: s[4]=')' 且 s[3]='(' -> dp[4] = dp[2] + 2 = 2 + 2 = 4
# 所以 dp[4] = 4，max_len = 4
# 结果：4
|
记录生活