美团3.11笔试记录

自我感觉良好，尤其是我很菜情况下，幸运的没有碰到比较离谱的题

第一题签到

第二题 有代价的走格子吃金币，二维dp，这题接近AC，为了赶时间没管

第三题 看流星，每个流行有起始时间和结束时间，找能看到的最多的流行和持续时间

第四题 坦克大战游戏模拟 死活不AC

第五题 森林递归遍历，难点在于构建

下面是部分题目代码

第三题

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main
{
    static class Node
    {
        int start;
        int end;

        public Node(int start, int end)
        {
            this.start = start;
            this.end = end;
        }

        public int getStart()
        {
            return start;
        }

        public int getEnd()
        {
            return end;
        }
    }
    public static void main(String[] args)
    {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.nextLine();
        int[] start = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();
        int[] end = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();
        Node[] nodes = new Node[n];
        for (int i = 0; i < nodes.length; i++) {
            nodes[i] = new Node(start[i], end[i]);
        }
        Arrays.sort(nodes, Comparator.comparingInt(Node::getStart));
        PriorityQueue<Node> queue = new PriorityQueue<>(Comparator.comparing(Node::getEnd));
        int max = -1;
        int time = 0;
        int prevTime = 0;
        int nextTime = 0;
        int endTime = 0;
        int totalTime = 0;
        for (int i = 0; i < nodes.length; i++) {
            if (queue.isEmpty()) {
                queue.add(nodes[i]);
                time = nodes[i].start;
                continue;
            }

            queue.add(nodes[i]);
            time = nodes[i].start;
            while (!queue.isEmpty() && queue.peek().end < time) {
                Node poll = queue.poll();
                endTime = Math.max(endTime, poll.end);
            }
            if (queue.size() > max) {
                max = queue.size();
                prevTime = time;
            }
            else if (queue.size() == max) {
                totalTime += time - prevTime;
                prevTime = time;
            }
        }
        System.out.println(max);
        System.out.println(totalTime + 1);
    }
}

第五题

import java.util.*;
import java.util.stream.Collectors;

public class Main
{
    static class Node
    {
        LinkedList<Node> children;
        char color;

        public Node(int color)
        {

            this.color = (char)color;
            this.children = new LinkedList<>();
        }

    }
    static int ans;
    public static void main(String[] args)
    {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.nextLine();
        Node[] nodes = new Node[n];
        List<Node> collect = scanner.nextLine().chars().mapToObj(Node::new).collect(Collectors.toList());
        collect.toArray(nodes);
        int[] arr = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();
        for (int i = 0; i < arr.length; i++) {
            int father = arr[i] - 1;
            int current = i + 1;
            nodes[father].children.add(nodes[current]);
        }
        dfs(nodes[0]);
        System.out.println(ans);
    }

    static class Counter
    {
        int red;
        int blue;

        void add(Counter counter)
        {
            this.red += counter.red;
            this.blue += counter.blue;
        }

        boolean isBalanced()
        {
            return this.red == this.blue;
        }
    }
    public static Counter dfs(Node node)
    {

        Counter counter = new Counter();
        for (Node child : node.children) {
            counter.add(dfs(child));
        }
        if (counter.isBalanced()) {
            ans++;
        }
        if(node.color == 'R') counter.red++;
        else if(node.color == 'B') counter.blue++;
        return counter;
    }
}