跳到内容
当前位置:首页>面试真题>华为机试面试真题

华为机试面试真题

  • 2026-11-21 03:39:01
华为机试面试真题

题目名称

1、水晶的魔力之和

题目背景与描述

在古老星界的边缘,藏着一座由魔法水晶排成的长阵。每一颗水晶都蕴含着或正或负的魔力,它们连成一条永不间断的光之轨迹。传说中,只有连续一段水晶的魔力之和,恰好等于星轨密钥 k 时,这段水晶才会共鸣发光,形成一道稳定封印,守护这片魔法领域。

你是被选中的星轨巫师,现在需要:

  • 找出一共有多少道这样的稳定封印;

  • 在所有能形成封印的连续水晶中,找到最短的那一段,它由多少颗水晶构成?

若不存在任何能形成封印的水晶段,则次数记为 0,最短长度记为 -1。

数据范围

  • 1≤n≤2×1051≤n≤2×105

  • −−109≤ 每颗水晶的魔力值 ≤109

  • −2×1014≤k≤2×1014

  • 连续一段水晶 指长度不小于 1 的连续子段

  • 触发封印的次数最大可达 n(n+1)/2=2×1010   n(n+1)/2=2×1010,请使用 64 位整数存储与输出

解答要求

  • 时间限制:C/C++ 2000ms,其他语言 4000ms

  • 内存限制:C/C++ 512MB,其他语言 1024MB

输入描述

第一行:整数 n(水晶数量)和整数 k(目标魔力和)第二行:n 个整数,表示每颗水晶的魔力值

输出描述

一行两个整数:触发封印的次数、最短封印长度(若无合法封印,次数为 0,最短长度输出 -1)

样例 1

输入:

text

5 3
1 -1 5 -2 3

输出:

text

3 1

解释: 第 1-4 颗水晶:1+(−1)+5+(−2)=3(长度 4)

简化一下题目

对于这个题目解决的办法是

通过排序之后去查找l-r的最小值,当我们的l越小也就在当前r数组下所取得的长度就最小
#include<iostream>// 引入输入输出流库,用于 cin 和 cout#include<vector>// 引入动态数组 vector 容器库#include<climits>// 引入包含 INT_MAX 等常量限制的库using namespace std;      // 使用标准命名空间,省去 std:: 前缀intmain(){              // 程序主函数入口    ios::sync_with_stdio(false); // 关闭 C 和 C++ 标准流的同步,加快 cin/cout 速度    cin.tie(nullptr);            // 解除 cin 和 cout 的绑定,进一步提高输入输出效率    int n;                // 声明整型变量 n,用于存储数组的长度    long long k;          // 声明长整型变量 k,用于存储目标子数组的和(因为累加可能超出 int 范围)    if (!(cin >> n >> k)) return 0; // 尝试读取 n 和 k,如果读取失败(如文件结束)则程序直接退出    vector<longlong> a(n); // 创建一个大小为 n 的长整型 vector 数组 a    for (int i = 0; i < n; ++i) cin >> a[i]; // 循环 n 次,将输入的数字逐个存入数组 a 中    long long total_count = 0; // 初始化满足条件的子数组总个数为 0(使用 long long 防止溢出)    int min_len = INT_MAX;     // 初始化最短子数组长度为整型最大值(方便后续比较取较小值)    // 暴力枚举所有连续子数组    for (int i = 0; i < n; ++i) {           // 外层循环:枚举子数组的起始位置 i        long long sum = 0;                  // 每次更换起始位置时,将当前子数组的累加和清零        for (int j = i; j < n; ++j) {       // 内层循环:枚举子数组的结束位置 j(从 i 开始向后延伸)            sum += a[j];                    // 将当前元素 a[j] 累加到 sum 中            if (sum == k) {                 // 如果当前累加和恰好等于目标值 k                ++total_count;              // 满足条件的子数组总个数加 1                min_len = min(min_len, j - i + 1); // 计算当前子数组长度 (j-i+1),并与历史最短长度比较,保留较小值            }        }    }    if (total_count == 0)                   // 如果遍历完所有子数组,都没有找到符合条件的情况        cout << "0 -1\n";                   // 按照题目要求,输出 "0 -1" 并换行    else                                    // 如果存在符合条件的子数组        cout << total_count << " " << min_len << "\n"; // 输出总个数和最短长度,中间用空格隔开,最后换行    return 0;                               // 主函数正常结束,返回 0}

    C++暴力实现该后会出现超时,因此基于哈希表进行优化

