欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Coursera-Algorithms,Part I-Robert Sedgewick-Programming Assignment 2

程序员文章站 2022-07-09 13:48:09
...

Programming Assignment 2:Deques and Randomized Queues

问题描述

Deque.java

// import java.util.Scanner;  // Uncomment this line when using client testing
import java.util.Iterator;

public class Deque<Item> implements Iterable<Item> {

    private Node first;
    private Node last;
    private int size;

    private class Node
    {
        Node next;
        Node previous;
        Item item;
    }

    public Deque()                           // construct an empty deque
    {   
        first = null;
        last = null;
        size = 0;
    }

    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(); }
        Node oldFirst = first;
        first = new Node();
        first.item = item;
        first.next = oldFirst;
        first.previous = null;
        if (isEmpty()) last = first;
        else oldFirst.previous = first;
        size++;
    }

    public void addLast(Item item)           // add the item to the end
    {
        if (item == null)
        {   throw new java.lang.IllegalArgumentException(); }
        Node oldLast = last;
        last = new Node();
        last.item = item;
        last.previous = oldLast;
        last.next = null;
        if (isEmpty()) first = last;
        else oldLast.next = last;
        size++;
    }

    public Item removeFirst()                // remove and return the item from the front
    {
        if (isEmpty()) throw new java.util.NoSuchElementException();
        Item item = first.item;
        first = first.next;
        if(first == null) last = null;
        else first.previous = null;
        size--;
        return item;
    }

    public Item removeLast()                 // remove and return the item from the end
    {
        if (isEmpty()) throw new java.util.NoSuchElementException();
        Item item = last.item;
        last = last.previous;
        if (last == null) first = null;
        else last.next = null;
        size--;
        return item;
    }

    public Iterator<Item> iterator()         // return an iterator over items in order from front to end
    {   return new IteratorDeque(); }

    private class IteratorDeque implements Iterator<Item>
    {
        private Node current = first;
        public boolean hasNext()
        {   return current != null; }
        public Item next()
        {   
            if (!hasNext())
            {   throw new java.util.NoSuchElementException();   }
            Item item = current.item;
            current = current.next;
            return item;    
        }
        public void remove()
        {   throw new java.lang.UnsupportedOperationException();    }
    }

    public static void main(String[] args)   // unit testing (optional)
    {
        System.out.println("client starts:");


//      Deque<String> deque = new Deque<String>();
//      Scanner scanner = new Scanner(System.in);
//      String str;
//      boolean ifFirst = false;
//      Iterator<String> iterator = deque.iterator();
//      while (true)
//      {      
//          if (ifFirst) System.out.println("Operation on First:");
//          else         System.out.println("Operation on Last:");
//          str = scanner.nextLine();
//          if (str.compareTo("quit") == 0) break;
//          if (str.compareTo("none") == 0) 
//          {   
//              ifFirst = !ifFirst;
//              continue;
//          }
//          if (str.compareTo("-") == 0) 
//          {
//              if (ifFirst) System.out.println(deque.removeFirst());
//              else System.out.println(deque.removeLast());
//          }
//          else if (str.compareTo("count") == 0) System.out.println(deque.size());
//          else if (str.compareTo("all") == 0) 
//          {
//              System.out.println();
//              for (String s : deque)
//              {   System.out.print(s+" ");    }
//              System.out.println();
//          }
//          else if (str.compareTo("null") == 0) 
//          {
//              if (ifFirst) deque.addFirst(null);
//              else deque.addLast(null);
//          }
//          else if (str.compareTo("iter") == 0) 
//          {   iterator = deque.iterator();    }
//          else if (str.compareTo("remove") == 0) 
//          {   iterator.remove();  }
//          else if (str.compareTo("next") == 0) 
//          {   System.out.println(iterator.next());    }
//          else 
//          {
//              if (ifFirst) deque.addFirst(str);
//              else deque.addLast(str);
//          }
//         
//      }
//      scanner.close(); 
    }


}

RandomizedQueue.java
思路:整体上类似栈的实现,取出前将栈顶元素与栈内部随机某个元素交换。

主类的dequeue()方法在实现这个交换时是直接对items[]数组交换的。将这种实现套用到iterator实现时,发现无法通过并行测试和嵌套测试。原因是每个iterator实例在调用next()方法的时候修改了它们共有的items[]数组,导致混乱,出现重复而无法遍历等问题。

因此改进为:每个iterator实例维护一个出栈顺序索引数组idx[],初始化为0,1,2…N-1。每次出栈前对该数组进行前述交换,用idx[]上的交换替代以前那种对items[]具有破坏性的交换。这时每次调用next()方法,只需要返回索引值为idx[--current]的元素即可,即items[idx[--current]]

进一步改进为:iterator实例初始化时就利用StdRandom.shuffle()把它打乱,免去了每次的交换。开销上应该是差不多的,但是代码更清晰。

// import java.util.Scanner;  // Uncomment this line when using client testing
import java.util.Iterator;
import edu.princeton.cs.algs4.StdRandom;

public class RandomizedQueue<Item> implements Iterable<Item> {
    private Item[] items;
    private int N;    

    public RandomizedQueue()                 // construct an empty randomized queue
    {
        items = (Item[]) new Object[1];
        N = 0;
    }

    public boolean isEmpty()                 // is the randomized queue empty?
    {   return N == 0;  }

    public int size()                        // return the number of items on the randomized queue
    {   return N;   }

