Animal Shelter: An animal shelter, which holds only dogs and cats, operates on a strictly"first in, first out" basis. People must adopt either the"oldest" (based on arrival time) of all animals at the shelter, or they can select whether they would prefer a dog or a cat (and will receive the oldest animal of that type). They cannot select which specific animal they would like. Create the data structures to maintain this system and implement operations such as enqueue, dequeueAny, dequeueDog, and dequeueCat. You may use the built-in LinkedList data structure.
Hints: #22, #56, #63
分析
简单来说这么几个要求：
- Dog / Cat 按照插入的时间顺序排列
- 如果要求取Dog，则拿最早的Dog
- 如果要求取Cat，则拿最早的Cat
- 如果不要求，则拿最早的，拿到啥是啥
解法1
就弄一个链表，里面放了Dog和Cat，链表头是最旧的，链表尾是最新的。
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
|
public class Animal {}
public class Dog extends Animal {}
public class Cat extends Animal {}
public class AnimalShelter {
private LinkedList<Animal> animals = new LinkedList<>();
public void enqueue(Animal animal) {
animals.add(animal);
}
public Animal dequeueAny() {
return animals.removeFirst();
}
public Dog dequeueDog() {
for (Iterator<Animal> iter = animals.iterator(); iter.hasNext();) {
Animal animal = iter.next();
if (animal instanceof Dog) {
iter.remove();
return animal;
}
}
return null;
}
public Cat dequeueCat() {
// 和上面类似
}
}
|
时间复杂度：对于dequeueDog和dequeueCat来说复杂度是 O(n)。
解法2
有没有办法把dequeueDog和dequeueCat的时间复杂度变成 O(1)。
可以弄两个链表分别存储Dog和Cat，Dog和Cat里都入队时间。
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
|
public class Animal {
private long timestamp = System.currentTimeMillis();
}
public class Dog extends Animal {}
public class Cat extends Animal {}
public class AnimalShelter {
private LinkedList<Dog> dogs = new LinkedList<>();
private LinkedList<Cat> cats = new LinkedList<>();
public void enqueue(Animal animal) {
if (animal instanceof Dog) {
dogs.add((Dog)animal);
} else {
cats.add((Cat)animal);
}
}
public Animal dequeueAny() {
if (dogs.isEmpty()) {
return dequeueCats();
}
if (cats.isEmpty()) {
return dequeueDogs();
}
if (dogs.first().timestamp < cats.first().timestamp) {
return dequeueDogs();
}
return dequeueCats();
}
public Dog dequeueDog() {
if (dogs.isEmpty()) {
return null;
}
return dogs.removeFirst();
}
public Cat dequeueCat() {
if (cats.isEmpty()) {
return null;
}
return cats.removeFirst();
}
}
|
评论