山西省大同市网站建设公司,网站建设代码标准,网站域名解析怎么做,Wordpress如何加联盟广告LeetCode 432. 全 O(1) 的数据结构
难度#xff1a;hard\color{red}{hard}hard 题目描述
请你设计一个用于存储字符串计数的数据结构#xff0c;并能够返回计数最小和最大的字符串。
实现 AllOneAllOneAllOne 类#xff1a; AllOne()AllOne()AllOne() 初始化数据结构的对…LeetCode 432. 全 O(1) 的数据结构
难度hard\color{red}{hard}hard 题目描述
请你设计一个用于存储字符串计数的数据结构并能够返回计数最小和最大的字符串。
实现 AllOneAllOneAllOne 类
AllOne()AllOne()AllOne() 初始化数据结构的对象。inc(Stringkey)inc(String key)inc(Stringkey) 字符串 keykeykey 的计数增加 111 。如果数据结构中尚不存在 keykeykey 那么插入计数为 111 的 keykeykey 。dec(Stringkey)dec(String key)dec(Stringkey) 字符串 keykeykey 的计数减少 111 。如果 keykeykey 的计数在减少后为 000 那么需要将这个 keykeykey 从数据结构中删除。测试用例保证在减少计数前keykeykey 存在于数据结构中。getMaxKey()getMaxKey()getMaxKey() 返回任意一个计数最大的字符串。如果没有元素存在返回一个空字符串 。getMinKey()getMinKey()getMinKey() 返回任意一个计数最小的字符串。如果没有元素存在返回一个空字符串 。
注意 每个函数都应当满足 O(1)O(1)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提示
1key.length101 key.length 101key.length10keykeykey 由小写英文字母组成测试用例保证在每次调用 decdecdec 时数据结构中总存在 keykeykey最多调用 incincinc、decdecdec、getMaxKeygetMaxKeygetMaxKey 和 getMinKeygetMinKeygetMinKey 方法 5∗1045 * 10^{4}5∗104 次 算法
(哈希表双向链表)
定义结构体 Node记录值 value 和所有等于该值的字符串集合。维护一个哈希表每个 key 对应的一个 Node 类型的指针。Node 结构按值的顺序组成双向链表。初始时有值为 INT_MIN 和值为 INT_MAX 的两个哨兵结点。对于插入操作如果哈希表中不存在则在哈希表中添加 h[key] new node(val)。从哈希表中取出当前结构体将这个 key 添加到下一个结构体中如果不存在则新建立结点并在当前结构体中删除 key。对于删除同理进行移动 key 的操作。取最大最小值时直接取链表的头或尾所对应的的字符串集合。
复杂度分析 时间复杂度O(1)O(1)O(1) 空间复杂度 : O(n)O(n)O(n)
C 代码
class AllOne {
public://创建一个双链表其中有左右指针struct Node {Node *left, *right;int val;unordered_setstring S;Node(int _val) {val _val;left right NULL;}}*left, *right;// 创建一个哈希表unordered_mapstring, Node* hash;//初始化双链表最左边的节点和最右边的节点AllOne() {left new Node(INT_MIN), right new Node(INT_MAX);right-left left, left-right right;}//在节点的右边插入一个新的节点Node* add_to_right(Node *node, string key, int val) {if (node-right-val val) node-right-S.insert(key);else {auto t new Node(val);t-S.insert(key);t-right node-right, node-right-left t;node-right t, t-left node;}return node-right;}//在节点的左边边插入一个新的节点Node* add_to_left(Node *node, string key, int val) {if (node-left-val val) node-left-S.insert(key);else {auto t new Node(val);t-S.insert(key);t-left node-left, node-left-right t;node-left t, t-right node;}return node-left;}//删除一个节点void remove(Node* node) {node-left-right node-right;node-right-left node-left;delete node;}void inc(string key) {//如果该节点计数为0,在最左边插入一个值为1的节点if (hash.count(key) 0) hash[key] add_to_right(left, key, 1);else {//向右插入一个新的节点auto t hash[key];t-S.erase(key);hash[key] add_to_right(t, key, t-val 1);if (t-S.empty()) remove(t);}}void dec(string key) {if (hash.count(key) 0) return;auto t hash[key];t-S.erase(key);if (t-val 1) {hash[key] add_to_left(t, key, t-val - 1);} else {hash.erase(key);}if (t-S.empty()) remove(t);}string getMaxKey() {if (right-left ! left) return *right-left-S.begin();return ;}string getMinKey() {if (left-right ! right) return *left-right-S.begin();return ;}
};/*** Your AllOne object will be instantiated and called as such:* AllOne* obj new AllOne();* obj-inc(key);* obj-dec(key);* string param_3 obj-getMaxKey();* string param_4 obj-getMinKey();*/修改变量版本
class AllOne {
public:struct Node {Node *pre, *nxt;int value;unordered_setstring keys;Node (int val) {value val;pre nxt NULL;}}*left, *right;unordered_mapstring, Node* hash;AllOne() {left new Node(0);right new Node(INT_MAX);left-nxt right;right-pre left;}Node* add_to_right(Node* node, string key, int val) {if (node-nxt-value val) node-nxt-keys.insert(key);else {auto t new Node(val);t-keys.insert(key);t-nxt node-nxt, node-nxt-pre t;t-pre node, node-nxt t;}return node-nxt;}Node* add_to_left(Node* node, string key, int val) {if (node-pre-value val) node-pre-keys.insert(key);else {auto t new Node(val);t-keys.insert(key);node-pre-nxt t, t-nxt node;t-pre node-pre, node-pre t;}return node-pre;}void remove(Node *node) {node-pre-nxt node-nxt;node-nxt-pre node-pre;delete node;}void inc(string key) {if (hash.count(key) 0) hash[key] add_to_right(left, key, 1);else {auto t hash[key];t-keys.erase(key);hash[key] add_to_right(t, key, t-value 1);if (t-keys.empty()) remove(t);}}void dec(string key) {if (hash.count(key) 0) return;auto t hash[key];t-keys.erase(key);if (t-value 1) {hash[key] add_to_left(t, key, t-value - 1);} else {hash.erase(key);}if (t-keys.empty()) remove(t);}string getMaxKey() {if (left-nxt ! right) return *right-pre-keys.begin();return ;}string getMinKey() {if (right-pre ! left) return *left-nxt-keys.begin();return ;}
};/*** Your AllOne object will be instantiated and called as such:* AllOne* obj new AllOne();* obj-inc(key);* obj-dec(key);* string param_3 obj-getMaxKey();* string param_4 obj-getMinKey();*/
