算法<初级> - 第二章 数据结构

题目一 用数组实现大小固定的队列和栈（一面题）

数组实现大小固定栈

/***
*   size是对头索引（initSize是固定大小） 也是当前栈大小
*   size=下个进队index
*   size-1=下个出队index
*   size==initSize时队满 判满
*   size==0时队空 判空
***/

public static class ArrayStack {
    private Integer[] arr;
    private Integer size;   /

    public ArrayStack(int initSize) {
        if (initSize < 0) {
            throw new IllegalArgumentException("The init size is less than 0");
        }
        arr = new Integer[initSize];
        size = 0;
    }

    public Integer peek() {     //返回栈头元素
        if (size == 0) {
            return null;
        }
        return arr[size - 1];
    }

    public void push(int obj) {
        if (size == arr.length) {
            throw new ArrayIndexOutOfBoundsException("The queue is full");
        }
        arr[size++] = obj;
    }

    public Integer pop() {
        if (size == 0) {
            throw new ArrayIndexOutOfBoundsException("The queue is empty");
        }
        return arr[--size];
    }
}

数组实现大小固定队列

/***
*   size当前队列大小；用size关联first/last更加方便
*   last队尾
*   first队头
*   循环队列：
*   first = first == arr.length - 1 ? 0 : first + 1;
*   last = last == arr.length - 1 ? 0 : last + 1; 
***/
public static class ArrayQueue {
    private Integer[] arr;
    private Integer size;
    private Integer first;
    private Integer last;

    public ArrayQueue(int initSize) {
        if (initSize < 0) {
            throw new IllegalArgumentException("The init size is less than 0");
        }
        arr = new Integer[initSize];
        size = 0;
        first = 0;
        last = 0;
    }

    public Integer peek() { //查看队头元素
        if (size == 0) {
            return null;
        }
        return arr[first];
    }

    public void push(int obj) {    //进队
        if (size == arr.length) {
            throw new ArrayIndexOutOfBoundsException("The queue is full");
        }
        size++;
        arr[last] = obj;
        last = last == arr.length - 1 ? 0 : last + 1; //循环队列
    }

    public Integer poll() {      //出队弹出
        if (size == 0) {
            throw new ArrayIndexOutOfBoundsException("The queue is empty");
        }
        size--;
        int tmp = first;
        first = first == arr.length - 1 ? 0 : first + 1;
        return arr[tmp];
    }
}

题目二：实现一个特殊的栈

• 题目表述：实现一个特殊的栈，在实现栈的基本功能上再实现返回栈最小值的操作。
  【要求】：
  1. pop、push、geiMin操作的时间复杂度O(1)
  2. 设计的栈类型可以使用现成的栈结构

• 思想：
  • 基本栈的结构 - 双向链表/动态数组
  • 思路一：构造两个栈，一个data栈，一个min栈。data栈压栈入栈元素，同时min栈压栈最小元素（每来一个元素与栈顶元素比较，谁小压谁）。出栈则两个栈同时弹出
    • data：||32415
    • min：||32211
  • 思路二：构造两个栈，data / min栈。data栈压入栈元素，min栈顶元素比较，小则同时压入min栈，否则不压栈。出栈则比较，data栈出栈元素=min栈顶元素时，min栈出栈。
    • data：||32415
    • min：||321

思路一

• 算法实现（Java）

public static class MyStack1 {           //思路一
        private Stack<Integer> stackData;
        private Stack<Integer> stackMin;

        public MyStack1() {
            this.stackData = new Stack<Integer>();
            this.stackMin = new Stack<Integer>();
        }

        public void push(int newNum) {
            if (this.stackMin.isEmpty()) {
                this.stackMin.push(newNum);
            } else if (newNum <= this.getmin()) {
                this.stackMin.push(newNum);
            }
            this.stackData.push(newNum);
        }

