华为暑期实习 2023.05.24 机试题目与题解

发表于 2023-06-02 更新于 2023-11-11 分类于笔试阅读次数：本文字数： 2.5k 阅读时长 ≈ 2 分钟

1、连续空闲内存合并管理

动态内存管理根据用户的需求分配任意大小的内存，当用户释放内存时，被释放的内存回到池 (堆) 中供其他用户使用。

现设计某实时操作系统计划的内存管理功能，请你实现被释放内存的回收合并模块，当经过一次内存释放操作后，请返回当前最大的连续内存块的起始位置，以及此连续内存的数量 (块数)。

若存在多个最大连续内存块，则返回编号最小的内存块信息。当前已经把连续内存，按块进行连续编号。

输入

输入：1,3,2,5 表示释放四块内存，ID 分别为 1.3.2.5，每块内存的大小为 1 个单位 [预制条件]

函数执行前，所有内存均已被申请完毕，无空闲，不需考虑内存重复释放 [取值范围]

内存 ID 编号: $0 < I D < 2^{31} - 1$ ，单次释放的内存个数 $< 10000$

输出

输出：1,3 经过回收处理后，当前可用的最大连续内存大小 3，以及此内存的起始编号 1.

说明：1,3,2,5 四块内存，前面三块 1,3,2 为连续内存，合并后的连续内存数为 3 个单位起始编号为 1，因此返回 1,3。

样例

输入：
1,3,2,5

输出：
1,3

提示：1,3,2,5四块内存，前面三块1,3,2为连续内存，合并后的连续内存数为3个单位。起始编号为1，因此返回1,3。

输入：
2,4,3,7,6

输出：
2,3

提示：
2,4,3,7,6，表示释放了5块内存，内存块编号分别为2、4、3、7、6。
经过回收合并后，2、3、4三块内存连续，可以合并为一块大内存，大小为3个单位。
6、7两块内存连续，合井后的连续内存大小为2。
因此返回此时的最大连续内存的起始位置为2，内存大小为3。

解答

将整个数组进行排序，然后使用双指针 $i, j$ 求得一个极长的相邻元素差为 $1$ 的子数组 $A [i : j]$ 即可。需要注意的是，如果枚举的两个子数组长度恰好相等，那么需要取前面一个，因此这里使用大于号 $>$ 来找到第一个满足条件最长的数组。

代码

a = sorted(map(int, input().split(',')))
pos, cnt = 0, 0
i = 0
while i < len(a):
    j = i + 1
    while j < len(a) and a[j] - a[j - 1] == 1:
        j += 1
    if j - i > cnt:
        pos, cnt = a[i], j - i
    i = j
print("{},{}".format(pos, cnt))

2、海量日志抑制

程序运行日志是重要的运维手段，需要尽量记录下有效信息，避免无效日志，而 “海量日志” 就是一种比较典型的日志使用问题：

大量打印相同或相似的内容，将有效日志淹没，还可能降低系统运行效率。

因此，需要 “海量日志” 抑制机制，避免系统运行时产生 “海量日志” 问题。

“海量日志” 定义: 10ms 内 (<10ms) 打印 2 条相同日志 (包含第 2 条均需要被抑制)，即：仅保留第一条或 100ms 内 (<100ms) 打印 10 条相似日志 (去除数字后完全相同的两条日志认为是 “相似”，包含第 10 条均需要被抑制)，即：仅保留前 9 条。

日志抑制的理解：被抑制的日志，不记录到日志文件中。

输入

本用例的日志条数 (最大不超过 1000 条) 时间截：日志打印内容

约束

时间戳单位是 ms，用 32 位无符号 10 进制整数表示；
用例保证后一条日志时间戳不小于前一条；
一条日志打打印只占一行，一条日志内容不超过 1024Bytes;
用例保证 1s 内 (<1s)，最多 100 条日志；
数字均为正整数。

输出

时间戳：日志打印内容输出需要除去被抑制的日志。

样例

输入：
4
123:This is a log
123:This is a log
136:This is a new log
138:This is a new log

输出：
123:This is a log
136:This is a new log

提示：第二条“123:This is a log”以及“136:This is a new log”被抑制，因为满足“相同日志”抑制规则。

解答

先读取每一条日志，然后按照日志内容，将时间戳和日志下标归类好（分别按照相同和相似的方式）。至于相似字符串的求解，可以使用正则表达式对字符串中的所有数字进行去除。最终归类到两个字典 mp_s, mp_l 中。

这些字典的 key 是日志本身，val 是一个列表，按时间戳顺序存储着 (时间戳，日志下标) 二元组。遍历这些二元组，判断它们相同时是否和前一条记录是否超过 $10 ms$ （类似的，相似时是否超过 $100 ms$ ）并对日志进行标记。

最终，通过每一条标记表示日志是否应该输出。

代码

import re
from collections import defaultdict

