题目很简单,只是描述的不太清楚。和LRU类似,用一个free集合表示可用的机器,用一个use集合表示正在使用中的,用一个hash表存放id和所有集合中元素的映射关系,以便根据id查找。
思路:
1. 定义node节点,存放id和时间戳,id就是题目输入的id,时间戳初始化为1,每次操作的时候自增,当要插入的时候更新node的时间戳
2. 为node定义比较函数,比较准则为时间戳的大小,free_set和use_set都使用该准则,以便取出的第一个元素就是最早加入的机器
3. add操作:判断id是否已经在hash表中,不在就插入到free_set中,并更新hash[id]为插入返回的迭代器
4. delete操作:判断hash[id]是否存在,存在则从free_set或者use_set中删除,然后再从hash中删除
5.select操作:如果free_set为空,返回use_set的个数,否则返回free_set.begin对应的id,并且将该机器移动到use_set中,然后更新hash[id]
6.release操作:将id对于的机器从use_set中删除,然后放入free_set中,并更新hash[id]
代码如下:
struct node
{
int id;
int timestamp;
};
class compare_obj
{
public:
bool operator()(const node &left, const node &right)
{
return left.timestamp < right.timestamp;
}
};
class Solution
{
public:
vector<int> SLB(vector<vector<int>> &operators)
{
int time = 0;
std::set<node, compare_obj> free_set;
std::unordered_map<int, std::set<node>::iterator> hash;
std::set<node, compare_obj> use_set;
std::vector<int> ans;
for (auto &v : operators)
{
int op = v[0];
time++;
if (op == 1) // add
{
if (hash.find(v[1]) == hash.end())
{
node n;
n.id = v[1];
n.timestamp = time;
hash[n.id] = free_set.insert(free_set.begin(), n);
}
}
else if (op == 2) // delete
{
int id = v[1];
if (hash.find(id) != hash.end())
{
if (free_set.find(*hash[id]) != free_set.end())
{
free_set.erase(hash[id]);
}
else if (use_set.find(*hash[id]) != use_set.end())
{
use_set.erase(hash[id]);
}
hash.erase(id);
}
}
else if (op == 3) // select
{
if (free_set.empty())
{
ans.push_back(use_set.size());
}
else
{
auto it = free_set.begin();
ans.push_back(it->id);
hash[it->id] = use_set.insert(use_set.begin(), *it);
free_set.erase(it);
}
}
else if (op == 4) // release
{
int id = v[1];
if (hash.find(id) != hash.end())
{
auto n = *hash[id];
use_set.erase(hash[id]);
hash[id] = free_set.insert(free_set.begin(), n);
}
}
}
return ans;
}
};

京公网安备 11010502036488号