2022-4-15 网易互娱笔试
第一题:树
package org.wangyi; import java.util.HashMap; import java.util.Map; import java.util.Scanner; public class Main { static Map<Integer,Integer> position=new HashMap<>(); static int res=0; public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int[] inorder=new int[n]; int[] postorder=new int[n]; for(int i=0;i<n;i++){ inorder[i]=sc.nextInt(); position.put(inorder[i],i); } for(int i=0;i<n;i++){ postorder[i]=sc.nextInt(); } TreeNode root=build(inorder,0,n-1,postorder,0,n-1); // dfs01(root); dfs(root); System.out.println(res); } public static TreeNode build(int[] inorder,int left1,int right1,int[] postorder,int left2,int right2){ if(left1>right1){ return null; } int index=position.get(postorder[right2]); TreeNode root=new TreeNode(postorder[right2]); root.left=build(inorder,left1,index-1,postorder,left2,left2+index-1-left1); root.right=build(inorder,index+1,right1,postorder,left2+index-left1,right2-1); return root; } public static void dfs01(TreeNode root){ if(root==null){ return ; } System.out.println(root.val); dfs01(root.left); dfs01(root.right); } public static int dfs(TreeNode root){ if(root==null){ return 0; } int left=0,right=0; if(root.left!=null){ left=dfs(root.left); } if(root.right!=null){ right=dfs(root.right); } // System.out.println("root.val"+root.val); res=Math.max(res,left+right); return Math.max(left,right)+1; } } class TreeNode{ int val; TreeNode left; TreeNode right; public TreeNode(int val){ this.val=val; } public TreeNode(int val,TreeNode left,TreeNode right){ this.val=val; this.left=left; this.right=right; } }第二题: LRU
package org.wangyi; import java.util.*; import java.util.concurrent.LinkedBlockingDeque; public class Solution { public static void main(String[] args) { int i = stat_hit_count(new int[]{1, 2, 1, 3, 2}, 3); System.out.println(i); } static ListNode head,tail; static Map<Integer,ListNode> map=new HashMap<>(); static int res=0; static int capacity; static int size; public static int stat_hit_count (int[] R, int N) { // write code here head=new ListNode(0); tail=new ListNode(0); head.next=tail; tail.prev=head; size=0; capacity=N; ListNode cur=head; for(int i=0;i<R.length;i++){ get(R[i]); // cur=head; // while(cur.next!=tail){ // System.out.print(cur.next.val+" "); // cur=cur.next; // } // System.out.println(); } return res; } public static void get(int val){ ListNode node=map.get(val); if(node==null){ ListNode newNode=new ListNode(val); if(size==capacity){ ListNode listNode = removeTail(); map.remove(listNode.val); addHead(newNode); map.put(val,newNode); }else{ addHead(newNode); size++; map.put(val,newNode); } }else{ res++; removeNode(node); addHead(node); } } public static void removeNode(ListNode node){ node.prev.next=node.next; node.next.prev=node.prev; } public static void addHead(ListNode node){ node.next=head.next; node.prev=head.next.prev; head.next.prev=node; head.next=node; } public static ListNode removeTail(){ ListNode res=tail.prev; removeNode(res); return res; } } class ListNode{ ListNode prev; ListNode next; int val; public ListNode(int val){ this.val=val; } public ListNode(int val,ListNode prev,ListNode next){ this.val=val; this.prev=prev; this.next=next; } }第三题 0%
package org.wangyi; import java.util.*; public class Test01 { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int[] jump=new int[n]; for(int i=0;i<n;i++){ jump[i]=sc.nextInt(); } int res=bfs(jump); System.out.println(res); } public static int bfs(int[] jump){ Queue<Integer> queue=new LinkedList<>(); queue.offer(0); int cnt=0; while (!queue.isEmpty()) { int size=queue.size(); for(int k=0;k<size;k++){ Integer node = queue.poll(); if(node>=jump.length){ return cnt; } for(int i=0;i<node;i++){ queue.offer(i); } queue.offer(node+jump[node]); } cnt++; } return cnt; } }