本系列博客習(xí)題來自《算法(第四版)》法希，算是本人的讀書筆記嵌赠，如果有人在讀這本書的瞧哟，歡迎大家多多交流倚舀。為了方便討論，本人新建了一個(gè)微信群(算法交流)谷羞，想要加入的帝火，請?zhí)砑游业奈⑿盘枺簔hujinhui207407 謝謝。另外湃缎，本人的個(gè)人博客 http://www.kyson.cn 也在不停的更新中犀填，歡迎一起討論

算法(第4版)

知識點(diǎn)

• 鏈表節(jié)點(diǎn)增刪查改
• Fisher–Yates洗牌算法

題目

1.3.35 隨機(jī)隊(duì)列。隨機(jī)隊(duì)列能夠存儲一組元素并支持下表中的 API嗓违。

API for a generic random queue

1.3.35 Random queue. A random queue stores a collection of items and supports the following API: Write a class RandomQueue that implements this API. Hint : Use an array representation (with resizing). To remove an item, swap one at a random position (indexed 0 through N-1) with the one at the last position (index N-1). Then delete and return the last ob- ject, as in ResizingArrayStack. Write a client that deals bridge hands (13 cards each) using RandomQueue<Card>.

分析

跟隨機(jī)背包差不多冕广，還是要熟練使用作者提供的StdRandom庫

API for our library of static methods for random numbers

答案

public class RandomQueue<Item> implements Iterable<Item> {
    private Item[] a;
    private int N;

    public RandomQueue() {
        a = (Item[]) (new Object[1]);
        N = 0;
    }

    public boolean isEmpty() {
        return N == 0;
    }

    public int size() {
        return N;
    }

    public void enqueue(Item x) {
        if (N == a.length) {
            this.resize(a.length * 2);
        }
        a[N++] = x;
    }

    public Item dequeue() {
        if (this.isEmpty()) {
            return null;
        }
        if (N == a.length / 4) {
            resize(a.length / 2);
        }
        int index = StdRandom.uniform(N);
        Item x = a[index];
        a[index] = a[--N];
        a[N] = null;
        return x;
    }

    public void resize(int max) {
        Item[] temp = (Item[]) new Object[max];
        for (int i = 0; i < N; i++) {
            temp[i] = a[i];
        }
        a = temp;
    }

    public Item sample() {
        if (this.isEmpty()) {
            return null;
        }
        int index = StdRandom.uniform(N);
        return a[index];
    }

    public Iterator<Item> iterator() {
        return new RandomQueueIterator();
    }
    
    
    public class RandomQueueIterator implements Iterator<Item>{

        private Item[] temp;
        private int index ;
        
        public RandomQueueIterator(){
            temp = (Item[])new Object[N];
            for (int i = 0; i < N; i++)
                temp[i] = a[i];
            
            StdRandom.shuffle(temp);
            index = 0;
        }
        
        public boolean hasNext() {
            return index < N;
        }

        public Item next() {
            return temp[index++];
        }

        public void remove() {
            
        }
        
    }
    
    public static void main(String[] args) {
        RandomQueue<Integer> queue = new RandomQueue<Integer>();
        for (int i = 1; i <= 52; i++)
            queue.enqueue(i);
        
        for (Object object : queue) {
            System.out.println(object);
    }       
}

代碼索引

RandomQueue.java

題目

1.3.36 隨機(jī)迭代器。為上一題中的 RandomQueue<Card> 編寫一個(gè)迭代器偿洁，隨機(jī)返回隊(duì)列中的所有元素撒汉。

1.3.36 Random iterator. Write an iterator for RandomQueue<Item> from the previous exercise that returns the items in random order.

分析

上面一題已經(jīng)寫了答案，這邊再貼出來

答案

public class RandomQueueIterator implements Iterator<Item>{
    private Item[] temp;
    private int index ;
    
    public RandomQueueIterator(){
        temp = (Item[])new Object[N];
        for (int i = 0; i < N; i++)
            temp[i] = a[i];
        
        StdRandom.shuffle(temp);
        index = 0;
    }
    
    public boolean hasNext() {
        return index < N;
    }

    public Item next() {
        return temp[index++];
    }

    public void remove() {
        
    }
    
}       

代碼索引

RandomQueue.java

廣告

我的首款個(gè)人開發(fā)的APP壁紙寶貝上線了涕滋，歡迎大家下載睬辐。

壁紙寶貝