華為OD機試真題——簡易內存池（2025A卷：200分）Java/python/JavaScript/C++/C/GO最佳實現

在這里插入圖片描述

2025 A卷 200分 題型

本文涵蓋詳細的問題分析、解題思路、代碼實現、代碼詳解、測試用例以及綜合分析；
并提供Java、python、JavaScript、C++、C語言、GO六種語言的最佳實現方式！

本文收錄于專欄：《2025華為OD真題目錄+全流程解析/備考攻略/經驗分享》

華為OD機試真題《簡易內存池》：

目錄

    • 題目名稱：簡易內存池
      • 題目描述
    • Java
      • 問題分析
      • 解題思路
      • 代碼實現
      • 代碼詳細解析
      • 示例測試
        • 示例1輸入：
        • 示例2輸入：
        • 示例3輸入：
      • 綜合分析
    • python
      • 問題分析
      • 解題思路
      • 代碼實現
      • 代碼詳細解析
      • 示例測試
        • 示例1輸入：
        • 示例2輸入：
        • 示例3輸入：
      • 綜合分析
    • JavaScript
      • 問題分析
      • 解題思路
      • 代碼實現
      • 代碼詳細解析
      • 示例測試
        • 示例1輸入：
        • 示例2輸入：
        • 示例3輸入：
      • 綜合分析
    • C++
      • 問題分析
      • 解題思路
      • 代碼實現
      • 代碼詳細解析
      • 示例測試
        • 示例1輸入：
        • 示例2輸入：
        • 示例3輸入：
      • 綜合分析
    • C語言
      • 問題分析
      • 解題思路
      • 代碼實現
      • 代碼詳細解析
      • 示例測試
        • 示例1輸入：
        • 示例2輸入：
        • 示例3輸入：
      • 綜合分析
    • GO
      • 問題分析
      • 解題思路
      • 代碼實現
      • 代碼詳細解析
      • 示例測試
        • 示例1輸入：
        • 示例2輸入：
        • 示例3輸入：
      • 綜合分析
    • 更多內容：

題目名稱：簡易內存池

  • 知識點：內存管理（首次適應算法）、邏輯處理
  • 時間限制：1秒
  • 空間限制：256MB
  • 限定語言：不限

題目描述

請實現一個簡易內存池，根據請求命令完成內存分配和釋放。
內存池支持兩種操作命令：REQUEST和RELEASE，其格式為：

  1. REQUEST=請求的內存大小：請求分配指定大小的連續內存。
    • 若分配成功，返回分配到的內存首地址；
    • 若內存不足或請求大小為0，輸出 error。
  2. RELEASE=釋放的內存首地址：釋放指定首地址的內存塊。
    • 釋放成功無需輸出；
    • 若釋放不存在的首地址，輸出 error。

約束條件：

  1. 內存池總大小為 100字節，地址從0開始分配。
  2. 分配必須為連續內存，優先從低地址分配。
  3. 釋放后的內存可被再次分配，但已釋放的內存塊不可二次釋放。
  4. 不會釋放已分配內存塊的中間地址，僅能通過首地址操作。

輸入描述：

  • 首行為整數 N（操作命令數，0 < N ≤ 100）。
  • 后續 N 行，每行一個操作命令，格式為 命令=參數（如 REQUEST=10）。

輸出描述：

  • 按順序輸出每個 REQUEST 的分配結果或 error，RELEASE 僅需在失敗時輸出 error。

示例：
輸入：

5  
REQUEST=10  
REQUEST=20  
RELEASE=0  
REQUEST=20  
REQUEST=10

輸出：

0  
10  
30  
0

說明：

  1. 第一條 REQUEST=10 分配地址0~9，返回首地址0。
  2. 第二條 REQUEST=20 分配地址10~29，返回首地址10。
  3. RELEASE=0 釋放首地址0的內存塊，0~9變為空閑。
  4. 第三條 REQUEST=20 因0~9空間不足，從30開始分配，返回首地址30。
  5. 第四條 REQUEST=10 重新分配0~9，返回首地址0。

補充說明：

  • 輸入保證合法，無需處理非法參數（如負數）。
  • 同一列表元素順序不可變，動態規劃或回溯法為典型解法。

Java

問題分析

我們需要實現一個簡易內存池，支持 REQUEST 和 RELEASE 命令。內存池總大小為 100 字節，地址從 0 開始。分配時采用首次適應算法，優先低地址分配連續內存。釋放時需處理合并相鄰空閑塊。

解題思路

  1. 數據結構設計：

    • 空閑塊列表：按起始地址升序排列，記錄每個空閑塊的起始地址和大小。
    • 已分配塊字典：記錄已分配塊的首地址和大小，用于快速查找。

  2. REQUEST 處理：

    • 遍歷空閑塊列表，找到第一個足夠大的塊。
    • 分割該塊，記錄已分配塊，更新空閑列表。

  3. RELEASE 處理：

    • 檢查要釋放的塊是否存在。
    • 將釋放的塊插入空閑列表并合并相鄰塊。

代碼實現

import java.util.*;class Block {int start;int size;public Block(int s, int sz) {start = s;size = sz;}
}public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int N = Integer.parseInt(scanner.nextLine());List<Block> freeList = new ArrayList<>();freeList.add(new Block(0, 100)); // 初始空閑塊：0-99Map<Integer, Integer> allocated = new HashMap<>();for (int i = 0; i < N; i++) {String line = scanner.nextLine();String[] parts = line.split("=");String cmd = parts[0];int param = Integer.parseInt(parts[1]);if (cmd.equals("REQUEST")) {// REQUEST 處理int size = param;if (size <= 0) {System.out.println("error");continue;}boolean found = false;for (int j = 0; j < freeList.size(); j++) {Block block = freeList.get(j);if (block.size >= size) {// 分配該塊allocated.put(block.start, size);System.out.println(block.start);// 處理剩余空間int remaining = block.size - size;if (remaining > 0) {freeList.set(j, new Block(block.start + size, remaining));} else {freeList.remove(j);}found = true;break;}}if (!found) {System.out.println("error");}} else if (cmd.equals("RELEASE")) {// RELEASE 處理int addr = param;if (!allocated.containsKey(addr)) {System.out.println("error");continue;}int size = allocated.get(addr);Block newBlock = new Block(addr, size);// 插入到正確位置int insertIdx = 0;while (insertIdx < freeList.size() && freeList.get(insertIdx).start < newBlock.start) {insertIdx++;}freeList.add(insertIdx, newBlock);// 合并左邊while (insertIdx > 0) {Block prev = freeList.get(insertIdx - 1);if (prev.start + prev.size == newBlock.start) {newBlock.start = prev.start;newBlock.size += prev.size;freeList.remove(insertIdx - 1);insertIdx--;} else {break;}}// 合并右邊while (insertIdx < freeList.size() - 1) {Block next = freeList.get(insertIdx + 1);if (newBlock.start + newBlock.size == next.start) {newBlock.size += next.size;freeList.remove(insertIdx + 1);} else {break;}}allocated.remove(addr);}}}
}

