石家庄教育平台网站建设,青海建设工程信息网站,17网站一起做网店普宁池尾,杭州公司注册虚拟地址模拟散列表
维护一个集合#xff0c;支持如下几种操作#xff1a; 1.“I x”#xff0c;插入一个数x 2.“Q x”#xff0c;询问数x是否在集合中出现过 现在要进行N次操作#xff0c;对于每个询问操作输出对应的结果
输入格式
第一行包含整数N#xff0c;表示操作数量 …模拟散列表
维护一个集合支持如下几种操作 1.“I x”插入一个数x 2.“Q x”询问数x是否在集合中出现过 现在要进行N次操作对于每个询问操作输出对应的结果
输入格式
第一行包含整数N表示操作数量 接下来N行每行包含一个操作指令操作指令为I xQ x中的一种
输出格式
对于每个询问指令Q x输出一个询问结果如果x在集合中出现过则输出Yes否则输出No 每个结果占一行
数据范围 1 ≤ N ≤ 1 0 5 1\le N\le 10^5 1≤N≤105 − 1 0 9 ≤ x ≤ 1 0 9 -10^9\le x\le 10^9 −109≤x≤109
输入样例 5 I 1 I 2 Q 2 Q 5 输出样例 Yes No 问题分析 哈希表 { 存储结构 { 开放寻址法 拉链法 字符串哈希方式 哈希表\left\{ \begin{aligned} 存储结构 \left\{ \begin{aligned} 开放寻址法\\ 拉链法 \end{aligned} \right. \\ \\ 字符串哈希方式 \end{aligned} \right. 哈希表⎩ ⎨ ⎧存储结构{开放寻址法拉链法字符串哈希方式
AC代码
法一拉链法
#includeiostream
#includecstring
using namespace std;const int N 1e5 3;int h[N], e[N], ne[N], idx;void insert(int x) {// keep the remainder positive int k (x % N N) % N;e[idx] x;ne[idx] h[k];h[k] idx;
}bool find(int x) {int k (x % N N) % N;for(int i h[k]; i ! -1; i ne[i])if(e[i] x) return true;return false;
}int main() {int n;scanf(%d, n);memset(h, -1, sizeof(h));while(n--) {char op[2];int x;scanf(%s%d, op, x);if(op[0] I) insert(x);else {if(find(x)) puts(Yes);else puts(No);}}return 0;
}法二开放寻址法推荐
#includeiostream
#includecstring
using namespace std;const int N 2e5 3, null 0x3f3f3f3f;int h[N];int find(int x) {int k (x % N N) % N;while(h[k] ! null h[k] ! x) {k;if(k N) k 0; }return k;
}int main() {int n;scanf(%d, n);memset(h, 0x3f, sizeof(h));while(n--) {char op[2];int x;scanf(%s%d, op, x);int k find(x);if(op[0] I) h[k] x;else {if(h[k] ! null) puts(Yes);else puts(No);}}return 0;
}
