华为机试特点

了解其特点是高效备考的第一步。

1. 难度较高：题目通常不是简单的“模板题”，而是需要进行一定的分析、转化和优化的题目，很多问题本质上是经典算法的变种或组合。
2. 时间压力大：通常时长为 60-90 分钟，题目数量在 3-5 道左右，时间非常紧张，要求你不仅要会做，还要做得快。
3. 输入/输出模式：需要自己处理输入和输出，不能依赖 IDE 的调试，输入格式可能比较复杂（如多组数据、文件结尾 EOF 等），输出格式要求严格（如空格、换行）。
4. 偏向工程思维：除了算法，华为也很看重代码的健壮性、边界条件处理和代码风格，一个能通过所有测试用例的、优雅的解决方案比一个暴力解法更受欢迎。
5. 知识点覆盖广：
   • 基础数据结构与算法：数组、字符串、链表、栈、队列、哈希表、排序、二分查找。
   • 高级数据结构：树（二叉树、Trie树、AVL树）、图（DFS、BFS、最短路径、最小生成树）。
   • 动态规划：这是华为机试的绝对重点和难点，每年必考，且题目形式多变。
   • 贪心算法：与 DP 经常一起出现，需要判断问题是否具有贪心性质。
   • 字符串处理：KMP、字符串匹配、正则表达式等。
   • 模拟题：根据题意进行逻辑模拟，考察代码实现能力。
   • 数学问题：数论、组合数学、概率等。

备考策略与建议

1. 打牢基础，系统复习

   • 数据结构：确保对常见数据结构的原理、时间/空间复杂度、适用场景了如指掌，特别是链表、树、图，要能随手写出核心操作的代码。
   • 算法思想：重点攻克 动态规划 和 贪心算法，DP 是重中之重，需要大量练习来培养“状态定义”和“状态转移方程”的思维能力，贪心算法则要多做总结，判断其是否适用。
   • 刷题平台：以 LeetCode 为主，不要只刷简单题，中等难度的题是主力。

2. 专项突破，华为特色

   • 动态规划：在 LeetCode 上专门刷“动态规划”标签的题目，从简单的爬楼梯、打家劫舍开始，逐步进阶到编辑距离、背包问题、区间 DP 等。
   • 字符串处理：熟悉字符串的各种操作，以及 KMP 算法的思想和实现。
   • 输入输出练习：在牛客网等平台多练习，熟练掌握如何读取多组数据、如何处理 EOF、如何控制输出格式。

3. 模拟实战，提升速度

   • 使用牛客网：牛客网是华为机试最主要的官方合作平台，上面有大量的华为历年真题和模拟题。
   • 严格计时：给自己设定 60-90 分钟的时限，完整地做 3-5 道题，这能帮你合理分配时间，并练习在压力下编码。
   • 复盘总结：做完题后，无论对错，都要看题解，学习更优的解法，思考自己为什么没做出来（是思路问题、边界问题还是代码实现问题？）。

4. 代码规范与健壮性

   • 命名规范：变量名、函数名要清晰易懂。
   • 边界处理：时刻考虑空输入、只有一个元素、元素重复、数值越界等特殊情况。
   • 异常处理：虽然机试不要求，但写出健壮的代码是工程师的基本素养。

真题示例与解析

华为的题库很大,且每年会更新，但很多题目是“新瓶装旧酒”，下面列举几个经典的、有代表性的题目类型。

示例1：动态规划类（经典背包问题）

描述**： 有 N 件物品和一个容量为 V 的背包，第 i 件物品的体积是 vi，价值是 wi，求解将哪些物品装入背包可使这些物品的总体积不超过背包容量，且总价值最大。

输入： 第一行是两个整数 N 和 V，用空格隔开，分别表示物品的数量和背包的容量。 接下来有 N 行，每行两个整数 vi 和 wi，用空格隔开，分别表示第 i 件物品的体积和价值。

输出： 输出一个整数，表示最大价值。

思路解析： 这是一个 0-1 背包问题 的标准模板题，使用动态规划解决。

1. 定义状态：dp[i][j] 表示只考虑前 i 件物品，背包容量为 j 时可以获得的最大价值。
2. 状态转移方程：
   • 对于第 i 件物品，我们有两种选择：放或不放。
   • 不放：dp[i][j] = dp[i-1][j]
   • 放：前提是 j >= vi，dp[i][j] = dp[i-1][j - vi] + wi
   • 取两种情况的最大值：dp[i][j] = max(dp[i-1][j], dp[i-1][j - vi] + wi)
