O(1)问题之栈与Map

Description

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
Follow up:
Could you do both operations in O(1) time complexity?
Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
push(x) — Push element x onto stack.
pop() — Removes the element on top of the stack.
top() — Get the top element.
getMin() — Retrieve the minimum element in the stack.
Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
Calling next() will return the next smallest number in the BST.
Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

Solution

[leetcode 146] LRU Cache

题目的意思是指定容器大小，如果put的时候发现容器满了，就将最后的元素剔除掉，将当前元素添加到最前面；使用get访问过的元素，需要将其提到最前面来。
这里参考了Java—-Easy Version To Understand
先定义一个节点，该节点的前驱节点，后继节点，节点的key，value对应着Map的key和value

class Node {
    int key;
    int value;
    Node pre;
    Node next;
    public Node(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

初始化：先定义两个节点，维持一个双向链表，作为链表的头结点和尾节点；用一个Map来记录put的值；
get：先判断是否在Map中，如果不在直接返回-1；如果在，先将Map中的值取出来，然后在对应的双向链表中将该节点提到最前面来，返回该值
put：先判断put的值是否已经在Map中，如果在，直接将双向链表中对应的节点提到最前面来；如果不在，先判断是否Map达到指定大小了，如果没有，直接在双向链表中添加该节点，并添加到Map中，如果超过了，就将双向链表中的最后一个节点删除，同时删除Map中对应的值，在将其添加。
代码如下：

public class LRUCache {
    HashMap<Integer, Node> map;
    int capicity, count;
    Node head, tail;
    public LRUCache(int capacity) {
        this.capicity = capacity;
        map = new HashMap<>();
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.pre = head;
        head.pre = null;
        tail.next = null;
        count = 0;
    }
    public void deleteNode(Node node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }
    public void addToHead(Node node) {
        node.next = head.next;
        node.next.pre = node;
        node.pre = head;
        head.next = node;
    }
    public int get(int key) {
        if (map.get(key) != null) {
            Node node = map.get(key);
            int result = node.value;
            deleteNode(node);
            addToHead(node);
            return result;
        }
        return -1;
    }
    public void put(int key, int value) {
        if (map.get(key) != null) {
            Node node = map.get(key);
            node.value = value;
            deleteNode(node);
            addToHead(node);
        } else {
            Node node = new Node(key, value);
            map.put(key, node);
            if (count < capicity) {
                count++;
                addToHead(node);
            } else {
                map.remove(tail.pre.key);
                deleteNode(tail.pre);
                addToHead(node);
            }
        }
    }
}

[leetcode 155] Min Stack

用两个栈，一个将全部元素入栈，一个将当前的最小值入栈,注意一些条件
虽然很简单，但是我觉得这种题还是有意义的，代码如下：

public class MinStack {
    Stack<Integer> stack1;
    Stack<Integer> stack2;
    /** initialize your data structure here. */
    public MinStack() {
        stack1=new Stack<>();
        stack2=new Stack<>();
    }
    //这里有重复的元素出现，需要加上>=，比如0，1，0
    public void push(int x) {
        stack1.push(x);
        if(stack2.isEmpty()||stack2.peek()>=x)stack2.push(x);
    }
    public void pop() {
        if(stack1.isEmpty())return;
        int temp=stack1.pop();
        if(temp==stack2.peek())stack2.pop();
    }
    public int top() {
        return stack1.peek();
    }
    public int getMin() {
        return stack2.peek();
    }
}

[leetcode 173] Binary Search Tree Iterator

二叉搜索树的一大特征就是按前序遍历输出的序列是有序的，题目中要求非递归的前序遍历，然后给出时间复杂度和空间复杂度的限制，空间复杂度的h为树高，如果h为节点的个数的话，是可以用map做的，用递归的方法前序遍历二叉树，存储节点到map中，这样直接取就可以，如下：

public class BSTIterator {
    Map<Integer,Integer> map;
    int i=0;
    int index=0;
    public BSTIterator(TreeNode root) {
        map=new HashMap<>();
        pushMap(map,root);
    }
    private void pushMap(Map<Integer, Integer> map, TreeNode node) {
        if(node!=null){
            pushMap(map,node.left);
            map.put(i,node.val);
            i++;
            pushMap(map,node.right);
        }
    }
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        if(index>=i)return false;
        else return true;
    }
    /** @return the next smallest number */
    public int next() {
        return map.get(index++);
    }
}

但是这道题专门强调了空间复杂度中的h为树高，所以这样做是不合理的(虽然通过了)，只能用stack做，discuss中的解法也全部用的是stack，但是有一个问题，在使用next的时候，如果出现节点的左子树为空，但是右子树却很长的情况，时间复杂度显然不是O(1)，不过有提到是平均复杂度，好吧，这是唯一的解法了，如下：

public class BSTIterator {
    private Stack<TreeNode> stack = new Stack<TreeNode>();
    
    public BSTIterator(TreeNode root) {
        pushAll(root);
    }
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !stack.isEmpty();
    }
    /** @return the next smallest number */
    public int next() {
        TreeNode tmpNode = stack.pop();
        pushAll(tmpNode.right);
        return tmpNode.val;
    }
    
    private void pushAll(TreeNode node) {
        for (; node != null; stack.push(node), node = node.left);
    }
}

参考：My solutions in 3 languages with Stack