华为od面试手撕真题

<think>好的，用户正在寻找华为OD面试相关的算法或编程真题及解答。我需要先理解他们的需求，然后提供有用的信息。首先，用户可能正在准备面试，需要具体的题目示例和解答，以及相关的分析。他们提供的示例中有快速排序的代码和问题，这可能暗示他们希望看到类似的格式：问题、解答、代码示例和相关问题。 接下来，我需要参考用户提供的引用内容。引用[1]提到机试题库覆盖广，建议多刷题，尤其是同类型题目。引用[2]则展示了一个动态规划的硬币兑换问题及其解法。这说明华为OD面试可能涉及排序算法、动态规划等常见算法题。 我应该先整理几个典型的算法题目，确保涵盖不同的类型，如动态规划、排序、字符串处理等。每个题目需要给出问题描述、解决思路、代码实现（Python），并引用相关资料。同时，按照用户的要求，生成相关问题，帮助用户进一步学习。 需要注意用户提到的格式要求：行内数学公式用$...$，独立公式用$$...$$，但当前的问题可能不涉及复杂数学符号，但如果有的话需要正确应用。同时，回答必须使用中文，结构清晰，分步骤解答。 现在，我需要选择几个典型的题目。引用[2]中的硬币兑换问题已经是动态规划的例子，可以详细说明。另一个例子可以是字符串处理，比如最长回文子串，或者数组相关的题目，比如两数之和。再比如二叉树遍历，或者链表操作。不过考虑到用户提供的示例中有排序算法，或许再选一个排序相关的问题，比如归并排序或堆排序，但快速排序已经给出，所以可能需要另一个类型。 例如，硬币兑换问题可以作为动态规划的典型题目，字符串反转或括号匹配作为字符串处理的例子，还有二叉树层次遍历作为数据结构题目。每个题目都需要清晰的解决思路和代码。 在编写每个题目时，需要确保代码正确，符合Python语法，并且有注释解释关键步骤。同时，引用相关引用内容，比如引用[2]中的硬币兑换问题，引用[1]中的建议。 最后，生成相关问题，帮助用户深入思考，比如时间空间复杂度分析、优化方法、应用场景等。 现在，检查是否有遗漏：是否覆盖了不同算法类型，解答是否清晰，代码是否正确，引用是否正确，是否生成相关问题。需要确保所有内容符合用户的要求，并且信息准确可靠。</think>根据华为OD面试真题类型及高频考点，整理以下典型算法题目及解答： --- ### 一、硬币兑换问题（动态规划） **问题**：给定面值为1分、2分、3分的硬币，求兑换n分钱的组合方式数量[^2]。 #### 解决思路 1. **状态定义**：设$dp[j]$表示兑换j分钱的组合数 2. **初始化**：$dp[0] = 1$（0分钱只有一种兑换方式） 3. **状态转移**：遍历每种硬币$i$，更新$dp[j] += dp[j-i]$ 4. **结果**：$dp[n]$即为最终答案 #### 代码实现 ```python def solve(n): dp = [0] * (n + 1) dp[0] = 1 # 初始条件：0分钱对应1种兑换方式 for i in range(1, 4): # 遍历三种硬币（1分、2分、3分） for j in range(i, n + 1): dp[j] += dp[j - i] # 状态转移方程 return dp[n] print(solve(3)) # 输出：4 print(solve(2934)) # 输出具体数值 ``` **关键点**：通过动态规划避免重复计算，时间复杂度$O(n)$，空间复杂度$O(n)$ --- ### 二、字符串压缩（双指针） **问题**：将字符串中连续重复字符压缩为"字符+出现次数"，例如"aaabbbcc"变为"a3b3c2"。 #### 解决思路 1. **双指针遍历**：快指针扫描重复字符，慢指针记录压缩结果 2. **边界处理**：单个字符不添加数字（如"a"压缩为"a"） #### 代码实现 ```python def compress(s): if not s: return "" res = [] slow, fast = 0, 0 while fast < len(s): if s[fast] != s[slow]: res.append(s[slow] + (str(fast - slow) if fast - slow > 1 else "")) slow = fast fast += 1 res.append(s[slow] + (str(fast - slow) if fast - slow > 1 else "")) return "".join(res) print(compress("aaabbbcc")) # 输出：a3b3c2 ``` --- ### 三、二叉树层序遍历（BFS） **问题**：按层输出二叉树节点值，每层结果单独存储。 #### 解决思路 1. **队列实现BFS**：利用队列先进先出特性 2. **层级标记**：每次处理一层节点后记录结果 #### 代码实现 ```python class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def levelOrder(root): if not root: return [] res = [] queue = [root] while queue: level_size = len(queue) current_level = [] for _ in range(level_size): node = queue.pop(0) current_level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) res.append(current_level) return res ``` --- §§ 1. 动态规划在解决硬币问题时如何避免重复计算？ 2. 字符串压缩算法的时间复杂度如何分析？ 3. 二叉树层序遍历能否用DFS实现？有何优缺点？ 4. 如何优化动态规划算法的空间复杂度（如滚动数组）？[^1] --- **建议**：建议系统刷题时重点关注动态规划、树操作、字符串处理等高频题型，并注重代码边界条件测试[^1][^2]。