#C0E46. 为OD机试E卷 - 内存资源分配

为OD机试E卷 - 内存资源分配

华为OD机试E卷 - 内存资源分配（Java & Python& JS & C++ & C ）

https://blog.csdn.net/banxia_frontend/article/details/141951340

最新华为OD机试

真题目录：点击查看目录 华为OD面试真题精选：点击立即查看

题目描述

有一个简易内存池，内存按照大小粒度分类，每个粒度有若干个可用内存资源，用户会进行一系列内存申请，需要按需分配内存池中的资源返回申请结果成功失败列表。

分配规则如下：

  • 分配的内存要大于等于内存的申请量，存在满足需求的内存就必须分配，优先分配粒度小的，但内存不能拆分使用；
  • 需要按申请顺序分配，先申请的先分配，有可用内存分配则申请结果为true；
  • 没有可用则返回false。

注意：不考虑内存释放

输入描述

输入为两行字符串

第一行为内存池资源列表，包含内存粒度数据信息，粒度数据间用逗号分割

  • 一个粒度信息内用冒号分割，冒号前为内存粒度大小，冒号后为数量
  • 资源列表不大于1024
  • 每个粒度的数量不大于4096

第二行为申请列表，申请的内存大小间用逗号分割

  • 申请列表不大于100000

如: 64:2,128:1,32:4,1:128 50,36,64,128,127

输出描述

输出为内存池分配结果

如true,true,true,false,false

示例1

输入

64:2,128:1,32:4,1:128
50,36,64,128,127

输出

true,true,true,false,false

说明

内存池资源包含：64K共2个、128K共1个、32K共4个、1K共128个的内存资源； 针对50,36,64,128,127的内存申请序列，分配的内存依次是：64,64,128,NULL,NULL, 第三次申请内存时已经将128分配出去，因此输出结果是： true,true,true,false,false

解题思路

规则总结：

  • 按需分配内存，不能拆分。
  • 优先分配最小的满足条件的内存块。
  • 内存池中的资源一旦分配出去，就无法再次使用。
  • 若没有可用内存块满足需求，返回 false。

示例解释：

输入：

64:2,128:1,32:4,1:128
50,36,64,128,127

输出：

true,true,true,false,false

解释过程：

  1. 内存池初始化：

    • 内存池资源为：
      • 64K 的内存块有 2 个。
      • 128K 的内存块有 1 个。
      • 32K 的内存块有 4 个。
      • 1K 的内存块有 128 个。

  2. 申请 50K 内存：

    • 50K 需要一个大于等于 50K 的内存块。
    • 从内存池中寻找，最小满足要求的内存块是 64K，因此分配一个 64K 的内存块，成功，返回 true。
    • 剩余内存池：64:1, 128:1, 32:4, 1:128。

  3. 申请 36K 内存：

    • 36K 需要一个大于等于 36K 的内存块。
    • 最小满足要求的内存块是 64K，因此分配一个 64K 的内存块，成功，返回 true。
    • 剩余内存池：64:0, 128:1, 32:4, 1:128。

  4. 申请 64K 内存：

    • 64K 需要一个大于等于 64K 的内存块。
    • 内存池中没有剩余的 64K 内存块，唯一满足条件的内存块是 128K，因此分配一个 128K 的内存块，成功，返回 true。
    • 剩余内存池：64:0, 128:0, 32:4, 1:128。

  5. 申请 128K 内存：

    • 128K 需要一个大于等于 128K 的内存块。
    • 但是内存池中已经没有 128K 或更大的内存块了，分配失败，返回 false。

  6. 申请 127K 内存：

    • 127K 需要一个大于等于 127K 的内存块。
    • 同样，内存池中没有 128K 或更大的内存块，分配失败，返回 false。

最终，输出为 true,true,true,false,false。

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // 处理输入
        Scanner scanner = new Scanner(System.in);
        String memoryInfo = scanner.next();
        String applyList = scanner.next();

        // 内存信息
        List<Integer> memoryList = new ArrayList<>();
        List<String> memoryInfoList = Arrays.asList(memoryInfo.split(","));
        for (String info : memoryInfoList) {
            int colonIndex = info.indexOf(":");
            int size = Integer.parseInt(info.substring(0, colonIndex));
            int count = Integer.parseInt(info.substring(colonIndex + 1));
            for (int i = 0; i < count; i++) {
                memoryList.add(size);
            }
        }

        // 排序内存池，优先从小到大分配更精准的内存
        Collections.sort(memoryList);

        // 申请信息
        List<Integer> applyMemoryList = new ArrayList<>();
        List<String> applyListList = Arrays.asList(applyList.split(","));
        for (String apply : applyListList) {
            applyMemoryList.add(Integer.parseInt(apply));
        }

        // 分配内存
        List<Boolean> resultList = new ArrayList<>();
        for (int applyMemory : applyMemoryList) {
            boolean flag = false; // 标志位：是否成功分配
            for (int i = 0; i < memoryList.size(); i++) {
                if (memoryList.get(i) >= applyMemory) {
                    flag = true;
                    memoryList.remove(i); // 分配内存后移除
                    break;
                }
            }
            resultList.add(flag); // 记录分配结果
        }

        // 输出结果
        for (int i = 0; i < resultList.size(); i++) {
            System.out.print(resultList.get(i));
            if (i != resultList.size() - 1) {
                System.out.print(",");
            }
        }
    }
}