代碼詳細解析

  1. Block 類：表示內存塊，包含起始地址 start 和大小 size。
  2. 初始化：
    • freeList 初始為 0-99 的塊。
    • allocated 記錄已分配塊的首地址和大小。
  3. REQUEST 處理：
    • 遍歷 freeList 找第一個足夠大的塊。
    • 分配后分割剩余空間，更新 freeList 和 allocated。
  4. RELEASE 處理：
    • 檢查地址是否存在，不存在則輸出錯誤。
    • 插入釋放的塊到 freeList，合并相鄰塊。

示例測試

示例1輸入：
5  
REQUEST=10  
REQUEST=20  
RELEASE=0  
REQUEST=20  
REQUEST=10

輸出：

0  
10  
30  
0

解析：

  • 前兩次分配分別獲得 0-9 和 10-29。
  • 釋放 0-9 后，第三次分配 30-49。
  • 第四次分配重新使用 0-9。
示例2輸入：
3  
REQUEST=50  
RELEASE=0  
REQUEST=50

輸出：

0  
error  
0

解析：

  • 首次分配 0-49，釋放后合并為 0-99。
  • 再次分配成功。
示例3輸入：
4  
REQUEST=100  
RELEASE=0  
REQUEST=99  
REQUEST=1

輸出：

0  
99  
error

解析：

  • 首次分配全部內存，釋放后再次分配 99 字節成功，剩余 1 字節不足以分配。

綜合分析

  1. 時間復雜度：O(N^2)

    • 每個 REQUEST 和 RELEASE 最壞需遍歷列表，但 N ≤ 100，實際可行。

  2. 空間復雜度：O(N)

    • 空閑塊和已分配塊的數量與操作數相關，但總量較小。

  3. 優勢：

    • 首次適應算法：簡單高效，優先低地址分配。
    • 合并策略：釋放時合并相鄰塊，減少內存碎片。

  4. 適用場景：

    • 適用于操作數較少且內存管理簡單的場景。

python

問題分析

我們需要實現一個簡易內存池，支持 REQUEST 和 RELEASE 操作。內存池總大小為 100 字節，地址從 0 開始分配。分配時采用首次適應算法，優先從低地址分配連續內存。釋放后需合并相鄰空閑塊。

解題思路

  1. 數據結構設計：

    • 空閑塊列表：按起始地址升序排列，每個塊記錄起始地址和大小。
    • 已分配塊字典：記錄已分配塊的首地址和大小，便于快速查找。

  2. REQUEST 處理：

    • 遍歷空閑塊列表，找到第一個足夠大的塊。
    • 分割該塊，記錄已分配塊，更新空閑列表。

  3. RELEASE 處理：

    • 檢查要釋放的塊是否存在。
    • 將釋放的塊插入空閑列表并合并相鄰塊。

代碼實現

import bisectn = int(input())
free_blocks = [(0, 100)]  # 空閑塊列表，按起始地址排序
allocated = {}             # 已分配塊字典 {起始地址: 大小}for _ in range(n):line = input().strip()cmd, param = line.split('=')param = int(param)if cmd == 'REQUEST':size = paramif size <= 0:print('error')continuefound = False# 遍歷空閑塊，找到第一個足夠大的塊for i in range(len(free_blocks)):start, block_size = free_blocks[i]if block_size >= size:print(start)allocated[start] = size# 處理剩余空間remaining = block_size - sizeif remaining > 0:free_blocks[i] = (start + size, remaining)else:del free_blocks[i]found = Truebreakif not found:print('error')elif cmd == 'RELEASE':addr = paramif addr not in allocated:print('error')continuesize = allocated[addr]del allocated[addr]# 將釋放的塊插入空閑列表starts = [block[0] for block in free_blocks]i = bisect.bisect_left(starts, addr)free_blocks.insert(i, (addr, size))# 合并左側的空閑塊while i > 0 and free_blocks[i-1][0] + free_blocks[i-1][1] == free_blocks[i][0]:prev_start, prev_size = free_blocks.pop(i-1)free_blocks[i-1] = (prev_start, prev_size + free_blocks[i-1][1])i -= 1# 合并右側的空閑塊while i < len(free_blocks)-1 and free_blocks[i][0] + free_blocks[i][1] == free_blocks[i+1][0]:curr_start, curr_size = free_blocks.pop(i)next_start, next_size = free_blocks.pop(i)free_blocks.insert(i, (curr_start, curr_size + next_size))

代碼詳細解析

  1. 輸入處理：

    • 讀取操作數 n，逐行解析命令。
    • free_blocks 初始化為 [(0, 100)]，表示整個內存池空閑。
    • allocated 字典記錄已分配塊。

  2. REQUEST 處理：

    • 遍歷 free_blocks，找到首個足夠大的塊。
    • 分配后更新 allocated 和 free_blocks，分割剩余塊。

  3. RELEASE 處理：

    • 檢查地址是否在 allocated 中，若不存在輸出錯誤。
    • 使用 bisect 插入釋放的塊到正確位置。
    • 合并左側和右側的空閑塊，確保連續空間合并。

示例測試

示例1輸入：
5  
REQUEST=10  
REQUEST=20  
RELEASE=0  
REQUEST=20  
REQUEST=10