#include<iostream>#include<vector>#include<unordered_map>#include<climits>using namespace std;intmain(){    ios::sync_with_stdio(false);    cin.tie(nullptr);    int n;    long long k;    if (!(cin >> n >> k)) return 0;    vector<longlong> a(n);    for (int i = 0; i < n; ++i) cin >> a[i];    // 记录前缀和值 -> 出现过的所有下标(用 vector 存,方便遍历求最短长度)    unordered_map<long long, vector<int>> mp;    mp.reserve(n * 2);                // 预分配,减少 rehash    mp.max_load_factor(0.7);    mp[0].push_back(0);               // 空前缀,和为 0,下标 0(这里 pre 的下标 0 表示“没有元素”)    long long total_count = 0;    int min_len = INT_MAX;    long long pre = 0;    for (int i = 1; i <= n; ++i) {        pre += a[i - 1];              // pre 表示前 i 个元素的和        long long target = pre - k;        auto it = mp.find(target);        if (it != mp.end()) {            // 遍历所有满足 pre[l] = pre[i] - k 的左端点 l            for (int l : it->second) {                ++total_count;                min_len = min(min_len, i - l);   // 子数组长度 = i - l            }        }        // 把当前前缀和加入表        mp[pre].push_back(i);    }    if (total_count == 0)        cout << "0 -1\n";    else        cout << total_count << " " << min_len << "\n";    return 0;}

前缀和加哈希表的计算复杂度为O(n)

下面看一看第二个问题

【华为校园招聘 软件】 2、元素法师的最终试炼

迷宫规则详解:
迷宫由 n×mn×m 个房间组成,每个房间蕴含一种元素能量(0-9)。
法师只能向右或向下移动,从左上角 (0,0) 出发,抵达终点——右下角的封印法阵 (n−1,m−1)。

规则1:
沿途收集的元素能量必须恰好等于 T 点。(太少无法形成封印,太多则会引发能量反噬)

规则2:

  • 阳炎元素(奇数能量值,如1,3,5,7,9):炽热狂暴的红色元素。

  • 寒冰元素(偶数能量值,如2,4,6,8):冰冷沉寂的蓝色元素。

  • 混沌元素(能量值为0):温和中立的灰色元素。

连续收集同种元素会致命:

  • 连续激活两个阳炎元素(奇数),炽热的能量会将你焚烧。

  • 连续收集两个寒冰元素(偶数非零),极寒的能量会将你冻结。

  • 特别地,混沌元素(0)不属于阳炎也不属于寒冰,它没有任何限制。混沌元素可以与任何元素(包括另一个混沌元素)相邻,连续经过任意多个混沌元素都是安全的。

问题:
年轻的法师,在这危机四伏的迷宫中,你有多少种方法能够安全抵达封印法阵(即迷宫终点右下角),并积累恰好 T 点能量?

解答要求:

  • 输入: 第一行三个整数 n,m,T (1≤n,m≤15,0≤T≤100);接下来 n行,每行 m个0-9的整数,表示迷宫各房间的元素能量值。

  • 输出: 一个整数,表示满足所有生存条件的路径数量。


