结构设计

232. 用栈实现队列

• 栈：先进后出FILO

• 队列：先进先出FIFO

• 准备两个栈，一个数据栈data,一个辅助栈help

  • push时，只需要向help栈中推

  • pop时，只要去data的栈顶元素，即data.pop(),但是data栈没有元素了需要怎样?将help栈的元素不断往data栈推，推完为止，如果data,help栈均无元素，报错

  • peek时，与pop的过程一样，只是在返回的时候，data.peek()

  • empty，当data,help均为空时，返回true

 class MyQueue {
        Stack<Integer> data;
        Stack<Integer> help;
 
        public MyQueue() {
            data = new Stack<>();
            help = new Stack<>();
        }

        public void push(int x) {
            help.push(x);
        }

        public int pop() {
            if (data.isEmpty() && help.isEmpty()) throw new RuntimeException("empty queue");
            if (data.isEmpty()) {
                while (!help.isEmpty()) data.push(help.pop());
            }
            return data.pop();
        }

        public int peek() {
            if (data.isEmpty() && help.isEmpty()) throw new RuntimeException("empty queue");
            if (data.isEmpty()) {
                while (!help.isEmpty()) data.push(help.pop());
            }
            return data.peek();
        }

        public boolean empty() {
            return data.isEmpty() && help.isEmpty();
        }
    }

剑指 Offer 09. 用两个栈实现队列

方法1:Stack

• 参考「232. 用栈实现队列」

class CQueue {

    Stack<Integer> data;
    Stack<Integer> help;

    public CQueue() {
        data = new Stack<>();
        help =new Stack<>();
    }
    
    public void appendTail(int value) {
        help.push(value);
    }
    
    public int deleteHead() {
      	//两个栈的数据都为空，返回-1
        if(data.isEmpty() && help.isEmpty()) return -1;
      	//data的数据没有了从help中拿
        if(data.isEmpty()){
            while(!help.isEmpty()) data.push(help.pop());
        }
      	//弹出data的栈顶元素
        return data.pop();
    }
}

方法2:Deque

• 注释的代码写法是等价的，详细参考基础与技巧

        class CQueue {

            Deque<Integer> data;
            Deque<Integer> help;

            public CQueue() {
                data = new ArrayDeque<>();
                help = new ArrayDeque<>();
            }

            public void appendTail(int value) {
                help.addFirst(value);
//                help.push(value);
            }

            public int deleteHead() {
                if (data.isEmpty() && help.isEmpty()) return -1;
                if (data.isEmpty()) {
                    while (!help.isEmpty()) {
//                        data.addFirst(help.pollFirst());
                        data.push(help.pop());
                    }
                }
//                return data.pollFirst();
                return data.pop();
            }
        }

225. 用队列实现栈

方法1:两个队列

• 队列是先进先出，栈是先进后出，在top()方法中，为了避免，数据拷贝，有一个swap()的动作，data与help的存储顺序是一样的

• 因为data队列的元素始终存在，判断栈是否为空的时候，只需要关注size(data)==0

• top()与pop()方法只是在弹出data的最后一个元素的时候是否要继续放回help队列

 class MyStack {
        private Queue<Integer> data;
        private Queue<Integer> help;

        /**
         * Initialize your data structure here.
         */
        public MyStack() {
            data = new LinkedList<>();
            help = new LinkedList<>();
        }

        /**
         * Push element x onto stack.
         */
        public void push(int x) {
            data.add(x);
        }

        /**
         * Removes the element on top of the stack and returns that element.
         */
        public int pop() {
            if (data.isEmpty()) throw new RuntimeException("stack empty");
            while (data.size() != 1) help.add(data.poll());
            int res = data.poll();
            swap();
            return res;
        }

        /**
         * Get the top element.
         */
        public int top() {
            if (data.isEmpty()) throw new RuntimeException("stack empty");
            while (data.size() != 1) help.add(data.poll());
            int res = data.poll();
            help.add(res);
            swap();
            return res;
        }


        private void swap() {
            Queue tmp = help;
            help = data;
            data = tmp;
        }

        /**
         * Returns whether the stack is empty.
         */
        public boolean empty() {
            return data.size() == 0;
        }
    }

