堆内存申请 - 华为OD统一考试(D卷)
OD统一考试（D卷）
分值： 100分
题解： Java / Python / C++
题目描述
有一个总空间为100字节的堆，现要从中新申请一块内存，内存分配原则为:
优先分配紧接着前一块已使用的内存，分配空间足够时分配最接近申请大小的空闲内存。
输入描述
第1行是1个整数，表示期望申请的内存字节数。
第2到第N行是用空格分割的两个整数，表示当前已分配的内存的情况，每一行表示一块已分配的连续内存空间，每行的第1个和第2个整数分别表示偏移地址和内存块大小，如: 0 1 3 2 表示0偏移地址开始的1个字节和3偏移地址开始的2个字节已被分配，其余内存空闲。
输出描述
若申请成功，输出申请到内存的偏移 若申请失败，输出-1。
备注 1.若输入信息不合法或无效，则申请失败
2.若没有足够的空间供分配，则申请失败
3.堆内存信息有区域重叠或有非法值等都是无效输入
示例1
输入：
1
0 1
3 2
输出：
1
说明：
堆中已使用的两块内存是偏移从0开始的1字节和偏移从3开始的2字节，空闲的两块内存是偏移从1开始2个字节和偏移从5开始95字节根据分配原则，新申请的内存应从1开始分配1个字节，所以输出偏移为1。
题解
这道题属于内存管理中的内存分配问题，需要模拟堆内存的管理，根据现有已分配内存块和分配原则，来确定能否满足新的内存申请。
解题思路
- 内存使用情况：使用一个布尔数组
used表示每个字节的使用情况，True表示已使用，False表示空闲。- 标记内存使用 (
mark)：遍历输入的已分配内存块，标记内存块中的每个字节。如果发现重叠或非法情况，则返回False。- 申请内存 (
allocate)：遍历used数组，寻找能够容纳新申请的内存块的连续空闲空间。优先选择紧邻已使用内存块的空闲空间，并且选择最接近申请大小的空闲块。- 解决函数 (
solve)：首先标记所有已分配的内存块，然后尝试分配新申请的内存，返回内存偏移地址或者失败标志-1。- 输入处理和调用：处理输入数据并调用
solve函数。
Java
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/**
* @author code5bug
*/
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int req = in.nextInt();
List<int[]> lst = new ArrayList<>();
while (in.hasNextInt()) {
lst.add(new int[]{in.nextInt(), in.nextInt()});
}
Solution solution = new Solution();
System.out.println(solution.solve(lst, req));
}
}
class Solution {
// 内存使用情况
boolean[] used = new boolean[100];
/**
* 标记内存使用
*
* @param offset 偏移地址
* @param size 内存块大小
* @return
*/
public boolean mark(int offset, int size) {
// 输入信息不合法
if (offset < 0 || offset > 99 || size > 100) return false;
for (int i = 0; i < size; i++) {
// 区域重叠非法
if (used[offset + i]) return false;
used[offset + i] = true;
}
return true;
}
/**
* 申请内存
*
* @param reqSize 申请的内存大小
* @return
*/
public int allocate(int reqSize) {
int len = used.length;
if (reqSize > len) return -1;
// 申请到内存的偏移、 分配内存空闲的间隙值（空闲内存空间大小 - 申请的内存空间大小）
int offset = -1, gap = len;
for (int left = 0; left < len; ) {
if (used[left]) {
left++;
continue;
}
int right = left + 1;
while (right < len && !used[right]) right++;
// 空闲的内存空间大小
int freeSize = right - left;
// 空闲内存够分配 且 更接近申请的内存空间大小
if (freeSize >= reqSize && freeSize - reqSize <= gap) {
offset = left;
gap = freeSize - reqSize;
}
left = right;
}
return offset;
}
public int solve(List<int[]> lst, int req) {
for (int[] t : lst) {
if (!mark(t[0], t[1])) return -1;
}
return allocate(req);
}
}
Python
# 内存使用情况
used = [False] * 100
def mark(offset, size):
"""
标记内存使用
:param offset: 偏移地址
:param size: 内存块大小
:return: 成功标记返回 True，否则返回 False
"""
# 输入信息不合法
if offset < 0 or offset > 99 or size > 100:
return False
for i in range(size):
# 区域重叠非法
if used[offset + i]:
return False
used[offset + i] = True
return True
def allocate(req_size):
"""
申请内存
:param req_size: 申请的内存大小
:return: 成功分配返回偏移地址，否则返回 -1
"""
len_used = len(used)
if req_size > len_used:
return -1
# 申请到内存的偏移、 分配内存空闲的间隙值（空闲内存空间大小 - 申请的内存空间大小）
offset = -1
gap = len_used
left = 0
while left < len_used:
if used[left]:
left += 1
continue
right = left + 1
while right < len_used and not used[right]:
right += 1
# 空闲的内存空间大小
free_size = right - left
# 空闲内存够分配 且 更接近申请的内存空间大小
if free_size >= req_size and free_size - req_size <= gap:
offset = left
gap = free_size - req_size
left = right
return offset
def solve(lst, req):
"""
:param lst: 内存块列表
:param req: 申请的内存大小
:return: 成功分配返回偏移地址，否则返回 -1
"""
for t in lst:
if not mark(t[0], t[1]):
return -1
return allocate(req)
def main():
req = int(input().strip())
lst = []
try:
while True:
a, b = map(int, input().strip().split())
lst.append((a, b))
except EOFError:
pass
print(solve(lst, req))
if __name__ == "__main__":
main()
C++
#include <iostream>
#include <vector>
using namespace std;
// 内存使用情况
bool used[100] = {false};
/**
* 标记内存使用
*
* @param offset 偏移地址
* @param size 内存块大小
* @return
*/
bool mark(int offset, int size) {
// 输入信息不合法
if (offset < 0 || offset > 99 || size > 100) return false;
for (int i = 0; i < size; i++) {
// 区域重叠非法
if (used[offset + i]) return false;
used[offset + i] = true;
}
return true;
}
/**
* 申请内存
*
* @param reqSize 申请的内存大小
* @return
*/
int allocate(int reqSize) {
int len = sizeof(used) / sizeof(used[0]);
if (reqSize > len) return -1;
// 申请到内存的偏移、 分配内存空闲的间隙值（空闲内存空间大小 - 申请的内存空间大小）
int offset = -1, gap = len;
for (int left = 0; left < len; ) {
if (used[left]) {
left++;
continue;
}
int right = left + 1;
while (right < len && !used[right]) right++;
// 空闲的内存空间大小
int freeSize = right - left;
// 空闲内存够分配 且 更接近申请的内存空间大小
if (freeSize >= reqSize && freeSize - reqSize <= gap) {
offset = left;
gap = freeSize - reqSize;
}
left = right;
}
return offset;
}
/**
* 解决函数
*
* @param lst 内存块列表
* @param req 申请的内存大小
* @return
*/
int solve(const vector<pair<int, int>>& lst, int req) {
for (const auto& t : lst) {
if (!mark(t.first, t.second)) return -1;
}
return allocate(req);
}
int main() {
int req;
cin >> req;
vector<pair<int, int>> lst;
int a, b;
while (cin >> a >> b) {
lst.push_back({a, b});
}
cout << solve(lst, req) << endl;
return 0;
}
#面经##春招##秋招##校招##华为#希望这个专栏不仅能帮您成功通过华为机试，还能让您熟练掌握算法。
整理题解不易， 如果有帮助到您，请给点个赞 ❤️ 和收藏 ⭐，让更多的人看到。🙏🙏🙏
投递小米集团等公司9个岗位 >