n = int(input())
record = []
mp_s = defaultdict(list)
mp_l = defaultdict(list)
for i in range(n):
    s = input()
    record.append(s)
    tm, same = s.split(':')
    tm = int(tm)
    like = re.sub(r'\d+', '', same)
    mp_s[same].append((tm, i))
    mp_l[like].append((tm, i))
flag = [True for _ in range(n)]
for _, ls in mp_s.items():
    for i in range(len(ls) - 1):
        if ls[i + 1][0] - ls[i][0] < 10:
            flag[ls[i + 1][1]] = False
for _, ls in mp_l.items():
    for i in range(len(ls) - 9):
        if ls[i + 1][0] - ls[i][0] < 100:
            flag[ls[i + 1][1]] = False
for i in range(n):
    if flag[i]:
        print(record[i])

3、网络升级改造

由于软件技术的提升，原有部署网络中某些节点可以撤掉，这样可以简化网络节省维护成本。

但是要求撤掉网络节点时，不能同时撤掉原来两个直接相互连接的节点。

输入的网络是一个满二叉树结构，每个网络节点上标注一个数值，表示该节点的每年维护成本费用。

给定每个输入网络，按照要求撤掉某些节点后，求出能够节省的最大的维护成本。

输入

第一行：一个正整数 N，表示后面有 N 个数值。1<=N<=10000

第二行：N 个非负整数，表示网络节点每年的维护成本，按照满二又树的” 广度优先遍历序号” 给出。 0 表示不存在该关联节点，0 只会存在于叶子节点上。每个数字的取值范围为 [0,1000]

第一行输入：7，表示后面有 7 个数字。

第二行输入：5 3 5 0 6 0 1，表示网络节点每年的维护成本，按照满二叉树的 “广度优先遍历序号” 给出。

0 表示不存在该关联节点。

输出

能够节省的最大的维护成本。

样例

输入：
7
5 3 5 0 6 0 1

输出：
12

提示：
第一行输入:7，表示后面有7个数值
第二行输入:5 3 5 0 6 0 1，表示“表示网络节点每年的维护成本，按照满二又树的度优先遍历序号”给出。
输出：12，能够节省的最大维护成本：5+6+1

输入：
7
2 7 8 2 4 9 2

输出：
19

解答

这是一道树上动态规划的题目，为力扣 337 的特殊版本题。由于这棵树是一棵满二叉树，因此对于一个节点 $i$ ，如果他有左子节点，那么编号为 $l_{i} = 2 i$ ；如果它有右子节点，那么编号为 $r_{i} = 2 i + 1$ 。

令状态 $f_{i, 0}$ 表示节点 $i$ 没有被撤掉的情况下，以 $i$ 为根节点的子树中，最大能够节省的成本；类似的，令状态 $f_{i, 1}$ 表示节点 $i$ 有被撤掉的情况下，以 $i$ 为根节点的子树中，最大能够节省的成本，那么可以写出关于 $f_{i, 0}, f_{i, 1}$ 的状态转移方程：

$\begin{aligned} f_{i, 0} & = max (f_{l_{i}, 0}, f_{l_{i}, 1}) + max (f_{r_{i}, 0}, f_{r_{i}, 1}) \\ f_{i, 1} & = f_{l_{i}, 0} + f_{r_{i}, 0} + a [i] \end{aligned}$

如果 $f$ 的第一个下标 $i$ 超出了范围，那么为了方便实现，假定为 $f_{i, 0} = f_{i, 1} = 0$ 。

第一条方程，由于当且节点 $i$ 是不被撤走的，因此左子节点 $l_{i}$ 是否被撤走并没有所谓，我们取最优的一个，即 $max (f_{l_{i}, 0}, f_{l_{i}, 1})$ ；类似的，右子节点是否被撤走也没有所谓，因此取最优的一个，即 $max (f_{r_{i}, 0}, f_{r_{i}, 1})$ 。左子树和右子树的取法是独立的，因此将两边的式子相加就得到第一条方程。

第二条方程，由于当且节点 $i$ 是被撤走的，因此左子节点 $l_{i}$ 不能被撤走，取 $f_{l_{i}, 0}$ ；类似的，右子节点 $l_{i}$ 不能被撤走，取 $f_{r_{i}, 0}$ 。再加上根节点自身被撤走的价值 $a [i]$ ，得到原来的方程。

节点 $1$ 是整棵树的根，因此最优答案为 $max (f_{1, 0}, f_{1, 1})$ 。

代码

# include <bits/stdc++.h>
using namespace std;

const int N=20004;
int f[N][2],n,a[N];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=n;i>=1;i--){
        int l=2*i,r=2*i+1;
        f[i][0]=max(f[l][0],f[l][1])+max(f[r][0],f[r][1]);
        f[i][1]=f[l][0]+f[r][0]+a[i];
    }
    int ans=max(f[1][0],f[1][1]);
    printf("%d\n",ans);
}