笔试时间：2023年5月24日 暑期实习

第一题

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

动态内存管理根据用户的需求分配任意大小的内存，当用户释放内存时，被释放的内存回到池(堆)中供其他用户使用。现设计某实时操作系统计划的内存管理功能，请你实现被释放内存的回收合并模块，当经过一次内存释放操作后，请返回当前最大的连续内存块的起始位置，以及此连续内存的数量(块数)。若存在多个最大连续内存块，则返回编号最小的内存块信息。当前已经把连续内存，按块进行连续编号。

解答要求

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

输入描述

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

1,3,2,5

示例2:

2,4,3,7,6

样例输出

示例1:

1,3

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

示例2:

2,3

解释：2,4,3,7,6，表示释放了5块内存，内存块编号分别为2、4、3、7、6。

经过回收合并后，2、3、4三块内存连续，可以合并为一块大内存，大小为3个单位

6、7两块内存连续，合井后的连续内存大小为2。

因此返回此时的最大连续内存的起始位置为2，内存大小为3输入中第二行的十六进制数0xE77F，其中只有前14个bit有效，转换为二进制序列为11100111011111

输出表示有2种补偿方案，分别是右移2个小孔和左移2个小孔，对应的’0‘/’1‘连续字符序列表示所有孔的开关状态.

参考题解

C++:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    string input;
    getline(cin, input);
    vector<int> nums;

    size_t start = 0, found = input.find(",");
    while (found != string::npos) {
        nums.push_back(stoi(input.substr(start, found - start)));
        start = found + 1;
        found = input.find(",", start);
    }
    nums.push_back(stoi(input.substr(start)));

    sort(nums.begin(), nums.end());

    int st = -1, mxlen = -1;
    int n = nums.size();
    int index = 0;

    while (index < n) {
        int i = index;
        for (int j = index + 1; j < n; j++) {
            if (nums[j] - nums[i] != 1) break;
            i++;
        }
        if (mxlen < i - index + 1) {
            mxlen = i - index + 1;
            st = index;
        }
        index = i + 1;
    }

    cout << nums[st] << "," << mxlen << endl;

    return 0;
}

Java：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine();
        String[] numsStr = input.split(",");
        List<Integer> nums = new ArrayList<>();

        for (String numStr : numsStr) {
            nums.add(Integer.parseInt(numStr));
        }

        Collections.sort(nums);

        int st = -1, mxlen = -1;
        int n = nums.size();
        int index = 0;

        while (index < n) {
            int i = index;
            for (int j = index + 1; j < n; j++) {
                if (nums.get(j) - nums.get(i) != 1) break;
                i++;
            }
            if (mxlen < i - index + 1) {
                mxlen = i - index + 1;
                st = index;
            }
            index = i + 1;
        }

        System.out.println(nums.get(st) + "," + mxlen);
    }
}

Python:

nums = [int(c) for c in input().split(",")]

nums.sort()

st, mxlen = -1,-1
n = len(nums)
index = 0
while index < n:
    i = index
    for j in range(index+1, n):
        if nums[j]-nums[i] != 1: break
        i += 1
    if mxlen < i-i