Appearance
432. 全 O(1) 的数据结构
题目描述
请你设计一个用于存储字符串计数的数据结构，并能够返回计数最小和最大的字符串。
实现 AllOne 类：
- `AllOne()` 初始化数据结构的对象。
- `inc(String key)` 字符串 `key` 的计数增加 `1` 。如果数据结构中尚不存在 `key` ，那么插入计数为 `1` 的 `key` 。
- `dec(String key)` 字符串 `key` 的计数减少 `1` 。如果 `key` 的计数在减少后为 `0` ，那么需要将这个 `key` 从数据结构中删除。测试用例保证：在减少计数前，`key` 存在于数据结构中。
- `getMaxKey()` 返回任意一个计数最大的字符串。如果没有元素存在，返回一个空字符串 `""` 。
- `getMinKey()` 返回任意一个计数最小的字符串。如果没有元素存在，返回一个空字符串 `""` 。
**注意：**每个函数都应当满足 O(1) 平均时间复杂度。
示例：
输入 ["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", "getMinKey"] [[], ["hello"], ["hello"], [], [], ["leet"], [], []] 输出 [null, null, null, "hello", "hello", null, "hello", "leet"]
解释 AllOne allOne = new AllOne(); allOne.inc("hello"); allOne.inc("hello"); allOne.getMaxKey(); // 返回 "hello" allOne.getMinKey(); // 返回 "hello" allOne.inc("leet"); allOne.getMaxKey(); // 返回 "hello" allOne.getMinKey(); // 返回 "leet"
提示：
- `1 <= key.length <= 10`
- `key` 由小写英文字母组成
- 测试用例保证：在每次调用 `dec` 时，数据结构中总存在 `key`
最多调用 `inc`、`dec`、`getMaxKey` 和 `getMinKey` 方法 5 * 104 次
难度： Hard
题解代码
javascript
var AllOne = function() {
this.hash = {}
this.head = new ListNode()
this.tail = new ListNode()
this.head.next = this.tail
this.tail.prev = this.head
};
/**
* @param {string} key
* @return {void}
*/
AllOne.prototype.inc = function(key) {
if (key in this.hash) {
this.hash[key].set.delete(key)
const oldNode = this.hash[key]
const isEmpty = this.hash[key].set.size === 0
const cnt = this.hash[key].cnt
if (cnt + 1 === this.hash[key].prev.cnt) {
this.hash[key].prev.set.add(key)
this.hash[key] = this.hash[key].prev
} else {
const node = new ListNode(cnt + 1)
node.set.add(key)
node.prev = this.hash[key].prev
this.hash[key].prev.next = node
node.next = this.hash[key]
this.hash[key].prev = node
this.hash[key] = node
}
if (isEmpty) {
oldNode.prev.next = oldNode.next
oldNode.next.prev = oldNode.prev
}
} else {
if (this.tail.prev.cnt === 1) {
this.tail.prev.set.add(key)
this.hash[key] = this.tail.prev
} else {
const node = new ListNode(1)
node.set.add(key)
this.tail.prev.next = node
node.prev = this.tail.prev
node.next = this.tail
this.tail.prev = node
this.hash[key] = node
}
}
};
/**
* @param {string} key
* @return {void}
*/
AllOne.prototype.dec = function(key) {
this.hash[key].set.delete(key)
const oldNode = this.hash[key]
const isEmpty = this.hash[key].set.size === 0
const cnt = this.hash[key].cnt
if (cnt - 1 === this.hash[key].next.cnt) {
this.hash[key].next.set.add(key)
this.hash[key] = this.hash[key].next
} else if (cnt - 1 > 0) {
const node = new ListNode(cnt - 1)
node.set.add(key)
node.next = this.hash[key].next
this.hash[key].next.prev = node
this.hash[key].next = node
node.prev = this.hash[key]
this.hash[key] = node
} else if (cnt === 1) {
delete this.hash[key]
}
if (isEmpty) {
oldNode.prev.next = oldNode.next
oldNode.next.prev = oldNode.prev
}
};
/**
* @return {string}
*/
AllOne.prototype.getMaxKey = function() {
return [...this.head.next.set.keys()][0] || ''
};
/**
* @return {string}
*/
AllOne.prototype.getMinKey = function() {
return [...this.tail.prev.set.keys()][0]|| ''
};
function ListNode (cnt) {
this.cnt = cnt
this.prev = null
this.next = null
this.set = new Set()
}
/**
* 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()
*/