华为OD机试 双机位C卷题库疯狂收录中刷题点这里专栏导读本专栏收录于《华为OD机试真题Java/Python/JS/C/C》。刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新。一、题目描述请实现一个简易内存池,根据请求命令完成内存分配和释放。内存池支持两种操作命令REQUEST和RELEASE其格式为1、REQUEST请求的内存大小表示请求分配指定大小内存如果分配成功返回分配到的内存首地址如果内存不足或指定的大小为0则输出error。2、RELEASE释放的内存首地址 表示释放掉之前分配的内存释放成功无需输出如果释放不存在的首地址则输出error。注意1.内存池总大小为100字节。2.内存池地址分配必须是连续内存并优先从低地址分配。3.内存释放后可被再次分配已释放的内存在空闲时不能被二次释放。4.不会释放已申请的内存块的中间地址。5.释放操作只是针对首地址所对应的单个内存块进行操作不会影响其它内存块。二、输入描述首行为整数N表示操作命令的个数。接下来的N行每行将给出一个操作命令操作命令和参数之间用“”分割三、输出描述输出最后请求的内存的首地址。如果位置已满则输出-1。样例2REQUEST10REQUEST20输出样例010四、解题思路定义一个map存储内存的分配情况key内存的首地址value内存的尾地址请求内存时如果map是空放在首地址0处如果map不为空遍历已经存入的首地址已经存入的首地址 - 第一个空闲区域的首地址 大于 请求的内存值将当前请求的内存的首地址和内存的尾地址存入map反之重置前一个空闲区域的首地址判断剩余内存是否可以容下当前请求值如果可以容下将当前请求的内存的首地址和内存的尾地址存入map如果容不下输出error释放内存时将其首地址的key移除map最后输出最后一次请求的首地址。注意如果最后发起的命令是RELEASE也是可以的会返回最后一次REQUEST的首地址。五、测试用例1、输入4REQUEST20REQUEST30RELEASE0REQUEST302、输出503、说明第一次请求20第二请求30第三次释放首地址为0的内存第四次请求30第一个空闲区域的首地址是0但空闲长度只有20放不下当前请求的地址因此消耗剩余内存输出最后一次请求的首地址为50。4、再输入6REQUEST20REQUEST30RELEASE0REQUEST30REQUEST10REQUEST105、再说明第一次请求20第二请求30第三次释放首地址为0的内存第四次请求30第一个空闲区域的首地址是0但空闲长度只有20放不下当前请求的地址因此消耗剩余内存。第五次请求10第一个空闲区域的首地址是0长度20可以容下当前请求的内存10。第六次请求10第一个空闲区域的首地址是10长度10可以容下当前请求的内存10。输出最后一次请求的首地址为10。6、如果走后一次请求的是20会怎么样呢六、Python算法源码classMemoryManager:REQUESTREQUESTRELEASERELEASEERRORerrorMAX100def__init__(self):self.memory_map{}defmain(self):try:# 操作命令的个数Nint(input().strip())# 每一行的操作命令和参数line_arr[input().strip().split()for_inrange(N)]forcommand,value_strinline_arr:valueint(value_str)ifcommand.startswith(self.REQUEST):# 请求# 非法输入内存池总大小为100字节ifvalueself.MAXorvalue0:print(self.ERROR)returnself.request(value)elifcommand.startswith(self.RELEASE):# 释放self.memory_map.pop(value,None)else:# 非法输入print(self.ERROR)exceptExceptionase:# 非法输入print(self.ERROR)defrequest(self,value):zero0before_head_address0ifnotself.memory_map:# 如果memory_map是空放在首地址0处self.memory_map[zero]valueprint(zero)else:head_listsorted(self.memory_map.keys())forrequested_headinhead_list:ifrequested_head-before_head_addressvalue:self.memory_map[before_head_address]before_head_addressvalueprint(before_head_address)returnelse:before_head_addressself.memory_map[requested_head]ifself.MAX-before_head_addressvalue:self.memory_map[before_head_address]before_head_addressvalueprint(before_head_address)else:print(-1)if__name____main__:MemoryManager().main()七、JavaScript算法源码classMemoryManager{constructor(){this.REQUESTREQUEST;this.RELEASERELEASE;this.ERRORerror;this.MAX100;this.memoryMapnewMap();// 用于存储内存的分配情况}main(){try{constinputrequire(readline-sync);// 操作命令的个数constNparseInt(input.question().trim());// 每一行的操作命令和参数constlineArr[];for(leti0;iN;i){lineArr.push(input.question().trim().split());}for(leti0;iN;i){const[command,valueStr]lineArr[i];constvalueparseInt(valueStr);if(command.startsWith(this.REQUEST)){// 请求// 非法输入内存池总大小为100字节if(valuethis.MAX||value0){console.log(this.ERROR);return;}this.request(value);}elseif(command.startsWith(this.RELEASE)){// 释放this.memoryMap.delete(value);}else{// 非法输入console.log(this.ERROR);}}}catch(e){// 非法输入console.log(this.ERROR);}}request(value){letzero0;letbeforeHeadAddress0;if(this.memoryMap.size0){// 如果memoryMap是空放在首地址0处this.memoryMap.set(zero,value);console.log(zero);}else{constheadListArray.from(this.memoryMap.keys()).sort((a,b)a-b);for(letrequestedHeadofheadList){if(requestedHead-beforeHeadAddressvalue){this.memoryMap.set(beforeHeadAddress,beforeHeadAddressvalue);console.log(beforeHeadAddress);return;}else{beforeHeadAddressthis.memoryMap.get(requestedHead);}}if(this.MAX-beforeHeadAddressvalue){this.memoryMap.set(beforeHeadAddress,beforeHeadAddressvalue);console.log(beforeHeadAddress);}else{console.log(-1);}}}}// 执行内存管理器constmemoryManagernewMemoryManager();memoryManager.main();八、C算法源码#includestdio.h#includestdlib.h#includestring.h#defineREQUESTREQUEST#defineRELEASERELEASE#defineERRORerror#defineMAX100typedefstructMemoryBlock{intstart;intend;structMemoryBlock*next;}MemoryBlock;MemoryBlock*headNULL;voidrequest(intvalue);voidrelease(intvalue);voidprint_error();voidprint_memory_address(intaddress);intmain(){intN;scanf(%d,N);for(inti0;iN;i){charcommand[10];intvalue;scanf(%s%d,command,value);if(strncmp(command,REQUEST,strlen(REQUEST))0){if(valueMAX||value0){print_error();return0;}request(value);}elseif(strncmp(command,RELEASE,strlen(RELEASE))0){release(value);}else{print_error();return0;}}return0;}voidrequest(intvalue){intbeforeHeadAddress0;if(headNULL){// 如果链表为空放在首地址0处MemoryBlock*newBlock(MemoryBlock*)malloc(sizeof(MemoryBlock));newBlock-start0;newBlock-endvalue;newBlock-nextNULL;headnewBlock;print_memory_address(0);}else{MemoryBlock*currenthead;MemoryBlock*prevNULL;while(current!NULL){if(current-start-beforeHeadAddressvalue){MemoryBlock*newBlock(MemoryBlock*)malloc(sizeof(MemoryBlock));newBlock-startbeforeHeadAddress;newBlock-endbeforeHeadAddressvalue;newBlock-nextcurrent;if(prevNULL){headnewBlock;}else{prev-nextnewBlock;}print_memory_address(newBlock-start);return;}beforeHeadAddresscurrent-end;prevcurrent;currentcurrent-next;}if(MAX-beforeHeadAddressvalue){MemoryBlock*newBlock(MemoryBlock*)malloc(sizeof(MemoryBlock));newBlock-startbeforeHeadAddress;newBlock-endbeforeHeadAddressvalue;newBlock-nextNULL;prev-nextnewBlock;print_memory_address(newBlock-start);}else{print_memory_address(-1);}}}voidrelease(intvalue){MemoryBlock*currenthead;MemoryBlock*prevNULL;while(current!NULL){if(current-startvalue){if(prevNULL){headcurrent-next;}else{prev-nextcurrent-next;}free(current);return;}prevcurrent;currentcurrent-next;}}voidprint_error(){printf(%s\n,ERROR);}voidprint_memory_address(intaddress){printf(%d\n,address);}九、C算法源码#includeiostream#includemap#includestringusingnamespacestd;classMemoryManager{public:staticconstintMAX100;conststring REQUESTREQUEST;conststring RELEASERELEASE;conststring ERRORerror;voidmain(){try{intN;cinN;cin.ignore();// 忽略换行符string lineArr[N][2];for(inti0;iN;i){string command;getline(cin,command);size_t poscommand.find();if(pos!string::npos){lineArr[i][0]command.substr(0,pos);lineArr[i][1]command.substr(pos1);}}for(inti0;iN;i){intvaluestoi(lineArr[i][1]);if(lineArr[i][0].find(REQUEST)0){// 请求if(valueMAX||value0){coutERRORendl;return;}request(value);}elseif(lineArr[i][0].find(RELEASE)0){// 释放memoryMap.erase(value);}else{// 非法输入coutERRORendl;}}}catch(...){// 非法输入coutERRORendl;}}private:mapint,intmemoryMap;voidrequest(intvalue){intbeforeHeadAddress0;if(memoryMap.empty()){// 如果memoryMap是空放在首地址0处memoryMap[0]value;cout0endl;}else{for(autoitmemoryMap.begin();it!memoryMap.end();it){if(it-first-beforeHeadAddressvalue){memoryMap[beforeHeadAddress]beforeHeadAddressvalue;coutbeforeHeadAddressendl;return;}beforeHeadAddressit-second;}if(MAX-beforeHeadAddressvalue){memoryMap[beforeHeadAddress]beforeHeadAddressvalue;coutbeforeHeadAddressendl;}else{cout-1endl;}}}};intmain(){MemoryManager memoryManager;memoryManager.main();return0;}本文收录于华为OD机试真题Python/JS/C/C刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新。