当前位置: 首页 > news >正文

【Leetcode】随笔 - 详解

你好呀!我是 山顶风景独好
欢迎踏入我的博客世界,能与您在此邂逅,真是缘分使然!
愿您在此停留的每一刻,都沐浴在轻松愉悦的氛围中。
这里不仅有丰富的知识和趣味横生的内容等您来探索,更是一个自由交流的平台,期待您留下独特的思考与见解。
让我们一起踏上这段探索与成长的旅程,携手挖掘更多可能,共同进步!✨

题目一:分割数组的最大值(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 个子数组”的判定问题,通过二分查找快速定位最优解:

  1. 二分查找范围确定
    • 左边界 left:数组中最大元素的值(每个子数组至少含一个元素,最大和不能小于最大元素);
    • 右边界 right:数组所有元素的和(当 m=1 时,最大和为数组总和)。
  2. 可行性判定函数
    • 函数 can_split(max_sum):遍历数组,累加元素和,若超过 max_sum 则开启新子数组,最终判断子数组个数是否 ≤ m
    • 优化:当子数组个数超过 m 时提前返回 false,减少无效遍历。
  3. 二分查找流程
    • 计算中间值 mid = (left + right) // 2,若 can_split(mid)true,尝试更小的最大和(right = mid);
    • 否则需要更大的最大和(left = mid + 1);
    • 最终 leftright 收敛到最小可行值,即为答案。

示例代码

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+11+1+21+2+12+1+11+33+12+2);输入 nums = [9], target = 3,输出 0;输入 nums = [2,1,3], target = 3,输出 3。

解题思路(动态规划+顺序敏感处理)

核心是定义 dp[i] 表示“总和为 i 的组合个数”,通过控制遍历顺序确保不同顺序的组合被分别计数,同时优化空间复杂度:

  1. 状态定义与初始化
    • dp[i] 代表总和为 i 的组合个数,dp[0] = 1(空组合是总和为 0 的唯一组合,作为递推基础);
    • 初始化 dp 数组为 target+1 大小,其余元素为 0。
  2. 状态转移与遍历顺序
    • 遍历目标值 i 从 1 到 target
    • 对每个 i,遍历数组 nums 中的每个元素 num
      • num ≤ i,则 dp[i] += dp[i - num](总和为 i 的组合 = 所有“总和为 i - num 的组合后追加 num”的结果);
    • 顺序敏感性关键:先遍历目标值再遍历数组元素,确保不同顺序的组合被分别统计(如 1+22+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→35→2→1-3→11);输入 root = [1,null,2,null,3,null,4,null,5], targetSum = 3,输出 2;输入 root = [-3], targetSum = -3,输出 1。

解题思路(前缀和+DFS回溯)

核心是通过记录从根节点到当前节点的前缀和,利用“当前前缀和 - 目标和 = 历史前缀和”的数学关系统计路径数,结合回溯避免跨路径干扰:

  1. 前缀和定义:从根节点到当前节点的路径和为前缀和。若当前前缀和为 curr_sum,则存在路径和为 targetSum 的充要条件是:存在历史前缀和 prev_sum = curr_sum - targetSum,且该 prev_sum 出现过 k 次(对应 k 条有效路径)。
  2. 哈希表记录频次:用字典 prefix_count 存储前缀和及其出现次数,初始 prefix_count = {0: 1}(表示“空路径”的前缀和 0 出现 1 次,对应路径从当前节点开始的场景)。
  3. DFS回溯流程
    • 递归计算当前节点的前缀和 curr_sum += node.val
    • 统计 prev_sum = curr_sum - targetSumprefix_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主页交流:山顶风景独好

http://www.hskmm.com/?act=detail&tid=21697

相关文章:

  • DevEco Studio 编辑器的使用 - 实践
  • docker安装MySQL8.0.25的坑
  • WPF 深入系列.2.布局系统.尺寸属性 - 指南
  • 实训
  • Kosaraju算法
  • bat批处理设置临时PATH路径不能访问
  • 10. Spring AI + RAG - Rainbow
  • 《AI智能体实战研发教程(从0到企业级项目落地)》全网上线|CSDN B站同步首发
  • 9. Spring AI 当中对应 MCP 的操作 - Rainbow
  • 9/30
  • rhel8无法输入中文问题(红帽8安装中文输入法)
  • 威佐夫博弈(Wythoff‘s Game)
  • C语言⽂件管理讲解(1)
  • 2025年9月30日
  • Min-p采样:通过动态调整截断阈值让大模型文本生成兼顾创造力与逻辑性
  • 2025 年快速卷帘门品牌最新推荐排行榜:聚焦智能定制与高效供货,精选快速卷帘门实力厂家
  • ARL灯塔搭建
  • 记 Charles 抓不到包 - Higurashi
  • STM32H743-ARM例程13-SDIO - 实践
  • 贼猴 0930 模拟赛 T2 | 计数
  • 题解:AT_abc311_h [ABC311Ex] Many Illumination Plans
  • 一个孤单的程序员
  • 根号大杂烩
  • 学习java的第二天
  • 日记.txt
  • Beatty 定理
  • 2025-9-27 提高组模拟赛 div2
  • part2
  • Controversial Rounds
  • 题解:B4410 [GESP202509 一级] 金字塔