本文主要是介绍LeetCode：经典题之389 题解与延伸，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
系列目录
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)
{int k = (x % N + N) % N; // 构造一个哈希函数，将x映射到[0，1e5)这个区间里e[idx] = x;ne[idx] = h[k];h[k] = idx ++;
}// 查询x是否存在
bool contain(int x) // 查询操作是一个布尔类型的操作(返回true表示存在)
{ // 见注释int k = (x % N + N) % N;for (int i = h[k]; i != -1; i = ne[i])if (e[i] == x)return true;return false; // 否则返回false
}// 拉链法
int main()
{int n;scanf("%d", &n);memset(h, -1, sizeof h); // 空指针一般用-1表示——将所有的槽清空while (n --) {char op[2]; // 若是用scanf的读入方式,尽量读入字符串scanf会自动过滤掉字符串中的回车、空格、制表符等int x; // 降低出错的概率(一般不用scanf读入字符)scanf("%s%d", op, &x);if (*op == 'I') add(x); // 指针和整数比较出错；(禁止指针和整数进行比较)else { // 这里的*+指针(字符串)表示：(指针)op是一个指向char类型的指针变量if (contain(x)) puts("Yes");else puts("No"); }// else_end}// while_endreturn 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;}
};
这篇关于LeetCode：经典题之389 题解与延伸的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
