230 Animal shelter

Leave a comment

September 1, 2016 by oneOokay

进化史:

大概三十分钟写了个跑过的渣算法:

  • 1个Animal class{name, type};
  • 1个ArrayList<Animal>存所有动物;
  • 2个queue,分别存猫和狗的index。
  • enqueue的时候,放入ArrayList中,记下当前index,然后猫或者狗的queue enqueue这个index
  • dequeueAny:猫狗的queue peek,找出较小的那个index,从arraylist按index上找出该animal,并且从queue里面pop掉
  • dequeueCat:猫的queue,poll出index,从arrayList中按index找出该animal。
  • dequeueDog:同Cat。

看了九章之后的优化,依旧是使用两个queue,这个应该是理想答案吧。

九章上面的明明也是用了两个queue啊,也不晓得怎么用一个queue。然后我不喜欢他那个写法,我比较喜欢建一个class,觉得更加清楚一些。。。

  • 1Animal class{name, type, index};
  • 1个ArrayList<Animal>存所有动物;
  • 2个queue<Animal>,分别存猫和狗的index
  • 1个integer,存anmial总数,为index。
  • enqueue的时候,index++,分类放入queue中。
  • dequeueAny:猫狗的queue peek,找出较小的那个index,call dequeueCat or dequeueDog
  • dequeueCat:直接dequeue猫的queue。
  • dequeueDog:同Cat。

key points:

  • Queue initialization: Queue<T> queue= new LinkedList<T>();
  • queue.pop()  doesn’t return value.
  • queue.poll() returns a value.
  • queue.remove()
  • dequeueAny 对于dequeueCat和dequeueDog的引用

代码没什么好看的。。。

public class AnimalShelter {

private class Animal{
String name;
Integer type;
Integer index;
public Animal(String n, Integer t, int i){
name = n;
type = t;
index = i;
}
}

private Queue<Animal> dogQ;
private Queue<Animal> catQ;
private int index;
public AnimalShelter() {
// do initialize if necessary
dogQ = new LinkedList<Animal>();
catQ = new LinkedList<Animal>();
index = 0;
}

/**
* @param name a string
* @param type an integer, 1 if Animal is dog or 0
* @return void
*/
void enqueue(String name, int type) {
// Write your code here
index ++;
if (type == 0){
catQ.add(new Animal(name, type, index));
}else {
dogQ.add(new Animal(name, type, index));
}
}

public String dequeueAny() {
// Write your code here
if(catQ.size() != 0 && dogQ.size() != 0){
int catIndex = catQ.peek().index;
int dogIndex = dogQ.peek().index;
if (catIndex < dogIndex){
return dequeueCat();
}else {
return dequeueDog();
}
}else if(catQ.size() == 0)
{
return dequeueDog();
}else {
return dequeueCat();
}
}

public String dequeueDog() {
// Write your code here

return dogQ.poll().name;

}

public String dequeueCat() {
// Write your code here
return catQ.poll().name;
}
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: