华为机试5.24，暑假实习，赶紧来练习一下

第一题：连续空闲内存合并管理

题目描述

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

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

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

输入

输入: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。

第二题：海量日志抑制

题目描述

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

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

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

“海量日志”定义:

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

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

输入

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

约束

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

输出

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

示例一

输入

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”被抑制，因为满足“相同日志”抑制规则。

第三题：网络升级改造

题目描述

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

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

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

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

输入

第一行:一个正整数 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