题解 | #某云SLB负载均衡#
某云SLB负载均衡
https://www.nowcoder.com/practice/067358deef2841dc8110ccfea928954b
题目很简单，只是描述的不太清楚。和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;
}
};
