题解 | #CD100 猫狗队列#

双队列解法

• 运行时间：2054ms，超过52.30% 用Java提交的代码
• 占用内存：45940KB，超过96.82%用Java提交的代码

第一遍做，代码思想就是对的，一直不通过，是因为每次结果都立即输出，会因多次IO操作而超时。 改进措施可以先用StringBuilder拼接输出，最后再一次性输出结果，缺点是占用内存较多。

import java.util.*;
import java.io.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    Deque<Node> dogs = new LinkedList<>();
    Deque<Node> cats = new LinkedList<>();
    int index = 0;
    public static void main(String[] args) throws IOException {
        Main mn = new Main();
        BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
        int row = Integer.parseInt(sc.readLine());
        for (int i = 0; i < row; i++) {
            String s = sc.readLine();
            switch (s) {
                case "pollAll":
                    mn.pollAll();
                    break;
                case "pollDog":
                    mn.pollDog();
                    break;
                case "pollCat":
                    mn.pollCat();
                    break;
                case "isEmpty":
                    mn.isEmpty();
                    break;
                case "isDogEmpty":
                    mn.isDogEmpty();
                    break;
                case "isCatEmpty":
                    mn.isCatEmpty();
                    break;
                default:
                    String[] ss = s.split(" ");
                    String pet = ss[1];
                    int num = Integer.valueOf(ss[2]);
                    mn.add(pet, num);
                    break;

            }
        }
    }
    private void isEmpty() {
        if (cats.isEmpty() && dogs.isEmpty()) {
            System.out.println("yes");
        } else {
            System.out.println("no");
        }
    }
    private void isDogEmpty() {
        if (dogs.isEmpty())  {
            System.out.println("yes");
        } else {
            System.out.println("no");
        }
    }
    private void isCatEmpty() {
        if (cats.isEmpty())  {
            System.out.println("yes");
        } else {
            System.out.println("no");
        }
    }
    private void pollAll() {
        StringBuilder sb = new StringBuilder();
        while (!dogs.isEmpty() && !cats.isEmpty()) {
            int didx = dogs.peek().idx;
            int cidx = cats.peek().idx;
            if (didx < cidx) {
                Node node = dogs.pop();
                sb.append("dog ");
                sb.append(node.val);
                sb.append("\n");

//                 System.out.println("dog " + node.val);
            } else {
                Node node = cats.pop();
                sb.append("cat ");
                sb.append(node.val);
                sb.append("\n");
//                 System.out.println("cat " + node.val);
            }
        }
        while (!dogs.isEmpty()) {
            Node node = dogs.pop();
            sb.append("dog ");
            sb.append(node.val);
            sb.append("\n");
//             System.out.println("dog " + node.val);
        }

        while (!cats.isEmpty()) {
            Node node = cats.pop();
            sb.append("cat ");
            sb.append(node.val);
            sb.append("\n");
//             System.out.println("cat " + node.val);
        }
        System.out.print(sb.toString());
    }

    private void pollDog() {
        StringBuilder sb = new StringBuilder();
        while (!dogs.isEmpty()) {
            Node node = dogs.pop();
            sb.append("dog ");
            sb.append(node.val);
            sb.append("\n");
        }
        System.out.print(sb.toString());

    }
    private void pollCat() {
        StringBuilder sb = new StringBuilder();
        while (!cats.isEmpty()) {
            Node node = cats.pop();
            sb.append("cat ");
            sb.append(node.val);
            sb.append("\n");
        }
        System.out.print(sb.toString());
    }
    private void add(String type, int num) {
        Node node = new Node(index++, num);
        if (type.equals("cat")) {
            cats.add(node);
        } else {
            dogs.add(node);
        }
    }
}

class Node {
    Integer idx;
    Integer val;

    Node() {}
    Node(int idx, int val) {
        this.idx = idx;
        this.val = val;
    }

}

单队列解法

把 Cat 和 Dog 保存在同一个队列中，Node 多增加了 cat 和 dog 指针。算下来，在时间和内存上都比双队列要提升一点点，但是提升不多，代码倒是复杂许多，不是非常好的做法

• 运行时间：1804ms，超过56.18% 用Java提交的代码
• 占用内存：32312KB， 超过97.53%用Java提交的代码

import java.util.*;
import java.io.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    Node head = new Node();
    Node tail = head;
    Node tdog = head;
    Node tcat = head;
    public static void main(String[] args) throws IOException {
        Main mn = new Main();
        BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
        int row = Integer.parseInt(sc.readLine());
        for (int i = 0; i < row; i++) {
            String s = sc.readLine();
            switch (s) {
                case "pollAll":
                    mn.pollAll();
                    break;
                case "pollDog":
                    mn.pollDog();
                    break;
                case "pollCat":
                    mn.pollCat();
                    break;
                case "isEmpty":
                    mn.isEmpty();
                    break;
                case "isDogEmpty":
                    mn.isDogEmpty();
                    break;
                case "isCatEmpty":
                    mn.isCatEmpty();
                    break;
                default:
                    String[] ss = s.split(" ");
                    String pet = ss[1];
                    int num = Integer.valueOf(ss[2]);
                    mn.add(pet, num);
                    break;

            }
        }
    }
    private void isEmpty() {
        if (tail == head) {
            System.out.println("yes");
        } else {
            System.out.println("no");
        }
    }
    private void isDogEmpty() {
        if (tdog == head)  {
            System.out.println("yes");
        } else {
            System.out.println("no");
        }
    }
    private void isCatEmpty() {
        if (tcat == head)  {
            System.out.println("yes");
        } else {
            System.out.println("no");
        }
    }
    private void pollAll() {
        StringBuilder sb = new StringBuilder();
        Node p = head.next;
        while(p != null) {
            if(p.type == 0) {
                sb.append("cat ");
            }else {
                sb.append("dog ");
            }
            sb.append(p.val);
            sb.append("\n");
            p = p.next;
        }
        head.next = null;
        head.dog = null;
        head.cat = null;
            
        tail = head;
        tcat = head;
        tdog = head;
        System.out.print(sb.toString());
    }

    private void pollDog() {
        StringBuilder sb = new StringBuilder();
        Node p = head.dog;
        while (p != null) {
            sb.append("dog ");
            sb.append(p.val);
            sb.append("\n");
            p.prev.next = p.next;
            if (p.next != null) {
                p.next.prev = p.prev;
            }
            p = p.dog;
        }
        head.dog = null;
        tdog = head;
        if(tail.type == 1) tail = tcat;
        System.out.print(sb.toString());

    }
    private void pollCat() {
        StringBuilder sb = new StringBuilder();
        Node p = head.cat;
        while (p != null) {
            sb.append("cat ");
            sb.append(p.val);
            sb.append("\n");
            p.prev.next = p.next;
            if (p.next != null) {
                p.next.prev = p.prev;
            }
            p = p.cat;
        }
        head.cat = null;
        tcat = head;
        if(tail.type == 0) tail = tdog;
        System.out.print(sb.toString());

    }
    private void add(String type, int num) {
        Node node = new Node(num);
        node.prev = tail;
        tail.next = node;
        tail = node;
        if (type.equals("cat")) {
            node.type = 0;
            tcat.cat = node;
            tcat = node;
        } else {
            node.type = 1;
            tdog.dog = node;
            tdog = node;
        }
    }
}

class Node {
    Node next;
    Node cat;
    Node dog;
    Node prev;
    Integer val;
    int type;

    Node() {}
    Node(int val) {
        this.val = val;
    }

}