lintcode练习

在一个宠物避难所里，仅有狗和猫两种动物可供领养，且领养时严格执行“先进先出”的规则。如果有人想要从避难所领养动物，他只有两种选择：要么选择领养所有动物中最资深的一只（根据到达避难所的时间，越早到的越资深），要么选择领养猫或狗（同样，也只能领养最资深的一只）。也就是说，领养者不能随意选择某一指定动物。请建立一个数据结构，使得它可以运行以上规则，并可实现 enqueue, dequeueAny, dequeueDog， 和 dequeueCat 操作。

建议使用 LinkedList 作为数据结构实现。

int DOG = 1

int CAT = 2

enqueue("james", DOG);

enqueue("tom", DOG);

enqueue("mimi", CAT);

dequeueAny(); // should return "james"

dequeueCat(); // should return "mimi"

dequeueDog(); // should return "tom"

Can you do it with single Queue?

定义一个队列，元素形式为（name，type），当弹出猫狗时，从前遍历，遇到第一个猫狗弹出。

class AnimalShelter:

def __init__(self):

self.animal = []

"""

@param: name: a string

@param: type: an integer, 1 if Animal is dog or 0

@return: nothing

"""

def enqueue(self, name, type):

self.animal.append((name, type))

"""

@return: A string

"""

def dequeueAny(self):

res = self.animal.pop(0)

return res[0]

"""

@return: A string

"""

def dequeueDog(self):

for i in range(len(self.animal)):

if self.animal[i][1] == 1:

return self.animal.pop(i)[0]

"""

@return: A string

"""

def dequeueCat(self):

for i in range(len(self.animal)):

if self.animal[i][1] == 0:

return self.animal.pop(i)[0]

使用链表来解决

class LinkedAnimal:

def __init__(self, name, type, next=None):

self.name = name

self.type = type

self.next = next

class AnimalShelter:

def __init__(self):

self.dummy = LinkedAnimal("start", 0)

self.tail = self.dummy

"""

@param: name: a string

@param: type: an integer, 1 if Animal is dog or 0

@return: nothing

"""

def enqueue(self, name, type):

newAnimal = LinkedAnimal(name, type)

head = self.dummy

while head.next:

head = head.next

head.next = newAnimal

"""

@return: A string

"""

def dequeueAny(self):

if self.dummy.next == None:

return None

name = self.dummy.next.name

self.dummy.next = self.dummy.next.next

return name

"""

@return: A string

"""

def dequeueDog(self):

head = self.dummy

while head:

if head.next == None:

return None

if head.next.type != 1:

head = head.next

else:

name = head.next.name

head.next = head.next.next

return name

"""

@return: A string

"""

def dequeueCat(self):

head = self.dummy

while head:

if head.next == None:

return None

if head.next.type == 1:

head = head.next

else:

name = head.next.name

head.next = head.next.next

return name

相关知识

php表达式ax 2 bx c=0,python求解ax² + bx + c = 0
练习
指法练习
表演小练习丨情感表现练习
灵敏性练习方法
宠物练习
2.4节练习
怎样练习敏捷
怎样练习狗狗定点大小便，狗狗大小便练习教程
慈心冥想练习【第6天】对动物慈爱的练习

网址: lintcode练习 https://www.mcbbbk.com/newsview757198.html