Algorithms on Coursera 学习记录 week2.1

主题为Stacks and Queues，测试作业为Deques and Randomized Queues

没有做笔记的习惯，但是最好还是写点东西..

因为是英语网课所以没写中文注释，我平时写东西喜欢写一大堆注释..（包括很多废话）


import java.util.Iterator;

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

  // construct an empty deque
  public Deque() {



  }

  private Node first = null;
  private Node last = null;

  private class Node{
    Item item;
    Node next;
  }

  //private int counts;

  // is the deque empty?
  public boolean isEmpty(){
    return first == null;
  }

  // return the number of items on the deque
  public int size(){
    Node pointer = first;

    int counts = 0;
    while(pointer != null){

      pointer = pointer.next;
      counts++;

    }
    return counts;
  }

  // add the item to the front
  public void addFirst(Item item){

    if (item == null){
      throw new IllegalArgumentException();
    }

    Node oldFirst = first;
    first = new Node();
    first.item = item;
    first.next = oldFirst;
    if (oldFirst==null){
      last = first;
    }

  }

  // add the item to the back
  public void addLast(Item item){

    if (item == null){
      throw new IllegalArgumentException();
    }

    Node oldLast = last;
    last = new Node();
    last.item = item;
    if(isEmpty()) {
      first = last;
    }
    else {
      oldLast.next = last;
    }


  }

  // remove and return the item from the front
  public Item removeFirst(){

    if (isEmpty()){
      throw new java.util.NoSuchElementException();
    }

    Item item = first.item;
    first = first.next;
    if(isEmpty()){
      last = first;
    }
    return item;
  }

  // remove and return the item from the back
  public Item removeLast(){

    if (isEmpty()){
      throw new java.util.NoSuchElementException();
    }

    Item item = last.item;
    Node pointer = first;


    if(pointer.next!=null) {
      while (pointer.next.next != null)
      {
        pointer = pointer.next;
      }

      last = pointer;
      last.item = pointer.item;
      last.next=null;
    }
    else{
      last = null;
      first = null;
    }
    return item;
  }
  // return an iterator over items in order from front to back
  public Iterator<Item> iterator(){
    return new DequeIterator() {
    };
  }
  private class DequeIterator implements Iterator<Item>{

    private Node pointer = first;

    public void remove(){throw new UnsupportedOperationException();}//not supported

    public boolean hasNext(){
      return (pointer != null);
    }
    public Item next(){
      if (!hasNext()){
        throw new java.util.NoSuchElementException();
      }
      Item item = pointer.item;
      pointer = pointer.next;

      return item;
    }



  }
  // unit testing (required)
  public static void main(String[] args){

    Deque<Integer> test = new Deque<>();
    test.addFirst(3);
    test.addFirst(2);
    test.addFirst(1);
    test.addLast(4);
    test.addLast(5);
    test.addLast(6);

    System.out.println(test.removeFirst());
    System.out.println(test.size());
    System.out.println(test.removeLast());
    System.out.println(test.size());
    System.out.println(test.removeFirst());
    System.out.println(test.size());
    System.out.println(test.removeLast());
    System.out.println(test.size());
    System.out.println(test.removeFirst());
    System.out.println(test.size());
    System.out.println(test.removeFirst());
    System.out.println(test.size());
  }


}

-----------------------------------------------------------------------------------------

import edu.princeton.cs.algs4.StdRandom;

import java.util.Iterator;

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

  // construct an empty randomized queue
  public RandomizedQueue(){


  }
  private Node first = null;

  private class Node{
    Item item;
    Node next;
  }
  // is the randomized queue empty?
  public boolean isEmpty(){
    return first == null;
  }

  // return the number of items on the randomized queue
  public int size(){
    Node pointer = first;

    int counts = 0;
    while(pointer != null){

      pointer = pointer.next;
      counts++;

    }
    return counts;
  }

  // add the item
  public void enqueue(Item item){
    if(item ==null){
      throw new IllegalArgumentException();
    }
    Node oldFirst = first;
    first = new Node();
    first.item = item;
    first.next = oldFirst;
  }

  // remove and return a random item
  public Item dequeue(){
    if(isEmpty()){throw new java.util.NoSuchElementException();}//

    Node pointer = first;
    int times = StdRandom.uniform(size());
    for (int i=0;i<times;i++){
      pointer = pointer.next ;
    }

    Item item = pointer.item;//get item

    //remove item

    if(pointer==first){
      first=first.next;
    }

    else {
      Node prevPointer = first;
      for(int i=0;i<times - 1;i++){
        prevPointer = prevPointer.next ;
      }
      prevPointer.next=pointer.next;
    }


    return item;
  }

  // return a random item (but do not remove it)
  public Item sample(){
    if(isEmpty()){throw new java.util.NoSuchElementException();}//

    Node pointer = first;
    for (int i=0;i<StdRandom.uniform(size());i++){
      pointer = pointer.next ;
    }
    return pointer.item;
  }

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

    //private Node pointer = first;

    public void remove(){throw new UnsupportedOperationException();}//not supported

    public boolean hasNext(){
      return (size() != 0);
    }
    public Item next(){
      if (!hasNext()){
        throw new java.util.NoSuchElementException();
      }

      return dequeue();
    }
  }

  // unit testing (required)
  public static void main(String[] args){

    RandomizedQueue<String> test = new RandomizedQueue<>();
    test.enqueue("AA");
    test.enqueue("BB");
    test.enqueue("CC");
    test.enqueue("DD");
    test.enqueue("EE");
    System.out.println( test.dequeue());
    System.out.println( test.dequeue());
    System.out.println( test.dequeue());
    System.out.println( test.dequeue());
    System.out.println( test.sample());
    System.out.println( test.dequeue());
    System.out.println( test.size());

  }



}