輸出：

0  
10  
30  
0

解析：

  • 前兩次分配地址0-9和10-29。
  • 釋放0-9后，第三次分配30-49。
  • 第四次重新分配0-9。
示例2輸入：
3  
REQUEST=50  
RELEASE=0  
REQUEST=50

輸出：

0  
0

解析：

  • 首次分配0-49，釋放后合并為0-99，再次分配成功。
示例3輸入：
4  
REQUEST=100  
RELEASE=0  
REQUEST=99  
REQUEST=1

輸出：

0  
99  
error

解析：

  • 分配全部內存后釋放，再次分配99字節成功，剩余1字節不足。

綜合分析

  1. 時間復雜度：O(N2)

    • 每個 REQUEST 最壞遍歷整個空閑列表，但操作數 ≤ 100，實際可行。

  2. 空間復雜度：O(N)

    • 空閑塊和已分配塊數量與操作數相關，內存消耗較小。

  3. 優勢：

    • 首次適應算法：快速找到可用塊，保證低地址優先。
    • 高效合并：釋放后合并相鄰塊，減少碎片。

  4. 適用場景：

    • 適用于內存分配操作較少、需要高效管理連續內存的場景。

JavaScript

問題分析

我們需要實現一個簡易內存池，支持 REQUEST 和 RELEASE 操作。內存池總大小為 100 字節，地址從 0 開始分配。分配時采用首次適應算法，優先低地址分配連續內存。釋放后需合并相鄰空閑塊。

解題思路

  1. 數據結構設計：
    • 空閑塊列表：按起始地址升序排列，每個塊記錄 start 和 size。
    • 已分配塊字典：記錄已分配塊的首地址和大小，便于快速查找。
  2. REQUEST 處理：
    • 遍歷空閑塊列表，找到第一個足夠大的塊。
    • 分割該塊，記錄已分配塊，更新空閑列表。
  3. RELEASE 處理：
    • 檢查要釋放的塊是否存在。
    • 將釋放的塊插入空閑列表并合并相鄰塊。

代碼實現