    public void enqueue(Item item)           // add the item
    {
        if (item == null) throw new java.lang.IllegalArgumentException();
        if (items.length == N)
        {   resize(2 * items.length);   }
        items[N++] = item;
    }

    private void resize(int newSize)
    {
        // System.out.println("Resizing from " + items.length + " to " + newSize); // Debugging info
        Item copy[] = (Item[]) new Object[newSize];
        for (int i = 0; i < N; i++)
        {   copy[i] = items[i]; }
        items = copy;
    }

    public Item dequeue()                    // remove and return a random item
    {
        if (isEmpty()) throw new java.util.NoSuchElementException(); 
        swap(N-1, StdRandom.uniform(N));
        Item item = items[--N];
        items[N] = null;
        if (N == items.length / 4 && N > 0) resize(items.length / 2); 
        return item;
    }

    private void swap(int idx1, int idx2)
    {
        Item temp = items[idx1];
        items[idx1] = items[idx2];
        items[idx2] = temp;     
    }

    public Item sample()                     // return a random item (but do not remove it)
    {
        if (isEmpty()) throw new java.util.NoSuchElementException(); 
        swap(N-1, StdRandom.uniform(N));
        return items[N-1];
    }

    public Iterator<Item> iterator()         // return an independent iterator over items in random order
    {   return new QueueIterator(); }

    private class QueueIterator implements Iterator<Item>
    {
        private int current;    
        private int[] idx;
        public QueueIterator()
        {   
            current = N;
            idx = new int[N];
            for (int i = 0; i < N; i++)
            {   idx[i] = i; }
            StdRandom.shuffle(idx, 0, N);   
        }
//      private void swapIndex(int i, int j)
//      {
//          int temp = idx[i];
//          idx[i] = idx[j];
//          idx[j] = temp;
//      }
        public boolean hasNext()
        {   return current != 0;    }
        public Item next()
        {   
            if (!hasNext()) throw new java.util.NoSuchElementException();
            // swapIndex(current-1, StdRandom.uniform(current));
            return items[idx[--current]];   
        }
        public void remove()
        {   throw new java.lang.UnsupportedOperationException();    }
    }

    public static void main(String[] args)   // unit testing (optional)
    {
        System.out.println("client starts:");


//      // Parallel test and nested test
//      RandomizedQueue<String> queue1 = new RandomizedQueue<String>();
//      for (int i = 1; i < 4; i++)
//      {   queue1.enqueue(i + ""); }
//      RandomizedQueue<String> queue2 = new RandomizedQueue<String>();
//      for (int i = 1; i < 4; i++)
//      {   queue2.enqueue(i + 3 + ""); }
//      RandomizedQueue<String> queue3 = new RandomizedQueue<String>();
//      for (int i = 1; i < 4; i++)
//      {   queue3.enqueue(i + 6 + ""); }
//
//      RandomizedQueue<RandomizedQueue<String>> queueOfQueues = new RandomizedQueue<RandomizedQueue<String>>();
//      queueOfQueues.enqueue(queue1);
//      queueOfQueues.enqueue(queue2);
//      queueOfQueues.enqueue(queue3);
//              
//      Iterator<String> iterator1 = queue1.iterator(); 
//      Iterator<String> iterator2 = queue1.iterator(); 
//      
//      // Parallel test
//      while (iterator1.hasNext())
//      {
//          System.out.print(iterator1.next() + " ");
//          System.out.print(iterator2.next() + " \n");
//      }
//      
//      // Nested test
//      for (RandomizedQueue<String> queue : queueOfQueues)
//      {   
//          System.out.println();
//          for (String s : queue)  
//          {   System.out.print(s + " ");  }
//      }



//      // Interactive test             
//      Scanner scanner = new Scanner(System.in);
//      RandomizedQueue<String> queue = new RandomizedQueue<String>();
//      Iterator<String> iterator = queue.iterator(); 
//      String str;
//      while (true)
//      {
//          str = scanner.nextLine();
//          if (str.compareTo("quit") == 0) break;
//          if (str.compareTo("-") == 0) 
//          {   System.out.println(queue.dequeue());    }
//          else if (str.compareTo("sample") == 0) 
//          {   System.out.println(queue.sample()); }
//          else if (str.compareTo("all") == 0)
//          {   
//              System.out.println();
//              for (String s : queue) System.out.print(s + " ");
//              System.out.println();
//          }
//          else if (str.compareTo("null") == 0)
//          {   queue.enqueue(null);    }
//          else if (str.compareTo("remove") == 0)
//          {   
//              iterator = queue.iterator();
//              iterator.remove();
//          }
//          else if (str.compareTo("iter") == 0)
//          {   
//              iterator = queue.iterator();
//          }
//          else if (str.compareTo("next") == 0)
//          {   
//              System.out.println(iterator.next());
//          }
//          else queue.enqueue(str);
//      }
//      scanner.close();

    }

}

Permutation.java

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
import java.util.Iterator;
public class Permutation {
   public static void main(String[] args)
   {
       int k = Integer.parseInt(args[0]);
       RandomizedQueue<String> queue = new RandomizedQueue<String>();
       while (!StdIn.isEmpty())
       {
           queue.enqueue(StdIn.readString());
       }
       Iterator<String> iterator = queue.iterator();
       for (int i = 0; i < k; i++)
       {    StdOut.println(iterator.next());    }
   }
}