响应式网站模块,wordpress批量,dw网站开发环境,微信网站开发源代码文章目录1. 题目2. 解题1. 题目
请你实现一个数据结构支持以下操作#xff1a;
Inc(key) - 插入一个新的值为 1 的 key。 或者使一个存在的 key 增加一#xff0c;保证 key 不为空字符串。Dec(key) - 如果这个 key 的值是 1#xff0c;那么把他从数据结构中移除掉。 否则使…
文章目录1. 题目2. 解题1. 题目
请你实现一个数据结构支持以下操作
Inc(key) - 插入一个新的值为 1 的 key。 或者使一个存在的 key 增加一保证 key 不为空字符串。Dec(key) - 如果这个 key 的值是 1那么把他从数据结构中移除掉。 否则使一个存在的 key 值减一。 如果这个 key 不存在这个函数不做任何事情。key 保证不为空字符串。GetMaxKey() - 返回 key 中值最大的任意一个。 如果没有元素存在返回一个空字符串 。GetMinKey() - 返回 key 中值最小的任意一个。 如果没有元素存在返回一个空字符串。
挑战 你能够以 O(1) 的时间复杂度实现所有操作吗 来源力扣LeetCode 链接https://leetcode-cn.com/problems/all-oone-data-structure 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
参考大佬的题解 class node
{
public:int val;unordered_setstring s;node(int v){val v;}
};
class AllOne {unordered_mapstring, listnode::iterator m;listnode l;
public:/** Initialize your data structure here. */AllOne() {}/** Inserts a new key Key with value 1. Or increments an existing key by 1. */void inc(string key) {auto it m.find(key);if(it m.end()){if(l.empty() || l.front().val 1)l.push_front(node(1));//没有val为1的新建l.begin()-s.insert(key);m[key] l.begin();}else{auto iter it-second;//迭代器位置int num iter-val;//当前数字iter-s.erase(key);//原位置处删除auto olditer iter;auto newiter iter;num;if(newiter ! l.end() newiter-val num){ //新位置数字刚好是1以后的newiter-s.insert(key);m[key] newiter;}else{ //新开辟节点auto temp l.insert(newiter,node(num));//新节点之前插入temp-s.insert(key);//返回的当前节点存入字符串m[key] temp;}if(olditer-s.empty())l.erase(olditer);//原来节点为空要删除}}/** Decrements an existing key by 1. If Keys value is 1, remove it from the data structure. */void dec(string key) {auto it m.find(key);if(it m.end()) return;auto iter it-second;int num iter-val;iter-s.erase(key);auto olditer iter;auto newiter --iter;num--;if(num 0)m.erase(key);else if(olditer ! l.begin() newiter-val num){ //前面还有节点且数字吻合newiter-s.insert(key);m[key] newiter;}else{ //前面数字不符合在老节点前插入auto temp l.insert(olditer,node(num));temp-s.insert(key);m[key] temp;}if(olditer-s.empty())l.erase(olditer);}/** Returns one of the keys with maximal value. */string getMaxKey() {if(l.empty()) return ;return *(l.back().s.begin());}/** Returns one of the keys with Minimal value. */string getMinKey() {if(l.empty()) return ;return *(l.front().s.begin());}
};100 ms 24.9 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