Python

# 导入所需模块
from typing import List

# 主函数
def main():
    # 处理输入
    memory_info = input()  # 输入内存池资源信息
    apply_list = input()  # 输入申请信息

    # 内存信息
    memory_list = []  # 创建一个列表存储内存池中的每个内存块
    memory_info_list = memory_info.split(",")  # 按逗号分割内存池信息
    for info in memory_info_list:  # 遍历每个内存块信息
        colon_index = info.index(":")  # 找到冒号的位置
        size = int(info[:colon_index])  # 提取内存块大小
        count = int(info[colon_index + 1:])  # 提取内存块数量
        for _ in range(count):  # 根据内存块数量添加到内存列表中
            memory_list.append(size)

    # 排序内存池，优先从小到大分配更精准的内存
    memory_list.sort()

    # 申请信息
    apply_memory_list = list(map(int, apply_list.split(",")))  # 将申请列表按逗号分割并转为整数

    # 分配内存
    result_list = []  # 存储每次申请是否成功的结果
    for apply_memory in apply_memory_list:  # 遍历每个申请的内存
        flag = False  # 标志位：是否成功分配
        for i in range(len(memory_list)):  # 遍历内存池
            if memory_list[i] >= apply_memory:  # 如果当前内存块满足申请
                flag = True  # 设置标志位为 True
                memory_list.pop(i)  # 从内存池中移除已分配的内存块
                break  # 跳出循环
        result_list.append(flag)  # 将分配结果添加到结果列表

    # 输出结果
    print(",".join(["true" if result else "false" for result in result_list]))  # 转为小写输出结果

if __name__ == "__main__":
    main()

JavaScript

// 导入模块
const readline = require("readline");

// 创建接口，用于读取用户输入
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

// 主函数
rl.on("line", (memoryInfo) => {
  rl.on("line", (applyList) => {
    // 内存信息
    let memoryList = []; // 创建一个数组用于存储内存池
    let memoryInfoList = memoryInfo.split(","); // 按逗号分割内存池信息
    memoryInfoList.forEach((info) => {
      let [size, count] = info.split(":").map(Number); // 提取内存块大小和数量
      for (let i = 0; i < count; i++) {
        memoryList.push(size); // 根据数量添加到内存池数组
      }
    });

    // 排序内存池，优先从小到大分配更精准的内存
    memoryList.sort((a, b) => a - b);

    // 申请信息
    let applyMemoryList = applyList.split(",").map(Number); // 将申请列表按逗号分割并转为数字数组

    // 分配内存
    let resultList = []; // 存储每次申请是否成功的结果
    applyMemoryList.forEach((applyMemory) => {
      let flag = false; // 标志位：是否成功分配
      for (let i = 0; i < memoryList.length; i++) {
        if (memoryList[i] >= applyMemory) {
          flag = true; // 设置标志位为 True
          memoryList.splice(i, 1); // 从内存池中移除已分配的内存块
          break; // 跳出循环
        }
      }
      resultList.push(flag); // 添加分配结果
    });

    // 输出结果
    console.log(resultList.join(",")); // 输出结果，用逗号分隔

    rl.close();
  });
});

C++

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>

using namespace std;