python方式的实现
import sys  # 导入 sys 模块,用于读取标准输入def solve():    # 从标准输入读取全部内容并按空白字符切分,返回字符串列表    input_data = sys.stdin.read().split()    # 如果输入为空,直接返回    if not input_data:        return    # 依次解析 n(行数)、m(列数)、T(目标能量值)    n = int(input_data[0])    m = int(input_data[1])    T = int(input_data[2])    # 初始化迷宫二维列表    grid = []    idx = 3  # 从输入数据列表的第 3 个下标开始读取迷宫元素    for _ in range(n):  # 逐行读取        row = []  # 当前行        for _ in range(m):  # 逐列读取            row.append(int(input_data[idx]))  # 转为整数并加入当前行            idx += 1  # 下标后移        grid.append(row)  # 将当前行加入迷宫    # dp[i][j][k][s] 表示:    # 走到坐标 (i,j) 时,累计能量为 k,且上一个元素的类型为 s 的路径数量    # s 的含义:0 -> 混沌元素(0) 或无上一步(起点);1 -> 阳炎元素(奇数);2 -> 寒冰元素(偶数非零)    # 使用四维列表,维度依次为 n、m、T+1、3    dp = [[[[0] * 3 for _ in range(T + 1)] for _ in range(m)] for _ in range(n)]    # 辅助函数:根据元素数值判断其类型    def get_type(val):        if val == 0:  # 混沌元素            return 0        elif val % 2 == 1:  # 奇数 -> 阳炎            return 1        else:  # 偶数且非零 -> 寒冰            return 2    # 初始化起点 (0,0)    start_val = grid[0][0]  # 起点元素值    if start_val <= T:  # 如果起点能量已超过 T,则无解,不初始化        start_type = get_type(start_val)  # 起点元素类型        dp[0][0][start_val][start_type] = 1  # 起点路径数为 1    # 遍历整个迷宫    for i in range(n):  # 枚举行        for j in range(m):  # 枚举列            if i == 0 and j == 0:  # 起点已在初始化中处理,跳过                continue            val = grid[i][j]  # 当前格子的元素值            cur_type = get_type(val)  # 当前格子的元素类型            # 从上方 (i-1, j) 转移过来            if i > 0:                for k in range(T - val + 1):  # 枚举上一个累计能量 k,保证 k + val <= T                    for prev_type in range(3):  # 枚举上一步的元素类型                        if dp[i - 1][j][k][prev_type] > 0:  # 如果该状态可达                            # 根据当前类型和上一步类型判断是否合法                            if cur_type == 0:  # 当前是混沌元素,无任何限制                                dp[i][j][k + val][0] += dp[i - 1][j][k][prev_type]                            elif cur_type == 1 and prev_type != 1:  # 阳炎,且上一步不是阳炎                                dp[i][j][k + val][1] += dp[i - 1][j][k][prev_type]                            elif cur_type == 2 and prev_type != 2:  # 寒冰,且上一步不是寒冰                                dp[i][j][k + val][2] += dp[i - 1][j][k][prev_type]            # 从左方 (i, j-1) 转移过来            if j > 0:                for k in range(T - val + 1):  # 枚举上一个累计能量 k                    for prev_type in range(3):  # 枚举上一步的元素类型                        if dp[i][j - 1][k][prev_type] > 0:  # 如果该状态可达                            if cur_type == 0:  # 当前是混沌元素,无限制                                dp[i][j][k + val][0] += dp[i][j - 1][k][prev_type]                            elif cur_type == 1 and prev_type != 1:  # 当前阳炎,上一步非阳炎                                dp[i][j][k + val][1] += dp[i][j - 1][k][prev_type]                            elif cur_type == 2 and prev_type != 2:  # 当前寒冰,上一步非寒冰                                dp[i][j][k + val][2] += dp[i][j - 1][k][prev_type]    # 最终答案:到达终点 (n-1, m-1) 且能量恰好为 T 的所有状态之和    ans = sum(dp[n - 1][m - 1][T])    print(ans)  # 输出结果if __name__ == "__main__":    solve()  # 调用主函数
c++的实现方案
#include<iostream>// 用于输入输出#include<vector>// 用于动态数组using namespace std;// 辅助函数:根据元素值判断类型// 返回 0 表示混沌元素(0),1 表示阳炎(奇数),2 表示寒冰(偶数非零)intgetType(int val){    if (val == 0) return 0;    if (val % 2 == 1) return 1;    return 2;}intmain(){    ios::sync_with_stdio(false); // 关闭同步,加速输入输出    cin.tie(nullptr);            // 解除 cin 与 cout 的绑定,进一步加速    int n, m, T;    cin >> n >> m >> T;  // 读取行数、列数、目标能量值    // 读取迷宫数据    vector<vector<int>> grid(n, vector<int>(m));    for (int i = 0; i < n; ++i) {        for (int j = 0; j < m; ++j) {            cin >> grid[i][j];        }    }    // dp[i][j][k][s]:到达 (i,j) 时累计能量为 k,且上一元素类型为 s 的路径数    // s:0 -> 混沌/无,1 -> 阳炎,2 -> 寒冰    // 使用四维 vector 动态分配,维度依次为 n、m、T+1、3    vector<vector<vector<vector<long long>>>> dp(        n, vector<vector<vector<long long>>>(               m, vector<vector<long long>>(                      T + 1, vector<long long>(3, 0))));    // 初始化起点    int startVal = grid[0][0];    if (startVal <= T) {  // 起点能量不能超过 T        int startType = getType(startVal);        dp[0][0][startVal][startType] = 1;    }    // 遍历整个迷宫    for (int i = 0; i < n; ++i) {        for (int j = 0; j < m; ++j) {            if (i == 0 && j == 0) continue;  // 起点已处理            int val = grid[i][j];       // 当前格子元素值            int curType = getType(val); // 当前元素类型            // 从上方 (i-1, j) 转移            if (i > 0) {                for (int k = 0; k <= T - val; ++k) {  // 保证 k + val <= T                    for (int prevType = 0; prevType < 3; ++prevType) {                        long long ways = dp[i - 1][j][k][prevType];                        if (ways == 0) continue;  // 不可达则跳过                        // 根据当前类型和上一类型判断合法性                        if (curType == 0) {                            dp[i][j][k + val][0] += ways;                        } else if (curType == 1 && prevType != 1) {                            dp[i][j][k + val][1] += ways;                        } else if (curType == 2 && prevType != 2) {                            dp[i][j][k + val][2] += ways;                        }                    }                }            }            // 从左方 (i, j-1) 转移            if (j > 0) {                for (int k = 0; k <= T - val; ++k) {  // 保证 k + val <= T                    for (int prevType = 0; prevType < 3; ++prevType) {                        long long ways = dp[i][j - 1][k][prevType];                        if (ways == 0) continue;  // 不可达则跳过                        if (curType == 0) {                            dp[i][j][k + val][0] += ways;                        } else if (curType == 1 && prevType != 1) {                            dp[i][j][k + val][1] += ways;                        } else if (curType == 2 && prevType != 2) {                            dp[i][j][k + val][2] += ways;                        }                    }                }            }        }    }    // 最终答案:到达终点且能量恰好为 T 的所有状态之和    long long ans = 0;    for (int s = 0; s < 3; ++s) {        ans += dp[n - 1][m - 1][T][s];    }    cout << ans << "\n";  // 输出结果    return 0;}
#include<iostream>#include<vector>#include<cstring>using namespace std;// 获取元素类型: 0=混沌(0), 1=阳炎(奇数), 2=寒冰(偶数非0)intgetType(int val){    if (val == 0) return 0;    if (val % 2 != 0) return 1;    return 2;}intmain(){    int n, m, T;    if (!(cin >> n >> m >> T)) return 0;    vector<vector<int>> a(n, vector<int>(m));    for (int i = 0; i < n; i++) {        for (int j = 0; j < m; j++) {            cin >> a[i][j];        }    }    // dp[i][j][v][p]: 到达(i,j)总和为v且上一步类型为p的方案数    // 由于 T 可能为 0,维度要开 T+1    vector<vector<vector<vector<long long>>>> dp(        n, vector<vector<vector<long long>>>(            m, vector<vector<long long>>(                T + 1, vector<long long>(3, 0)            )        )    );    // 初始化起点    int start_val = a[0][0];    if (start_val <= T) {        dp[0][0][start_val][getType(start_val)] = 1;    }    for (int i = 0; i < n; i++) {        for (int j = 0; j < m; j++) {            if (i == 0 && j == 0) continue;            int val = a[i][j];            int cur_type = getType(val);            // 遍历所有可能的来源方向(上、左)            int dirs[2][2] = {{-1, 0}, {0, -1}};            for (int d = 0; d < 2; d++) {                int ni = i + dirs[d][0];                int nj = j + dirs[d][1];                if (ni < 0 || ni >= n || nj < 0 || nj >= m) continue;                // 遍历来源的所有可能状态                for (int v = 0; v <= T; v++) {                    for (int p = 0; p < 3; p++) {                        if (dp[ni][nj][v][p] == 0) continue;                        // 检查连续收集同种元素是否合法                        if (cur_type == 1 && p == 1) continue; // 连续阳炎                        if (cur_type == 2 && p == 2) continue; // 连续寒冰                        int new_v = v + val;                        if (new_v <= T) {                            dp[i][j][new_v][cur_type] += dp[ni][nj][v][p];                        }                    }                }            }        }    }    // 统计终点 (n-1, m-1) 且总和恰好为 T 的所有状态    long long ans = 0;    for (int p = 0; p < 3; p++) {        ans += dp[n - 1][m - 1][T][p];    }    cout << ans << endl;    return 0;}