普林斯顿大学算法Week2:Deques and Randomized Queues(95分)--总结及代码
总结
一.Deque
目标:
A double-ended queue or deque is a generalization of a stack and a queue that supports adding and removing items from either the front or the back of the data structure. Create a generic data type Deque that implements the following API
要求:
Your deque implementation must support each deque operation (including construction) in constant worst-case time. A deque containing n items must use at most 48n + 192 bytes of memory and use space proportional to the number of items currently in the deque. Additionally, your iterator implementation must support each operation (including construction) in constant worst-case time.
分析:
deque可以分别在头尾做添加删除操作,并且在最坏的情况下消耗常数时间,所以数组不行,因为使用数组在头部添加或删除元素时必须修改后面所有元素的索引,这个操作耗费时间随数组长度的增加而增加.所以采用链表结构,在头尾维护两个指针即可实现constant time
二.Randomized queue
目标:
A randomized queue is similar to a stack or queue, except that the item removed is chosen uniformly at random from items in the data structure. Create a generic data type RandomizedQueue that implements the following API
要求:
Your randomized queue implementation must support each randomized queue operation (besides creating an iterator) in constant amortized time. That is, any sequence of m randomized queue operations (starting from an empty queue) must take at most cm steps in the worst case, for some constant c. A randomized queue containing n items must use at most 48n + 192 bytes of memory. Additionally, your iterator implementation must support operations next() and hasNext() in constant worst-case time; and construction in linear time; you may (and will need to) use a linear amount of extra memory per iterator.
分析:
为实现randomized queue的(除iterator操作)操作平摊时间最差是常数需要采用数组实现,虽然数组长度的扩展或者缩短所需时间正比于数组当前存储元素的个数,但是实现其余API(除iterator操作)的操作只需常数时间,把耗费的时间平摊后就是常数时间了.
为什么不能采用链表结构呢?链表结构实现literator非常方便,只需创建一个指针,不断移动指针的位置就可以实现iterator的各个功能,耗费常数时间,但是题目并不要求iterator耗费常数时间,注意到public Item dequeue()这个API,要求remove and return a random item,难点在于随机返回一个元素,首先创建一个随机数作为索引,对于链表来说,需要移动相应次数的指针找到那个元素,这个操作耗费时间正比于随机数的大小,不是常数时间.
三. Permutation
目标:Write a client program Permutation.java that takes an integer k as a command-line argument; reads in a sequence of strings from standard input using StdIn.readString(); and prints exactly k of them, uniformly at random. Print each item from the sequence at most once.
要求:
The running time of Permutation must be linear in the size of the input. You may use only a constant amount of memory plus either one Deque or RandomizedQueue object of maximum size at most n. (For an extra challenge, use only one Deque or RandomizedQueue object of maximum size at most k)
分析:
没能完成extra challenge,所以扣了5分
这个直接看代码即可
代码
一.Deque
import java.util.Iterator;
public class Deque<Item> implements Iterable<Item>{
private Node first,last; //64位系统,每个引用8bytes,此处共16bytes
private int n; //4bytes
private class Node{ //64位系统,对象头16bytes , 内部类开销8bytes
private Item item; //64位系统,8bytes
private Node next; //64位系统,8bytes
private Node pre; //64位系统,8bytes 所以,1个Node占用48bytes,n个Node就是48n bytes
}
// construct an empty deque
public Deque() {
first = null;
last = null;
n = 0;
}
//is Deque empty?
public boolean isEmpty() {
return n == 0;
}
// return the number of items on the deque
public int size() {
return n;
}
// add the item to the front
public void addFirst(Item item) {
if(item==null) throw new java.lang.IllegalArgumentException("there is nothing");
Node oldfirst = first;
first = new Node();
first.item = item;
first.next = oldfirst;
//if(isEmpty()) just use n rather to call isEmpty()
if(n==0) last = first;
else oldfirst.pre = first;
n++;
}
// add the item to the end
public void addLast(Item item) {
if(item==null) throw new java.lang.IllegalArgumentException("there is nothing");
Node oldlast = last;
last = new Node();
last.item = item;
last.pre = oldlast;
if(n==0) first = last;
else oldlast.next = last;
n++;
}
// remove and return the item from the front
public Item removeFirst() {
//if 'if' runs,the program would stop
if(n==0) throw new java.util.NoSuchElementException("Deque is empty!!");
Item temp = first.item;
first = first.next;
n--;
//check if the Deque is empty after remove
if(n==0) last = null;//first is null now
else first.pre = null;
return temp;
}
// remove and return the item from the end
public Item removeLast() {
if(n==0) throw new java.util.NoSuchElementException("Deque is empty!!");
Item temp = last.item;
last = last.pre;
n--;
if(n==0)first = null;
else last.next=null;
return temp;
}
// return an iterator over items in order from front to end
public Iterator<Item> iterator(){
return new ListIterator();
}
private class ListIterator implements Iterator<Item>{ //对象头:16bytes
private Node current = first; //内部类额外开销8bytes,引用8bytes
public boolean hasNext() {
return current != null;
}
public void remove() {
throw new java.lang.UnsupportedOperationException("you mustn't do this!");
}
public Item next() {
if(current == null) throw new java.util.NoSuchElementException("no such element");
Item temp = current.item;
current = current.next;
return temp;
}
}
//main
public static void main(String[] args) {
Deque<String> deque = new Deque<String>();
System.out.println(deque.size());
deque.addFirst("haha");
deque.addFirst("hehe");
deque.addFirst("heihei");
deque.addFirst("hiahia");
deque.addFirst("houhou");
System.out.println(deque.size());
deque.removeFirst();
System.out.println(deque.size());
deque.removeLast();
System.out.println(deque.size());
Iterator<String> i = deque.iterator();
while(i.hasNext()) System.out.println(i.next());
}
}
二.Randomized queue
import java.util.Iterator;
import edu.princeton.cs.algs4.StdRandom;
//Additionally, your iterator implementation must support operations next() and hasNext()
//in constant worst-case time;
public class RandomizedQueue<Item> implements Iterable<Item> {
private Item[] randomq;
private int n;
// construct an empty randomized queue
public RandomizedQueue() {
randomq = (Item[]) new Object[1];
n = 0;
}
// is the randomized queue empty?
public boolean isEmpty() {
return n == 0;
}
// return the number of items on the randomized queue
public int size() {
return n;
}
//resize the array
private void resize(int size) {
//temp is a "yinyong"
Item[] temp = (Item[]) new Object[size];
for(int i=0;i<n;i++) temp[i] = randomq[i];
randomq = temp;
}
// add the item
public void enqueue(Item item) {
if (item==null) throw new java.lang.IllegalArgumentException("there is nothing");
if(n==randomq.length) resize(2*n);
randomq[n++] = item;
}
// remove and return a random item
//exchange the chosen element with the last element
//then,delete the last one
//so that realize deleting the random element in the end of queue
public Item dequeue() {
//faster than call isEmpty()
if(n==0) throw new java.util.NoSuchElementException("array is empty");
int i = StdRandom.uniform(0,n);
Item temp = randomq[i];
// pay attention to the change of n
if(i != --n) randomq[i] = randomq[n];
randomq[n] = null;
//here without n>0.wrong,try:add one,delete one
if(n>0 && n==randomq.length/4) resize(randomq.length/2);
return temp;
}
// return a random item (but do not remove it)
public Item sample() {
if(n==0) throw new java.util.NoSuchElementException("array is empty");
return randomq[StdRandom.uniform(0,n)];
}
// return an independent iterator over items in random order
public Iterator<Item> iterator(){
return new RandomIterator();
}
// inner class
private class RandomIterator implements Iterator<Item>{
// m is as index,just like the pointer in Deque
private int m;
private Item[] iterq;
private RandomIterator() {
iterq = (Item[])new Object[n];
for(int i=0;i<n;i++) iterq[i] = randomq[i];
//random order
StdRandom.shuffle(iterq);
}
public boolean hasNext() {
return m < n;
}
public void remove() {
throw new java.lang.UnsupportedOperationException("you mustn't do this!");
}
public Item next() {
if(m>=n) throw new java.util.NoSuchElementException("no next element!");
Item temp = iterq[m++];
return temp;
}
}
// unit testing (optional)
public static void main(String[] args) {
RandomizedQueue<String> rq = new RandomizedQueue<String>();
System.out.println(rq.isEmpty());
System.out.println(rq.size());
rq.enqueue("haha");
rq.enqueue("heihei");
rq.enqueue("hiahia");
rq.enqueue("hehe");
rq.enqueue("houhou");
System.out.println(rq.size());
rq.dequeue();
rq.dequeue();
Iterator<String> iter = rq.iterator();
while(iter.hasNext()) System.out.println(iter.next());
System.out.println();
Iterator<String> iter2 = rq.iterator();
while(iter2.hasNext()) System.out.println(iter2.next());
}
}
三. Permutation
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
public class Permutation {
public static void main(String[] args) {
//jvm在调用主函数时,传入的是new args[0]
int k = Integer.parseInt(args[0]);
RandomizedQueue rq = new RandomizedQueue();
while(!StdIn.isEmpty()) {
rq.enqueue(StdIn.readString());
}
while(rq.size()-k>0) rq.dequeue();
for(int i=0;i<k;i++) {
StdOut.println(rq.dequeue());
}
}
}