const readline = require("readline");const rl = readline.createInterface({input: process.stdin,output: process.stdout,terminal: false,
});let lineCount = 0;
let n;
const freeBlocks = [{ start: 0, size: 100 }]; // 空閑塊列表（按地址升序）
const allocated = new Map();                  // 已分配塊字典rl.on("line", (line) => {if (lineCount === 0) {n = parseInt(line.trim());} else {const [cmd, param] = line.trim().split("=");const value = parseInt(param);if (cmd === "REQUEST") {handleRequest(value);} else if (cmd === "RELEASE") {handleRelease(value);}}lineCount++;
});// 處理 REQUEST 命令
function handleRequest(size) {if (size <= 0) {console.log("error");return;}for (let i = 0; i < freeBlocks.length; i++) {const block = freeBlocks[i];if (block.size >= size) {// 分配該塊console.log(block.start);allocated.set(block.start, size);// 分割剩余空間const remaining = block.size - size;if (remaining > 0) {freeBlocks.splice(i, 1, { start: block.start + size, size: remaining });} else {freeBlocks.splice(i, 1);}return;}}// 沒有找到足夠大的塊console.log("error");
}// 處理 RELEASE 命令
function handleRelease(addr) {if (!allocated.has(addr)) {console.log("error");return;}const size = allocated.get(addr);allocated.delete(addr);// 找到插入位置let insertIndex = 0;while (insertIndex < freeBlocks.length &&freeBlocks[insertIndex].start < addr) {insertIndex++;}// 插入新空閑塊const newBlock = { start: addr, size };freeBlocks.splice(insertIndex, 0, newBlock);// 合并左側空閑塊while (insertIndex > 0) {const prevBlock = freeBlocks[insertIndex - 1];if (prevBlock.start + prevBlock.size === newBlock.start) {newBlock.start = prevBlock.start;newBlock.size += prevBlock.size;freeBlocks.splice(insertIndex - 1, 1);insertIndex--;} else {break;}}// 合并右側空閑塊while (insertIndex < freeBlocks.length - 1) {const nextBlock = freeBlocks[insertIndex + 1];if (newBlock.start + newBlock.size === nextBlock.start) {newBlock.size += nextBlock.size;freeBlocks.splice(insertIndex + 1, 1);} else {break;}}
}

代碼詳細解析

  1. 輸入處理：

    • 使用 readline 逐行讀取輸入。
    • freeBlocks 初始化為 [{ start: 0, size: 100 }]，表示整個內存池空閑。
    • allocated 用 Map 記錄已分配塊。

  2. REQUEST 處理：

    • 遍歷 freeBlocks 尋找足夠大的塊。
    • 輸出分配的首地址，并更新空閑列表：
      freeBlocks.splice(i, 1, { start: block.start + size, size: remaining });

  3. RELEASE 處理：

    • 檢查地址是否存在，不存在則輸出錯誤。
    • 找到插入位置并插入釋放的塊：
      while (insertIndex < freeBlocks.length && freeBlocks[insertIndex].start < addr) {insertIndex++;
}
    • 合并左側和右側相鄰塊，確保連續空間合并。

示例測試

示例1輸入：
5  
REQUEST=10  
REQUEST=20  
RELEASE=0  
REQUEST=20  
REQUEST=10

輸出：

0  
10  
30  
0

解析：

  • 前兩次分配地址 0-9 和 10-29。
  • 釋放后合并空閑塊，第三次分配 30-49，第四次重新分配 0-9。
示例2輸入：
3  
REQUEST=50  
RELEASE=0  
REQUEST=50

輸出：

0  
0

解析：

  • 首次分配 0-49，釋放后合并為 0-99，再次分配成功。
示例3輸入：
4  
REQUEST=100  
RELEASE=0  
REQUEST=99  
REQUEST=1

輸出：

0  
99  
error

解析：

  • 分配全部內存后釋放，再次分配 99 字節成功，剩余 1 字節不足。

綜合分析

  1. 時間復雜度：

    • REQUEST：最壞 O(N)，需遍歷空閑列表。
    • RELEASE：最壞 O(N)，需遍歷插入位置并合并相鄰塊。

  2. 空間復雜度：

    • 空閑塊和已分配塊數量與操作數相關，內存消耗較小。

  3. 優勢：

    • 首次適應算法：快速找到可用塊，保證低地址優先。
    • 高效合并：釋放后自動合并相鄰塊，減少內存碎片。

  4. 適用場景：

    • 適用于內存分配操作較少、需要高效管理連續內存的場景。

C++

問題分析

我們需要實現一個簡易內存池，支持 REQUEST 和 RELEASE 操作。內存池總大小為 100 字節，地址從 0 開始分配。分配時采用首次適應算法，優先低地址分配連續內存。釋放后的內存需合并相鄰空閑塊。

解題思路

  1. 數據結構設計：

    • 空閑塊列表：按起始地址升序排列，記錄每個空閑塊的起始地址和大小。
    • 已分配塊字典：記錄已分配塊的首地址和大小，便于快速查找。

  2. REQUEST 處理：

    • 遍歷空閑塊列表，找到第一個足夠大的塊。
    • 分割該塊，記錄已分配塊，更新空閑列表。

  3. RELEASE 處理：

    • 檢查要釋放的塊是否存在。
    • 將釋放的塊插入空閑列表并合并相鄰塊。

代碼實現

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>using namespace std;int main() {int n;cin >> n;vector<pair<int, int>> free_blocks; // 空閑塊列表（按起始地址升序）free_blocks.emplace_back(0, 100);   // 初始內存池：0~99unordered_map<int, int> allocated;  // 已分配塊字典 {起始地址: 大小}for (int i = 0; i < n; ++i) {string line;cin >> line;size_t eq_pos = line.find('=');string cmd = line.substr(0, eq_pos);int param = stoi(line.substr(eq_pos + 1));if (cmd == "REQUEST") {int size = param;if (size <= 0) {cout << "error" << endl;continue;}bool found = false;// 遍歷空閑塊列表，找到第一個足夠大的塊for (auto it = free_blocks.begin(); it != free_blocks.end();) {int start = it->first;int block_size = it->second;if (block_size >= size) {// 分配該塊cout << start << endl;allocated[start] = size;// 處理剩余空間int remaining = block_size - size;if (remaining > 0) {*it = {start + size, remaining}; // 修改當前塊為剩余部分} else {free_blocks.erase(it); // 無剩余則刪除該塊}found = true;break;} else {++it; // 繼續查找下一個塊}}if (!found) {cout << "error" << endl;}} else if (cmd == "RELEASE") {int addr = param;auto it = allocated.find(addr);if (it == allocated.end()) {cout << "error" << endl;continue;}int size = it->second;allocated.erase(it); // 從已分配字典中刪除// 將釋放的塊插入到空閑列表的正確位置pair<int, int> new_block = {addr, size};auto insert_it = lower_bound(free_blocks.begin(), free_blocks.end(), new_block,[](const pair<int, int>& a, const pair<int, int>& b) {return a.first < b.first;});int pos = insert_it - free_blocks.begin();free_blocks.insert(insert_it, new_block);// 合并左側相鄰塊while (pos > 0 && free_blocks[pos - 1].first + free_blocks[pos - 1].second == free_blocks[pos].first) {free_blocks[pos - 1].second += free_blocks[pos].second;free_blocks.erase(free_blocks.begin() + pos);pos--;}// 合并右側相鄰塊while (pos < free_blocks.size() - 1 && free_blocks[pos].first + free_blocks[pos].second == free_blocks[pos + 1].first) {free_blocks[pos].second += free_blocks[pos + 1].second;free_blocks.erase(free_blocks.begin() + pos + 1);}}}return 0;
}

代碼詳細解析

  1. 數據結構初始化：

    • free_blocks 初始化為 {0, 100}，表示整個內存池空閑。
    • allocated 用哈希表記錄已分配塊。

  2. REQUEST 處理：

    • 遍歷 free_blocks，找到首個足夠大的塊。
    • 分割該塊：若剩余空間大于0，修改當前塊；否則刪除該塊。
    • 輸出分配的首地址，并記錄到 allocated。

  3. RELEASE 處理：

    • 檢查地址是否存在，不存在則輸出錯誤。
    • 使用 lower_bound 找到插入位置，保持空閑塊有序。
    • 插入后合并左右相鄰的空閑塊，確保內存連續。

示例測試

示例1輸入：
5  
REQUEST=10  
REQUEST=20  
RELEASE=0  
REQUEST=20  
REQUEST=10

輸出：

0  
10  
30  
0

解析：

  • 分配 0-9 和 10-29，釋放后合并空閑塊，第三次分配 30-49，第四次分配 0-9。
示例2輸入：
3  
REQUEST=50  
RELEASE=0  
REQUEST=50

輸出：

0  
0

解析：

  • 首次分配 0-49，釋放后合并為 0-99，再次分配成功。
示例3輸入：
4  
REQUEST=100  
RELEASE=0  
REQUEST=99  
REQUEST=1

輸出：

0  
99  
error

解析：

  • 分配全部內存后釋放，再次分配 99 字節成功，剩余1字節不足。

綜合分析

  1. 時間復雜度：

    • REQUEST：最壞 O(N)，需遍歷空閑塊列表。
    • RELEASE：插入和合并操作最壞 O(N)，但操作數 ≤ 100，實際高效。

  2. 空間復雜度：

    • 空閑塊和已分配塊數量與操作數相關，內存占用較小。

  3. 優勢：

    • 首次適應算法：優先低地址分配，減少內存碎片。
    • 高效合并：釋放時自動合并相鄰塊，優化內存利用率。

  4. 適用場景：

    • 適用于內存操作較少、需高效管理連續內存的場景。

C語言

問題分析

我們需要實現一個簡易內存池，支持 REQUEST 和 RELEASE 操作。內存池總大小為 100 字節，地址從 0 開始。分配時采用首次適應算法，優先從低地址分配連續內存。釋放時需合并相鄰空閑塊。

解題思路

  1. 數據結構設計：
    • 空閑塊數組：按起始地址升序排列，記錄每個空閑塊的起始地址和大小。
    • 已分配塊數組：記錄已分配塊的首地址和大小，便于快速查找。
  2. REQUEST 處理：
    • 遍歷空閑塊數組，找到第一個足夠大的塊。
    • 分割該塊，記錄已分配塊，更新空閑數組。
  3. RELEASE 處理：
    • 檢查要釋放的塊是否存在，不存在則輸出錯誤。
    • 將釋放的塊插入空閑數組，合并相鄰塊。

代碼實現

#include <stdio.h>
#include <stdlib.h>
#include <string.h>typedef struct {int start;int size;
} Block;Block *free_blocks = NULL;    // 空閑塊數組
int free_count = 0;            // 空閑塊數量typedef struct {int start;int size;
} AllocatedBlock;AllocatedBlock *allocated = NULL; // 已分配塊數組
int allocated_count = 0;          // 已分配塊數量// 初始化內存池，初始時整個內存池空閑
void init_free_blocks() {free_blocks = malloc(sizeof(Block));free_blocks[0].start = 0;free_blocks[0].size = 100;free_count = 1;
}// 處理 REQUEST 命令
void handle_request(int size) {if (size <= 0) {printf("error\n");return;}// 遍歷空閑塊數組，找到第一個足夠大的塊for (int i = 0; i < free_count; i++) {if (free_blocks[i].size >= size) {int allocated_start = free_blocks[i].start;printf("%d\n", allocated_start);// 記錄到已分配數組AllocatedBlock *temp = realloc(allocated, (allocated_count + 1) * sizeof(AllocatedBlock));if (!temp) {fprintf(stderr, "Memory allocation failed\n");exit(1);}allocated = temp;allocated[allocated_count].start = allocated_start;allocated[allocated_count].size = size;allocated_count++;// 處理剩余空間int remaining = free_blocks[i].size - size;if (remaining > 0) {// 修改當前空閑塊的起始地址和大小free_blocks[i].start += size;free_blocks[i].size = remaining;} else {// 無剩余空間，移除該空閑塊memmove(&free_blocks[i], &free_blocks[i + 1], (free_count - i - 1) * sizeof(Block));free_count--;free_blocks = realloc(free_blocks, free_count * sizeof(Block));}return;}}// 無足夠大的空閑塊printf("error\n");
}// 處理 RELEASE 命令
void handle_release(int addr) {// 查找要釋放的塊是否存在int found = 0;int size = 0;int index = -1;for (int i = 0; i < allocated_count; i++) {if (allocated[i].start == addr) {found = 1;size = allocated[i].size;index = i;break;}}if (!found) {printf("error\n");return;}// 從已分配數組中移除memmove(&allocated[index], &allocated[index + 1], (allocated_count - index - 1) * sizeof(AllocatedBlock));allocated_count--;allocated = realloc(allocated, allocated_count * sizeof(AllocatedBlock));// 創建新空閑塊Block new_block = {addr, size};// 找到插入位置（按地址升序）int insert_pos = 0;while (insert_pos < free_count && free_blocks[insert_pos].start < new_block.start) {insert_pos++;}// 插入到空閑數組free_blocks = realloc(free_blocks, (free_count + 1) * sizeof(Block));memmove(&free_blocks[insert_pos + 1], &free_blocks[insert_pos], (free_count - insert_pos) * sizeof(Block));free_blocks[insert_pos] = new_block;free_count++;// 合并左側相鄰塊while (insert_pos > 0) {Block prev = free_blocks[insert_pos - 1];if (prev.start + prev.size == new_block.start) {free_blocks[insert_pos - 1].size += new_block.size;memmove(&free_blocks[insert_pos], &free_blocks[insert_pos + 1], (free_count - insert_pos - 1) * sizeof(Block));free_count--;insert_pos--;new_block = free_blocks[insert_pos];} else {break;}}// 合并右側相鄰塊while (insert_pos < free_count - 1) {Block next = free_blocks[insert_pos + 1];if (new_block.start + new_block.size == next.start) {free_blocks[insert_pos].size += next.size;memmove(&free_blocks[insert_pos + 1], &free_blocks[insert_pos + 2], (free_count - insert_pos - 2) * sizeof(Block));free_count--;} else {break;}}
}int main() {init_free_blocks();int n;scanf("%d", &n);getchar(); // 讀取換行符for (int i = 0; i < n; i++) {char line[50];fgets(line, sizeof(line), stdin);line[strcspn(line, "\n")] = '\0'; // 去除換行符char *eq = strchr(line, '=');if (!eq) continue; // 輸入格式錯誤，跳過*eq = '\0';char *cmd = line;int param = atoi(eq + 1);if (strcmp(cmd, "REQUEST") == 0) {handle_request(param);} else if (strcmp(cmd, "RELEASE") == 0) {handle_release(param);}}free(free_blocks);free(allocated);return 0;
}

