米哈游笔试8-6号,第三题

米哈游,给树结点染色的问题,一开始没想出来,后来下来弄明白了。

问题:

树(其实是无向图),的节点涂色,只能涂R,G,B三色。同时非叶子结点两旁一定有与它自己不同的两种颜色,而叶子结点则不需要考虑这个问题。

比如,一个非叶子节点是R,跟它相连的至少有两个节点(我们假设有四个节点跟它相连),也就意味着,跟它相连的不仅有G,还有B(或许还有R,但是至少要满足G,和B才能谈别的)。

输入,N,节点总数  接下来n-1行,为n-1条边,但是保证不会成环,而且是连通图。


package com.exam; import java.util.*; /**  * @author pfh  * @date 2022/8/6 9:58  * @describe  * @return  * @requirement  */ public class Solution {     public static void main(String[] args) {         int n=5;        // int[][] adjcent = new int[n-1][2];         int[][] adjcent={{1,3},{3,5},{5,4},{2,3}};         List<List<Integer>> edgs = new ArrayList<>();         for(int i=0;i<n;i++){             edgs.add(new ArrayList<Integer>());         }         int[] color=new int[n]; // 用二进制来进行计算,这个用来记录,自己以及周围 节点已经选的颜色。         char[] colorChar=new char[n];         // 构建bfs         int[] inde=new int[n];         for(int i=0;i<adjcent.length;i++){             int u=adjcent[i][0];             int v=adjcent[i][1];             edgs.get(u-1).add(v-1);             edgs.get(v-1).add(u-1);             inde[u-1]++; //             inde[v-1]++;         }       // 因为是无向图,所以从哪一点出发都没问题,我们设置从0出发         colorChar[0]='R';         color[0]=4;// 100         LinkedList<Integer> queue = new LinkedList();         queue.offer(0);         boolean[] visited = new boolean[n];         while (!queue.isEmpty()){             int len = queue.size();             while (len-->0){                 int cur=queue.poll();                 visited[cur]=true;                 List<Integer> edg = edgs.get(cur);                 for(int next:edg){                     if(visited[next]){                         continue;                     }                     colorChar[next]=find(color, cur, colorChar[cur]);                     // 初始化color[next],color[next]一开始只与它自己选了什么和它的上一个节点有关。                     color[next]=check(colorChar[next])|check(colorChar[cur]);                     queue.offer(next);                 }             }         }         for(char co:colorChar){             System.out.println(co);         }     }     public static char find(int[] color,int index,char before){ // 这个before是来知道到底前一个是什么东西的         int nxchoose=color[index]^7; //与7异或,就知道要找哪一个了         char chooseChar='R';         int choice=0;         // 其实基本上只有这个地方能用到before,因为周围RGB颜色都没有,或者都选光的时候,特别是选光了的时候才需要去查看before是什么。         if(nxchoose==0||nxchoose==7){             // 那三个颜色都可以选;             if(before!='R')             {                 chooseChar ='R';                  choice=4;             }             else if(before!='G'){                 chooseChar ='G';                 choice=2;             }             else{                 chooseChar ='B';                 choice=1;             }         }         if(nxchoose==1){             chooseChar ='B';             choice=1;         }         if(nxchoose==2){             chooseChar ='G';             choice=2;         }         if(nxchoose==3){             if(before!='G'){                 chooseChar ='G';                 choice=2;             }             else{                 chooseChar ='B';                 choice=1;             }         }         if(nxchoose==4){             if(before!='R'){                 chooseChar ='R';                 choice=4;             }         }         if(nxchoose==5){             if(before!='R'){                 chooseChar ='R';                 choice=4;             }             else{                 chooseChar ='B';                 choice=1;             }         }         if(nxchoose==6){             if(before!='R'){                 chooseChar ='R';                 choice=4;             }             else{                 chooseChar ='G';                 choice=2;             }         }         color[index] = color[index] | choice;  // 更新cur的color状态。 因为是添加的关系,所以这里使用的是或。         return  chooseChar;     }     public static int check(char clorChar){         switch (clorChar){             case 'R':                 return 4;             case 'G':                 return 2;             default:                 return 1;         }     } }

#米哈游笔试#
全部评论
大佬牛逼啊,终于看到一个发答案的
点赞 回复 分享
发布于 2022-08-11 11:38
我想请问下这题输入输出、测试用例是什么样的?题目已经忘了
点赞 回复 分享
发布于 2022-08-11 13:56
面试时间是多久?
点赞 回复 分享
发布于 2022-08-09 20:46

相关推荐

jack_miller:杜:你不用我那你就用我的美赞臣
点赞 评论 收藏
分享
死在JAVA的王小美:哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈,我也是,让我免了一轮,但是硬气拒绝了
点赞 评论 收藏
分享
7 21 评论
分享
牛客网
牛客企业服务