Cinte's Leetcode Record
0%

面试题 03.06. 动物收容所

Posted on Edited on In Disqus:
Symbols count in article: 3.1k Reading time ≈ 3 mins.

面试题 03.06. 动物收容所

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
class AnimalShelf {
public:
    AnimalShelf() : head(new Node()), tail(new Node()) {
        head->next = tail;
        tail->prev = head;
    }
    
    void enqueue(vector<int> animal) {
        push(animal[0], animal[1]);
    }
    
    vector<int> dequeueAny() {
        if(tail->prev == head)
            return {-1, -1};
        vector<int> ret{tail->prev->num, tail->prev->type};
        deleteNode(tail->prev);
        return ret;
    }
    
    vector<int> dequeueDog() {
        auto ret = pop(1);
        if(ret == -1)
            return {-1, -1};
        return {ret, 1};
    }
    
    vector<int> dequeueCat() {
        auto ret = pop(0);
        if(ret == -1)
            return {-1, -1};
        return {ret, 0};
    }
private:
    struct Node
    {
        Node* next;
        Node* prev;
        int num = 0;
        int type;
        Node() = default;
        Node(Node* next, Node* prev, int num, int type) : next(next), prev(prev), num(num), type(type) {};
    };
    Node *head, *tail;
    void push(int num, int type)
    {
        auto next = head->next;
        head->next = new Node(head->next, head, num, type);
        next->prev = head->next;
    }
    int pop(int type)
    {
        auto point = tail->prev;
        while(point != head)
        {
            if(point->type == type)
            {
                auto ret = point->num;
                deleteNode(point);
                return ret;
            }
            point = point->prev;
        }
        return -1;
    }
    void deleteNode(Node* node)
    {
        auto tmp = node;
        node->prev->next = node->next;
        node->next->prev = node->prev;
        delete tmp;
    }
};

/**
 * Your AnimalShelf object will be instantiated and called as such:
 * AnimalShelf* obj = new AnimalShelf();
 * obj->enqueue(animal);
 * vector<int> param_2 = obj->dequeueAny();
 * vector<int> param_3 = obj->dequeueDog();
 * vector<int> param_4 = obj->dequeueCat();
 */

题目没写出来，编号是有先后的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class AnimalShelf {
public:
    AnimalShelf() {

    }
    
    void enqueue(vector<int> animal) {
        if(animal[1] == 0)
            cat.push_back(animal[0]);
        else
            dog.push_back(animal[0]);
    }
    
    vector<int> dequeueAny() {
        if(dog.empty() && cat.empty())
            return {-1, -1};
        if(dog.empty())
        {
            auto ret = cat.front();
            cat.pop_front();
            return {ret, 0};
        }else if(cat.empty())
        {
            auto ret = dog.front();
            dog.pop_front();
            return {ret, 1};
        }else if(dog.front() < cat.front())
        {
            auto ret = dog.front();
            dog.pop_front();
            return {ret, 1};
        }else
        {
            auto ret = cat.front();
            cat.pop_front();
            return {ret, 0};
        }
    }
    
    vector<int> dequeueDog() {
        if(dog.empty())
            return {-1, -1};
        auto ret = dog.front();
        dog.pop_front();
        return {ret, 1};
    }
    
    vector<int> dequeueCat() {
        if(cat.empty())
            return {-1, -1};
        auto ret = cat.front();
        cat.pop_front();
        return {ret, 0};
    }
private:
    deque<int> cat;
    deque<int> dog;
};

/**
 * Your AnimalShelf object will be instantiated and called as such:
 * AnimalShelf* obj = new AnimalShelf();
 * obj->enqueue(animal);
 * vector<int> param_2 = obj->dequeueAny();
 * vector<int> param_3 = obj->dequeueDog();
 * vector<int> param_4 = obj->dequeueCat();
 */