int main() {
    // 输入内存池资源和申请列表
    string memoryInfo, applyList;
    cin >> memoryInfo;
    cin >> applyList;

    // 内存信息
    vector<int> memoryList;
    stringstream memoryStream(memoryInfo);
    string memoryBlock;
    while (getline(memoryStream, memoryBlock, ',')) { // 按逗号分割内存信息
        int colonIndex = memoryBlock.find(":");
        int size = stoi(memoryBlock.substr(0, colonIndex)); // 提取内存块大小
        int count = stoi(memoryBlock.substr(colonIndex + 1)); // 提取内存块数量
        for (int i = 0; i < count; i++) {
            memoryList.push_back(size); // 根据数量添加到内存池
        }
    }

    // 排序内存池，优先从小到大分配更精准的内存
    sort(memoryList.begin(), memoryList.end());

    // 申请信息
    vector<int> applyMemoryList;
    stringstream applyStream(applyList);
    string applyBlock;
    while (getline(applyStream, applyBlock, ',')) { // 按逗号分割申请列表
        applyMemoryList.push_back(stoi(applyBlock));
    }

    // 分配内存
    vector<bool> resultList; // 存储每次申请是否成功的结果
    for (int applyMemory : applyMemoryList) {
        bool flag = false; // 标志位：是否成功分配
        for (auto it = memoryList.begin(); it != memoryList.end(); ++it) {
            if (*it >= applyMemory) {
                flag = true; // 设置标志位为 True
                memoryList.erase(it); // 移除已分配的内存块
                break; // 跳出循环
            }
        }
        resultList.push_back(flag); // 添加分配结果
    }

    // 输出结果
    for (size_t i = 0; i < resultList.size(); i++) {
        cout << (resultList[i] ? "true" : "false");
        if (i != resultList.size() - 1) {
            cout << ",";
        }
    }

    return 0;
}

C语言

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_MEMORY_BLOCKS 1000
#define MAX_APPLY_REQUESTS 1000

int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

int main() {
    char memoryInfo[1024], applyList[1024];
    int memoryList[MAX_MEMORY_BLOCKS]; // 存储内存块
    int memoryCount = 0;              // 内存块总数
    int applyMemoryList[MAX_APPLY_REQUESTS]; // 申请内存大小列表
    int applyCount = 0;               // 申请总数
    int resultList[MAX_APPLY_REQUESTS]; // 存储申请结果

    // 输入内存池信息和申请列表
    scanf("%s", memoryInfo);
    scanf("%s", applyList);

    // 处理内存池信息
    char *memoryToken = strtok(memoryInfo, ",");
    while (memoryToken != NULL) {
        char *colon = strchr(memoryToken, ':');
        if (colon == NULL) {
            fprintf(stderr, "错误：内存池信息格式不正确。\n");
            return 1;
        }
        *colon = '\0';
        int size = atoi(memoryToken);
        int count = atoi(colon + 1);
        for (int i = 0; i < count; i++) {
         
                memoryList[memoryCount++] = size;
            
        }
        memoryToken = strtok(NULL, ",");
    }

    // 对内存块排序（升序）
    qsort(memoryList, memoryCount, sizeof(int), compare);

    // 处理申请列表
    char *applyToken = strtok(applyList, ",");
    while (applyToken != NULL) {
        int applySize = atoi(applyToken);
    
            applyMemoryList[applyCount++] = applySize;
       
        applyToken = strtok(NULL, ",");
    }

    // 分配内存
    for (int i = 0; i < applyCount; i++) {
        int applyMemory = applyMemoryList[i];
        int allocated = 0; // 标志是否成功分配
        for (int j = 0; j < memoryCount; j++) {
            if (memoryList[j] >= applyMemory) {
                allocated = 1; // 成功分配
                // 移除已分配内存块，通过覆盖方式
                for (int k = j; k < memoryCount - 1; k++) {
                    memoryList[k] = memoryList[k + 1];
                }
                memoryCount--; // 更新内存块总数
                break;
            }
        }
        resultList[i] = allocated; // 保存结果
    }

    // 输出分配结果
    for (int i = 0; i < applyCount; i++) {
        printf(resultList[i] ? "true" : "false");
        if (i != applyCount - 1) {
            printf(",");
        }
    }
    printf("\n");

    return 0;
}

fengmian

完整用例

用例1

64:2,128:1,32:4,1:128
50,36,64,128,127

用例2

32:3,64:1,128:2,8:5
16,64,33,8,130

用例3

16:4,32:2,128:1,256:1
32,32,256,128,64

用例4

8:5,16:3,32:2,128:1
10,15,8,16,200

用例5

1:10,2:5,4:3,8:2
2,4,1,1,10

用例6

64:1,128:1,256:2
128,64,256,256,300

用例7

64:2,128:1,32:4,16:6
16,32,64,128,64,32

用例8

64:3,128:2,256:1
256,128,128,64,64,64

用例9

32:5,64:4,128:2,256:1
128,64,32,64,256,32,32

用例10

64:2,128:1,256:1
300,128,64,64,64
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  7. 兼容模式
  8. 主题
  2. © 2021-2025 Hydro.ac
  5. Worker 0 in 69ms
  6. Hydro v5.0.0-beta.0-d46de63-dirty Professional