方法2:一个队列

• shift()方法是为top() 与pop()方法准备的，做一件事：就是弹出队头到倒数第2个队尾元素的，将其送到队列的尾部，在执行top() 与pop()，弹出queue的队头元素，如果是top()，继续保留这个元素，pop()时扔掉

class MyStack {

    private Queue<Integer> queue;

    /**
     * Initialize your data structure here.
     */
    public MyStack() {
        queue = new LinkedList<>();
    }

    /**
     * Push element x onto stack.
     */
    public void push(int x) {
        queue.offer(x);
    }

    /**
     * Removes the element on top of the stack and returns that element.
     */
    public int pop() {
        shift();
        int res = queue.poll();
        return res;
    }

    /**
     * Get the top element.
     */
    public int top() {
        shift();
        int res = queue.poll();
        queue.offer(res);
        return res;
    }


    public void shift() {
        int size = queue.size();
        for (int i = 0; i < size - 1; i++) {
            queue.offer(queue.poll());
        }

    }


    /**
     * Returns whether the stack is empty.
     */
    public boolean empty() {
        return queue.isEmpty();
    }
}

155. 最小栈

方法1：辅助栈[浪费空间]

• 基础版辅助栈，准备一个data, 数据栈，准备一个help 辅助栈

• 其中data的存数据的，help辅助栈用来存最小值，在push操作时，help如果栈顶元素大于待push的元素，将待push的元素塞进help中，如果不是，则重复塞一次help的栈顶元素，注意help为空的时候特殊处理下

• 准备两个栈，data和help，做push操作时，需要保持help栈顶的元素始终最小，data的数据正常推入，help栈顶维持最小，在执行getMin方法的时候，返回help的栈顶元素

class MinStack {
        private Stack<Integer> data;
        private Stack<Integer> help;

        /**
         * initialize your data structure here.
         */
        public MinStack() {
            data = new Stack<>();
            help = new Stack<>();
        }

        public void push(int x) {
            data.push(x);
            if (help.isEmpty()) help.push(x);
            else if (help.peek() < x) help.push(help.peek());
            else help.push(x);
        }

        public void pop() {
            if (data.isEmpty()) throw new RuntimeException("stack empty");
            data.pop();
            help.pop();
        }

        public int top() {
            if (data.isEmpty()) throw new RuntimeException("stack empty");
            return data.peek();

        }

        public int getMin() {
            if (data.isEmpty()) throw new RuntimeException("stack empty");
            return help.peek();
        }
    }

方法2：辅助栈[不浪费空间]

• 升级版本辅助栈，当push 进去的时候，

  • 当help的栈顶元素比新来的元素小的时候，这个时候保持help不变

  • 当help的栈顶元素大于等于新来的元素时，help同步要推一份新的元素进来

  • 当help元素为空的时候，也需要往里推

• pop的时候，pop的元素是否和help 的元素有重叠，有就将help的元素pop出去，没有就维持不动，data栈正常pop

class MinStack {
    Stack<Integer> data;
    Stack<Integer> help;

    /**
     * initialize your data structure here.
     */
    public MinStack() {
        data = new Stack<>();
        help = new Stack<>();
    }

    public void push(int x) {
        if (help.isEmpty() || help.peek() >= x) {
            help.push(x);
        }
        data.push(x);

    }

    public void pop() {
        if (data.isEmpty()) throw new RuntimeException("The stack is empty");
        int pop = data.pop();
        if (pop == help.peek()) {
            help.pop();
        }
    }

    public int top() {
        if (data.isEmpty()) throw new RuntimeException("The stack is empty");
        return data.peek();
    }

    public int getMin() {
        if (help.isEmpty()) throw new RuntimeException("The stack is empty");
        return help.peek();
    }
}

307. 区域和检索 - 数组可修改

方法1:二分

class NumArray {

    class TreeNode {
        int val;
        int start;
        int end;
        TreeNode left;
        TreeNode right;

