动物收容所。有家动物收容所只收容狗与猫，且严格遵守“先进先出”的原则。
在收养该收容所的动物时，收养人只能收养所有动物中“最老”（由其进入收容所的时间长短而定）的动物，
或者可以挑选猫或狗（同时必须收养此类动物中“最老”的）。
换言之，收养人不能自由挑选想收养的对象。
请创建适用于这个系统的数据结构，实现各种操作方法，
比如enqueue、dequeueAny、dequeueDog和dequeueCat。允许使用Java内置的LinkedList数据结构。
enqueue方法有一个animal参数，animal[0]代表动物编号，animal[1]代表动物种类，其中 0 代表猫，1 代表狗。
dequeue*方法返回一个列表[动物编号, 动物种类]，若没有可以收养的动物，则返回[-1,-1]。
示例1:输入：
["AnimalShelf", "enqueue", "enqueue", "dequeueCat", "dequeueDog", "dequeueAny"]
[[], [[0, 0]], [[1, 0]], [], [], []]
输出：[null,null,null,[0,0],[-1,-1],[1,0]]
示例2:输入：
["AnimalShelf", "enqueue", "enqueue", "enqueue", "dequeueDog", "dequeueCat", "dequeueAny"]
[[], [[0, 0]], [[1, 0]], [[2, 1]], [], [], []]
输出：[null,null,null,null,[2,1],[0,0],[1,0]]
说明:收纳所的最大容量为20000
解题思路分析1、双数组；时间复杂度O(1)，空间复杂度O(n)
type AnimalShelf struct {
cat [][]int
dog [][]int
}
func Constructor() AnimalShelf {
return AnimalShelf{
cat: make([][]int, 0),
dog: make([][]int, 0),
}
}
func (this *AnimalShelf) Enqueue(animal []int) {
if animal[1] == 0 {
this.cat = append(this.cat, animal)
} else {
this.dog = append(this.dog, animal)
}
}
func (this *AnimalShelf) DequeueAny() []int {
if len(this.dog) == 0 && len(this.cat) == 0 {
return []int{-1, -1}
}
if len(this.dog) == 0 || len(this.cat) == 0 {
if len(this.dog) == 0 {
res := this.cat[0]
this.cat = this.cat[1:]
return res
}
res := this.dog[0]
this.dog = this.dog[1:]
return res
}
if this.dog[0][0] > this.cat[0][0] {
res := this.cat[0]
this.cat = this.cat[1:]
return res
}
res := this.dog[0]
this.dog = this.dog[1:]
return res
}
func (this *AnimalShelf) DequeueDog() []int {
if len(this.dog) == 0 {
return []int{-1, -1}
}
res := this.dog[0]
this.dog = this.dog[1:]
return res
}
func (this *AnimalShelf) DequeueCat() []int {
if len(this.cat) == 0 {
return []int{-1, -1}
}
res := this.cat[0]
this.cat = this.cat[1:]
return res
}
2、内置list；时间复杂度O(1)，空间复杂度O(n)
type AnimalShelf struct {
arr [2]*list.List
}
func Constructor() AnimalShelf {
return AnimalShelf{
arr: [2]*list.List{list.New(), list.New()},
}
}
func (this *AnimalShelf) Enqueue(animal []int) {
this.arr[animal[1]].PushBack(animal[0])
}
func (this *AnimalShelf) DequeueAny() []int {
if this.arr[0].Len() == 0 && this.arr[1].Len() == 0 {
return []int{-1, -1}
}
if this.arr[1].Len() > 0 &&
(this.arr[0].Len() == 0 || this.arr[1].Front().Value.(int) < this.arr[0].Front().Value.(int)) {
return []int{this.arr[1].Remove(this.arr[1].Front()).(int), 1}
}
return []int{this.arr[0].Remove(this.arr[0].Front()).(int), 0}
}
func (this *AnimalShelf) DequeueDog() []int {
if this.arr[1].Len() > 0 {
return []int{this.arr[1].Remove(this.arr[1].Front()).(int), 1}
}
return []int{-1, -1}
}
func (this *AnimalShelf) DequeueCat() []int {
if this.arr[0].Len() > 0 {
return []int{this.arr[0].Remove(this.arr[0].Front()).(int), 0}
}
return []int{-1, -1}
}总结
Easy题目，使用双队列完成
