能帮我看看我写的8.30携程笔试第三题哪里有问题吗?

import java.util.*;
class TreeNode1 {
    int key;
    char color;
    List<TreeNode1> neibors = new ArrayList<>();
}
public class Main6 {
    public boolean DFS(TreeNode1 head,boolean[] flag,boolean[] isVisited) {
        if(head.color == 'r') flag[0] = true;
        else if(head.color == 'g') flag[1] = true;
        else flag[2] = true;
        if(flag[0]&&flag[1]&&flag[2]) return true;
        for(int i = 0;i<head.neibors.size();i++){
            TreeNode1 neibor = head.neibors.get(i);
            if(!isVisited[neibor.key]){
                isVisited[neibor.key] = true;
                if(DFS(neibor,flag,isVisited)){
                    return true;
                }
            }
        }
        return flag[0]&&flag[1]&&flag[2];
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        in.nextLine();
        String color = in.nextLine();
        char[] charArray = color.toCharArray();
        TreeNode1[] tree = new TreeNode1[n];
        int result = 0;
        Main6 main = new Main6();
        while(n>1){
            int i = in.nextInt();
            int j = in.nextInt();
            i-=1;
            j-=1;
            if(tree[i] == null) {
                tree[i] = new TreeNode1();
                tree[i].key = i;
                tree[i].color = charArray[i];
            }
            if(tree[j]==null){
                tree[j] = new TreeNode1();
                tree[j].key = j;
                tree[j].color = charArray[j];
            }
            tree[i].neibors.add(tree[j]);
            tree[j].neibors.add(tree[i]);
            n--;
        }
        Set<String> cutSet = new HashSet<>();
        for(int i = 0;i<tree.length;i++){
            for(int j = 0;j<tree[i].neibors.size();j++){
                TreeNode1 delet = tree[i].neibors.get(j);
                StringBuilder cut = new StringBuilder(i+","+tree[i].neibors.get(j).key);
                if(!cutSet.contains(cut.toString())){
                    cutSet.add(cut.toString());
                    cut.reverse();
                    cutSet.add(cut.toString());
                    boolean[] isVisited = new boolean[tree.length];
                    isVisited[i] = true;
                    isVisited[delet.key] = true;
                    if(main.DFS(tree[i],new boolean[3],isVisited)&&main.DFS(delet,new boolean[3],isVisited)){
                        result ++;
                    }
                }
            }
        }
        System.out.println(result);
    }
}
暴力删除边+DFS检测删除后生成的俩颗树是否符合条件
只过了百分之6.21,和骗分差不多了

#携程##携程笔试#
全部评论

相关推荐

找工作勤劳小蜜蜂:自我描述部分太差,完全看不出想从事什么行业什么岗位,也看不出想在哪个地区发展,这样 会让HR很犹豫,从而把你简历否决掉。现在企业都很注重员工稳定性和专注性,特别对于热爱本行业的员工。 你实习的工作又太传统的it开发(老旧),这部分公司已经趋于被淘汰,新兴的互联网服务业,比如物流,电商,新传媒,游戏开发和传统的It开发有天然区别。不是说传统It开发不行,而是就业岗位太少,基本趋于饱和,很多老骨头还能坚持,不需要新血液。 工作区域(比如长三角,珠三角,成渝)等也是HR考虑的因素之一,也是要你有个坚定的决心。否则去几天,人跑了,HR会被用人单位骂死。
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
正在热议
更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务