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;
    }
}

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;
    }
}

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;
    }
}