携程java后端笔试8.30 第三题

这里虽然是树,但其实要用图来做
思路:
图上的任意一个节点都可做树根。
对全图颜色做hash计数。
设置访问状态数组。

随意选择一个节点做树根进行深搜。
对于当前节点,记录为访问过的状态。
将当前节点做树根,做后续遍历,返回每个子树统计的color的rgb计数,并累计,最后加上树根的颜色。
得到以当前节点为树根的树的颜色hash,看是否rgb都包含,并用全图颜色hash计数和其相减,可得到另一子图的颜色计数,判断合法。
最后返回子树的颜色hash
以此类推,只需要深搜一次,应该不会超时
事后想到的,不晓得能过多少用例。
java代码如下

import java.util.*;
public class Main {
    public static boolean[] visit;
    public static Map> linjiebiao;
    public static int[] colorhash;
    public  static int  ans=0;
    public  static String colors;
    public static void main(String[] args) {
        Scanner s=new Scanner(System.in);
        int n=s.nextInt();
        visit=new boolean[n];
        colors=s.next();
        //color hash
        colorhash=new int[3];
        for (char ch:colors.toCharArray()) {
            if(ch=='r')colorhash[0]++;
            else if(ch=='g')colorhash[1]++;
            else if(ch=='b')colorhash[2]++;
        }
        //构建图
        linjiebiao=new HashMap();
        int[][] edges=new int[n-1][2];
        for(int i=0;i<n-1;i++){
            int a,b;
            a=s.nextInt()-1;
            b=s.nextInt()-1;
            edges[i][0]=a;
            edges[i][1]=b;
            List list;
            if(linjiebiao.containsKey(a)){
                list=linjiebiao.get(a);
            }else {
                list=new ArrayList();
            }
            list.add(b);
            linjiebiao.put(a,list);
            if(linjiebiao.containsKey(b)){
                list=linjiebiao.get(b);
            }else {
                list=new ArrayList();
            }
            list.add(a);
            linjiebiao.put(b,list);
        }
        //随意选一个节点当树根
        dfs(3);
        System.out.println(ans);
    }
    public static int[] dfs(int root){
        //后续遍历
        visit[root]=true;
        int[] roothash=new int[3];
        List child=linjiebiao.get(root);
        for(int nei:child){
            if(!visit[nei]){
                int[] thash=dfs(nei);
                for(int i=0;i<3;i++)roothash[i]+=thash[i];
            }
        }
        char ch=colors.charAt(root);
        if(ch=='r')roothash[0]++;
        else if(ch=='g')roothash[1]++;
        else if(ch=='b')roothash[2]++;
        //后续遍历
        int co3=0;
        boolean flag=false;
        for(int i=0;i<3;i++){
            if(roothash[i]==0){
                flag=true;
                break;
            }
            if(colorhash[i]-roothash[i]==0){
                flag=true;
                break;
            }
        }
        if(!flag&&root!=3)ans++;//注意,总树根这里相当于没有断边,可以排除一下这种情况,但其实这种情况由于另一子图为空,肯定不满足情况。这里写,便于理解
        System.out.print("root:"+root+"   :");
        for (int i = 0; i < 3; i++) {
            System.out.print(" "+roothash[i]);
        }
        System.out.println();
        return roothash;
    }
}
#携程笔试#
全部评论
我dfs最后一个用例超时了。
点赞 回复 分享
发布于 2022-08-31 09:57 浙江

相关推荐

我是小红是我:学校换成中南
点赞 评论 收藏
分享
2 6 评论
分享
牛客网
牛客企业服务