4.16携程笔试 2.25/4

第一题

    static void solve() throws IOException {
        String str = in.nextLine();
        // 贪心
        char[] s = str.toCharArray();
        int n = s.length;
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (i + 1 < n && s[i] == 'y' && s[i + 1] == 'u') {
                res++;
            }
        }
        out.println(res);
    }

第二题

    static void solve() throws IOException {
        // 贪心
        int n = in.nextInt();
        int[] a = new int[n], b = new int[n], c = new int[n];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) { a[i] = in.nextInt(); }
        for (int i = 0; i < n; i++) { b[i] = in.nextInt(); }
        for (int i = 0; i < n; i++) {
            c[i] = in.nextInt();
            map.merge(c[i], 1, Integer::sum);
        }
        int res = 0;
        for (int i = 0; i < n; i++) {
            int key = a[i] + b[i];
            if (map.getOrDefault(key, 0) > 0) {
                res++;
                map.merge(key, -1, Integer::sum);
            }
        }
        out.println(res);
    }

第三题 5%

感觉应该是 dp

    static final int MX = 1000005;
    static boolean[] isPrime = new boolean[MX];
    static {
        Arrays.fill(isPrime, true);
        isPrime[0] = false;
        isPrime[1] = false;
        for (int i = 2; i < MX; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j > 0 && j < MX; j += i) {
                    isPrime[j] = false;
                }
            }
        }
    }

    static void solve() throws IOException {
        // 贪心 分析：2 + 3 可以得到素数 5 多一次机会 2 + 5 可以得到素数 7 多一次机会 1 不是素数
        // dp
        int n = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) { a[i] = in.nextInt(); }
        int pre = a[0], res = n;
        for (int i = 1; i < n; i++) {
            if (isPrime[pre] && isPrime[a[i]] && isPrime[pre + a[i]]) {
                pre = pre + a[i];
                res--;
                continue;
            }
            if (i + 1 < n && isPrime[a[i + 1]] && isPrime[a[i]] && isPrime[a[i + 1] + a[i]]) {
                pre = a[i + 1] + a[i];
                i++;
                res--;
                continue;
            }
            if (isPrime[pre] && isPrime[a[i]]) {
                pre = pre + a[i];
                res--;
                continue;
            }
            pre = a[i];
        }
        out.println(res);
    }

第四题 20%

不会反向建图 求dis数组是O(n^2) 超时了

dis[n + 1][2]记录每个节点出发到达叶子节点的最长距离和次长距离

    static void solve() throws IOException {
        // 分析：需要的信息，从每个节点出发到达叶子节点的最长距离和次长距离
        int n = in.nextInt();
        List<Integer>[] g = new ArrayList[n + 1];
        root = new int[n + 1];
        root[1] = 0;
        Arrays.setAll(g, e -> new ArrayList<Integer>());
        for (int i = 0; i < n - 1; i++) {
            int u = in.nextInt(), v = in.nextInt();
            g[u].add(v);
            g[v].add(u);
        }
        for (int i = 1; i <= n; i++) {
            int[][] dis = new int[n + 1][2];
            dis[i] = dfs(i, -1, g, dis);
            if (dis[i][0] == 0 || dis[i][1] == 0) {
                out.println(dis[i][0] + dis[i][1] + 1);
            } else {
                out.println(dis[i][0] + dis[i][1]);
            }
        }
    }

    private static int[] dfs(int x, int fa, List<Integer>[] g, int[][] dis) {
        // 正向遍历 记录父结点 同时反向建图
        if (g[x].size() == 1 && g[x].get(0) == fa) {
            return dis[x];
        }
        for (int child : g[x]) {
            if (child == fa) continue;
            int[] info = dfs(child, x, g, dis);
            if (info[0] + 1 > dis[x][0]) {
                dis[x][1] = dis[x][0];
                dis[x][0] = info[0] + 1;
            } else if (info[0] + 1 > dis[x][1]) {
                dis[x][1] = info[0] + 1;
            }
        }
        return dis[x];
    }