本文主要是介绍(Nowcoder) J LRU management （静态链表），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门
题意读懂了，感觉这就是个大模拟，但是直接模拟复杂度太大，所以我们要用链表指针搞一搞。不知道是不是我写的实在太挫，还是卡常，一直狂T，哭了。
划重点，加上这个才过。设置哈希桶大小，队友加了才过，估了，才知道这玩也，相见恨晚，还是太菜了呀。
rk.rehash(500005);
a.rehash(500005);
#include<bits/stdc++.h>
#define il inline
#define pb push_back
#define ms(_data,v) memset(_data,v,sizeof(_data))
#define sc(n) scanf("%d",&n)
#define SC(n,m) scanf("%d %d",&n,&m)
#define SZ(a) int((a).size())
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define drep(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const double pi=acos(-1.0);
const double eps=1e-9;
const int maxn=1e6+5;
int T,q,m;
struct node{int pre,nxt;int val;
};
unordered_map<int,node> a;
unordered_map<string,int> rk;
char alls[maxn][20];
int allop[maxn],allv[maxn];
inline int read(){char ch = getchar(); int x = 0, f = 1;while(ch < '0' || ch > '9') {if(ch == '-') f = -1;ch = getchar();} while('0' <= ch && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();} return x * f;
}
int main(){T = read();rk.rehash(500005);a.rehash(500005);while(T--){q = read();m = read();int op,s,v,nlen=0;int fa=-1,last;a.clear(),rk.clear();rep(i,1,q){allop[i] = read();scanf(" %s",alls[i]);allv[i] = read();}int cnt=0;rep(i,1,q){if(rk.count(alls[i])==0) rk[alls[i]]=++cnt;}rep(i,1,q){op=allop[i],s=rk[alls[i]],v=allv[i];if(op==0){ //addif(nlen==0){a[fa].nxt=s;a[s].pre=fa,a[s].val=v;last=s,nlen++;printf("%d\n",v);}else{if(a.count(s)==0 || a[s].val==inf){ //不存在sa[last].nxt=s,a[s].pre=last;a[s].val=v,last=s,nlen++;printf("%d\n",v);if(nlen>m){ //删除头部if(m==1){int fato=a[fa].nxt;a[fato].val=inf;a[fato].pre=0,a[fato].nxt=0;a[fa].nxt=s,a[s].pre=fa;last=s;}else{int fato=a[fa].nxt;a[fato].val=inf;int to=a[fato].nxt;a[to].pre=fa,a[fa].nxt=to;a[fato].pre=0,a[fato].nxt=0;}nlen--;}}else{//存在sprintf("%d\n",a[s].val);if(s==last) continue;int spre=a[s].pre,sto=a[s].nxt;a[sto].pre=spre,a[spre].nxt=sto;a[last].nxt=s;a[s].pre=last;last=s;}}}else{ //queryif(a.count(s)==0 || a[s].val==inf){puts("Invalid");}else{if(v==0) printf("%d\n",a[s].val);if(v==-1){if(a[s].pre==fa) puts("Invalid");else printf("%d\n",a[a[s].pre].val);}if(v==1){if(s==last) puts("Invalid");else printf("%d\n",a[a[s].nxt].val);}}}}}return 0;
}
这篇关于(Nowcoder) J LRU management （静态链表）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
