作业|学习资料|题解

Deques and Randomized Queues

jxtxzzw · 3月10日 · 2020年 · · · 195次已读

Princeton Alhorithms Deques and Randomized Queues

普林斯顿大学算法课第 2 次作业“双端队列与随机队列 ”。

作业要求: https://coursera.cs.princeton.edu/algs4/assignments/queues/specification.php

这一次作业算是比较基本的作业,就是实现双端队列与随机队列,可以说是巩固链表和数组的基本知识的好作业,而且,初步认识到了不可变类型,初步了解到了什么是“多次调用不产生副作用”。

本次代码获得 95 分,正确性满分,空间复杂度满分(还有附加分),时间复杂度稍微扣了点分,但是也懒得去改了。

import java.util.Iterator;
import java.util.NoSuchElementException;

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

    private Node<Item> head;
    private Node<Item> tail;
    private int size;

    // construct an empty deque
    public Deque() {
    }

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

    // return the number of items on the deque
    public int size() {
        return size;
    }

    // add the item to the front
    public void addFirst(Item item) {
        if (item == null) {
            throw new IllegalArgumentException();
        }
        Node<Item> node = new Node<>(item);
        node.setNext(head);
        if (isEmpty()) {
            tail = node;
        }
        head = node;
        size++;
    }

    // add the item to the back
    public void addLast(Item item) {
        if (size == 0) {
            addFirst(item);
        } else {
            if (item == null) {
                throw new IllegalArgumentException();
            }
            Node<Item> node = new Node<>(item);
            tail.setNext(node);
            tail = node;
            if (isEmpty()) {
                head = tail;
            }
            size++;
        }
    }

    // remove and return the item from the front
    public Item removeFirst() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        Item item = head.getItem();
        head = head.getNext();
        size--;
        if (isEmpty()) {
            tail = head;
        }
        return item;
    }

    // remove and return the item from the back
    public Item removeLast() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        if (size == 1) {
            return removeFirst();
        }
        Node<Item> cur = head;
        while (cur.getNext() != tail) {
            cur = cur.getNext();
        }
        Item item = tail.getItem();
        tail = cur;
        tail.setNext(null);
        size--;
        return item;
    }

    // return an iterator over items in order from front to back
    @Override
    public Iterator<Item> iterator() {
        return new Iterator<Item>() {
            private Node<Item> cur = head;

            @Override
            public boolean hasNext() {
                return cur != null;
            }

            @Override
            public Item next() {
                if (cur == null) {
                    throw new NoSuchElementException();
                }
                Item item = cur.getItem();
                cur = cur.getNext();
                return item;
            }
        };
    }

    // unit testing (required)
    public static void main(String[] args) {
        Deque<Integer> dq = new Deque<>();
        dq.addFirst(0);
        System.out.println(dq.removeFirst());
        dq.addFirst(1);
        System.out.println(dq.removeLast());
        dq.addLast(2);
        System.out.println(dq.removeFirst());
        dq.addLast(3);
        System.out.println(dq.removeLast());
        System.out.println(dq.isEmpty());
        dq.addFirst(200);
        dq.addFirst(100);
        dq.addLast(300);
        dq.addLast(400);
        System.out.println(dq.size());
        Iterator<Integer> it = dq.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }
    }

}

class Node<Item> {
    private final Item item;
    private Node<Item> next;

    public Node(Item item) {
        this.item = item;
        next = null;
    }

    public void setNext(Node<Item> next) {
        this.next = next;
    }

    public Node<Item> getNext() {
        return next;
    }

    public Item getItem() {
        return item;
    }
}
import java.util.Iterator;
import java.util.NoSuchElementException;

import edu.princeton.cs.algs4.StdRandom;

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

    private Node<Item> head;
    private int size;

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

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

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

    // add the item
    public void enqueue(Item item) {
        if (item == null) {
            throw new IllegalArgumentException();
        }
        Node<Item> node = new Node<>(item);
        node.setNext(head);
        head = node;
        size++;
    }

    private Item randomize(boolean delete) {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        int r = StdRandom.uniform(0, size);
        if (r == 0) {
            // remove head only
            Item item = head.getItem();
            if (delete) {
                head = head.getNext();
                size--;
            }
            return item;
        }
        // go through, and keep pre and cur
        Node<Item> pre = head;
        Node<Item> cur = head.getNext();
        for (int i = 1; i < r; i++) {
            pre = cur;
            cur = cur.getNext();
        }
        Item item = cur.getItem();
        if (delete) {
            pre.setNext(cur.getNext());
            size--;
        }
        return item;
    }

    // remove and return a random item
    public Item dequeue() {
        return randomize(true);
    }

    // return a random item (but do not remove it)
    public Item sample() {
        return randomize(false);
    }

    // return an independent iterator over items in random order
    @Override
    public Iterator<Item> iterator() {
        return new Iterator<Item>() {

            int left = size;
            boolean[] visited = new boolean[left];

            @Override
            public boolean hasNext() {
                return left > 0;
            }

            @Override
            public Item next() {
                if (left == 0) {
                    throw new NoSuchElementException();
                }
                int r = StdRandom.uniform(size);
                while (visited[r]) {
                    r = StdRandom.uniform(size);
                }
                visited[r] = true;
                left--;
                Node<Item> cur = head;

                for (int i = 0; i < r; i++) {
                    cur = cur.getNext();
                }
                return cur.getItem();
            }
        };
    }

    // unit testing (required)
    public static void main(String[] args) {
        RandomizedQueue<Integer> rq = new RandomizedQueue<>();
        rq.enqueue(1);
        rq.enqueue(2);
        rq.enqueue(3);
        System.out.println(rq.isEmpty());
        System.out.println(rq.size());
        System.out.println(rq.sample());
        System.out.println(rq.dequeue());
        Iterator<Integer> it = rq.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }
    }

}

class Node<Item> {
    private final Item item;
    private Node<Item> next;

    public Node(Item item) {
        this.item = item;
        next = null;
    }

    public void setNext(Node<Item> next) {
        this.next = next;
    }

    public Node<Item> getNext() {
        return next;
    }

    public Item getItem() {
        return item;
    }
}
import edu.princeton.cs.algs4.StdIn;

import java.util.NoSuchElementException;

public class Permutation {
    public static void main(String[] args) {
        int k = Integer.parseInt(args[0]);
        RandomizedQueue<String> rq = new RandomizedQueue<>();
        while (!StdIn.isEmpty()) {
            rq.enqueue(StdIn.readString());
        }
        for (int i = 0; i < k; i++) {
            System.out.println(rq.dequeue());
        }
    }
}

查看其它 Assignment 题解

Percolation

2017-11-7 0

说点什么

avatar

您可以根据需要插入表情、图片、音频、视频或者其他附件,也可以 @ 你需要提及的用户

  
不开心么么什么再见加油发火可以可怜可爱吐吐血吓呵呵哈哈哦哭哼喜欢嗯嘿嘿困圣诞坏笑圣诞调皮坏笑女汉子奸笑好的委屈宝宝害羞小清新心塞快哭了恭喜发财惆怅我最美抓狂抠鼻放空无奈晕汗泪奔温柔女生狗年生气笑笑泪衰调皮调皮女生鄙视酷静静额鼓掌
上传图片
 
 
 
上传视频和音频
 
 
 
上传其他类型文件
 
 
 
  订阅评论动态  
提醒