华为嵌入式软件实习笔试3

《嵌入式软件开发笔试与面试手册》：https://blog.nowcoder.net/zhuanlan/jvN8gj

《嵌入式软件笔试-23年真题汇总》：https://blog.nowcoder.net/zhuanlan/0oDWVm

获取公共链表片段

给定两个链表，获取两者中相同节点值的最大连续片段。如果没有公共片段，返回-1。

解答要求

时间限制: C/C++ 1000ms,其他语言: 2000ms内存限制: C/C++ 256MB, 其他语言: 512MB

输入

第一行表示链表1，第二行表示链表2，每条链表长度不超过20个元素，链表不会为空。

输出

公共链表片段

样例1

输入

1 2 2 3 9 1 5

9 2 2 3 6 8

输出

2 2 3

#include <iostream>
#include <string>
#include <set>
using namespace std;

int main() {
    string nums1, nums2;
    getline(cin, nums1);
    getline(cin, nums2);

    set<string> s;
    int n = nums1.size(), m = nums2.size();

    // 存储所有可能的子字符串到集合中
    for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j) {
            s.insert(nums1.substr(i, j - i + 1));
        }
    }

    string res = "";
    // 查找最长的公共子字符串
    for (int i = 0; i < m; ++i) {
        for (int j = i; j < m; ++j) {
            string sub = nums2.substr(i, j - i + 1);
            if (s.find(sub) != s.end() && sub.size() > res.size()) {
                res = sub;
            }
        }
    }

    if (!res.empty()) {
        cout << res << endl;
    } else {
        cout << -1 << endl;
    }

    return 0;
}

矿车运输成本

露天矿采矿作业的特点是规模大，矿石和废料的移动量达到百万吨，运输成本开销较大，需要寻求一种最优的运输路径节省成本。

已知矿场可以划分成N*M的网格图，每个网格存在地形的差异，因此通过不同网格时，成本开销存在差异。

网格有以下5种类型：

1、标志为'S’的网格为运输起点；

2、标志为'E”的网格时运输终点；

3、标志为'B’的网格为阻塞点，不允许通行；

4、标志为'C'的网格为检查点，矿车在运输路径中，至少需要进入一次检查点。

5、标志为‘数字”的网格，其数字表示经过该网格的成本开销。

运输矿车只能上下左右4个方向运行，不允许斜对角进入其他网格。必要时可重复进入网格。

请根据输入的网格图，寻求一条从S网格到E网格，并且至少经过一次检查点的最低成本运输路径，并输出其成本开销。

解答要求

时间限制: C/C++ 1000ms,其他语言: 2000ms内存限制: C/C++ 256MB, 其他语言: 512MB

输入

第一行：网格图的行数N[3,200]和网格图的列数M[3,200]，使用空格隔开。

第二行至第N+1行：网格图每一行的元素，可以为'S’，E’，'B'，‘C'或者数字[0,100]，并且有且仅有一个'S’和一个'E’，同时存在一个或者多个‘C'，并依次使用空格隔开。

输出：

第一行：输出运输最低成本开销。如果不存在可达通路，请输出-1

示例 1：

输入：

3 3

S 4 5

7 B 3

C 9 E

输出：

16

import heapq
from math import inf

# 读入矩阵的行数和列数
n, m = map(int, input().split())
matrix = []
# 读入矩阵内容
for _ in range(n):
    matrix.append(input().split())

def solve(st_i: int, st_j: int):
    # 初始化距离矩阵和访问状态矩阵
    distance = [[inf] * m for _ in range(n)]
    visited = [[False] * m for _ in range(n)]
    distance[st_i][st_j] = 0
    h = []
    heapq.heappush(h, [0, st_i, st_j])
    # 使用优先队列进行Dijkstra算法
    while h:
        d, i, j = heapq.heappop(h)
        if visited[i][j]: continue
        visited[i][j] = True

        # 检查四个方向上的相邻单元
        for ni, nj in ((i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)):
            if ni < 0 or nj < 0 or ni >= n or nj >= m or visited[ni][nj] or matrix[ni][nj] == 'B':
                continue
            w = 0
            if matrix[ni][nj] in ('C', 'E', 'S'):
                w = 0
            else:
                w = int(matrix[ni][nj])

            # 更新最短路径
            if distance[ni][nj] > distance[i][j] + w:
                distance[ni][nj] = distance[i][j] + w
                heapq.heappush(h, [distance[ni][nj], ni, nj])

    return distance

# 找到所有'C'位置
C = []
for i in range(n):
    for j in range(m):
        if matrix[i][j] == 'C':
            C.append([i, j])

