美文网首页北美程序员面试干货
LintCode 230 [Animal Shelter]

LintCode 230 [Animal Shelter]

作者: Jason_Yuan | 来源:发表于2016-07-10 06:53 被阅读40次

原题

在一个宠物避难所里,仅有狗和猫两种动物可供领养,且领养时严格执行“先进先出”的规则。如果有人想要从避难所领养动物,他只有两种选择:要么选择领养所有动物中最资深的一只(根据到达避难所的时间,越早到的越资深),要么选择领养猫或狗(同样,也只能领养最资深的一只)。也就是说,领养者不能随意选择某一指定动物。请建立一个数据结构,使得它可以运行以上规则,并可实 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"

解题思路

  • 使用两个数组分别记录加入的猫和狗,用0和1表示
  • 存储时,在python中可以使用set来同时记录名字和先后顺序(使用数字记录age),初始tot = 0,之后每次tot += 1,在dequeueAny的时候只需要比较Dog[0]和Cat[0]的tot,值越小表明age越大,pop谁

完整代码

class AnimalShelter(object):

    def __init__(self):
        # do some intialize if necessary
        self.cats = []
        self.dogs = []
        self.tot = 0

    """
    @param {string} name
    @param {int} type, 1 if Animal is dog or 0
    @return nothing
    """
    def enqueue(self, name, type):
        # Write yout code here
        self.tot += 1
        if type == 1:
            self.dogs.append((name, self.tot))
        else:
            self.cats.append((name, self.tot))

    # return a string
    def dequeueAny(self):
        # Write your code here
        if len(self.dogs) == 0:
            return self.dequeueCat()
        elif len(self.cats) == 0:
            return self.dequeueDog()
        else:
            if self.dogs[0][1] < self.cats[0][1]:
                return self.dequeueDog()
            else:
                return self.dequeueCat()

    # return a string
    def dequeueDog(self):
        # Write your code here
        name = self.dogs[0][0]
        del self.dogs[0]
        return name

    # return a string
    def dequeueCat(self):
        # Write your code here
        name = self.cats[0][0]
        del self.cats[0]
        return name

相关文章

  • LintCode 230 [Animal Shelter]

    原题 在一个宠物避难所里,仅有狗和猫两种动物可供领养,且领养时严格执行“先进先出”的规则。如果有人想要从避难所领养...

  • Animal Shelter

    设计动物救助站,可以收容狗和猫。 来收养动物的,只能选最先进来的狗,或者最先进来的猫,或者不区分动物,但也必须是最...

  • 猫咪和难民

    因为喜欢小动物,来美国后一直在animal shelter做义工,主要负责猫咪的socialize。简单说来就是让...

  • SHELTER

    每分钟脱贫20人?我他么穷了20年也没见有好转,大集上依旧是为了一毛几分钱起争执的平头百姓。 习近平走访中国最贫困...

  • java设计者模式之单例模式

    public class Animal { private static Animal animal = new...

  • 6,向上转型和向下转型

    向上转型:Animal animal = new Cat(); //向上转型animal.eat(); 将子类对象...

  • 单例类

    Animal.h Animal.m

  • This place is A shelter

    藤条长椅上 我们头顶着是夏季的星空 蝉鸣不断 谈笑不止 我还记得那时… 天空布满繁星你的眼睛是雪亮的 如今… 你与...

  • shelter 凛

    沉睡了大约四年后,凛逐渐恢复了意识,发现自己身处在一个透明的方行空间里,手边的一切使她感到陌生,却又有几分...

  • shelter 因

    据计算,一颗占地球十分之一质量的卫星将于数年后进入太阳引力范围之内,并最终被地球捕捉最后相撞。此消息一经公...

网友评论

    本文标题:LintCode 230 [Animal Shelter]

    本文链接:https://www.haomeiwen.com/subject/wtgrjttx.html