华为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
*/
