[leetCode 丶每日随机] 641. 设计循环双端队列

原题: 641.设计循环双端队列

描述:

设计实现双端队列。

实现 MyCircularDeque 类:

MyCircularDeque(int k) ：构造函数,双端队列最大为 k 。
boolean insertFront()：将一个元素添加到双端队列头部。如果操作成功返回 true ，否则返回 false 。
boolean insertLast() ：将一个元素添加到双端队列尾部。如果操作成功返回 true ，否则返回 false 。
boolean deleteFront() ：从双端队列头部删除一个元素。如果操作成功返回 true ，否则返回 false 。
boolean deleteLast() ：从双端队列尾部删除一个元素。如果操作成功返回 true ，否则返回 false 。
int getFront()：从双端队列头部获得一个元素。如果双端队列为空，返回 -1 。
int getRear() ：获得双端队列的最后一个元素。如果双端队列为空，返回 -1 。
boolean isEmpty() ：若双端队列为空，则返回 true ，否则返回 false 。
boolean isFull() ：若双端队列满了，则返回 true ，否则返回 false 。

示例 1：

输入

["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]

输出

[null, true, true, true, false, 2, true, true, true, 4]

解释
MyCircularDeque circularDeque = new MycircularDeque(3); // 设置容量大小为3
circularDeque.insertLast(1); // 返回 true
circularDeque.insertLast(2); // 返回 true
circularDeque.insertFront(3); // 返回 true
circularDeque.insertFront(4); // 已经满了，返回 false
circularDeque.getRear(); // 返回 2
circularDeque.isFull(); // 返回 true
circularDeque.deleteLast(); // 返回 true
circularDeque.insertFront(4); // 返回 true
circularDeque.getFront(); // 返回 4

提示

1 <= k <= 1000
0 <= value <= 1000
insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, isFull 调用次数不大于 2000 次

个人版答案

执行用时: 4 ms 执行内存消耗: 43.68 M

class MyCircularDeque {

		public int[] f;
        public int fc = 0;
        public int[] r;
        public int rc = 0;

        public MyCircularDeque(int k) {
            f = new int[k];
            r = new int[k];
        }

        public boolean insertFront(int value) {
            if((fc + rc) < f.length){
                fc++;
                f[fc-1] = value;
                return true;
            }
            return false;
        }

        public boolean insertLast(int value) {
            if((fc + rc) < r.length){
                rc++;
                r[rc-1] = value;
                return true;
            }
            return false;
        }

        public boolean deleteFront() {
            if (fc > 0){
                fc--;
                f[fc] = 0;
                return true;
            }
            if (rc > 0){
                rc--;
                for (int i = 0; i < rc; i++) {
                    r[i] = r[i+1];
                }
                return true;
            }
            return false;
        }

        public boolean deleteLast() {
            if (rc > 0){
                rc--;
                r[rc] = 0;
                return true;
            }
            if (fc > 0){
                fc--;
                for (int i = 0; i < fc; i++) {
                    f[i] = f[i+1];
                }
                return true;
            }
            return false;
        }

        public int getFront() {
            if (fc > 0){
                return f[fc-1];
            }
            if (rc > 0){
                return r[0];
            }
            return -1;
        }

        public int getRear() {
            if (rc > 0){
                return r[rc-1];
            }
            if (fc > 0){
                return f[0];
            }
            return -1;

        }

        public boolean isEmpty() {
            return fc == 0 && rc == 0;
        }

        public boolean isFull() {
            return fc + rc == f.length;
        }
}

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque obj = new MyCircularDeque(k);
 * boolean param_1 = obj.insertFront(value);
 * boolean param_2 = obj.insertLast(value);
 * boolean param_3 = obj.deleteFront();
 * boolean param_4 = obj.deleteLast();
 * int param_5 = obj.getFront();
 * int param_6 = obj.getRear();
 * boolean param_7 = obj.isEmpty();
 * boolean param_8 = obj.isFull();
 */

优秀解法及思路

class MyCircularDeque {
    private class DLinkListNode {
        int val;
        DLinkListNode prev, next;

        DLinkListNode(int val) {
            this.val = val;
        }
    }

    private DLinkListNode head, tail;
    private int capacity;
    private int size;

    public MyCircularDeque(int k) {
        capacity = k;
        size = 0;
    }

    public boolean insertFront(int value) {
        if (size == capacity) {
            return false;
        }
        DLinkListNode node = new DLinkListNode(value);
        if (size == 0) {
            head = tail = node;
        } else {
            node.next = head;
            head.prev = node;
            head = node;
        }
        size++;
        return true;
    }

    public boolean insertLast(int value) {
        if (size == capacity) {
            return false;
        }
        DLinkListNode node = new DLinkListNode(value);
        if (size == 0) {
            head = tail = node;
        } else {
            tail.next = node;
            node.prev = tail;
            tail = node;
        }
        size++;
        return true;
    }

    public boolean deleteFront() {
        if (size == 0) {
            return false;
        }
        head = head.next;
        if (head != null) {
            head.prev = null;
        }
        size--;
        return true;
    }

    public boolean deleteLast() {
        if (size == 0) {
            return false;
        }
        tail = tail.prev;
        if (tail != null) {
            tail.next = null;
        }
        size--;
        return true;
    }

    public int getFront() {
        if (size == 0) {
            return -1;
        }
        return head.val;
    }

    public int getRear() {
        if (size == 0) {
            return -1;
        }
        return tail.val;
    }

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

    public boolean isFull() {
        return size == capacity;
    }
}

个人解题思路与优秀答案解析

题目分析及个人版思路

循环双端队列, 我自己理解就是可以头尾操作, 头部插入一个元素后, 从尾部获取直接可以获取到当前唯一元素即可
同理, 如果尾部插入, 则从头部获取原则则为刚尾插的元素.
那么我们容易想到, 实现两个等长数组. A / B , 一个代表前插队列, 一个代表尾插队列. 那么我们只需要保证两个等长数组内有效长度之和小于等于K即可
根据题目描述方法来看, 我们需要特别注意一开始分析的独立元素头插和尾插的特性, 当元素入组A后, 从尾部查询B时, B数组内没有有效元素, 则应从A的前序索引中获取下标为0的首位元素作为队列尾部
同理尾插入B组时, 前序查询则应从B的前序索引获取下标为0的首位元素作为队列头部
根据以上分析, 删除头尾元素逻辑同查询, 因为数组需要移动对象向前移动. 又已知元素k小于1000...嘻嘻, 直接for咯
代码写的很详细啦. 我使用了两个变量分别控制数组A/B的入队数量. 则获取下标的时候, 要注意大小, 是先-- 还是后++.
4ms 击败了百分百....可把自己厉害坏了. 内存控制不是很好. 因为我又新建多余数组. 写完之后看其余大佬的答案, 数组还是可以继续优化的. 但是...我的目标又不是这.
找了个官方题解的链表答案, 大家可以欣赏一下. 根本上的思路还是一致的, 而且比我的双数组在索引控制和队列前后操作上具有更好的理解加成.