432. 全 O(1) 的数据结构

日期:2022-9-21 16:51 | 标签: | 阅读:10

这道题思路倒不是很复杂,考的是你的编程能力,对边界条件的判断,一定得耐心的实操几遍。

  1. 采用哈希+双向链表思路实现
    • 哈希用来存储键值对
    • 双向链表按照计数值排序
  2. 在添加/删除时需要考虑几种情况
    • 只有根节点的情形
    • 计数器值不连续的情形,说明有可能需要新增
    • 当计数器置为 0 时,需要删除节点
  3. 在 Javascript 中可以使用 Map 模拟哈希,构建 Node 类来模拟链表
/** 数据结构参考自标准答案 */
class Node {
    constructor(key, count) {
        count ? this.count = count : 0;
        this.keys = new Set();
        key ? this.keys.add(key) : this.keys.add("");
    }

    insert(node) {
        node.prev = this;
        node.next = this.next;
        node.prev.next = node;
        node.next.prev = node;
        return node;
    }

    remove() {
        this.prev.next = this.next;
        this.next.prev = this.prev;
    }
}


let AllOne = function () {
    this.keysMap = new Map();
    this.root = new Node();
    this.root.prev = this.root;
    this.root.next = this.root;
};

AllOne.prototype.inc = function (key) {
    if (this.keysMap.has(key)) {
        const curr = this.keysMap.get(key);
        if (curr.next === this.root || curr.next.count > curr.count + 1) {
            this.keysMap.set(key, curr.insert(new Node(key, curr.count + 1)));
        } else {
            curr.next.keys.add(key);
            this.keysMap.set(key, curr.next);
        }
        curr.keys.delete(key)
        if (curr.keys.size === 0) {
            curr.remove();
        }
    } else {
        if (this.root.next === this.root || this.root.next.count > 1) {
            this.keysMap.set(key, this.root.insert(new Node(key, 1)));
        } else {
            this.root.next.keys.add(key);
            this.keysMap.set(key, this.root.next);
        }
    }
};

/** 
 * @param {string} key
 * @return {void}
 */
AllOne.prototype.dec = function (key) {
    const curr = this.keysMap.get(key);
    if (curr.count === 1) {
        this.keysMap.delete(key);
    } else {
        if (curr.prev === this.root || curr.prev.count < curr.count - 1) {
            this.keysMap.set(key, curr.prev.insert(new Node(key, curr.count - 1)));
        } else {
            curr.prev.keys.add(key);
            this.keysMap.set(key, curr.prev);
        }
    }
    curr.keys.delete(key)
    if (curr.keys.size === 0) {
        curr.remove();
    }
};

/**
 * @return {string}
 */
AllOne.prototype.getMaxKey = function () {
    if (this.root.prev === this.root) {
        return "";
    } else {
        for (let key of this.root.prev.keys) {
            if (key) {
                return key;
            }
        }
        return "";
    }
};

/**
 * @return {string}
 */
AllOne.prototype.getMinKey = function () {
    if (this.root.next === this.root) {
        return "";
    } else {
        for (let key of this.root.next.keys) {
            if (key) {
                return key;
            }
        }
        return "";
    }
};



/**
 * Your AllOne object will be instantiated and called as such:
 * var obj = new AllOne()
 * obj.inc(key)
 * obj.dec(key)
 * var param_3 = obj.getMaxKey()
 * var param_4 = obj.getMinKey()
 */

版权声明: 署名-非商业性使用-禁止演绎 4.0 国际(CC BY-NC-ND 4.0
Copyright ©2013-2022 | 粤ICP备14081691号 | yipeng手工打造 | 联系方式