        public int pop() {
            if (this.stackData.isEmpty()) {
                throw new RuntimeException("Your stack is empty.");
            }
            int value = this.stackData.pop();
            if (value == this.getmin()) {
                this.stackMin.pop();
            }
            return value;
        }

        public int getmin() {
            if (this.stackMin.isEmpty()) {
                throw new RuntimeException("Your stack is empty.");
            }
            return this.stackMin.peek();
        }
    }

思路二

• 算法实现（Java）

public static class MyStack2 {          //思路二
        private Stack<Integer> stackData;
        private Stack<Integer> stackMin;

        public MyStack2() {
            this.stackData = new Stack<Integer>();
            this.stackMin = new Stack<Integer>();
        }

        public void push(int newNum) {
            if (this.stackMin.isEmpty()) {
                this.stackMin.push(newNum);
            } else if (newNum < this.getmin()) {
                this.stackMin.push(newNum);
            } else {
                int newMin = this.stackMin.peek();
                this.stackMin.push(newMin);
            }
            this.stackData.push(newNum);
        }

        public int pop() {
            if (this.stackData.isEmpty()) {
                throw new RuntimeException("Your stack is empty.");
            }
            this.stackMin.pop();
            return this.stackData.pop();
        }

        public int getmin() {
            if (this.stackMin.isEmpty()) {
                throw new RuntimeException("Your stack is empty.");
            }
            return this.stackMin.peek();
        }
    }

题目三：队列实现栈 / 栈实现队列（灵活应用）

队列实现栈

• 思路
  • 用两个队列实现栈
  • 序列先全进第一个队列，进行以下操作：
    • 保留最后一个数其他元素全部出队列，进入第二个队列
    • 把第一个队列的值输出（即让最后进来的最先出去）
    • 之后第二个队列同样操作进入第一个队列，把最后一个元素输出
• 演示
  • 54321 空 —> 5 4321 输出5
  • 空 4321 —> 321 4 输出4

+算法实现（Java）

public static class TwoQueuesStack {
        private Queue<Integer> queue;
        private Queue<Integer> help;

        public TwoQueuesStack() {
            queue = new LinkedList<Integer>();
            help = new LinkedList<Integer>();
        }

        public void push(int pushInt) {
            queue.add(pushInt);
        }

        public int peek() {     //得到栈顶元素
            if (queue.isEmpty()) {
                throw new RuntimeException("Stack is empty!");
            }
            while (queue.size() != 1) {
                help.add(queue.poll());
            }
            int res = queue.poll();     //res为最后一个入队元素
            help.add(res);
            swap();     //两个栈引用交换一下
            return res;
        }

        public int pop() {
            if (queue.isEmpty()) {
                throw new RuntimeException("Stack is empty!");
            }
            while (queue.size() != 1) {
                help.add(queue.poll());
            }
            int res = queue.poll();
            swap();
            return res;
        }

        private void swap() {
            Queue<Integer> tmp = help;
            help = queue;
            queue = tmp;
        }

    }

栈实现队列

• 思路
  • 用两个栈实现队列：第一个栈专做push，第二个栈专做pop
  • 直接入第一个栈，全部倒入第二个栈，第二个栈再全部出栈，即可实现先进先出
  • 一栈倒二栈时机：
    1. 当pop栈中非空时，push栈不能倒
    2. pop栈为空时push倒，倒必须一次性倒完
  • 只要满足上述两个条件，无论倒数操作发生在什么时候，都一定对
• 算法实现（Java）

public static class TwoStacksQueue {
        private Stack<Integer> stackPush;
        private Stack<Integer> stackPop;

        public TwoStacksQueue() {
            stackPush = new Stack<Integer>();
            stackPop = new Stack<Integer>();
        }

        public void push(int pushInt) {
            stackPush.push(pushInt);
        }