代碼詳細解析

  1. 數據結構：

    • Block 結構體表示空閑塊，包含起始地址和大小。
    • AllocatedBlock 結構體表示已分配塊。
    • free_blocks 和 allocated 是動態數組，分別存儲空閑塊和已分配塊。

  2. 初始化：

    • init_free_blocks 初始化內存池，初始空閑塊為 0-99。

  3. REQUEST 處理：

    • 遍歷 free_blocks 數組，找到第一個足夠大的塊。
    • 分割該塊，剩余空間更新到原位置或刪除原塊。
    • 記錄已分配塊到 allocated 數組。

  4. RELEASE 處理：

    • 查找要釋放的塊是否存在。
    • 插入到 free_blocks 數組的正確位置。
    • 合并左側和右側相鄰的空閑塊。

  5. 輸入處理：

    • 讀取命令并解析參數，調用對應處理函數。

示例測試

示例1輸入：
5  
REQUEST=10  
REQUEST=20  
RELEASE=0  
REQUEST=20  
REQUEST=10

輸出：

0  
10  
30  
0

解析：

  • 分配 0-9 和 10-29，釋放 0-9 后合并空閑塊，重新分配 0-9。
示例2輸入：
3  
REQUEST=50  
RELEASE=0  
REQUEST=50

輸出：

0  
0

