华为暑期实习 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<ID<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\text{ms}\)（类似的，相似时是否超过\(100\text{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=2i\)；如果它有右子节点，那么编号为\(r_i=2i+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);
}