        public int poll() {
            if (stackPop.empty() && stackPush.empty()) {
                throw new RuntimeException("Queue is empty!");
            } else if (stackPop.empty()) {          //倒数操作 
                while (!stackPush.empty()) {
                    stackPop.push(stackPush.pop());
                }
            }
            return stackPop.pop();
        }

        public int peek() {
            if (stackPop.empty() && stackPush.empty()) {
                throw new RuntimeException("Queue is empty!");
            } else if (stackPop.empty()) {
                while (!stackPush.empty()) {
                    stackPop.push(stackPush.pop());
                }
            }
            return stackPop.peek();
        }
    }

题目四：猫狗队列

• 题目表述：有如下猫类狗类，实现一个猫狗队列结构
  • add方法将cat / dog类实例入队
  • pollAll方法将所有实例出队
  • pollDog方法将所有狗实例出队
  • pollCat方法同理
  • isEmpty方法判断是否还有猫狗实例
  • isDogEmpty方法同理
  • isCatEmpty方法同理
• 猫狗类型：

public static class Pet {
        private String type;

        public Pet(String type) {
            this.type = type;
        }

        public String getPetType() {
            return this.type;
        }
    }

    public static class Dog extends Pet {
        public Dog() {
            super("dog");
        }
    }

    public static class Cat extends Pet {
        public Cat() {
            super("cat");
        }
    }

• 思路
  • 猫狗各一个队列，队列中用封装类PetEnterQueue，封装了一个pet类和一个count标志。
  • all系列函数则根据count标志的大小来决定同一队头谁先出
• 算法实现（Java）

public static class PetEnterQueue {     //为了不修改底层类，封装进一个新类
        private Pet pet;    
        private long count;     //标记自己是几号，衡量猫狗谁先出

        public PetEnterQueue(Pet pet, long count) {
            this.pet = pet;
            this.count = count;
        }

        public Pet getPet() {
            return this.pet;
        }

        public long getCount() {
            return this.count;
        }

        public String getEnterPetType() {
            return this.pet.getPetType();
        }
    }

    public static class DogCatQueue {
        private Queue<PetEnterQueue> dogQ;
        private Queue<PetEnterQueue> catQ;
        private long count;

        public DogCatQueue() {
            this.dogQ = new LinkedList<PetEnterQueue>();
            this.catQ = new LinkedList<PetEnterQueue>();
            this.count = 0;
        }

        public void add(Pet pet) {
            if (pet.getPetType().equals("dog")) {
                this.dogQ.add(new PetEnterQueue(pet, this.count++));
            } else if (pet.getPetType().equals("cat")) {
                this.catQ.add(new PetEnterQueue(pet, this.count++));
            } else {
                throw new RuntimeException("err, not dog or cat");
            }
        }

        public Pet pollAll() {
            if (!this.dogQ.isEmpty() && !this.catQ.isEmpty()) {
                if (this.dogQ.peek().getCount() < this.catQ.peek().getCount()) {
                    return this.dogQ.poll().getPet();
                } else {
                    return this.catQ.poll().getPet();
                }
            } else if (!this.dogQ.isEmpty()) {
                return this.dogQ.poll().getPet();
            } else if (!this.catQ.isEmpty()) {
                return this.catQ.poll().getPet();
            } else {
                throw new RuntimeException("err, queue is empty!");
            }
        }

        public Dog pollDog() {
            if (!this.isDogQueueEmpty()) {
                return (Dog) this.dogQ.poll().getPet();
            } else {
                throw new RuntimeException("Dog queue is empty!");
            }
        }

        public Cat pollCat() {
            if (!this.isCatQueueEmpty()) {
                return (Cat) this.catQ.poll().getPet();
            } else
                throw new RuntimeException("Cat queue is empty!");
        }

        public boolean isEmpty() {
            return this.dogQ.isEmpty() && this.catQ.isEmpty();
        }

        public boolean isDogQueueEmpty() {
            return this.dogQ.isEmpty();
        }

        public boolean isCatQueueEmpty() {
            return this.catQ.isEmpty();
        }

    }

