SP2. 某云SLB负载均衡
描述
示例1
输入:
[[1, 1], [1, 2], [1, 3], [3], [3], [2, 1], [3], [4, 2], [3]]
输出:
[1,2,3,2]
说明:
先加入三台服务器到使用池，用户依次使用前两台，删除使用池中的第一台服务器，用户继续使用第三台，归还第二台以后用户使用第二台。C++ 解法, 执行用时: 3ms, 内存消耗: 396KB, 提交时间: 2022-07-06
using namespace std;
struct node {
int id;
int timestap;
node(int _id, int _timestap) : id(_id), timestap(_timestap) {}
bool operator<(const node& n) const {
return this->timestap < n.timestap;
}
};
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param operators int整型vector<vector<>>
* @return int整型vector
*/
vector<int> SLB(vector<vector<int> >& operators) {
// write code here
int time = 0;
set<node, less<>> free_set;
set<node, less<>> user_set;
unordered_map<int, set<node>::iterator> id_map;
vector<int> ans;
for (auto& v : operators) {
int op = v[0];
time++;
if (op == 1) { // add
int id = v[1];
if (id_map.find(id) == id_map.end()) {
node n(id, time);
id_map[id] = free_set.insert(free_set.begin(), n);
}
} else if (op == 2) { // delete
int id = v[1];
if (id_map.find(id) != id_map.end()) {
auto it = id_map[id];
id_map.erase(id);
if (free_set.find(*it) != free_set.end()) {
free_set.erase(it);
} else if (user_set.find(*it) != user_set.end()) {
user_set.erase(it);
}
}
} else if (op == 3) { // select
if (free_set.empty()) {
ans.push_back(id_map.size());
} else {
auto it = free_set.begin();
free_set.erase(it);
id_map[it->id] = user_set.insert(user_set.begin(), *it);
ans.push_back(it->id);
}
} else if (op == 4) { // release
int id = v[1];
if (id_map.find(id) != id_map.end()) {
auto it = id_map[id];
user_set.erase(it);
id_map[id] = free_set.insert(free_set.begin(), *it);
}
}
}
return ans;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 400KB, 提交时间: 2022-08-06
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param operators int整型vector<vector<>>
* @return int整型vector
*/
class ListNode{
public:
int id;
bool in_use;
ListNode *pre, *next;
ListNode():id(0), in_use(false), pre(nullptr), next(nullptr){};
ListNode(int id):id(id), in_use(false), pre(nullptr), next(nullptr){};
};
ListNode *head, *tail;
unordered_map<int, ListNode*> m;
int cnt;
vector<int> SLB(vector<vector<int> >& operators) {
// write code here
head = new ListNode();
tail = new ListNode();
head->next = tail;
tail->pre = head;
cnt = 0;
vector<int> ret;
for(int i=0; i<operators.size(); ++i){
switch(operators[i][0]){
case 1:
add_server(operators[i][1]);
break;
case 2:
delete_server(operators[i][1]);
break;
case 3:
ret.push_back(select_server());
break;
case 4:
release_server(operators[i][1]);
break;
}
}
return ret;
}
void add_server(int id){
if(m[id]){
return;
}
ListNode *node = new ListNode(id);
node->next = head->next;
node->pre = head;
node->next->pre = node;
node->pre->next = node;
m[id] = node;
++cnt;
}
void delete_server(int id){
if(!m[id]){
return;
}
ListNode *node = m[id];
node->pre->next = node->next;
node->next->pre = node->pre;
delete node;
m[id] = nullptr;
--cnt;
}
int select_server(){
ListNode *node = tail->pre;
while(node != head){
if(node->in_use){
node = node->pre;
}
else{
int id = node->id;
node->in_use = true;
return id;
}
}
return cnt;
}
void release_server(int id){
if(!m[id]){
return;
}
m[id]->in_use = false;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 460KB, 提交时间: 2022-07-20
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param operators int整型vector<vector<>>
* @return int整型vector
*/
struct node{
int key,val;
friend bool operator<(node a,node b){
return a.key<b.key;
}
};
set<node>mp;
unordered_map<int, node*>G;
vector<int> SLB(vector<vector<int> >& operators) {
// write code here
vector<int>res;
int n=operators.size();
for(int i=0;i<n;++i){
int x=operators[i][0];
if(x==1){
if(!G.count(operators[i][1])){
node *tmp=new node{i,operators[i][1]};
mp.insert(*tmp);
G[tmp->val]=tmp;
}
}
else if(x==2){
if(G.count(operators[i][1])){
mp.erase(*G[operators[i][1]]);
G.erase(operators[i][1]);
}
}
else if(x==3){
if(!mp.size()) res.push_back(G.size());
else {
res.push_back(mp.begin()->val);
mp.erase(mp.begin());
}
}
else{
if(G.count(operators[i][1])){
mp.insert(*G[operators[i][1]]);
}
}
}
return res;
}
};
C++ 解法, 执行用时: 4ms, 内存消耗: 400KB, 提交时间: 2022-07-06
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param operators int整型vector<vector<>>
* @return int整型vector
*/
int idx = 0; // 可用池中的序号
unordered_map<int, int> mp; // <id, idx>
map<int, int> pool; // 可用池，<idx，id>
unordered_set<int> used; // 使用中
void add(int id) {
if (!mp.count(id)) {
++idx;
pool[idx] = id;
mp[id] = idx;
}
}
void del(int id) {
if (mp.count(id)) {
int i = mp[id];
mp.erase(id);
pool.erase(i);
if (used.count(id))
used.erase(id);
}
}
int select() {
if (pool.empty())
return used.size();
auto iter = pool.begin();
used.insert(iter->second);
pool.erase(iter);
return iter->second;
}
void release(int id) {
if (used.count(id)) {
int i = mp[id];
used.erase(id);
pool[i] = id;
}
}
vector<int> SLB(vector<vector<int> >& operators) {
// write code here
vector<int> res;
for (auto item : operators) {
int i = item[1];
switch(item[0]) {
case 1:
add(i); break;
case 2:
del(i); break;
case 3:
res.push_back(select());
break;
case 4:
release(i); break;
}
}
return res;
}
};
C++ 解法, 执行用时: 4ms, 内存消耗: 404KB, 提交时间: 2022-07-03
#include <algorithm>
#include <unordered_map>
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param operators int整型vector<vector<>>
* @return int整型vector
*/
vector<int> SLB(vector<vector<int> >& operators) {
int i,sz=operators.size();
vector<int> servers,res;
unordered_map<int,bool> occupied;
for(i=0;i<sz;i++)
{
switch(operators[i][0])
{
case 1:
add(servers,occupied,operators[i][1]);
break;
case 2:
remove(servers,occupied,operators[i][1]);
break;
case 3:
res.push_back(select(servers,occupied));
break;
case 4:
release(servers,occupied,operators[i][1]);
break;
default:
break;
}
}
return res;
}
private:
bool add(vector<int>& servers,
unordered_map<int,bool>& occupied,int id)
{
bool res=(find(servers.begin(),
servers.end(),id)==servers.end());
if(res)
servers.push_back(id);
return res;
}
bool remove(vector<int>& servers,
unordered_map<int,bool>& occupied,int id)
{
vector<int>::iterator vit;
bool res=((vit=find(servers.begin(),
servers.end(),id))!=servers.end());
unordered_map<int,bool>::iterator mit;
if(res)
{
servers.erase(vit);
if((mit=occupied.find(id))!=occupied.end())
mit->second=false;
}
return res;
}
int select(vector<int>& servers,unordered_map<int,bool>& occupied)
{
int i,sz=servers.size(),res=sz;
bool found=false;
unordered_map<int,bool>::iterator it;
for(i=0;(!found)&&(i<sz);i++)
{
found=(((it=occupied.find(servers[i]))==occupied.end())||
(!(it->second)));
if(found)
{
if(it!=occupied.end())
it->second=true;
else
occupied.insert({servers[i],true});
res=servers[i];
}
}
return res;
}
bool release(vector<int>& servers,
unordered_map<int,bool>& occupied,int id)
{
bool res=(find(servers.begin(),servers.end(),id)!=servers.end());
unordered_map<int,bool>::iterator it;
if(res)
{
if((it=occupied.find(id))!=occupied.end())
it->second=false;
}
return res;
}
};