携程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; } }#携程笔试#