Java在线笔试编程（2）---模拟内存操作

约定不等于承诺〃 2022-09-25 13:22 151阅读 0赞

生命不息，学习不止。题目来自某公司在线笔试编程题。

题目描述如下：物联网技术的蓬勃发展，各种传感器纷纷出现，小B所在的项目组正在开发一个物联网项目，她们在研究设计一种新的传感器，这种传感器有自己的基本处理单元，有一定的自主性，能够进行简单的数据收集、处理、存储、和传输。为降低系统功耗，保证系统可靠性和可控性，她们要对内存进行基本的管理。研究小组计划开发1个实验性内存管理器，实现对内存的分配、释放和整理。对应的接口有new 、del、def，使用的语法如下：

new size：分配size字节大小的内存块，返回该内存块的句柄handle,size为正整数；

del handle：释放句柄handle指向的内存块；

def：整理内存碎片，将所有已分配内存块按地址从低到高的顺序迁移，使空闲内存碎片在高地址端拼接在一起；

初始内存为initSize字节大小的整片空闲内存，编号为1到initSize。

new size操作中，若存在不小于size的连续空闲内存，则按照小地址优先的原则从空闲内存区域中分配size大小的内存块，标记该内存块状态为已分配，并返回指向该内存的句柄，若无法分配，则返回空（NULL）。

del handle操作释放由handle标记的内存块，标记被释放的内存状态为空闲，若handle为无效句柄，则返回ILLEGAL\_OPERATION。

def完成内存的整理工作，无返回值。

根据设计，每次成功内存分配返回的句柄为一个正整数，从1开始，依次计数。失败的存储分配操作不影响计数。

项目小组将此项任务分配给小B，小B向你求助，你能帮助她吗？

**输入描述：**

输入中有多组测试数据，每组测试数据的第一行为两个正整数T和MaxMem(1<=T<=10000，1<=MaxMem<=10000)，其中T为操作次数，MaxMem为初始内存大小，随后有T行操作指令。

**输出描述：**

对每组测试数据，按操作顺序输出操作结果，对每个new操作，在单独行中输出结果，成功时输出其返回句柄值，失败则输出NULL。若del操作失败，输出ILLEGAL_OPERATION。def不产生输出。

**样例输入：**

6 10
    new 5
    new 3
    del 1
    new 6
    def
    new 6

**样例输出：**

1
    2
    NULL
    3

开始看到题目是想抓狂的，这么长，估计得好久才能理解，想放弃的，但是还是硬着头皮多看了几次，发现有点理解题目的意思了，于是就想试试，下面是我的思路，仅供参考， 如果我理解有错或者有可以优化的地方，欢迎指出，共同进步！

解题思路

按照题目的意思，给你一块内存空间，你去根据不同的指令去操作这块空间。于是我就认为内存空间就相当于一个大小为MaxMem的数组，初始数组元素都为0表示没有存储内容，数组元素为1表示该空间存储了数据。

new size 操作就相当于给数组中size个的元素赋值1,存储位置从小到大；

del handle 操作就相当于给对应handle句柄的内存块赋值0；

def 操作就相当于假如相邻的存储块之间间隔假如有0，通过这个操作可以将后面的内存块往前移。为什么存储块之间会有“0”，是因为进行了del操作，导致其中的一块内存置0了，这样就会出现间隔。

以下是关键代码块：

1.存储单元

/**
         * 存储内容到内存中
         * @param size 存储内容的大小
         * @return true表示存储成功
         */
    	private static boolean save2Memory(int size) {
    		boolean flag = true;
    		int index = 0;
    		Memory m = new Memory();
    		for (int i = 0; i < memorySize; i++) {
    			if (i>=position && index < size) {
    				m.start = position;// 记录起始值
    				memory[i] = 1;
    				index++;
    			}
    		}
    		
    		if (index != size) {// 表示内存不足，存储失败
    			flag = false;
    			for (int i = m.start; i < memorySize; i++) {
    					memory[i] = 0;
    			}
    		} else {
    			m.end = m.start + size-1;
    			position+=size;
    			handle++;
    			map.put(handle, m);// 添加
    		}
    		return flag;
    	}

class Memory {
    	int start;// 内存存储的开始地值
    	int end;// 内存存储的结束值
    
    }

其中第一个for循环是将内容存储到模拟内存块中，即给相应数组元素赋值1，为了保证存储内容地址从低到高，设置了个index值，记录已存储内容的大小。

循环结束后可能内存不足了，要进行判断index和size，如果存储失败了，注意应该把以前for循环赋值1的给置0，第一次我就犯了这个错误，= =！为此需要记住每次存储块的起始位置和结束位置，因此构建了一个Memory类，有2个属性：start和end。 其中还有个position，也是起到指示下一块内存开始的存储的起始位置。

