携程java后端 4.15 笔试

建房子

第一个月建一个红“R"房子，后面的每一个月在新建的房子左边建一个绿"G"房子右边见一个"R"房子
输入：N个月
输出：N个月后街道上的房子排列

例子：
输入：1
输出：R

输入：2
输出：GRR

输入：3
输出：GGRRGR

    static String buildingHouse(String n) {
        int N = 1;
        try {
            N = Integer.parseInt(n);
        } catch (NumberFormatException e) {
            return "N";
        }
        if (N < 1 || N > 12) {
            return "O";
        }
        return build(N, "R");
    }

    static String build(int round, String H) {
        if (round == 1) {
            return H;
        }
        String ret = build(round-1, "G") + H + build(round-1, "R");
        return ret;
    }

递归就完事了，和建括号差不多

找被污染的包

输入：第一行是被污染的包，后面的所有行是包的依赖关系，2,3,6表示2依赖于3和6
输出：找出所有受到影响的包的和

例子：
输入：
4
1,2
2,3,6
3,4,5,6
6,2,4
8,9
10

输出：12
受影响的是1，2，3，6加起来为12

邻接表BFS

import java.util.*;

public class Ctrip2 {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int source = cin.nextInt();
        cin.nextLine();
        HashMap<Integer, LinkedList> graph = new HashMap<>();
        while (cin.hasNextLine()) {
            String[] line = cin.nextLine().split(",");
            int N = line.length;
            int[] int_line = new int[N];
            for (int i=0; i < N; i++) {
                int_line[i] = Integer.parseInt(line[i]);
            }
            int influenced = int_line[0];
            for (int i=1; i < N; i++) {
                int key = int_line[i];
                LinkedList<Integer> link = graph.getOrDefault(key, new LinkedList<Integer>());
                link.add(influenced);
                graph.put(key, link);
            }
        }

        System.out.println(sumPollutants(graph, source));
    }

    public static int sumPollutants(HashMap<Integer, LinkedList> graph, int src) {
        if (!graph.containsKey(src)) {
            return -1;
        }
        Queue<Integer> q = new LinkedList<>();
        HashSet<Integer> visited = new HashSet<>();
        q.offer(src);
        visited.add(src);
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i=0; i < size; i++) {
                int curr = q.poll();
                if (!graph.containsKey(curr)) {
                    continue;
                }
                LinkedList<Integer> children = graph.get(curr);
                for (Integer child: children) {
                    if (visited.contains(child)) {
                        continue;
                    }
                    q.offer(child);
                    visited.add(child);
                }
            }
        }
        int sum = 0;
        for (Integer v: visited) {
            sum += v;
        }
        return sum - src;
    }
}