算法练习(41): 随机背包(1.3.34)

知识点

• 随机背包
• Fisher–Yates洗牌算法

题目

1.3.34 随机背包。随机背包能够存储一组元素并支持下表中的 API：

1.3.34 Random bag. A random bag stores a collection of items and supports the fol- lowing API:Write a class RandomBag that implements this API. Note that this API is the same as for Bag, except for the adjective random, which indicates that the iteration should provide the items in random order (all N ! permutations equally likely, for each iterator). Hint : Put the items in an array and randomize their order in the iterator’s constructor.

分析

这道题的难点在于“随机”二字，“随机访问背包中的所有元素”。这类就用到了一个经典的算法：Fisher–Yates洗牌算法（中文读作：费雪耶兹）

答案

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

    private Item[] a = (Item[]) new Object[1];
    private int N = 0;

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

    public int size() {
        return N;
    }

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

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

    public Iterator<Item> iterator() {
        // TODO Auto-generated method stub
        return new RandomBagIterator();
    }

    private class RandomBagIterator implements Iterator<Item> {
        private int[] seq = new int[N];
        private int index = 0;

        public RandomBagIterator() {
            for (int i = 0; i < seq.length; i++)
                seq[i] = i;
            StdRandom.shuffle(seq);
        }

        public boolean hasNext() {
            // TODO Auto-generated method stub
            return index < N;
        }

        public Item next() {
            // TODO Auto-generated method stub
            return a[seq[index++]];
        }

        public void remove() {
            // TODO Auto-generated method stub

        }
    }

    public static void main(String[] args) {
        RandomBag<String> randomBag = new RandomBag<String>();
        randomBag.add("我");
        randomBag.add("的");
        randomBag.add("名字");
        randomBag.add("叫");
        randomBag.add("顶级程序员不穿女装");
        

        for (String string : randomBag) {
            System.out.println(string);
        }
    }
}

代码索引

广告