2.删除单元

/**
         * 删除内存中指定的区域
         * @param start 起始值
         * @param end 结束值
         */
    	 private static void delMemory(int start, int end) {
    		for (int i = 0; i < end - start + 1; i++) {
    			memory[start + i] = 0;
    		}
    	  }

就是将指定区域的存储内容清空，即将数组元素置0

3.整理单元

int[] tempMemory = new int[memorySize];
         int index=0;
         for (int j = 0; j < memorySize; j++) {
    	 if (memory[j] != 0) {
    		tempMemory[index] = memory[j];
    		index++;
    	   }
         }
         position=index;//重置起始位置
         for (int j = 0; j < memorySize; j++) {
    	memory[j] = tempMemory[j];
         }

整理单元的话，我这里采用的是新建了一个同等大小的内存块，通过转移数组元素的达到“整理”的目的。具体过程可以参考如下示意图：

![Center][]

好了，整体的关键内容就是这些了。

自己在处理的时候也遇到了这样的一个问题，就是Scanner的next()和nextLine()方法，这里也顺便写下这2个方法的总结

简而言之，next()返回的是不包含空格的字符串，以换行或者空格符为分界线接收下一个String类型变量；nextLine()返回的是包含空格的字符串。

下面给出整体实现代码

import java.util.HashMap;
    import java.util.Map;
    import java.util.Scanner;
    
    public class TestB {
    	static int memorySize;
    	static int handle = 0;
    	static int[] memory;
    	static int position=0;//目前存储所在的位置
    	static Map<Integer, Memory> map = new HashMap<Integer, Memory>();
    
    	public static void main(String[] args) {
    		Scanner mScanner = new Scanner(System.in);
    		int handleTimes = mScanner.nextInt();// 总共操作次数
    		memorySize = mScanner.nextInt();// 总内存大小
    		memory = new int[memorySize];// 模拟内存空间
    		for (int i = 0; i < handleTimes; i++) {
    			String input = mScanner.next();
    			if (input.equals("new")) {
    				int size = mScanner.nextInt();// 分配内存空间的大小
    				if (save2Memory(size)) {
    					System.out.println(handle);
    				} else {
    					System.out.println("NULL");
    				}
    			} else if (input.equals("del")) {// 删除存储
    				int delFlag = mScanner.nextInt();// 要清除的内存区域
    				if (map.get(delFlag)!=null) {
    					int delStart = map.get(delFlag).start;
    					int delEnd = map.get(delFlag).end;
    					delMemory(delStart, delEnd);
    					map.remove(delFlag);//移除
    				}else{
    					System.out.println("ILLEGAL_OPERATION");
    				}
    			} else if (input.equals("def")) {// 整理内存
    				int[] tempMemory = new int[memorySize];
    				int index=0;
    				for (int j = 0; j < memorySize; j++) {
    					if (memory[j] != 0) {
    						tempMemory[index] = memory[j];
    						index++;
    					}
    				}
    				position=index;//重置起始位置
    				for (int j = 0; j < memorySize; j++) {
    					memory[j] = tempMemory[j];
    				}
    			}
    		}
    		
    	}
        /**
         * 存储内容到内存中
         * @param size 存储内容的大小
         * @return true表示存储成功
         */
    	private static boolean save2Memory(int size) {
    		boolean flag = true;
    		int index = 0;
    		Memory m = new Memory();
    		for (int i = 0; i < memorySize; i++) {
    			if (i>=position && index < size) {
    				m.start = position;// 记录起始值
    				memory[i] = 1;
    				index++;
    			}
    		}
    		
    		if (index != size) {// 表示内存不足，存储失败
    			flag = false;
    			for (int i = m.start; i < memorySize; i++) {
    					memory[i] = 0;
    			}
    		} else {
    			m.end = m.start + size-1;
    			position+=size;
    			handle++;
    			map.put(handle, m);// 添加
    		}
    		return flag;
    	}
        /**
         * 删除内存中指定的区域
         * @param start 起始值
         * @param end 结束值
         */
    	private static void delMemory(int start, int end) {
    		for (int i = 0; i < end - start + 1; i++) {
    			memory[start + i] = 0;
    		}
    	}
    
    }
    
    class Memory {
    	int start;// 内存存储的开始地值
    	int end;// 内存存储的结束值
    
    }

最后，如果对以上内容有疑惑，或者你有更好的方法，欢迎留言指出，共同进步！

[Center]: /images/20220717/e24197f299014a1ea5cd1afe4ef41022.png