【第三轮】7.7-7.13 CareerCup 3.7

donnice 发表于 2014-7-9 01:17
【解题思路】
用两个LinkedList
【时间复杂度】

Please do not use characters to represent dog and cat. It's better to create 2 classes. Thanks.

jason51122 发表于 2014-7-9 12:55
Please do not use characters to represent dog and cat. It's better to create 2 classes. Thanks.

昨天没时间了…没必要写两个 class啊，两个list就够了，分别给猫狗起名，dequeue时输入名字，contains（String name)而已，小技术

【解题思路】
Use two linked list, one for cats, one for dogs
add timestamps to cats and dogs

【时间复杂度】
O(1)


【空间复杂度】
O(n)


【gist link】
https://gist.github.com/happyWinner/8a155f4feea9cf27df4d

【解题思路】
Use two linked lists for cats and dogs respectively;  use an extra attribute for animal " order " to record the time they enter the shelter.
【时间复杂度】O(1)
【空间复杂度】O(n)
【gist link】https://gist.github.com/jyhjuzi/de9393fb070b4061d34e

【解题思路】
Maintain two separate queues for dogs and cats.

【时间复杂度】
O(1)

【空间复杂度】
O(n)

【gist link】
https://gist.github.com/JoyceeLee/d530c6ba41dd9c16abcc

【解题思路】
Create two Queue Cats and Dogs, the class Cat and Dog inherits from Animal, use id to indicate the arrival time
【时间复杂度】
O(1)
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/iwilbert/896f3f2b5b67a0ee3340

【解题思路】
开始没看见“use the built-in LinkedList data structure” 就自己写了个queue， 直接用java.util.LinkedList<E> 也是大同小异
这题主要考design，用继承和多态区分dog和cat就可以了，至于queue，可以用generic也可以用多太写
【时间复杂度】
O(1)
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/Noahsark/9974157a98091e89773e