华为5.8笔试
1.模拟寄存器计算
其实就是处理字符串
package exe4_模拟汇编计算; /** * @Author: jiew * @date: 2024/5/8 21:53 * @Description: **/ import java.util.HashMap; import java.util.Scanner; public class Solution { HashMap<String,Integer> var=new HashMap<>(); public void run(){ Scanner scanner=new Scanner(System.in);//处理输入 while (scanner.hasNextLine()){ String line=scanner.nextLine(); if(line.equals(""))break; String[] item=line.split(" "); int size=item.length; switch (size){ case 3: var.put(item[1], Integer.parseInt(item[2]));//字符串转整数 break; case 4: caculate(item); break; case 2: System.out.println(var.get(item[1])); } } } private void caculate(String[] item) { String item1=item[1]; String op1=item[2]; String op2=item[3]; if(item[0].equals("ADD")){ var.put(item1,getValue(op1)+getValue(op2)); } else if(item[0].equals("SUB")){ var.put(item1,getValue(op1)-getValue(op2)); } else if(item[0].equals("MUL")){ var.put(item1,getValue(op1)*getValue(op2)); } else if(item[0].equals("DIV")){ var.put(item1,getValue(op1)/getValue(op2)); } } private int getValue(String str){ if(str.startsWith("a")){ return var.get(str); }else return Integer.parseInt(str); } public static void main(String[] args) { Solution so=new Solution(); so.run(); } } /* MOV a1 100 MOV a2 200 PRINT a1 ADD a3 a1 100 SUB a4 a3 a2 PRINT a4 //100 0 MOV a1 100 MOV a2 200 ADD a3 a1 100 SUB a4 a3 a2 PRINT a4 //0 * */
2.最少使用次数+最久未使用缓存队列
package exe5_最久最少使用缓存; /** * @Author: jiew * @date: 2024/5/8 21:56 * @Description: 删除元素准则:1.最少使用次数 2.如果最少使用次数有相同的,就删除其中最久未使用的 * 1.查询时间O(1) 2.增加插入时间o(1)或o(n) 3.删除时间o(1) * 哈希表+双向链表 * 双向链表维护表头为刚刚使用的节点,表尾为最久未使用节点 * 哈希表映射key值对应的节点Node * Node记录key,value,countNum(使用次数记录) * * 1.通过哈希表映射节点读取Node.value * 2.缓存队列还有余量:插:构建节点-哈希表映射key,Node-节点插入链表头部 * 2.缓存队列满了:先删,再插: * 3.删除节点: 双向链表删除某节点+哈希表删除元素 遍历链表所有节点,将使用次数最少节点的key存到数组中,若只有一个元素直接删(链表中删节点+哈希表删节点),若数组中有多个节点则从链表尾端找到数组中最久未使用的节点删(链表+哈希表都删) **/ import java.util.ArrayList; import java.util.HashMap; import java.util.Scanner; class Node{ int key,value,useCount; Node lNode,rNode; Node(){} Node(int key,int value,int useCount){ this.key=key; this.value=value; this.useCount=useCount; } } //链表维护最久未使用 //节点记录使用次数 最少使用次数淘汰 则遍历n个节点进行保留次数最少使用的节点 public class Solution2 { Node head,tail; HashMap<Integer,Node> map; int capacity; Solution2(int capacity){ head=new Node(); tail=new Node(); head.rNode=tail; tail.lNode=head; map=new HashMap<>(capacity); this.capacity=capacity; } public void run(Scanner scanner){ while (scanner.hasNextLine()){ String line=scanner.nextLine(); if(line.equals(""))break; //写\读 刷新使用次数和时间 if(line.startsWith("wri")){ //如果链表没有满capacity //创建节点-写入map-写使用时间 //如果链表满了capacity //按照策略删节点再添加 int num=Integer.parseInt(scanner.nextLine()); for(int i=0;i<num;i++){ String line0=scanner.nextLine(); String[] item=line0.split(" "); write(item); } }else if(line.startsWith("rea")){ //更新使用次数和使用时间 int num=scanner.nextInt(); scanner.nextLine(); read(num); }else if(line.startsWith("que")){ int num=scanner.nextInt(); scanner.nextLine(); if(map.containsKey(num)){ System.out.println(map.get(num).value); }else { System.out.println(-1); } } } } private void read(int num) { //更新使用次数和使用时间 Node node=map.get(num); node.useCount=node.useCount+1; //更新使用时间 将该节点插入到链表头(链表头表示最新使用,链表尾表示最久没使用): 1.将该节点的左右节点先连起来 2.将该节点插入链表的开头 //1. node.lNode.rNode=node.rNode; node.rNode.lNode=node.lNode; //2. Node tmp=head.rNode; head.rNode=node; node.lNode=head; node.rNode=tmp; tmp.lNode=node; } //创建节点-写入map-构造链表 private void write(String[] item) { if(map.size()==capacity)delete(); int key=Integer.parseInt(item[0]); int value=Integer.parseInt(item[1]); Node node=new Node(key,value,1); //链表表头插入节点 新加入的节点表示最新访问的节点所以插入链表头 Node next=head.rNode; head.rNode=node; node.lNode=head; next.lNode=node; node.rNode=next; //写入map map.put(key,node); } //按照策略删除缓存节点 0.确认删哪个节点 1.在链表中删除这个节点 2.在哈希表中删除这个节点 private void delete() { //0. //有先删除最少次数的 然后是最久未使用 //找最久未使用:遍历所有节点 将使用次数最少的节点都记录在数组 从链表尾部开始遍历链表 删除第一个在数组中出现的节点 Node node=head.rNode; ArrayList<Integer>minCountNumKey=new ArrayList<>(); int minCountNum=Integer.MAX_VALUE; while (node!=tail){ if(node.useCount<minCountNum){ minCountNumKey.clear(); minCountNum=node.useCount; minCountNumKey.add(node.key); }else if(node.useCount==minCountNum){ minCountNumKey.add(node.key); } node=node.rNode; } if(minCountNumKey.size()==1){ //1.2. deleteNode(node); map.remove(node.key); } else { Node node1=tail.lNode; while (node1!=head){ if(minCountNumKey.contains(node1.key)){ //1.2. deleteNode(node1); map.remove(node1.key); break; } node1=node1.lNode; } } } //链表删除节点node private void deleteNode(Node node){ Node l=node.lNode; Node r=node.rNode; l.rNode=r; r.lNode=l; } public static void main(String[] args) { Scanner scanner=new Scanner(System.in); scanner.nextLine(); int capacity=scanner.nextInt(); scanner.nextLine(); Solution2 so=new Solution2(capacity); so.run(scanner); } } /*1.2h capacity: 4 write: 5 3 5 1 2 4 3 2 3 5 4 read: 4 read: 1 read: 2 read: 5 write: 1 6 1 query: 1 //2 capacity: 3 write: 3 1 2 4 3 2 3 read: 2 write: 1 3 1 query: 1 //-1 */