本文主要是介绍Coursera普林斯顿算法课第二次作业，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Deque: 使用LinkedList和哨兵节点即可。
import java.util.Iterator;
import java.util.NoSuchElementException;import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.Stopwatch;public class Deque<Item> implements Iterable<Item> {private int num; // number of nodesprivate Node first;private Node last;public Deque(){this.num = 0;this.first = null;this.last = null; }private class Node{private Item item;private Node next;private Node prev;}public boolean isEmpty(){return first == null;}public int size(){return num;}// add the item to the frontpublic void addFirst(Item item){if(item == null) throw new IllegalArgumentException();Node oldfirst = first;first = new Node();first.item = item;first.prev = null;if(oldfirst == null){last = first;first.next = null; }else{first.next = oldfirst;oldfirst.prev = first;}num++;}// add the item to the endpublic void addLast(Item item){if(item == null) throw new IllegalArgumentException();Node oldlast = last;last = new Node();last.item = item;last.next = null;if(isEmpty()){first = last;last.prev = null;}else{oldlast.next = last;last.prev = oldlast;}num++; }// remove and return the item from the frontpublic Item removeFirst(){if(isEmpty()) throw new NoSuchElementException();Item it = first.item;first = first.next;num--;if(num == 0) last = null;else first.prev = null;return it;}public Item removeLast(){if(isEmpty()) throw new NoSuchElementException();Item it = last.item;last = last.prev;num--;if(num == 0) first = null;else last.next = null;return it;}// return an iterator over items in order from front to endpublic Iterator<Item> iterator(){ return new DequeIterator(); }private class DequeIterator implements Iterator<Item>{private Node current = first;public boolean hasNext() {return current != null;}public void remove() {throw new UnsupportedOperationException();}public Item next() {if(!hasNext()) throw new NoSuchElementException();Item it = current.item;current = current.next;return it;}}// testpublic static void main(String[] args){Deque<String> dq = new Deque<String>();dq.addFirst("I");dq.addFirst("am");dq.addFirst("Hugh");dq.addLast("I");dq.addLast("Love");dq.addLast("Gals");Stopwatch sw = new Stopwatch();for(String s:dq){ StdOut.println(s);}StdOut.println("remove first: "+dq.removeFirst());StdOut.println("remove last: "+dq.removeLast());for(String s:dq){ StdOut.println(s);}StdOut.println("elapsed CPU time: "+sw.elapsedTime());}}RandomizedQueue: 使用ResizedArray实现，关键在于在每次dequeue操作后需要把末端节点存储的item转存到被随机移除item的节点处，然后将尾端节点设为null，避免loitering。同时也能避免wrap-around的问题，即不会出现数组前几项被dequeue后值为null的情况。
import java.util.Iterator;
import java.util.NoSuchElementException;import edu.princeton.cs.algs4.StdRandom;public class RandomizedQueue<Item> implements Iterable<Item> {private Item[] que;private int num; // number of elements on queuepublic RandomizedQueue(){que = (Item[]) new Object[2];num = 0;}public boolean isEmpty(){return num == 0;}public int size(){return num;}private void resize(int capacity){assert capacity >= num;Item[] temp = (Item[]) new Object[capacity];for(int i=0; i<num; i++){temp[i] = que[i];}que = temp;}public void enqueue(Item item){if(item == null) throw new IllegalArgumentException();if(num == que.length) resize(2 * que.length);que[num++] = item;}// remove and return a random itempublic Item dequeue(){if(isEmpty()) throw new NoSuchElementException();int ch = StdRandom.uniform(num);Item it = que[ch];if(ch != num-1) que[ch] = que[num-1];que[num-1] = null; // to avoid loiteringnum--;if(num > 0 && num == que.length / 4) resize(que.length / 2);return it;}// return a random item but not remove itpublic Item sample(){if(isEmpty()) throw new NoSuchElementException();int ch = StdRandom.uniform(num);return que[ch];}// return an independent iterator over items in random orderpublic Iterator<Item> iterator() {return new RandomizedQueueIterator();}private class RandomizedQueueIterator implements Iterator<Item>{private Item[] rdq; // independent iteratorprivate int current;public RandomizedQueueIterator(){rdq = (Item[]) new Object[num];current = 0;for(int k=0; k<num; k++){rdq[k] = que[k];}StdRandom.shuffle(rdq);}public boolean hasNext() {return current < num;}public void remove() {throw new UnsupportedOperationException();}public Item next() {if(!hasNext()) throw new NoSuchElementException();Item it = rdq[current];current++;return it;}}}
Permutation：注意k是从命令行获取的，以及不要有多余的输出。在参考资料中提到了新建字符串数组和使用readStrings函数获得bonus的方法，不过实际测试时却发现如下错误：
[ERROR] Permutation.java:11: Do not declare arrays in this program. [Performance]
[ERROR] Permutation.java:11:44: Do not call 'StdIn.readAllStrings()' in this program. Use only 'StdIn.readString()'.
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;public class Permutation {public static void main(String[] args){RandomizedQueue<String> r = new RandomizedQueue<String>();//StdOut.println(" size: " + r.size());// input from command lineint k = Integer.parseInt(args[0]);String s;//StdOut.println("Input strings: "); -> no redundant output!// use ctrl+z to end inputwhile(!StdIn.isEmpty()){//r.enqueue(s); -> the last string won't be enqueued!s = StdIn.readString();r.enqueue(s);}int count = 0;for(String ss:r){if(count < k){StdOut.println(ss);count++;}else break;}}}
references:
https://blog.csdn.net/sesiria/article/details/52586467
https://segmentfault.com/a/1190000005345079
https://blog.csdn.net/tumaolin94/article/details/43448485
这篇关于Coursera普林斯顿算法课第二次作业的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