解析：

  • 首次分配 0-49，釋放后合并為 0-99，再次分配成功。
示例3輸入：
4  
REQUEST=100  
RELEASE=0  
REQUEST=99  
REQUEST=1

輸出：

0  
99  
error

解析：

  • 分配全部內存后釋放，再次分配 99 字節成功，剩余 1 字節不足。

綜合分析

  1. 時間復雜度：

    • REQUEST：O(N)，遍歷空閑數組。
    • RELEASE：O(N)，查找和合并操作。

  2. 空間復雜度：

    • 動態數組存儲空閑塊和已分配塊，內存占用可控。

  3. 優勢：

    • 首次適應算法：優先低地址分配，減少內存碎片。
    • 高效合并：釋放后自動合并相鄰塊，優化內存利用率。

  4. 適用場景：

    • 適用于操作數較少、需高效管理連續內存的場景。

GO

問題分析

我們需要實現一個簡易內存池，支持 REQUEST 和 RELEASE 操作。內存池總大小為 100 字節，地址從 0 開始分配。分配時采用首次適應算法，優先低地址分配連續內存。釋放后需合并相鄰空閑塊。

解題思路

  1. 數據結構設計：

    • 空閑塊列表：按起始地址升序排列，記錄每個空閑塊的起始地址和大小。
    • 已分配塊字典：記錄已分配塊的首地址和大小，便于快速查找。

  2. REQUEST 處理：

    • 遍歷空閑塊列表，找到第一個足夠大的塊。
    • 分割該塊，記錄已分配塊，更新空閑列表。

  3. RELEASE 處理：

    • 檢查要釋放的塊是否存在。
    • 將釋放的塊插入空閑列表并合并相鄰塊。

代碼實現

package mainimport ("bufio""fmt""os""strconv""strings"
)type Block struct {Start intSize  int
}func main() {scanner := bufio.NewScanner(os.Stdin)// 初始化內存池：0~99 空閑freeBlocks := []Block{{Start: 0, Size: 100}}allocated := make(map[int]int) // 已分配塊：key=起始地址，value=大小scanner.Scan()n, _ := strconv.Atoi(scanner.Text())for i := 0; i < n; i++ {scanner.Scan()line := scanner.Text()parts := strings.Split(line, "=")cmd := parts[0]param, _ := strconv.Atoi(parts[1])if cmd == "REQUEST" {size := paramif size <= 0 {fmt.Println("error")continue}found := false// 遍歷空閑塊，找到第一個足夠大的塊for idx, block := range freeBlocks {if block.Size >= size {// 分配該塊fmt.Println(block.Start)allocated[block.Start] = size// 處理剩余空間remaining := block.Size - sizeif remaining > 0 {// 修改當前空閑塊freeBlocks[idx] = Block{Start: block.Start + size,Size:  remaining,}} else {// 移除該空閑塊freeBlocks = append(freeBlocks[:idx], freeBlocks[idx+1:]...)}found = truebreak}}if !found {fmt.Println("error")}} else if cmd == "RELEASE" {addr := paramsize, exists := allocated[addr]if !exists {fmt.Println("error")continue}// 從已分配字典中刪除delete(allocated, addr)// 創建新空閑塊newBlock := Block{Start: addr, Size: size}// 找到插入位置（保持按起始地址升序）insertIdx := 0for insertIdx < len(freeBlocks) && freeBlocks[insertIdx].Start < newBlock.Start {insertIdx++}// 插入新塊freeBlocks = append(freeBlocks[:insertIdx], append([]Block{newBlock}, freeBlocks[insertIdx:]...)...)// 合并左側相鄰塊for insertIdx > 0 {left := freeBlocks[insertIdx-1]if left.Start+left.Size == newBlock.Start {newBlock.Start = left.StartnewBlock.Size += left.Size// 移除左側塊freeBlocks = append(freeBlocks[:insertIdx-1], freeBlocks[insertIdx:]...)insertIdx--} else {break}}// 合并右側相鄰塊for insertIdx < len(freeBlocks)-1 {right := freeBlocks[insertIdx+1]if newBlock.Start+newBlock.Size == right.Start {newBlock.Size += right.Size// 移除右側塊freeBlocks = append(freeBlocks[:insertIdx+1], freeBlocks[insertIdx+2:]...)} else {break}}// 更新合并后的塊freeBlocks[insertIdx] = newBlock}}
}

代碼詳細解析

  1. 數據結構定義：

    type Block struct {Start intSize  int
}
    • Block 結構體表示空閑塊，包含起始地址和大小。

  2. 初始化：

    freeBlocks := []Block{{Start: 0, Size: 100}}
allocated := make(map[int]int)
    • freeBlocks 初始化為 0~99 的空閑塊。
    • allocated 字典記錄已分配塊的起始地址和大小。

  3. 輸入處理：

    scanner.Scan()