        public TreeNode(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    TreeNode root = null;


    private TreeNode buildTree(int[] nums, int start, int end) {
        if (start > end) return null;
        TreeNode curr = new TreeNode(start, end);
        if (start == end) curr.val = nums[start];
        else {
            int mid = start + (end - start) / 2;
            curr.left = buildTree(nums, start, mid);
            curr.right = buildTree(nums, mid + 1, end);
            curr.val = curr.left.val + curr.right.val;
        }
        return curr;
    }


    public NumArray(int[] nums) {
        root = buildTree(nums, 0, nums.length - 1);
    }

    public void update(int i, int val) {
        updateTree(root, i, val);
    }

    public void updateTree(TreeNode node, int i, int val) {
        if (node.start == node.end) {
            node.val = val;
        } else {
            int mid = node.start + (node.end - node.start) / 2;
            if (i <= mid) updateTree(node.left, i, val);
            else updateTree(node.right, i, val);
            node.val = node.left.val + node.right.val;
        }
    }

    public int sumRange(int i, int j) {
        return queryTree(root, i, j);
    }

    public int queryTree(TreeNode node, int i, int j) {
        System.out.println(String.format("i:%d,j:%d", i, j));
        System.out.println(node);
        System.out.println(String.format("Node.val:%d", node.val));
        if (node.start == i && node.end == j) return node.val;
        else {
            int mid = node.start + (node.end - node.start) / 2;
            if (j <= mid) {
                return queryTree(node.left, i, j);
            } else if (i >= mid + 1) {
                return queryTree(node.right, i, j);
            } else {
                return queryTree(node.left, i, mid) + queryTree(node.right, mid + 1, j);
            }
        }
    }
}

方法2:线段树

380. O(1) 时间插入、删除和获取随机元素

class RandomizedSet {

    Map<Integer, Integer> map = new HashMap<>();//k:插入的值，v:list的size
    List<Integer> list = new ArrayList<>();
    Random random = new Random();

    /**
     * Initialize your data structure here.
     */
    public RandomizedSet() {

    }

    /**
     * Inserts a value to the set. Returns true if the set did not already contain the specified element.
     */
    public boolean insert(int val) {
        if (map.containsKey(val)) return false;
        map.put(val, list.size());
        list.add(val);
        return true;
    }

    /**
     * Removes a value from the set. Returns true if the set contained the specified element.
     */
    public boolean remove(int val) {
        if (!map.containsKey(val)) return false;
        int idx = map.get(val);//找到val的索引
        int lastEle = list.get(list.size() - 1);//list中的最后一个元素
        list.set(idx, lastEle);//当前的val用lastEle替换
        map.put(lastEle, idx);//更新关系
        //移除元素
        list.remove(list.size() - 1);
        map.remove(val);
        return true;
    }

    /**
     * Get a random element from the set.
     */
    public int getRandom() {
        int ranIdx = random.nextInt(list.size());
        return list.get(ranIdx);
    }
}

146. LRU 缓存

需要一个哈希双端链表，DoubleLinkedNode

这个双端链表有下面的几个属性

        class DoubleLinkedNode {
            int key, value;//k,v
            DoubleLinkedNode pre, next;//前驱接节点，后继节点

            public DoubleLinkedNode(int key, int value) {
                this.key = key;
                this.value = value;
            }

            public DoubleLinkedNode() {
            }
        }

将新加入的节点插入到双端链表的头部位置addFirst(node)

image-20200904085250881.png

        /**
         * 将节点加入到双向链表的开头的位置
         */
        public void addFirst(DoubleLinkedNode node) {
            node.pre = head;//1.当前节点的前驱结点指向head节点
            node.next = head.next;//2.当前节点的后继节点指向head的后继节点

            head.next.pre = node;//3.head节点的后继节点的前驱结点指向当前节点
            head.next = node;//4.head的后继节点指向当前节点
        }

移除一个节点removeNode(node)

image-20200904090539191.png