哈希表

• 增删改查默认时间复杂度O(1)，但是常数项比较大 - 因为哈希函数在算值的时候代价比较大

哈希函数hashmap

• 性质
  1. 输入域无限，输出域有限
  2. 哈希函数不是随机函数，相同输入一定得到相同输出 same input same out
  3. 哈希碰撞：不同的输入也可能得到相同的输出 diff input same out
  4. 哈希函数的离散性：虽然性质①，但是不同的输入在输出域上得到的返回值会均匀分布（最重要性质）—> 用来打乱输入规律

哈希表/散列表

• 经典实现结构：由输出域组成的一组数组，每个值对应一组输入值链表。输入值根据哈希函数得到输出域上对应的某值，然后挂载在数组值的链表上。
• 哈希表扩容
  • 当挂载链表太长时，可以选择哈希表扩容，成倍扩容，时间复杂度可以做到O(1)
  • 可以离线扩容，扩容频率也不频繁
• Java哈希表实现结构：输出域仍然是一组数组，每个值后挂载的是一棵红黑树treemap
• hashset & hashmap
  • 实际上都是哈希表，前者add(key)，后者put(key,value)，value实际上就是key多出的一个伴随数据，并不影响哈希表结构

题目五：设计RandomPool结构

• 题目表述：设计一种结构，在该结构中有如下三个功能，要求时间复杂度O(1)：
  • insert(key)：将某个key加入到该结构，做到不重复加入
  • delete(key)：将原本在结构中的某个key移除
  • getRandom()：等概率随机返回结构中任何一个key
• 思路
  • 直接用哈希表就可以完成，难点的是（有delete情况下的getRandom）
  • 设置两张哈希表，第一个哈希表key是加入的值，value是第几个加入的；第二个哈希表key是第几个加入的，value是加入的值
  • 设置一个index变量，int index=0，每加入一个key，index++
  • insert和delete可以直接在第一个哈希表中完成，第二个哈希表也对应做出相同操作
  • getRandom可以直接随机函数生成一个随机数，但是问题是delete可能会使（第几个加入的）值变成不连续的，导致无法使用随机函数
  • 解决：
    • 每当删除一个key时，先让inedx--，再让index位置上的key（即最后加入的key），覆盖掉要删除的key，原要删除的value不变，把最后加入的key/value行删除。
    • 这样即可让value是一个连续的值，可以直接用随机函数随机get
      ```
      public static class Pool { //K模板
      private HashMap<K, Integer> keyIndexMap;
      private HashMap<Integer, K> indexKeyMap;
      private int size;

    public Pool() {
    this.keyIndexMap = new HashMap<K, Integer>();
    this.indexKeyMap = new HashMap<Integer, K>();
    this.size = 0;
    }

    public void insert(K key) {
    if (!this.keyIndexMap.containsKey(key)) {
    this.keyIndexMap.put(key, this.size);
    this.indexKeyMap.put(this.size++, key);
    }
    }

    public void delete(K key) {
    if (this.keyIndexMap.containsKey(key)) {
    int deleteIndex = this.keyIndexMap.get(key);
    int lastIndex = --this.size;
    K lastKey = this.indexKeyMap.get(lastIndex);
    this.keyIndexMap.put(lastKey, deleteIndex);
    this.indexKeyMap.put(deleteIndex, lastKey);
    this.keyIndexMap.remove(key);
    this.indexKeyMap.remove(lastIndex);
    }
    }

    public K getRandom() {
    if (this.size == 0) {
    return null;
    }
    int randomIndex = (int) (Math.random() * this.size);
    return this.indexKeyMap.get(randomIndex);
    }

  }
  ```

未完待续

算法<初级> - 第二章 队列、栈、哈希表相关问题

原文：https://www.cnblogs.com/ymjun/p/11700529.html