9.28 滴滴笔试 100 72

秋招到现在一场面试都没有，给鼠鼠一个机会吧求面试求意向

第一题上来我直接dfs，过了82%，加了个剪枝，就直接100%了

import java.util.Scanner;

public class first {
    public static int ans=0;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] wood=new int[3];
        wood[0]=in.nextInt();
        wood[1]=in.nextInt();
        wood[2]=in.nextInt();
        int[][][] find=new int[wood[0]+1][wood[1]+1][wood[2]+1];
        if(judge(wood)){
            find[wood[0]][wood[1]][wood[2]]=1;
            ans++;
        }
        dfs(n,1,wood,find);
        System.out.println(ans);
    }
    public static void dfs(int n,int cut,int[] wood,int[][][] find){
        if(cut>n)
            return;
        for(int i=0;i<3;i++){
            if(wood[i]>cut){
                wood[i]-=cut;
                boolean flag=false;
                //判断这种当前的组合是否已经计算过，是的话就不用再往下dfs了
                if(find[wood[0]][wood[1]][wood[2]]==1){
                    flag=true;
                }
                if(judge(wood)&&!flag){
                    find[wood[0]][wood[1]][wood[2]]=1;
                    ans++;
                }
                if(!flag)
                    dfs(n,cut+1,wood,find);
                wood[i]+=cut;
            }
        }
    }
    public static boolean judge(int[] wood){
        if(wood[0]+wood[1]>wood[2]&& Math.abs(wood[0]-wood[1])<wood[2])
            return true;
        return false;
    }
}

第二题用HashMap+List存树，每次询问都用bfs求所有距离再求和，过了72%

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class second {
    public static void main(String[] args) throws IOException {
        BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
        String[] first_line=bf.readLine().split(" ");
        int n = Integer.valueOf(first_line[0]);
        int m = Integer.valueOf(first_line[1]);
        HashMap<Integer, List<Integer>> map=new HashMap<>();
        for(int i=0;i<n;i++){
            map.put(i+1,new ArrayList<>());
        }
        String[] second_line=bf.readLine().split(" ");
        int index=0;
        for(int i=2;i<=n;i++){
            int node=Integer.valueOf(second_line[index++]);
            List<Integer> first=map.get(i);
            first.add(node);
            map.put(i,first);
            List<Integer> second=map.get(node);
            second.add(i);
            map.put(node,second);
        }
        String[] third_line=bf.readLine().split(" ");
        for(int i=0;i<m;i++){
            int start=Integer.valueOf(third_line[i]);
            int ans=bfs(start,n,map);
            System.out.println(ans);
        }
    }
    public static int bfs(int start,int n,HashMap<Integer, List<Integer>> map){
        boolean[] visited=new boolean[n+1];
        Queue<Integer> queue=new LinkedList<>();
        queue.add(start);
        int ans=0;
        int distance=1;
        while(!queue.isEmpty()){
            int nums=queue.size();
            while(nums>0){
                int st=queue.poll();
                visited[st]=true;
                List<Integer> neighbours=map.get(st);
                for(int neighbour:neighbours){
                    if(visited[neighbour]==false){
                        queue.add(neighbour);
                        ans+=distance;
                    }
                }
                nums--;
            }
            distance++;
        }
        return ans;
    }
}