从算法题到实战Python实现“删K位最小数”与“二叉树最长路径”全解析当数据结构从试卷走向代码编辑器抽象的理论突然变得具体而生动。本文将带你用Python实现两道经典算法题删K位得最小数和二叉树最长路径不仅还原解题思路更注重工程实践中的各种细节处理。1. 删K位数字问题贪心算法的精妙应用给定一个数字字符串删除其中K个字符后使剩余数字最小——这道看似简单的题目背后隐藏着贪心算法的典型应用场景。想象一下信用卡号输入错误需要删除几位数字的场景或者文件版本号需要精简时的处理逻辑。1.1 问题分析与核心思路贪心算法的关键在于局部最优导致全局最优。对于数字1432219要删除3位我们不应该随机删除而是从左到右寻找应该删除的数字维护一个结果栈遍历每个数字时只要当前数字比栈顶小且还能删除(k0)就弹出栈顶将当前数字压入栈如果遍历完k仍大于0从末尾继续删除def removeKdigits(num: str, k: int) - str: stack [] for digit in num: while k 0 and stack and stack[-1] digit: stack.pop() k - 1 stack.append(digit) # 处理剩余需要删除的情况 final_stack stack[:-k] if k 0 else stack # 去除前导零并处理空字符串情况 return .join(final_stack).lstrip(0) or 01.2 边界情况与测试用例实际编码时需要特别注意以下边界条件测试用例预期结果说明10200, 1200删除1后需去除前导零10, 20全部删除应返回012345, 2123单调递增时删除末尾10001, 40多个零的特殊处理提示在实际面试中能正确处理各种边界情况往往比算法本身更重要2. 二叉树最长路径递归与迭代的双解二叉树的最大深度问题看似简单但当需要获取具体路径而非仅长度时复杂度就显著提升。这在文件系统路径查找、组织架构层级分析等场景都有实际应用。2.1 递归解法深度优先的直观实现递归是解决树问题的自然思路后序遍历可以优雅地获取深度信息class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right def longestPath(root: TreeNode) - List[int]: max_path [] def dfs(node): nonlocal max_path if not node: return [] left_path dfs(node.left) right_path dfs(node.right) # 选择更长的子路径 longer_path left_path if len(left_path) len(right_path) else right_path current_path longer_path [node.val] # 更新全局最长路径 if len(current_path) len(max_path): max_path current_path return current_path dfs(root) return max_path2.2 迭代解法显式栈管理状态对于大型树或担心递归栈溢出的情况迭代解法更可靠def longestPathIterative(root: TreeNode) - List[int]: if not root: return [] stack [(root, [root.val])] max_path [] while stack: node, path stack.pop() if len(path) len(max_path): max_path path if node.right: stack.append((node.right, path [node.right.val])) if node.left: stack.append((node.left, path [node.left.val])) return max_path两种方法各有优劣递归代码简洁但深度过大可能栈溢出迭代性能稳定适合大规模数据但代码稍复杂3. 算法优化与性能对比理解算法的时间空间复杂度是工程实现的关键环节。3.1 删K位算法复杂度分析时间复杂度O(n)每个元素最多入栈出栈一次空间复杂度O(n)最坏情况需要存储整个字符串优化点提前终止当剩余需要删除的数字数等于剩余未处理数字数时直接处理并行处理超长字符串可分块处理3.2 二叉树路径算法对比方法时间复杂度空间复杂度适用场景递归O(n)O(h)树高度适中迭代O(n)O(n)树特别深或不确定深度4. 实际应用场景扩展这两个算法看似学术实则有着广泛的实际应用删K位数字的应用场景数据压缩去除冗余数字金融交易处理输错的金额版本控制精简过长的版本号二叉树最长路径的应用文件系统查找最深嵌套目录网络路由寻找最长匹配路径组织结构分析最长汇报链在实现这些业务逻辑时我们往往需要对基础算法进行适当改造。例如文件系统路径查找可能需要同时记录路径字符串而非仅长度这时算法框架不变只需调整存储的信息类型。
从哈工大数据结构期末算法题出发：手把手教你用Python实现“删K位得最小数”和“二叉树最长路径”
从算法题到实战Python实现“删K位最小数”与“二叉树最长路径”全解析当数据结构从试卷走向代码编辑器抽象的理论突然变得具体而生动。本文将带你用Python实现两道经典算法题删K位得最小数和二叉树最长路径不仅还原解题思路更注重工程实践中的各种细节处理。1. 删K位数字问题贪心算法的精妙应用给定一个数字字符串删除其中K个字符后使剩余数字最小——这道看似简单的题目背后隐藏着贪心算法的典型应用场景。想象一下信用卡号输入错误需要删除几位数字的场景或者文件版本号需要精简时的处理逻辑。1.1 问题分析与核心思路贪心算法的关键在于局部最优导致全局最优。对于数字1432219要删除3位我们不应该随机删除而是从左到右寻找应该删除的数字维护一个结果栈遍历每个数字时只要当前数字比栈顶小且还能删除(k0)就弹出栈顶将当前数字压入栈如果遍历完k仍大于0从末尾继续删除def removeKdigits(num: str, k: int) - str: stack [] for digit in num: while k 0 and stack and stack[-1] digit: stack.pop() k - 1 stack.append(digit) # 处理剩余需要删除的情况 final_stack stack[:-k] if k 0 else stack # 去除前导零并处理空字符串情况 return .join(final_stack).lstrip(0) or 01.2 边界情况与测试用例实际编码时需要特别注意以下边界条件测试用例预期结果说明10200, 1200删除1后需去除前导零10, 20全部删除应返回012345, 2123单调递增时删除末尾10001, 40多个零的特殊处理提示在实际面试中能正确处理各种边界情况往往比算法本身更重要2. 二叉树最长路径递归与迭代的双解二叉树的最大深度问题看似简单但当需要获取具体路径而非仅长度时复杂度就显著提升。这在文件系统路径查找、组织架构层级分析等场景都有实际应用。2.1 递归解法深度优先的直观实现递归是解决树问题的自然思路后序遍历可以优雅地获取深度信息class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right def longestPath(root: TreeNode) - List[int]: max_path [] def dfs(node): nonlocal max_path if not node: return [] left_path dfs(node.left) right_path dfs(node.right) # 选择更长的子路径 longer_path left_path if len(left_path) len(right_path) else right_path current_path longer_path [node.val] # 更新全局最长路径 if len(current_path) len(max_path): max_path current_path return current_path dfs(root) return max_path2.2 迭代解法显式栈管理状态对于大型树或担心递归栈溢出的情况迭代解法更可靠def longestPathIterative(root: TreeNode) - List[int]: if not root: return [] stack [(root, [root.val])] max_path [] while stack: node, path stack.pop() if len(path) len(max_path): max_path path if node.right: stack.append((node.right, path [node.right.val])) if node.left: stack.append((node.left, path [node.left.val])) return max_path两种方法各有优劣递归代码简洁但深度过大可能栈溢出迭代性能稳定适合大规模数据但代码稍复杂3. 算法优化与性能对比理解算法的时间空间复杂度是工程实现的关键环节。3.1 删K位算法复杂度分析时间复杂度O(n)每个元素最多入栈出栈一次空间复杂度O(n)最坏情况需要存储整个字符串优化点提前终止当剩余需要删除的数字数等于剩余未处理数字数时直接处理并行处理超长字符串可分块处理3.2 二叉树路径算法对比方法时间复杂度空间复杂度适用场景递归O(n)O(h)树高度适中迭代O(n)O(n)树特别深或不确定深度4. 实际应用场景扩展这两个算法看似学术实则有着广泛的实际应用删K位数字的应用场景数据压缩去除冗余数字金融交易处理输错的金额版本控制精简过长的版本号二叉树最长路径的应用文件系统查找最深嵌套目录网络路由寻找最长匹配路径组织结构分析最长汇报链在实现这些业务逻辑时我们往往需要对基础算法进行适当改造。例如文件系统路径查找可能需要同时记录路径字符串而非仅长度这时算法框架不变只需调整存储的信息类型。
