系列目录
88.合并两个有序数组
52.螺旋数组
567.字符串的排列
643.子数组最大平均数
150.逆波兰表达式
61.旋转链表
160.相交链表
83.删除排序链表中的重复元素
389.找不同
1491.去掉最低工资和最高工资后的工资平均值
896.单调序列
206.反转链表
92.反转链表II
141.环形链表
142.环型链表
目录
- 系列目录
- 389.找不同
- 哈希表
389.找不同
🌟数组+哈希表/计数法
原题链接
方法一 哈希表
class Solution {
public:
char findTheDifference(string s, string t) {
vector<int> table(26, 0);
for (auto& ch: s)
table[ch - 'a'] ++;
for (auto& ch: t) {
table[ch - 'a'] --;
if (table[ch - 'a'] < 0)
return ch;
}
// 这里return -1;也是可以的
// 字符串相关的题的错误指示符用——' '——较好
// 也就是return ' ';
return ' ';
}
};
哈希表
简单介绍
一、种类：
1、存储结构：开放寻址法(更推荐)和拉链法
2、字符串哈希方式
二、主要作用：
将一个较大的空间或值域(通过一定的对应法则)映射到比较小的空间或值域
[ − 1 0 9 , 1 0 9 ] − > [ 1 0 5 , 0 ) [-10^9, 10^9] \quad->\quad[10^5, 0) [−109,109]−>[105,0)
三、一般的实现方式：
1、通过一个哈希函数h(x)映射
a. h(x)常用写法
对x取模运算，模上数组的长度N
h(x) = x mod N(N一般取成尽可能远离2的整数次幂的质数)
// 寻找合适长度 N的方法
// 循环找到大于10w(1e5)的第一个整数
int main() {
// 无上约束条件
for (int i = 100000;; i ++) {
bool flag = true;
for (int j = 2; j * j <= i; j ++)
if (i % j == 0) {
flag = false;
break;
}
if (flag) {
cout << i << endl;
break;
}
return 0;
}
}
b. 哈希碰撞(哈希冲突)
eg. h(5) = 2; h(10) = 2;
用拉链法处理哈希冲突
拉链法：开一个一维数组存储哈希值，并辅助一个单链表；
一起来看一道例题吧～
AcWing.840 模拟散列表
维护一个集合，支持如下几种操作：
I x，插入一个整数 x；
Q x，询问整数 x 是否在集合中出现过；
现在要进行 N 次操作，对于每个询问操作输出对应的结果
输入格式
第一行包含整数 N，表示操作数量
接下来 N 行，每行包含一个操作指令，操作指令为 I x，Q x 中的一种
输出格式
对于每个询问指令 Q x，输出一个询问结果，如果 x 在集合中出现过，则输出 Yes，否则输出 No
每个结果占一行
数据范围
1 ≤ N ≤ 105
−109 ≤ x ≤ 109
输入样例：
5
I 1
I 2
I 3
Q 2
Q 5
输出样例：
Yes
No
#include <bits/stdc++.h>
using namespace std;
// 通过上述方法或观察法
const int N = 100003;
// e[] 表示当前节点的值；ne[] 表示下一个节点的地址
// idx 表示当前用到哪个位置
int h[N], e[N], ne[N], idx;
// 插入x
void add(int x)
{
// 构造一个哈希函数，将x映射到[0，1e5)这个区间里
// 为什么这么定义 k——见注解
int k = (x % N + N) % N;
e[idx] = x;
ne[idx] = h[k];
h[k] = idx ++;
}
// 查询x是否存在，返回一个布尔类型
bool contain(int x)
{
int k = (x % N + N) % N;
for (int i = h[k]; i != -1; i = ne[i])
if (e[i] == x)
return true;
// 这里略写 else
return false;
}
// 拉链法
int main()
{
int n;
scanf("%d", &n);
// 空指针一般用-1表示——将所有的槽清空
memset(h, -1, sizeof h);
while (n --) {
char op[2];
int x;
// 若是用scanf的读入方式,尽量读入字符串;
// scanf会自动过滤掉字符串中的回车、空格、制表符等
scanf("%s%d", op, &x);
// 指针和整数比较出错；(禁止指针和整数进行比较)
// * 表示op是一个指向char类型的指针(变量)
if (*op == 'I') {
add(x);
} else {
if (contain(x))
puts("Yes");
else
puts("No");
}
}
return 0;
}
注解：
(x % N + N) / N
- C++中的模运算
- 若x为负，则余数(运算结果)为负
- 若x为证，则余数为正
+N的目的- 将余数(可能为负的)变为正数
memset(h, -1, sizeof h); // 空指针一般用-1表示——将所有的槽清空
初始化
scanf("%s%d", op, &x)
若使用scanf读入方式，应尽量读入字符串
读入字符串，scanf会自动过滤掉空格、回车、制表符等，降低出错的概率；
一般不用scanf读入字符
char *op
a.如果不加星号*
会报错：指针和整数比较出错；(禁止指针和整数进行比较)
b.这里的*+指针(字符串)表示:(指针)op是一个指向char类型的指针变量
四、基本操作(创建，销毁，增删改 查——创销增删查)
添加——void add(int x)
删除——remove(int x)
构造一个布尔类型的函数，在h(x)上打上标记，从逻辑上删除x(物理上并没有删除)
查找——bool contain(int x)
a.找到h(x)所在的槽
b.遍历这个槽存的值，以及对应的单链表，比较值是否相同，判断是否存在x
方法二 求和
class Solution {
public:
char findTheDifference(string s, string t) {
// accumulate of ..
int as = 0, at = 0;
for (auto ch: s)
as += ch;
for (auto ch: t)
at += ch;
return at - as;
}
};
异或(XOR)运算
异或运算对任何给定的数字x 的性质，即x ^ x = 0且x ^ 0 = x
LaTeX中，
\oplus表示A和B的异或
\bigoplus通常用于表示多个元素的异或
x ⊕ x = 0 x ⊕ 0 = x x\oplus x = 0\\x\oplus0=x x⊕x=0x⊕0=x
如果对两个相同的字符串进行异或，结果将是0；
如果再对结果和第三个字符串(即那个不同的字符)进行异或，结果将是那个不同的字符
此方法只适用于找出两个字符串之间的一个差异字符
方法三 异或运算
// 类似方法二
class Solution {
public:
char findTheDifference(string s, string t) {
// 声明一个char变量，用来存最后的结果
char res = 0;
for (auto ch: s)
res ^= ch;
for (auto ch: t)
res ^= ch;
return res;
}
};