怎么说呢，其实作业不符合要求，但是应付过关了

第一个双向队列Deque，我为了减少memory使用了单向链表，导致两端中有一端的出队操作需要从另一端开始遍历..严重增加了timing。

第二个题目随机队列Randomized Queues，只写了链表实现而没写数组实现，而链表实现的迭代器所需时间难以（或者说无法）用常数时间实现，不符合题目要求。

等下用数组实现写一下看看能不能更多的pass

我自己原来的迭代器会进行“出队”操作，从网上借鉴了一个用stdRandom.shuffle将数组随机重组的函数，然后从头到尾输出的迭代器。

剩下的两分是双向链表的timing,我就先不去修改了..开始学习下一节！

import edu.princeton.cs.algs4.StdRandom;
import java.util.Iterator;

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



  private int pointer = 0;
  private Item[] rQueue;



  // construct an empty randomized queue
  public RandomizedQueue(){
    rQueue =(Item[]) new Object[20];
  }

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

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

  // add the item
  public void enqueue(Item item){

    if(item ==null){
      throw new IllegalArgumentException();
    }

    //extend if full
    if(rQueue.length==size()){
      Item[] oldRq = rQueue;
      rQueue = (Item[]) new Object[oldRq.length*2];
      System.arraycopy(oldRq, 0, rQueue, 0, size());
    }

    rQueue[pointer++]=item;

  }

  // remove and return a random item
  public Item dequeue(){
    if(isEmpty()){throw new java.util.NoSuchElementException();}

    //shrink if less than 1/4 full
    if(size()<= rQueue.length/4){
      Item[] oldRq = rQueue;
      rQueue = (Item[]) new Object[oldRq.length/2];
      System.arraycopy(oldRq, 0, rQueue, 0, size());
    }

    int dePointer = StdRandom.uniform(size());
    Item item= rQueue[dePointer];
    rQueue[dePointer]=rQueue[--pointer];
    rQueue[pointer]=null;

    return item;
  }

  // return a random item (but do not remove it)
  public Item sample(){
    if(isEmpty()){throw new java.util.NoSuchElementException();}
    return rQueue[StdRandom.uniform(size())];
  }

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

    //////////////////////////抄的（从别人那里学的）代码
    private int i=0;
    private Item[] randomFormedArray =(Item[]) new Object[pointer];

    public RandomizedQueueIterator(){
      System.arraycopy(rQueue,0,randomFormedArray,0,pointer);
      StdRandom.shuffle(randomFormedArray);
    }

    public void remove(){throw new UnsupportedOperationException();}//not supported

    public boolean hasNext(){
      return (i<pointer);
    }
    public Item next(){
      if (!hasNext()){
        throw new java.util.NoSuchElementException();
      }
      Item item = randomFormedArray[i];
      i++;
      return item;
    }
  }

  // unit testing (required)
  public static void main(String[] args){

    RandomizedQueue<String> test = new RandomizedQueue<>();
    test.enqueue("AA");
    test.enqueue("BB");
    test.enqueue("CC");
    test.enqueue("DD");
    test.enqueue("EE");
    System.out.println( test.dequeue());
    System.out.println( test.size());
    System.out.println( test.dequeue());
    System.out.println( test.size());
    System.out.println( test.dequeue());
    System.out.println( test.dequeue());
    System.out.println( test.sample());
    System.out.println( test.dequeue());
    System.out.println( test.size());

  }

}

Algorithms on Coursera 学习记录 week2.1

无缘消受GPW

Algorithms on Coursera 学习记录 week2.2 Elementary Sorts

Mofeng

Comments | NOTHING

取消回复

Mofeng's Blog