今日学习记录
1. 设计路由器leetcode.3508
关键词：设计
问题分析：
- 这个题有点难,以下是几个难点分析
- 怎么去重三个值
- 题目中的这个装时间数组的队列似乎无法正常工作(如果直接使用队列)
核心思路
- 首先就是这个三个数据同时存在的去重,我们都知道去重直接使用 set 就行,可是对于这个三个值的对象 tuple,set 是无法获取这个对象的哈希值,如果不使用的话就要一个个存储然后检查是否相同,巨耗时间必超时,之前学过利用 long 的双整数二进制大小来捆绑两个值进行储存,但是这里是三个值也用不了,所以要快速查找去重,只能重写哈希值计算函数
c++ 17,最最通用平衡最好
使用了0x9e3779b9这个约等于黄金比例数(32 位),目的是增加随机性和分散性
struct TupleHash{
template<typename T>
static void hash_combine(size_t& seed,const T& v){
seed ^= hash<T>{}(v)+0x9e3779b9+(seed<<6)+(seed>>2);
}
size_t operator()(const tuple<int,int,int>&t)const{
auto &[a,b,c] = t;
size_t seed = 0;
hash_combine(seed,a);
hash_combine(seed,b);
hash_combine(seed,c);
return seed;
}
};c++11 以上除了 auto 不能用之外没区别
追求极致性能
使用的是FNV这个非加密哈希函数 核心思想是:使用质数乘法来混合每个字节 在 32 位中:
- 初始值为 2166136261U
- 质数: 16777619U 在 64 位数中:
- 初始值为 14695981039346656037ULL
- 质数: 1099511628211ULL
struct TupleHash{
size_t operator()(const tuple<int,int,int>&t)const{
const auto &a = get<0>(t);
const auto &b = get<1>(t);
const auto &c = get<2>(t);
size_t seed = 2166136261U;
seed = (seed^a)*16777619U;
seed = (seed^b)*16777619U;
seed = (seed^c)*16777619U;
return seed;
}
};追求极致质量
使用 splitmix64 来进行操作,性能上虽然有损失,但是哈希冲突概率极低
struct EnhancedTupleSplitMix64Hash {
//定义黄金比例常数为初始种子
static constexpr uint64_t prime1 = 0x9e3779b97f4a7c15ULL; // 64位黄金比例
//混合质数
static constexpr uint64_t prime2 = 0xbf58476d1ce4e5b9ULL; // SplitMix64 常数1
static constexpr uint64_t prime3 = 0x94d049bb133111ebULL; // SplitMix64 常数2
static uint64_t splitmix64(uint64_t x) {
x = (x ^ (x >> 30)) * prime2;
x = (x ^ (x >> 27)) * prime3;
return x ^ (x >> 31);
}
static uint64_t hash_int(int value) {
return splitmix64(static_cast<uint64_t>(value) ^ prime1);
}
size_t operator()(const std::tuple<int, int, int>& t) const {
auto& [a, b, c] = t;
uint64_t h = hash_int(a);
h = (h ^ (h >> 27)) * prime3 + hash_int(b);
h = (h ^ (h >> 27)) * prime3 + hash_int(c);
// 最终混合
h = splitmix64(h);
return static_cast<size_t>(h);
}
};- 还有就是这个存储时间的数组,因为题目本质上是需要(先进先出)队列实现的,但是要查询,还要存储一个时间的数组,用队列明显是实现不了的,所以使用数组来模拟队列的出队的操作,首先就是查询,就是 map,key 为地址,value 为时间的数组,但是怎么模拟队列呢,我们要定义一个常数指向队头,用来模拟出队的操作,每次出队的时候这个队头向右移,那么进一步优化,我们把这个值与时间数组绑在一起,就有了 pair<时间数组,队头>
**最终代码：
struct TupleHash{
template<typename T>
static void hash_combine(size_t& seed,const T& v){
seed ^= hash<T>{}(v)+0x9e3779b9+(seed<<6)+(seed>>2);
}
size_t operator()(const tuple<int,int,int>&t)const{
auto &[a,b,c] = t;
size_t seed = 0;
hash_combine(seed,a);
hash_combine(seed,b);
hash_combine(seed,c);
return seed;
}
};
class Router {
int len = 0;//限制最大数量
queue<tuple<int,int,int>> q;
unordered_set<tuple<int,int,int>,TupleHash> st;
//地址值,地址值对应的所有时间
unordered_map<int,pair<vector<int>,int>> mp;
public:
//此处直接设置大小变量就行
//初见为队列
Router(int memoryLimit) {
len = memoryLimit;
}
//用数组来装
//但是有一个在队列中查找重复的操作,无论是那种队列结构都不适合查找
//map要来储存所有的数据,不能用于单个去重
//使用set的去重来检查是否重复
bool addPacket(int source, int destination, int timestamp) {
auto pak = tuple(source,destination,timestamp);
if(!st.insert(pak).second) return false;
q.push(pak);
if(q.size()>len) forwardPacket();
mp[destination].first.push_back(timestamp);
return true;
}
//要出队的话,有很多东西要注意
vector<int> forwardPacket() {
if(q.empty()) return {};
auto it = q.front();
q.pop();
st.erase(it);
auto [source,destination,timestamp] = it;
mp[destination].second++;
return {source,destination,timestamp};
}
//这里要查找时间范围的上界和下界,使用两个二分查找
//但是队列中的时间数据要单调,单调队列吗
//在查找时间的前提是地址相同,所以以地址为主头
int getCount(int destination, int startTime, int endTime) {
auto &[arr,head] = mp[destination];
auto left = ranges::lower_bound(arr.begin()+head,arr.end(),startTime);
auto right = ranges::upper_bound(arr.begin()+head,arr.end(),endTime);
return right-left;
}
};学到的点：
- 黄金比例数
- FNV
- splitmix64