# 初始化结果为无限大
res = inf
si, sj, ei, ej = 0, 0, 0, 0
# 寻找起始点'S'和结束点'E'
for i in range(n):
    for j in range(m):
        if matrix[i][j] == 'S':
            si, sj = i, j
        elif matrix[i][j] == 'E':
            ei, ej = i, j

# 计算从'C'经过起始点到终点的最短路径
for ci, cj in C:
    dis = solve(ci, cj)
    if dis[si][sj] == inf or dis[ei][ej] == inf:
        continue
    else:
        res = min(res, dis[si][sj] + dis[ei][ej])

# 输出结果
if res == inf:
    print(-1)
else:
    print(res)

最优索引选择

某项目组打算使用建立索引方法提升数据库系统的性能。

已知当前数据库系统存在N个表，并且已经通过实际业务workload测试，得到了各个表进行索引的实用值（收益），以及索引的空间开销。

我们把索引分成若干个索引组，所有索引组构成一个树型结构，每个索引组作为树的一个节点。并且挑选索引时有以下两个约束：

1、父子依赖：当从某个索引组节点中挑选索引，则需要保证其父节点至少存在一个索引已经被挑选。题目保证树的正确性，并且保证父节点的组编号，小于子节点的组编号。

2、路径互斥：不同路径上的索引组存在互斥。当挑选了某个路径上的索引，则不能挑选其他不在该路径上的索引。

如下图，根据父子依赖约束，假设挑选组路径为[0，1，3]，当挑选组3里面的索引，需要保证组1里至少有一个索引已被挑选，同样需要保证组0里至少有一个索引已经被挑选。然后根据路径互斥约束，组3和组2不在同一个路径里，挑选了组3里面的索引，则不能再挑选组2里面的索引。

请根据每个表的索引的实用值、空间开销、组的依赖关系和组的互斥关系，选择若干个索引，保证所选的索引总空间开销不超过给定的空间闽值 B 的前提下，使得总实用值最大，并输出这个最大值。

解答要求

时间限制: C/C++ 2000ms,其他语言: 4000ms内存限制: C/C++ 256MB, 其他语言: 512MB

输入：

第一行3个整数（单空格间隔），依次表示：空间阈值B [1,5000］、表索引的数量N [1,10000］，和分组数量M[1,100]（组编号从0开始依次递增）。

第二行至第N+1行每行3个整数（单空格间隔），依次表示每个表索引的组编号、实用值和空间开销。

第N+2行M个整数（单空格间隔），从组0开始依次为每个组的父组编号；若值为-1，表示无父（该组即为根节点）。

输出

第一行：输出最大的总实用值

示例 1：

输入：

40 4 2

0 10 10

1 30 10

0 5 20

1 60 40

-1 0

输出：

45

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int B, N, M;
vector<vector<pair<int, int>>> nodes; // 节点将存储成对的（价值，成本）
vector<int> fa; // 父数组
vector<vector<int>> graph; // 图来存储子节点
vector<vector<int>> dp; // dp表用于记忆化

void dfs(int node, int cst) {
    vector<int> f(cst + 1, 0); // 当前节点计算的临时数组
    vector<pair<int, int>>& curIndexs = nodes[node];
    int n = curIndexs.size();

    for (int i = 1; i <= n; ++i) {
        for (int j = cst; j >= curIndexs[i-1].second; --j) {
            f[j] = max(f[j], f[j - curIndexs[i-1].second] + curIndexs[i-1].first);
        }
    }
    dp[node][cst] = f[cst]; // 在当前预算下存储当前节点的最大值
    
    for (int nx : graph[node]) {
        int cur = 0;
        for (int j = 0; j <= cst; ++j) {
            dfs(nx, cst - j);
            if (f[j] != 0) {
                cur = max(cur, f[j] + dp[nx][cst - j]);
            }
        }
        dp[node][cst] = max(dp[node][cst], cur);
    }
}

int main() {
    cin >> B >> N >> M;
    nodes.assign(M, vector<pair<int, int>>());
    graph.assign(M, vector<int>());
    dp.assign(M, vector<int>(B + 1, 0));

    for (int i = 0; i < N; ++i) {
        int idx, val, cst;
        cin >> idx >> val >> cst;
        nodes[idx].push_back({val, cst});
    }

    fa.resize(M);
    int root = -1;
    for (int i = 0; i < M; ++i) {
        cin >> fa[i];
        if (fa[i] == -1) {
            root = i;
        } else {
            graph[fa[i]].push_back(i);
        }
    }

    dfs(root, B);

    cout << dp[root][B] << endl;
    return 0;
}