SP4. 某音一致性哈希
描述
示例1
输入:
2,999
输出:
1
C++ 解法, 执行用时: 3ms, 内存消耗: 404KB, 提交时间: 2022-07-21
class Solution {
public:
struct computer
{
int start;
int end;
int index;
int range() const
{
return end-start;
}
};
struct cmp
{
bool operator()(const computer& a,const computer& b)
{
return a.range()==b.range()?a.index<b.index:a.range()>b.range();
}
};
int consistentHashing(int n, int ID) {
set<computer,cmp>s;
computer c;
c.start=0;
c.end=799;
c.index=1;
s.insert(c);
int ind=ID%800;
int res=1;
for(int i=2;i<=n;i++)
{
auto c=*s.begin();
s.erase(s.begin());
computer ne;
ne.start=(c.start+c.end)/2+1;
ne.end=c.end;
ne.index=i;
c.end=(c.start+c.end)/2;
s.insert(c);
s.insert(ne);
if(ind>=ne.start&&ind<=ne.end)
res=ne.index;
else if(ind>=c.start&&ind<=c.end)
res=c.index;
}
return res;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 412KB, 提交时间: 2022-07-21
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int整型
* @param ID int整型
* @return int整型
*/
int consistentHashing(int n, int ID) {
// write code here
ID%=800;
int ptr[n],len[n];
ptr[0]=0;
len[0]=800;
for(int i=1;i<n;++i){
int maxx=0,p;
for(int j=0;j<i;++j)
if(len[j]>maxx) maxx=len[p=j];
len[p]=len[p]-len[p]/2;
len[i]=maxx/2;
ptr[i]=ptr[p]+len[p];
}
for(int i=0;i<n;++i)
if(ID>=ptr[i]&&ID<ptr[i]+len[i])
return i+1;
return 1;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 420KB, 提交时间: 2022-07-12
struct computer
{
int id_start;
int id_end;
int index;
int range() const
{
return id_end - id_start;
}
};
struct compare_obj
{
// 先根据区间大小进行排序，如果区间大小一致，则根据机器编号排序
bool operator()(const computer &a, const computer &b)
{
if (a.range() != b.range())
{
return a.range() > b.range();
}
return a.index < b.index;
}
};
class Solution {
public:
int consistentHashing(int n, int ID)
{
std::set<computer, compare_obj> s;
computer c;
c.id_start = 0;
c.id_end = 799;
c.index = 1;
s.insert(c);
int index = ID % 800;
int ans = 1;
for (int i = 2; i <= n; ++i)
{
auto c = *s.begin();
s.erase(s.begin());
computer new_computer;
new_computer.id_start = (c.id_start + c.id_end) / 2 + 1;
new_computer.id_end = c.id_end;
new_computer.index = i;
c.id_end = (c.id_start + c.id_end) / 2;
s.insert(c);
s.insert(new_computer);
if (index >= new_computer.id_start && index <= new_computer.id_end)
{
ans = new_computer.index;
}
else if (index >= c.id_start && index <= c.id_end)
{
ans = c.index;
}
}
return ans;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 424KB, 提交时间: 2022-07-24
struct machine
{
int start;
int end;
int index;
int range() const{
return end - start;
}
};
struct compare_obj
{
// 先根据区间大小进行排序，如果区间大小一致，则根据机器编号排序
bool operator()(const machine &a, const machine &b) const
{
if (a.range() != b.range())
{
return a.range() > b.range();
}
return a.index < b.index;
}
};
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int整型
* @param ID int整型
* @return int整型
*/
int consistentHashing(int n, int ID) {
// write code here
// 集合初始化只有一个机器——范围为[0,799]，机器id为1，
std::set<machine, compare_obj> machineSet;
machine first;
first.start = 0;
first.end = 799;
first.index = 1;
machineSet.insert(first);
// h
int index = ID % 800;
int ans = 1;
for (int i = 2; i <= n; i++)
{
//新增机器：每次新增机器的时候都从集合的第一个元素取出范围进行划分，然后创建新的机器
auto c = *machineSet.begin();
machineSet.erase(machineSet.begin());
machine new_machine;
new_machine.start = (c.start + c.end) / 2 + 1;
new_machine.end = c.end;
new_machine.index = i;
c.end = (c.start + c.end) / 2;
// 将创建新的机器和原机器一起放入machineSet中，machineSet会自动排序
machineSet.insert(c);
machineSet.insert(new_machine);
}
for(set<machine>::iterator it = machineSet.begin(); it!=machineSet.end();it++)
{
if ((*it).start <= index && (*it).end >= index)
{
ans = (*it).index;
return ans;
}
}
return ans;
}
};
C++ 解法, 执行用时: 4ms, 内存消耗: 408KB, 提交时间: 2022-07-12
// struct computer
// {
// int id_start;
// int id_end;
// int index;
// int range()
// {
// return id_end - id_start;
// }
// computer(int start, int end, int _index): id_start(start), id_end(end), index(_index){}
// };
// class Solution {
// private:
// static bool cmp(computer &a, computer &b)
// {
// if (a.range() != b.range())
// {
// return a.range() > b.range();
// }
// return a.index < b.index;
// }
// public:
// /**
// * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
// *
// *
// * @param n int整型
// * @param ID int整型
// * @return int整型
// */
// int consistentHashing(int n, int ID) {
// // write code here
// std::set<computer, decltype(cmp)> s;
// computer c(0, 799, 1);
// s.insert(c);
// int index = ID % 800;
// int ans = 1;
// for (int i = 2; i <= n; ++i)
// {
// auto c = *s.begin();
// s.erase(s.begin());
// computer new_computer((c.id_start + c.id_end) / 2 + 1, c.id_end, i);
// c.id_end = (c.id_start + c.id_end) / 2;
// s.insert(c);
// s.insert(new_computer);
// if (index >= new_computer.id_start && index <= new_computer.id_end)
// {
// ans = new_computer.index;
// }
// else if (index >= c.id_start && index <= c.id_end)
// {
// ans = c.index;
// }
// }
// return ans;
// }
// };
struct computer
{
int id_start;
int id_end;
int index;
int range() const
{
return id_end - id_start;
}
};
struct compare_obj
{
// 先根据区间大小进行排序，如果区间大小一致，则根据机器编号排序
bool operator()(const computer &a, const computer &b)
{
if (a.range() != b.range())
{
return a.range() > b.range();
}
return a.index < b.index;
}
};
class Solution {
public:
int consistentHashing(int n, int ID)
{
std::set<computer, compare_obj> s;
computer c;
c.id_start = 0;
c.id_end = 799;
c.index = 1;
s.insert(c);
int index = ID % 800;
int ans = 1;
for (int i = 2; i <= n; ++i)
{
auto c = *s.begin();
s.erase(s.begin());
computer new_computer;
new_computer.id_start = (c.id_start + c.id_end) / 2 + 1;
new_computer.id_end = c.id_end;
new_computer.index = i;
c.id_end = (c.id_start + c.id_end) / 2;
s.insert(c);
s.insert(new_computer);
if (index >= new_computer.id_start && index <= new_computer.id_end)
{
ans = new_computer.index;
}
else if (index >= c.id_start && index <= c.id_end)
{
ans = c.index;
}
}
return ans;
}
};