n, _ := strconv.Atoi(scanner.Text())
    • 讀取命令數量 n，逐行處理每個命令。

  4. REQUEST 處理：

    • 遍歷 freeBlocks 查找第一個足夠大的塊：
      for idx, block := range freeBlocks {if block.Size >= size {// 分配該塊fmt.Println(block.Start)allocated[block.Start] = size
    • 分割剩余空間或移除空閑塊：
      remaining := block.Size - size
if remaining > 0 {freeBlocks[idx] = Block{Start: block.Start + size, Size: remaining}
} else {freeBlocks = append(freeBlocks[:idx], freeBlocks[idx+1:]...)
}

  5. RELEASE 處理：

    • 檢查地址是否存在：
      size, exists := allocated[addr]
if !exists {fmt.Println("error")continue
}
    • 插入新空閑塊到正確位置：
      insertIdx := 0
for insertIdx < len(freeBlocks) && freeBlocks[insertIdx].Start < newBlock.Start {insertIdx++
}
freeBlocks = append(freeBlocks[:insertIdx], append([]Block{newBlock}, freeBlocks[insertIdx:]...)...)
    • 合并左側和右側相鄰塊：
      for insertIdx > 0 {left := freeBlocks[insertIdx-1]if left.Start+left.Size == newBlock.Start {newBlock.Start = left.StartnewBlock.Size += left.SizefreeBlocks = append(freeBlocks[:insertIdx-1], freeBlocks[insertIdx:]...)insertIdx--}
}

示例測試

示例1輸入：
5  
REQUEST=10  
REQUEST=20  
RELEASE=0  
REQUEST=20  
REQUEST=10

輸出：

0  
10  
30  
0

解析：

  • 分配 0~9 和 10~29，釋放后合并空閑塊，第三次分配 30~49，第四次分配 0~9。
示例2輸入：
3  
REQUEST=50  
RELEASE=0  
REQUEST=50

輸出：

0  
0

解析：

  • 首次分配 0~49，釋放后合并為 0~99，再次分配成功。
示例3輸入：
4  
REQUEST=100  
RELEASE=0  
REQUEST=99  
REQUEST=1

輸出：

0  
99  
error

解析：

  • 分配全部內存后釋放，再次分配 99 字節成功，剩余 1 字節不足。

綜合分析

  1. 時間復雜度：

    • REQUEST：O(N)，遍歷空閑塊列表。
    • RELEASE：O(N)，插入和合并操作。

  2. 空間復雜度：

    • 空閑塊和已分配塊的數量與操作數相關，內存占用可控。

  3. 優勢：

    • 首次適應算法：優先低地址分配，減少內存碎片。
    • 高效合并：釋放后自動合并相鄰塊，優化內存利用率。

  4. 適用場景：

    • 適用于內存操作較少、需要高效管理連續內存的場景。

更多內容：

https://www.kdocs.cn/l/cvk0eoGYucWA

本文發表于【紀元A夢】，關注我，獲取更多實用教程/資源！

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/bicheng/78457.shtml
繁體地址，請注明出處：http://hk.pswp.cn/bicheng/78457.shtml
英文地址，請注明出處：http://en.pswp.cn/bicheng/78457.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

騰訊一面面經：總結一下

騰訊一面面經：總結一下

1. Java 中的 和 equals 有什么區別&#xff1f;比較對象時使用哪一個 1. 操作符&#xff1a; 用于比較對象的內存地址&#xff08;引用是否相同&#xff09;。 對于基本數據類型、 比較的是值。&#xff08;8種基本數據類型&#xff09;對于引用數據類型、 比較的是兩個引…
閱讀更多...
計算機網絡中的DHCP是什么呀？ 詳情解答

計算機網絡中的DHCP是什么呀？ 詳情解答

目錄 DHCP 是什么&#xff1f; DHCP 的工作原理 主要功能 DHCP 與網絡安全的關系 1. 正面作用 2. 潛在安全風險 DHCP 的已知漏洞 1. 協議設計缺陷 2. 軟件實現漏洞 3. 配置錯誤導致的漏洞 4. 已知漏洞總結 舉例說明 DHCP 與網絡安全 如何提升 DHCP 安全性 總結 D…
閱讀更多...
2025 年導游證報考條件新政策解讀與應對策略

2025 年導游證報考條件新政策解讀與應對策略

2025 年導游證報考政策有了不少新變化&#xff0c;這些變化會對報考者產生哪些影響&#xff1f;我們又該如何應對&#xff1f;下面就為大家詳細解讀新政策&#xff0c;并提供實用的應對策略。 最引人注目的變化當屬中職旅游類專業學生的報考政策。以往&#xff0c;中專學歷報考…
閱讀更多...
【物聯網】基于LORA組網的遠程環境監測系統設計（ThingsCloud云平臺版）

【物聯網】基于LORA組網的遠程環境監測系統設計（ThingsCloud云平臺版）

演示視頻： 基于LORA組網的遠程環境監測系統設計（ThingsCloud云平臺版） 前言：本設計是基于ThingsCloud云平臺版，還有另外一個版本是基于機智云平臺版本，兩個設計只是云平臺和手機APP的區別，其他功能都一樣。如下鏈接： 【物聯網】基于LORA組網的遠程環境監測系統設計（機…
閱讀更多...
SQL 函數進行左邊自動補位fnPadLeft和FORMAT

SQL 函數進行左邊自動補位fnPadLeft和FORMAT

目錄 1.問題 2.解決 方式1 方式2 3.結果 1.問題 例如在SQL存儲過程中&#xff0c;將1 或10 或 100 長度不足的時候&#xff0c;自動補足長度。 例如 1 → 001 10→ 010 100→100 2.解決 方式1 SELECT FORMAT (1, 000) AS FormattedNum; SELECT FORMAT(12, 000) AS Form…
閱讀更多...
Nacos簡介—2.Nacos的原理簡介

Nacos簡介—2.Nacos的原理簡介

大綱 1.Nacos集群模式的數據寫入存儲與讀取問題 2.基于Distro協議在啟動后的運行規則 3.基于Distro協議在處理服務實例注冊時的寫路由 4.由于寫路由造成的數據分片以及隨機讀問題 5.寫路由 數據分區 讀路由的CP方案分析 6.基于Distro協議的定時同步機制 7.基于Distro協…
閱讀更多...
中電金信聯合阿里云推出智能陪練Agent

中電金信聯合阿里云推出智能陪練Agent

在金融業加速數智化轉型的今天&#xff0c;提升服務效率與改善用戶體驗已成為行業升級的核心方向。面對這一趨勢&#xff0c;智能體與智能陪練的結合應用&#xff0c;正幫助金融機構突破傳統業務模式&#xff0c;開拓更具競爭力的創新機遇。 在近日召開的阿里云AI勢能大會期間&…
閱讀更多...
十分鐘恢復服務器攻擊——群聯AI云防護系統實戰

十分鐘恢復服務器攻擊——群聯AI云防護系統實戰

場景描述 服務器遭遇大規模DDoS攻擊&#xff0c;導致服務不可用。通過群聯AI云防護系統的分布式節點和智能調度功能&#xff0c;快速切換流量至安全節點&#xff0c;清洗惡意流量&#xff0c;10分鐘內恢復業務。 技術實現步驟 1. 啟用智能調度API觸發節點切換 群聯系統提供RE…
閱讀更多...
LLM量化技術全景：GPTQ、QAT、AWQ、GGUF與GGML

LLM量化技術全景：GPTQ、QAT、AWQ、GGUF與GGML

01 引言 本文介紹的是在 LLM 討論中經常聽到的各種量化技術。本文的目的是提供一步一步的解釋和代碼&#xff0c;讓大家可以自己使用這些技術來壓縮模型。 閑話少說&#xff0c;我們來研究一下吧&#xff01; 02 Quantization 量化是指將高精度數字轉換為低精度數字。低精…
閱讀更多...
IP的基礎知識以及相關機制

IP的基礎知識以及相關機制

IP地址 1.IP地址的概念 IP地址是分配給連接到互聯網或局域網中的每一個設備的唯一標識符 也就是說IP地址是你設備在網絡中的定位~ 2.IP版本~ IP版本分為IPv4和IPv6&#xff0c;目前我們最常用的還是IPv4~~但是IPv4有個缺點就是地址到現在為止&#xff0c;已經接近枯竭~~&…
閱讀更多...
本地使用Ollama部署DeepSeek

本地使用Ollama部署DeepSeek

以下是在本地使用Ollama部署DeepSeek的詳細教程&#xff0c;涵蓋安裝、修改安裝目錄、安裝大模型以及刪除大模型的操作步驟。 安裝Ollama 1. 系統要求 確保你的系統滿足以下條件&#xff1a; 操作系統&#xff1a;macOS、Linux或者Windows。足夠的磁盤空間和內存。 2. 安裝…
閱讀更多...
開源項目實戰學習之YOLO11：ultralytics-cfg-datasets-Objects365、open-images-v7.yaml文件（六）

開源項目實戰學習之YOLO11：ultralytics-cfg-datasets-Objects365、open-images-v7.yaml文件（六）

&#x1f449; 點擊關注不迷路 &#x1f449; 點擊關注不迷路 &#x1f449; 點擊關注不迷路 medical - pills.yaml 通常用于配置與醫學藥丸檢測任務相關的參數和信息 Objects365.yaml 用于配置與 Objects365 數據集相關信息的文件。Objects365 數據集包含 365 個不同的物體類別…
閱讀更多...
23種設計模式-行為型模式之策略模式（Java版本）

23種設計模式-行為型模式之策略模式（Java版本）

Java 策略模式&#xff08;Strategy Pattern&#xff09;詳解 &#x1f9e0; 什么是策略模式&#xff1f; 策略模式是一種行為型設計模式&#xff0c;它定義了一系列算法&#xff0c;把它們一個個封裝起來&#xff0c;并且使它們可以互相替換。策略模式讓算法獨立于使用它的客…
閱讀更多...
使用 AI Agent 改善師生互動的設計文檔

使用 AI Agent 改善師生互動的設計文檔

使用 AI Agent 改善師生互動的設計文檔 一、引言 1.1 研究背景 當前教育領域的師生互動存在諸多挑戰&#xff0c;如教師負擔過重、學生個體差異大導致難以滿足所有人的需求&#xff0c;以及信息傳遞延遲等問題。引入AI-Agent能夠有效緩解這些問題&#xff0c;通過自動化手段協…
閱讀更多...
2、Ubuntu 環境下安裝RabbitMQ

2、Ubuntu 環境下安裝RabbitMQ

?. 安裝Erlang RabbitMqRabbitMq需要Erlang語?的?持&#xff0c;在安裝rabbitMq之前需要安裝erlang需要Erlang語?的?持&#xff0c;在安裝rabitMq之前需要安裝erlang。 安裝erlang # 更新軟件包 sudo apt-get update # 安裝 erlang sudo apt-get install erlang 查看er…
閱讀更多...
Node.js 操作 ElasticSearch 完整指南：從安裝到實戰

Node.js 操作 ElasticSearch 完整指南：從安裝到實戰

本文將手把手教你如何搭建 ElasticSearch 環境&#xff0c;并通過 Node.js 實現高效數據檢索。包含 10 個可直接復用的代碼片段&#xff0c;助你快速掌握搜索、聚合等核心功能&#xff01; 環境搭建篇 1. ElasticSearch 安裝要點 下載 es下載連接 下載下來后&#xff0c;進…
閱讀更多...
硬核科普丨2025年安全、高效網絡準入控制系統深度解析

硬核科普丨2025年安全、高效網絡準入控制系統深度解析

陽途網絡準入控制系統&#xff08;Network Access Control&#xff0c;簡稱NAC&#xff09;是當代網絡安全領域的重要工具&#xff0c;有效防止未經授權的訪問和數據泄露&#xff0c;保障網絡資源的安全性和完整性。本文將深入探討陽途網絡準入控制系統的的重要性和作用。 一、…
閱讀更多...
搜索二叉樹-key的搜索模型

搜索二叉樹-key的搜索模型

二叉搜索樹(Binary Search Tree, BST)是一種重要的數據結構&#xff0c;它有兩種基本模型&#xff1a;Key模型和Key/Value模型。 一、Key模型 1.基本概念 Key模型是二叉搜索樹中最簡單的形式&#xff0c;每個節點只存儲一個鍵值(key)&#xff0c;沒有額外的數據值(value)。這…
閱讀更多...
安卓四大組件之ContentProvider

安卓四大組件之ContentProvider

目錄 實現步驟 代碼分析 onCreate insert query ContextHolder Cursor 作用與用法 基本步驟&#xff1a; 可能的面試題&#xff1a;為什么使用Cursor&#xff1f; 為什么使用Cursor 使用Cursor的好處 靜態內部類實現單例模式 AnndroidManifest.xml配置信息 注釋的…
閱讀更多...
【HTML】【Web開發】滑動條挑戰

【HTML】【Web開發】滑動條挑戰

最近在思考如何開發一些入門級的迷你游戲&#xff0c;于是抽空寫了個HTML的滑動條小游戲。 游戲規則如下&#xff1a; 在[0, 100]區間內隨機生成一個目標值&#xff0c;顯示為&#xff1a;X% 倒計時 3 秒過后&#xff0c;出現 10 秒的挑戰倒計時和【停止】按鈕 挑戰倒計時結…
閱讀更多...
最新文章

Copyright @ 2022~2023