Coursera-Algorithm Week2

Posted on | In

相比于Week1的作业，week2的比较简单，但是近几年在Permulation文件中设置了一个Bonus也是将难度提升了不少。

链接：课程的Specification

此次作业的目的是实现double-ended queue 和一个randomized queue。

Deque.java

首先看double-ended queue，很常规的操作，他具有queue和stack共同的操作,此处我是用链表实现的。同时每个节点连接了前一个节点和后一个节点。在coding中唯一要注意的是当链表只有一个元素时的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
import java.util.Iterator;

public class Deque<Item> implements Iterable<Item> {
	private class Node{
		Item item;
		Node next;
		Node before;
	}
	private int size;
	private Node first;
	private Node last;
	public Deque() {
		// construct an empty deque
		size = 0;
		first = null;
		last = null;
	}
	public boolean isEmpty() {
		// is the deque empty?
		return size==0;
	}
	public int size() {
		// return the number of items on the deque
		return size;
	}
	public void addFirst(Item item) {
		// add the item to the front
		if(item == null) {
			throw new java.lang.IllegalArgumentException();
		}
		size++;
		Node newfirst = new Node();
		newfirst.item = item;
		newfirst.next = first;	
		newfirst.before = null;
		if(size == 1)	last = newfirst;
		else	first.before = newfirst;
		first = newfirst;
	}
	public void addLast(Item item) {
		// add the item to the end
		if(item == null) {
			throw new java.lang.IllegalArgumentException();
		}
		size++;
		Node newlast = new Node();
		newlast.item = item;
		newlast.next= null;
		newlast.before = last;
		if(size==1) first = newlast;			
		else	last.next = newlast;
		last = newlast;
	}
	public Item removeFirst() {
		// remove and return the item from the front
		if(isEmpty()) {
			throw new java.util.NoSuchElementException();
		}
		size--;
		Item item = first.item;
		first = first.next;
		if(size == 0)	last = null;
		else first.before = null;
		return item;
	}
	public Item removeLast() {
		// remove and return the item from the end
		if(isEmpty()) {
			throw new java.util.NoSuchElementException();
		}
		size--;
		Node toRemove = last;
		last = toRemove.before;
		if(size == 0)	first = null;	
		else	last.next = null;
		return toRemove.item;
	}
	public Iterator<Item> iterator(){
		// return an iterator over items in order from front to end
		return new DequeIterator();
	}
	
	private class DequeIterator implements Iterator<Item>{
		private Node p = first;
		@Override
		public boolean hasNext() {
			return p !=null;
		}
		@Override
		public Item next() {
			if(!hasNext()) {
				throw new java.util.NoSuchElementException();
			}
			Item item = p.item;
			p = p.next;
			return item;
		}
		public void remove() {
			throw new java.lang.UnsupportedOperationException();
		}
	}
	public static void main(String[] args) {
	}
}

RandomizedQueue.java

需要随机选取元素和弹出元素，这里采用Resizing Array比较好。加入元素的时候加在数组末尾即可，tricky的地方是在dequeue操作，如果只是选取并将该处设为null，显然不合理。在这里我将被选中的元素与数组末尾元素互换后，删除数组末尾元素。

另外还有一些细节是在评分时才发现的，比如编译只能出一个错，就是

1
2
3
4
RandomizedQueue.java:46: warning: [unchecked] unchecked cast 
Item[] newArray = (Item[]) new Object[capacity]; 
^ required: Item[] found: Object[] where Item is a type-variable: Item extends Object declared in class RandomizedQueue
1 warning

因此在第10行，也就是构造函数中没有直接写Item[] newArray = (Item[]) new Object[capacity];

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
import java.util.Iterator;
import edu.princeton.cs.algs4.StdRandom;
public class RandomizedQueue<Item> implements Iterable<Item> {
	private int size;
	private Item[] array;
	public RandomizedQueue() {
		// construct an empty randomized queue
		resize(1);
		size = 0;
	}
	public boolean isEmpty() {
		// is the randomized queue empty?
		return size==0;
	}
	public int size() {
		// return the number of items on the randomized queue
		return this.size;
	}
	public void enqueue(Item item) {
		// add the item
		if(item == null) {
			throw new java.lang.IllegalArgumentException();
		}
		if(size == array.length)	resize(size * 2);
		array[size++] = item;
	}
	public Item dequeue() {
		// remove and return a random item
		if(isEmpty())	throw new java.util.NoSuchElementException();
		if(size == array.length /4)	resize(array.length /2);
		int ran = StdRandom.uniform(size);
		Item res = array[ran];
		array[ran] = array[--size];
		array[size] = null;
		return res;
	}
	public Item sample() {
		// return a random item (but do not remove it)
		if(isEmpty())	throw new java.util.NoSuchElementException();
		int ran = StdRandom.uniform(size);
		return array[ran];
	}
	private void resize(int capacity) {
		Item[] newArray = (Item[]) new Object[capacity];
		if(capacity == 1) {
			array = newArray;
			return;
		}
		for(int i=0;i<size;i++) {
			newArray[i] = array[i];
		}
		array = newArray;
	}
	public Iterator<Item> iterator(){
		// return an independent iterator over items in random order
		return new RandomQueueIterator();
	}
	private class RandomQueueIterator implements Iterator<Item>{
		private int p = 0;
		private int[] ran;
		public RandomQueueIterator() {
			ran = new int[size];
			for(int i=0;i<size;i++)	ran[i] = i;
			StdRandom.shuffle(ran);
		}
		@Override
		public boolean hasNext() {
			return p != size;
		}
		@Override
		public Item next() {
			if(!hasNext())	throw new java.util.NoSuchElementException();
			return array[ran[p++]];
		}
		public void remove() {
			throw new java.lang.UnsupportedOperationException();
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
	}
}

Permulation.java

对于规模不大的数据，将数据全部放进RandomizedQueue中，再弹出k个元素即可，但是如果对于大规模的数据，显然这样做浪费了太多的空间。可以利用蓄水池抽样法来解决，这个问题我在另一篇博文Reservoir Sampling Algorithm中提到，不过我将这个方法用于此时，online judge一直报这个错，也不知道如何解决，因此就只贴常规方法了。

1
2
OperationCountLimitExceededException 
Number of calls to methods in StdIn exceeds limit: 10000000

Week2 结束~用以上代码能获得100/100分，如果有大佬能帮我解决以上这个问题，请联系我，感激不尽~~