3. 初始化：dp[0][j] = 0 (没有物品时价值为0)，dp[i][0] = 0 (容量为0时价值为0)。
4. 空间优化：注意到 dp[i] 只与 dp[i-1] 有关，可以将二维数组优化为一维数组，倒序遍历容量 j 即可。

Python 代码示例：

def solve():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    v = int(data[1])
    volumes = []
    values = []
    index = 2
    for i in range(n):
        vi = int(data[index])
        wi = int(data[index + 1])
        index += 2
        volumes.append(vi)
        values.append(wi)
    # 一维DP数组优化
    dp = [0] * (v + 1)
    for i in range(n):
        # 倒序遍历，保证每个物品只被使用一次
        for j in range(v, volumes[i] - 1, -1):
            dp[j] = max(dp[j], dp[j - volumes[i]] + values[i])
    print(dp[v])
solve()

示例2：字符串处理类（简单模拟）

描述 给定一个字符串 s，请你反转字符串中单词的顺序。 单词是由非空格字符组成的字符串，s 中使用至少一个空格将单词分隔。 返回**：反转单词顺序后的字符串。

输入： "the sky is blue"

输出： "blue is sky the"

思路解析： 这是一个字符串处理的经典模拟题，考察对字符串 API 的熟练使用。

1. 去除多余空格：字符串开头、结尾以及单词之间可能有多个空格，需要先处理成规范的格式（如 "the sky is blue"）。
2. 反转整个字符串：先将整个字符串反转，得到 "eulb si yks eht"。
3. 反转每个单词：再遍历字符串，逐个反转每个单词，得到 "blue is sky the"。

Python 代码示例：

def reverseWords(s: str) -> str:
    # 1. 去除首尾空格并分割成单词列表
    words = s.strip().split()
    # 2. 反转单词列表
    words.reverse()
    # 3. 用空格连接成字符串
    return ' '.join(words)
# 测试
input_str = "the sky is blue"
print(reverseWords(input_str)) # 输出: blue is sky the

示例3：图论类（BFS/DFS）

描述**： 给定一个 m x n 的二维网格 grid，网格中的每个单元格要么是 '1'（陆地）要么是 '0'（水），岛屿是由水平或垂直方向上相邻的 '1' 组成的最大连通块，假设 grid 的四个边缘都被水包围，请你计算岛屿的数量。

输入： grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ]

输出： 1

思路解析： 这是一个典型的 岛屿问题，可以使用 DFS 或 BFS 来解决。

1. 遍历网格：从 (0, 0) 开始，遍历网格中的每一个单元格。
2. 发现陆地：当发现一个值为 '1' 的陆地时，岛屿数量 count 加 1。
3. 感染/淹没：以这个单元格为起点，进行 DFS 或 BFS，将所有相连的陆地都标记为 '0'（或者一个特殊标记），表示这部分陆地已经被访问过，属于同一个岛屿。
4. 继续遍历：继续遍历网格，直到所有单元格都被访问过。

Python 代码示例 (DFS)：

def numIslands(grid):
    if not grid or not grid[0]:
        return 0
    rows, cols = len(grid), len(grid[0])
    count = 0
    def dfs(r, c):
        # 递归终止条件：越界或遇到水
        if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] == '0':
            return
        # 标记为已访问，避免重复计数
        grid[r][c] = '0'
        # 递归访问上下左右四个方向
        dfs(r - 1, c)
        dfs(r + 1, c)
        dfs(r, c - 1)
        dfs(r, c + 1)
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)
    return count
# 测试
grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
print(numIslands(grid)) # 输出: 1

推荐资源

1. 刷题平台：

   • 牛客网：首选！ 上面有华为历年真题、模拟题、在线编程环境，是备战华为机试的核心平台。
   • LeetCode：用于系统性地练习算法和数据结构，巩固基础，特别是“剑指 Offer”和“Hot 100”系列。

2. 书籍推荐：

   • 《剑指 Offer》：经典中的经典，包含大量面试真题，思路清晰。
   • 《算法（第4版）》：算法和数据结构的圣经，内容全面，适合深入理解。
   • 《挑战程序设计竞赛》：日本经典算法竞赛教材，题目质量高，对提升思维能力很有帮助。

3. GitHub 项目：

   • 在 GitHub 上搜索 huawei-od、nowcoder-huawei 等关键词，可以找到很多大佬整理的题解和代码仓库。

祝你备考顺利，成功拿到华为的 Offer！ 刷题是量变到质变的过程，坚持下去，你一定能行。