你好呀!我是 山顶风景独好
欢迎踏入我的博客世界,能与您在此邂逅,真是缘分使然!
愿您在此停留的每一刻,都沐浴在轻松愉悦的氛围中。
这里不仅有丰富的知识和趣味横生的内容等您来探索,更是一个自由交流的平台,期待您留下独特的思考与见解。
让我们一起踏上这段探索与成长的旅程,携手挖掘更多可能,共同进步!✨
题目一:分割数组的最大值(LeetCode 410,困难)
题目分析
给定一个非负整数数组 nums
和一个整数 m
,将数组分成 m
个非空的连续子数组,使得这 m
个子数组各自和的最大值最小。例如:输入 nums = [7,2,5,10,8], m = 2
,输出 18(分割为 [7,2,5]
和 [10,8]
,最大和为 18);输入 nums = [1,2,3,4,5], m = 2
,输出 9;输入 nums = [1,4,4], m = 3
,输出 4。
解题思路(二分查找+可行性判定)
核心是将“最小化最大和”的优化问题转化为“给定最大和,能否分割数组为不超过 m
个子数组”的判定问题,通过二分查找快速定位最优解:
- 二分查找范围确定:
- 左边界
left
:数组中最大元素的值(每个子数组至少含一个元素,最大和不能小于最大元素); - 右边界
right
:数组所有元素的和(当m=1
时,最大和为数组总和)。
- 左边界
- 可行性判定函数:
- 函数
can_split(max_sum)
:遍历数组,累加元素和,若超过max_sum
则开启新子数组,最终判断子数组个数是否 ≤m
; - 优化:当子数组个数超过
m
时提前返回false
,减少无效遍历。
- 函数
- 二分查找流程:
- 计算中间值
mid = (left + right) // 2
,若can_split(mid)
为true
,尝试更小的最大和(right = mid
); - 否则需要更大的最大和(
left = mid + 1
); - 最终
left
与right
收敛到最小可行值,即为答案。
- 计算中间值
示例代码
def splitArray(nums, m) -> int:
def can_split(max_sum):
"""判断能否分割为k<=m个子数组,每个子数组和不超过max_sum"""
current_sum = 0
split_count = 1 # 初始分割数为1
for num in nums:
if current_sum + num > max_sum:
split_count += 1
current_sum = num
if split_count > m: # 提前终止
return False
else:
current_sum += num
return split_count <= m
left = max(nums)
right = sum(nums)
while left < right:
mid = (left + right) // 2
if can_split(mid):
right = mid
else:
left = mid + 1
return left
# 测试示例
nums1 = [7,2,5,10,8]
m1 = 2
print("最小最大和1:", splitArray(nums1, m1)) # 输出:18
nums2 = [1,2,3,4,5]
m2 = 2
print("最小最大和2:", splitArray(nums2, m2)) # 输出:9
nums3 = [1,4,4]
m3 = 3
print("最小最大和3:", splitArray(nums3, m3)) # 输出:4
代码解析
- 问题转化的高效性:将复杂的优化问题转化为简单的判定问题,二分查找的时间复杂度为 O(log S)(S 为数组总和与最大元素的差值),判定函数时间复杂度为 O(n),整体时间复杂度 O(n log S),远优于暴力枚举的 O(n^m)。
- 边界收敛逻辑:
left < right
的循环条件确保最终left
即为最小可行值,无需额外判断,代码简洁高效。
题目二:组合总和 IV(LeetCode 377,困难)
题目分析
给你一个由不同整数组成的数组 nums
和一个目标整数 target
,找出并返回总和为 target
的元素组合的个数。顺序不同的序列被视作不同的组合。例如:输入 nums = [1,2,3], target = 4
,输出 7(组合:1+1+1+1
、1+1+2
、1+2+1
、2+1+1
、1+3
、3+1
、2+2
);输入 nums = [9], target = 3
,输出 0;输入 nums = [2,1,3], target = 3
,输出 3。
解题思路(动态规划+顺序敏感处理)
核心是定义 dp[i]
表示“总和为 i
的组合个数”,通过控制遍历顺序确保不同顺序的组合被分别计数,同时优化空间复杂度:
- 状态定义与初始化:
dp[i]
代表总和为i
的组合个数,dp[0] = 1
(空组合是总和为 0 的唯一组合,作为递推基础);- 初始化
dp
数组为target+1
大小,其余元素为 0。
- 状态转移与遍历顺序:
- 遍历目标值
i
从 1 到target
; - 对每个
i
,遍历数组nums
中的每个元素num
:- 若
num ≤ i
,则dp[i] += dp[i - num]
(总和为i
的组合 = 所有“总和为i - num
的组合后追加num
”的结果);
- 若
- 顺序敏感性关键:先遍历目标值再遍历数组元素,确保不同顺序的组合被分别统计(如
1+2
和2+1
会被视为两个独立组合)。
- 遍历目标值
示例代码
def combinationSum4(nums, target) -> int:
dp = [0] * (target + 1)
dp[0] = 1 # 空组合对应总和0
# 先遍历目标值,再遍历数组元素(确保顺序敏感)
for i in range(1, target + 1):
for num in nums:
if num <= i:
dp[i] += dp[i - num]
return dp[target]
# 测试示例
nums1 = [1,2,3]
target1 = 4
print("组合个数1:", combinationSum4(nums1, target1)) # 输出:7
nums2 = [9]
target2 = 3
print("组合个数2:", combinationSum4(nums2, target2)) # 输出:0
nums3 = [2,1,3]
target3 = 3
print("组合个数3:", combinationSum4(nums3, target3)) # 输出:3
代码解析
- 遍历顺序的影响:若交换遍历顺序(先数组元素后目标值),则变为“组合不区分顺序”的问题(如 LeetCode 39 组合总和),体现了遍历顺序对动态规划结果的决定性作用。
- 边界处理的合理性:
dp[0] = 1
是递推的核心,确保单个元素num
能被正确计数为dp[num] += dp[0] = 1
。
题目三:路径总和 III(LeetCode 437,困难)
题目分析
给定一个二叉树的根节点 root
和一个整数 targetSum
,求该二叉树里节点值之和等于 targetSum
的路径数目。路径不需要从根节点开始,也不需要在叶子节点结束,但路径方向必须是向下的(只能从父节点到子节点)。例如:输入 root = [10,5,-3,3,2,null,11,3,-2,null,1]
, targetSum = 8
,输出 3(路径:5→3
、5→2→1
、-3→11
);输入 root = [1,null,2,null,3,null,4,null,5]
, targetSum = 3
,输出 2;输入 root = [-3]
, targetSum = -3
,输出 1。
解题思路(前缀和+DFS回溯)
核心是通过记录从根节点到当前节点的前缀和,利用“当前前缀和 - 目标和 = 历史前缀和”的数学关系统计路径数,结合回溯避免跨路径干扰:
- 前缀和定义:从根节点到当前节点的路径和为前缀和。若当前前缀和为
curr_sum
,则存在路径和为targetSum
的充要条件是:存在历史前缀和prev_sum = curr_sum - targetSum
,且该prev_sum
出现过k
次(对应k
条有效路径)。 - 哈希表记录频次:用字典
prefix_count
存储前缀和及其出现次数,初始prefix_count = {0: 1}
(表示“空路径”的前缀和 0 出现 1 次,对应路径从当前节点开始的场景)。 - DFS回溯流程:
- 递归计算当前节点的前缀和
curr_sum += node.val
; - 统计
prev_sum = curr_sum - targetSum
在prefix_count
中的频次,累加至结果; - 将当前前缀和加入
prefix_count
,递归遍历左右子树; - 回溯:将当前前缀和的频次减 1(确保哈希表仅保留当前路径的前缀和,避免影响其他分支)。
- 递归计算当前节点的前缀和
示例代码
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
from collections import defaultdict
def pathSum(root: TreeNode, targetSum: int) -> int:
prefix_count = defaultdict(int)
prefix_count[0] = 1 # 初始状态:空路径的前缀和0
def dfs(node, curr_sum):
if not node:
return 0
# 更新当前前缀和
curr_sum += node.val
# 计算需要的历史前缀和,累加有效路径数
prev_sum = curr_sum - targetSum
res = prefix_count[prev_sum]
# 将当前前缀和加入哈希表
prefix_count[curr_sum] += 1
# 递归遍历左右子树
res += dfs(node.left, curr_sum)
res += dfs(node.right, curr_sum)
# 回溯:移除当前路径的前缀和记录
prefix_count[curr_sum] -= 1
return res
return dfs(root, 0)
# 测试示例
root1 = TreeNode(10)
root1.left = TreeNode(5, TreeNode(3, TreeNode(3), TreeNode(-2)), TreeNode(2, None, TreeNode(1)))
root1.right = TreeNode(-3, None, TreeNode(11))
print("路径总数1:", pathSum(root1, 8)) # 输出:3
root2 = TreeNode(1, None, TreeNode(2, None, TreeNode(3, None, TreeNode(4, None, TreeNode(5)))))
print("路径总数2:", pathSum(root2, 3)) # 输出:2
代码解析
- 前缀和的高效性:将暴力枚举的 O(n²) 时间复杂度降至 O(n)(每个节点仅遍历一次),避免重复计算子路径和。
- 回溯的必要性:递归返回前减少当前前缀和的频次,确保哈希表状态与当前路径一致,是解决“路径方向向下”约束的关键。
✨ 本次分享的3道题覆盖“二分查找(分割数组)”“动态规划(组合总和IV)”“前缀和+DFS(路径总和III)”,均体现了“问题建模”与“算法选择”的深度融合。若对某题的拓展场景(如带权重的组合总和、分割数组的方案输出)或其他困难题有需求,随时告诉我!
更多算法解析欢迎到CSDN主页交流:山顶风景独好