首页 > 代码库 > 算法导论第四版学习——习题二Deques and Randomized Queues
算法导论第四版学习——习题二Deques and Randomized Queues
题目正文：
http://coursera.cs.princeton.edu/algs4/assignments/queues.html
作业难点：
1、选择使用链表还是数组，将会是第一个问题，选择合适会减少很多工作量。
2、并行从RandomizedQueue中取两个枚举，这两个枚举必须是不一样的，所以有很多偷懒的“伪随机”是行不通的。
3、SubSet仅需K存储而不是N存储，即可实现。（这个我也没想到方法实现）
作业技巧：
1、可遍数组和邻接节点两种数据结构都已经给你了，你只要改改，基本上实现第一个Deque没有任何难度
2、RandomizedQueue涉及到一个基本面试题问题，如果有一个0到100的数组，随机取不重复的元素，如何实现？
从大小为N的数组A中随机[0,N)取下标x的元素A[x]，让A[x]与A[N-1]交换，再随机[0,N-1)取下标x的元素A[y]与A[N-2]交换，以此类推。
3、无论是编译还是网站测试都会报警数组泛型的问题，这个可以百度，JAVA数组不支持泛型。对于作业来说忽略就好了。
代码参考：
（这是我自己亲测100分的答案，不代表写得最好，请在自己实在完成不了的时候再看，不然的话做这个题目的意义一点都没有）
1 import edu.princeton.cs.algs4.StdIn; 2 import edu.princeton.cs.algs4.StdOut; 3 4 import java.util.Iterator; 5 import java.util.NoSuchElementException; 6 7 8 public class Deque<Item> implements Iterable<Item> { 9 private int n; 10 private Node first; 11 private Node last; 12 13 public Deque() // construct an empty deque 14 { 15 n = 0; 16 first = null; 17 last = null; 18 } 19 20 public boolean isEmpty() // is the deque empty? 21 { 22 return first == null; 23 } 24 25 public int size() // return the number of items on the deque 26 { 27 return n; 28 } 29 30 public void addFirst(Item item) // add the item to the front 31 { 32 if (item == null) { 33 throw new NullPointerException(); 34 } 35 36 Node oldfirst = first; 37 first = new Node(); 38 first.item = item; 39 first.next = oldfirst; 40 41 if (oldfirst == null) { 42 last = first; 43 } else { 44 oldfirst.prev = first; 45 } 46 47 n++; 48 } 49 50 public void addLast(Item item) // add the item to the end 51 { 52 if (item == null) { 53 throw new NullPointerException(); 54 } 55 56 Node oldlast = last; 57 last = new Node(); 58 last.item = item; 59 last.prev = oldlast; 60 61 if (oldlast == null) { 62 first = last; 63 } else { 64 oldlast.next = last; 65 } 66 67 n++; 68 } 69 70 public Item removeFirst() // remove and return the item from the front 71 { 72 if (isEmpty()) { 73 throw new NoSuchElementException(); 74 } 75 76 Item item = first.item; 77 first = first.next; 78 79 if (first == null) { 80 last = null; 81 } else { 82 first.prev = null; 83 } 84 85 n--; 86 87 return item; 88 } 89 90 public Item removeLast() // remove and return the item from the end 91 { 92 if (isEmpty()) { 93 throw new NoSuchElementException(); 94 } 95 96 Item item = last.item; 97 last = last.prev; 98 99 if (last == null) {100 first = null;101 } else {102 last.next = null;103 }104 105 n--;106 107 return item;108 }109 110 public Iterator<Item> iterator() // return an iterator over items in order from front to end111 {112 return new DequeIterator();113 }114 115 public static void main(String[] args) // unit testing116 {117 Deque<String> deque = new Deque<String>();118 119 while (!StdIn.isEmpty()) {120 String item = StdIn.readString();121 122 if (item.equals("+")) {123 item = StdIn.readString();124 deque.addFirst(item);125 } else if (item.equals("++")) {126 item = StdIn.readString();127 deque.addLast(item);128 } else if (item.equals("exit")) {129 break;130 } else if (item.equals("show")) {131 for (String s : deque) {132 StdOut.println(s);133 }134 } else if (item.equals("-")) {135 if (!deque.isEmpty()) {136 StdOut.print(deque.removeFirst() + " ");137 }138 } else if (item.equals("--")) {139 if (!deque.isEmpty()) {140 StdOut.print(deque.removeLast() + " ");141 }142 }143 }144 145 StdOut.println("(" + deque.size() + " left on deque)");146 }147 148 private class DequeIterator implements Iterator<Item> {149 private Node current = first;150 151 public boolean hasNext() {152 return current != null;153 }154 155 public void remove() {156 throw new UnsupportedOperationException();157 }158 159 public Item next() {160 if (!hasNext()) {161 throw new NoSuchElementException();162 }163 164 Item item = current.item;165 current = current.next;166 167 return item;168 }169 }170 171 private class Node {172 private Item item;173 private Node next;174 private Node prev;175 }176 }
1 import edu.princeton.cs.algs4.StdIn; 2 import edu.princeton.cs.algs4.StdOut; 3 import edu.princeton.cs.algs4.StdRandom; 4 5 import java.util.Iterator; 6 import java.util.NoSuchElementException; 7 8 9 public class RandomizedQueue<Item> implements Iterable<Item> { 10 private Item[] a; // array of items 11 private int n; // number of elements on stack 12 13 public RandomizedQueue() // construct an empty randomized queue 14 { 15 a = (Item[]) new Object[2]; 16 n = 0; 17 } 18 19 public boolean isEmpty() // is the queue empty? 20 { 21 return n == 0; 22 } 23 24 public int size() // return the number of items on the queue 25 { 26 return n; 27 } 28 29 // resize the underlying array holding the elements 30 private void resize(int capacity) { 31 assert capacity >= n; 32 33 Item[] temp = (Item[]) new Object[capacity]; 34 35 for (int i = 0; i < n; i++) { 36 temp[i] = a[i]; 37 } 38 39 a = temp; 40 } 41 42 public void enqueue(Item item) // add the item 43 { 44 if (item == null) { 45 throw new NullPointerException(); 46 } 47 48 if (n == a.length) { 49 resize(2 * a.length); // double size of array if necessary 50 } 51 52 a[n++] = item; // add item 53 } 54 55 public Item dequeue() // remove and return a random item 56 { 57 if (isEmpty()) { 58 throw new NoSuchElementException(); 59 } 60 61 int targetid = StdRandom.uniform(0, n); 62 Item item = a[targetid]; 63 a[targetid] = a[n - 1]; 64 a[n - 1] = null; // to avoid loitering 65 n--; 66 67 // shrink size of array if necessary 68 if ((n > 0) && (n == (a.length / 4))) { 69 resize(a.length / 2); 70 } 71 72 return item; 73 } 74 75 public Item sample() // return (but do not remove) a random item 76 { 77 if (isEmpty()) { 78 throw new NoSuchElementException(); 79 } 80 81 int targetid = StdRandom.uniform(0, n); 82 83 return a[targetid]; 84 } 85 86 public Iterator<Item> iterator() // return an independent iterator over items in random order 87 { 88 return new RandomizedQueueIterator(); 89 } 90 91 public static void main(String[] args) // unit testing 92 { 93 RandomizedQueue<String> queue = new RandomizedQueue<String>(); 94 95 while (!StdIn.isEmpty()) { 96 String item = StdIn.readString(); 97 98 if (item.equals("-") && !queue.isEmpty()) { 99 StdOut.print(queue.dequeue() + " ");100 }101 else if (item.equals("--") && !queue.isEmpty()) {102 StdOut.print(queue.sample() + " ");103 }104 else if (item.equals("show")) {105 for (String s : queue) {106 StdOut.println(s);107 }108 }109 else if (item.equals("size")) {110 StdOut.println("(" + queue.size() + " left on stack)");111 }112 else if (item.equals("exit")) {113 break;114 } 115 else {116 queue.enqueue(item);117 }118 }119 120 StdOut.println("(" + queue.size() + " left on stack)");121 }122 123 private class RandomizedQueueIterator implements Iterator<Item> {124 private int i;125 private Item[] temp;126 127 public RandomizedQueueIterator() {128 i = n - 1;129 temp = (Item[]) new Object[a.length];130 for (int j = 0; j < n; j++) {131 temp[j] = a[j];132 }133 }134 135 public boolean hasNext() {136 return i >= 0;137 }138 139 public void remove() {140 throw new UnsupportedOperationException();141 }142 143 public Item next() {144 if (!hasNext()) {145 throw new NoSuchElementException();146 }147 148 int targetid = StdRandom.uniform(0, i + 1);149 Item item = temp[targetid];150 temp[targetid] = temp[i];151 temp[i] = item;152 i--;153 return item;154 }155 }156 }
1 import edu.princeton.cs.algs4.StdIn; 2 import edu.princeton.cs.algs4.StdOut; 3 public class Subset { 4 public static void main(String[] args) { 5 RandomizedQueue<String> queue = new RandomizedQueue<String>(); 6 int num = Integer.parseInt(args[0]); 7 8 while (!StdIn.isEmpty()) { 9 String item = StdIn.readString();10 // if (item.equals("exit")) {11 // break;12 // } 13 queue.enqueue(item);14 }15 16 for (String s : queue) {17 if (num == 0) {18 break;19 }20 21 StdOut.println(s);22 num--;23 }24 }25 }
算法导论第四版学习——习题二Deques and Randomized Queues
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。