        /**
         * 移除一个普通的节点
         *
         * @param node
         */
        public void removeNode(DoubleLinkedNode node) {
            DoubleLinkedNode next = node.next;
            DoubleLinkedNode pre = node.pre;
            pre.next = next;
            next.pre = pre;
        }

弹出最末尾的节点，并返回最后的节点popLast

        /**
         * 弹出最末尾的节点并将改节点返回
         *
         * @return
         */
        public DoubleLinkedNode popLast() {
            DoubleLinkedNode last = tail.pre;
            removeNode(last);
            return last;
        }

将一个已经在链表中存在的节点移动到链表的开头moveToHead(node)

• 先移除这个节点移除，再将这个节点添加到链表的开头

        /**
         * 将当前节点移动到最头部位置
         *
         * @param node
         */
        public void moveToHead(DoubleLinkedNode node) {
            removeNode(node);
            addFirst(node);
        }

下面开始LRU

思路

初始化

• 注意head节点和tail节点需要new出来

get(key)

• 如果cache中不存在key,返回-1

• 如果cache中存在，取出这个节点，将节点moveToHead，返回节点的值

put(k,v)

• 取出节点，分节点存在与否讨论：

  • 节点不存在：新创建节点，将该节点插入到链表的头部，并将其put进cache中

    • 做一个额外的判断：如果当前的cache的大小大于capacity，需要移除最末尾的节点，链表和$cache$都要做移除操作

  • 节点存在:返回节点的值，将节点移动到链表头部

    class LRUCache {
        DoubleLinkedNode head, tail;//Node的收尾节点
        int capacity;//容量
        Map<Integer, DoubleLinkedNode> cache;//<k,v> k是key，v是key生成的node

        /**
         * 初始化
         *
         * @param capacity
         */
        public LRUCache(int capacity) {
            this.capacity = capacity;
            this.cache = new HashMap<>();
            this.head = new DoubleLinkedNode();
            this.tail = new DoubleLinkedNode();
            this.head.next = tail;
            this.tail.pre = head;

        }

        public int get(int key) {
            if (!cache.containsKey(key)) return -1;
            DoubleLinkedNode node = cache.get(key);
            moveToHead(node);
            return node.value;
        }

        public void put(int key, int value) {
            DoubleLinkedNode node = cache.get(key);
            if (node == null) {
                node = new DoubleLinkedNode(key, value);
                addFirst(node);
                cache.put(key, node);
                if (cache.size() > capacity) {
                    DoubleLinkedNode last = popLast();
                    cache.remove(last.key);
                }
            } else {
                node.value = value;
                moveToHead(node);
            }
        }
    }

933. 最近的请求次数

class RecentCounter {
    Deque<Integer> q;

    public RecentCounter() {
        q = new LinkedList<>();
    }

    public int ping(int t) {
        q.offerLast(t);
        while (q.peek() < t - 3000) q.pollFirst();
        return q.size();
    }
}

• 另

class RecentCounter {

    PriorityQueue<Integer> pq;
    int N = 3000;

    public RecentCounter() {
        pq = new PriorityQueue<>();
    }

    public int ping(int t) {

        while (!pq.isEmpty() && pq.peek() < t - N) {
            pq.poll();
        }
        pq.offer(t);
        return pq.size();
    }
}

2043. 简易银行系统

方法1:模拟

class Bank {

    long[] balance;
    int capacity;

    public Bank(long[] balance) {
        this.balance = new long[balance.length + 1];
        this.capacity = balance.length + 1;
        for (int i = 0; i < balance.length; i++) {
            this.balance[i + 1] = balance[i];
        }
    }

    public boolean transfer(int account1, int account2, long money) {
        if (account1 > capacity || account2 > capacity) return false;
        if (this.balance[account1] < money) return false;
        this.balance[account1] -= money;
        this.balance[account2] += money;
        return true;
    }

    public boolean deposit(int account, long money) {
        if (account > capacity) return false;
        this.balance[account] += money;
        return true;
    }

    public boolean withdraw(int account, long money) {
        if (account > capacity) return false;
        if (this.balance[account] < money) return false;
        this.balance[account] -= money;
        return true;
    }
}