华为4.7晚实习笔试(机试)

第一题100% 第二题90% 第三题40%

第一题小孩分组

每个小孩都有想要一起组队的人如：(John, Jack)
输入N 和 N行上述二元组求老师最少可以将孩子们分为多少个组
思路：dfs或者bfs染色即可（坑点：N并不是孩子的数量
本人代码如下，可能不是很优雅。。大佬轻喷

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Map<String, Integer> color = new HashMap<>();
        Map<String, List<String>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            String s1 = sc.next();
            String s2 = sc.next();
            color.put(s1, -1);
            color.put(s2, -1);
            if (!map.containsKey(s1)) {
                List<String> tmp = new ArrayList<>();
                tmp.add(s2);
                map.put(s1, tmp);
            } else {
                map.get(s1).add(s2);
            }
            if (map.containsKey(s2)) {
                map.get(s2).add(s1);
            } else {
                List<String> tmp = new ArrayList<>();
                tmp.add(s1);
                map.put(s2, tmp);
            }
        }
        int c = 0;
        for (String s : map.keySet()) {
            if (color.get(s) == -1) {
                dfs(s, map, color, c);
                c++;
            }
        }
        System.out.println(c);
    }

    public static void dfs(String start, Map<String, List<String>> map,  Map<String, Integer> color, int c) {
        if (color.get(start) == -1) {
            color.put(start, c);
            if (map.get(start) != null){
                for (String s : map.get(start)) {
                    dfs(s, map, color, c);
                }
            }

        }
    }

第二题任务执行(自己瞎取的名字)

第一行输入n个逗号隔开的数，每个数分别对应0~n-1号任务需要执行的时间，如：1,3,4

代表任务0需要执行1个时间单位，任务1需要执行3个时间单位，等等

第二行输入任务之间的依赖关系，如：0->2,1->3

每个依赖关系由逗号隔开，没有空格
上述输入表示0依赖于任务2，且1依赖于任务3，任务依赖即代表，任务0需要在任务2完成之后才能进行，如果执行到任务0，任务2还没开始，则任务0移到队尾并开始等待，直到任务2完成后才能开始执行，等待的时间也需要被计算

最后输出每个任务的时间

包含执行时间和等待时间(如果存在等待时间的话)

样例：
1,3,4
0->2
输出：8,3,7
这道题本人直接是模拟做的，最后90%不太知道为啥，代码在下面，请大佬不吝赐教

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String line1 = sc.nextLine();
        String[] missions = line1.split(",");
        int n = missions.length;
        int[] missionTime = new int[n];
        Deque<Integer> dq = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            missionTime[i] = Integer.parseInt(missions[i]);
            dq.offer(i);
        }

        String line2 = sc.nextLine();
        String[] depends;
        if (line2.length() == 0) depends = new String[0];
        else depends = line2.split(",");
        int[] time = new int[n];

        Map<Integer, Integer> dependMap = new HashMap<>();
        for (String depend : depends) {
            String[] tmp = depend.split("->");
            int key = Integer.parseInt(tmp[0]);
            if (dependMap.containsKey(key)) {
                dependMap.put(key, Math.max(dependMap.get(key), Integer.parseInt(tmp[1])));
            } else dependMap.put(key, Integer.parseInt(tmp[1]));
        }
        Map<Integer, List<Integer>> reverse = new HashMap<>();
        for (Integer integer : dependMap.keySet()) {
            int revKey = dependMap.get(integer);
            if (reverse.containsKey(revKey)) {
                reverse.get(revKey).add(integer);
            } else {
                List<Integer> tmp = new ArrayList<>();
                tmp.add(integer);
                reverse.put(revKey, tmp);
            }
        }

        int exeTime = 0;
        Set<Integer> trigger = new HashSet<>();
        for (Integer key : dependMap.keySet()) {
            trigger.add(dependMap.get(key));
        }
        while (!dq.isEmpty()) {
            int poll = dq.poll();
            if (dependMap.containsKey(poll)) {
                dq.offer(poll);
            } else {
                if (trigger.contains(poll)) {
                    List<Integer> list = reverse.get(poll);
                    for (Integer integer : list) {
                        dependMap.remove(integer);
                    }
                }
                time[poll] = missionTime[poll] + exeTime;
                exeTime += missionTime[poll];
            }
        }
        for (int i = 0; i < time.length; i++) {
            if (i == time.length - 1) {
                System.out.print(time[i] + "\n");
            }
            else System.out.print(time[i] + ",");
        }

第三题游乐场游玩

输入三个数row，col，t和一个方阵方阵中每个元素代表该项目需要花费的时间
row代表行数，col代表列数，t则是一个给定的游玩时间，要求从左上角入口开始游玩到右下角出口，只能往右或者往下游玩，保证最终游玩时间不超过t且最接近t，并输出。如果不存在游玩时间满足前面条件，即最小游玩时间都超过t了，输出-1

这道题应该是dp，不太会。。
简单dp了以下把最小值算出来然后把-1的情况(20%)写了。然后再随便蒙了一点分最后40%

#华为##笔经#