散列
PAT (Advanced Level) Practice 散列题
目录
- 《算法笔记》 重点摘要
- 1002 A+B for Polynomials (25)
- 1009 Product of Polynomials (25)
- 1084 Broken Keyboard (20)
- 1092 To Buy or Not to Buy (20)
- 1116 Come on! Let’s C (20)
- 1121 Damn Single (25)
《算法笔记》 4.2 散列 重点摘要
1. 散列
将元素通过一个函数转换为整数，使得该整数可以尽量唯一地代表这个元素。
2. 散列函数
一般直接用STL中的 map 或 unordered_map，除非必须模拟这些方法或对算法效率要求较高，否则不需要自己实现解决冲突的方法
(1) 直接定址法
- 恒等变换：将 key(输入的数) 作为数组下标 ⭐——最常见最实用
- 线性变换：H(key) = a * key + b
(2) 平方取中法 —— 很少用
取 key 平方的中间若干位作为 hash 值
(3) 除留余数法
H(key) = key % mod (表长Tsize >= mod，否则会越界)
- 开放定址法
- 线性探查法：H(key), H(key)+1, …
- 平方探查法：H(key), H(key)+1^2, H(key)-1^2, H(key)+2^2, H(key)-2^2, …
- if (H(key) + k^2 > Tsize) H(key)+k^2 % Tsize
- if (H(key) – k^2 < 0) ((H(key) – k^2) % Tsize + Tsize) % Tsize （可只正向探查避免此种麻烦）
- 链地址法
3. 字符串 hash
将一个字符串S映射为一个整数，使得整数可以尽可能唯一地代表字符串S
(1) 字符串由大写字母 A-Z 组成
将大写字母 A-Z 视为 0-25，即对应到了26进制中，再转换为10进制。转换为的整数最大为26^len-1，len为字符串长度
int hashFunc(char S[], int len){
int id = 0;
for (int i = 0; i < len; i++){
id = id * 26 + (S[i] - 'A');
}
return id;
}
(2) 字符串由大写字母 A-Z 和小写字母 a-z 组成
52进制转10进制问题
(3) 字符串由大写字母 A-Z，小写字母 a-z 和 数字 1-9 组成
- (1) 62进制转10进制问题
- (2) 若保证字符串末尾是确定个数的数字，可将前面英文字母部分转换为整数后将数字拼接上去
int hashFunc(char S[], int len){
int id = 0;
for (int i = 0; i < len - 1; i++){
id = id * 26 + (S[i] - 'A');
}
id = id * 10 + (S[len-1] - '0');
return id;
}
1002 A+B for Polynomials (25)
#include<iostream>
using namespace std;
int main()
{
int k, n, sum = 0;
double a, p[1001] = {0};
scanf("%d", &k);
for (int i = 0; i < k; i++){
scanf("%d%lf", &n, &a);
p[n] += a;
}
scanf("%d", &k);
for (int i = 0; i < k; i++){
scanf("%d%lf", &n, &a);
p[n] += a;
}
for (int i = 0; i < 1001; i++) if (p[i]) sum++;
printf("%d", sum);
for (int i = 1000; i >= 0; i--) if (p[i]) printf(" %d %.1f", i, p[i]);
return 0;
}
简化代码（参考柳婼小姐姐的代码）
- 和多项式可直接在输入时计算，不必分别存储两个多项式再相加。
- 输出格式控制可将空格放在内容前面输出，这样不论检查到哪里输出尾部都不会有多余空格，不需要把不为 0 的单独放到 map 里集中输出
- 简化前代码如下
#include<iostream>
#include<map>
using namespace std;
int main()
{
int k, n, sum = 0;
double a, p1[1002] = {0}, p2[1002] = {0}, p[1002] = {0};
scanf("%d", &k);
for (int i = 0; i < k; i++){
scanf("%d%lf", &n, &a);
p1[n] = a;
}
scanf("%d", &k);
for (int i = 0; i < k; i++){
scanf("%d%lf", &n, &a);
p2[n] = a;
}
for (int i = 0; i < 1002; i++) p[i] = p1[i] + p2[i];
map<int,double,greater<int>> p_map;
for (int i = 0; i < 1002; i++){
if (p[i]){
sum++;
p_map[i] = p[i];
}
}
printf("%d", sum);
for (auto it : p_map) printf(" %d %.1f", it.first, it.second);
return 0;
}
- 系数是小数，要用double，输入要用%lf，输出用%f
- map 默认按 key 升序排列，降序排列需传入 std:greater<>
1009 Product of Polynomials (25)
题目思路
- 先用两个数组分别将第一个多项式的指数和系数都接收进来，接收第二个时可以边接收边计算边保存结果。
- 结果记录在一个大数组中，结果数组的索引即为结果多项式的指数，内容为此幂次的系数
- 结果多项式有多少项需要遍历一次结果数组记录系数不为零的项数
- 注意：因为相乘后指数可能最大为2000，所以ans数组最大要开到2001
#include<cstdio>
double result[2001] = {0};
int main()
{
int k1, k2, exp2;
double coe2;
scanf("%d", &k1);
int *exp1 = new int[k1];
double *coe1 = new double[k1];
for (int i = 0; i < k1; i++) scanf("%d%lf", exp1+i, coe1+i);
scanf("%d", &k2);
for (int i = 0; i < k2; i++){
scanf("%d%lf", &exp2, &coe2);
for (int j = 0; j < k1; j++)
result[exp1[j] + exp2] += coe1[j] * coe2;
}
int k = 0;
for (int i = 0; i < 2001; i++)
if (result[i] != 0) k++;
printf("%d",k);
for (int i = 2000; i >= 0; i--)
if (result[i] != 0)
printf(" %d %.1f", i, result[i]);
}
1084 Broken Keyboard (20)
参考思路（参考柳婼小姐姐的代码）
- 遍历原字符串，在打印的字符串中未出现的就是坏掉的
- 只能输出一次，用集合记录输出过的。
#include<iostream>
#include<set>
using namespace std;
int main()
{
string a, b;
cin >> a >> b;
set<char> printed;
for (int i = 0; i < a.length(); i++){
if (b.find(a[i]) == b.npos && printed.find(toupper(a[i])) == printed.end()){
printf("%c", toupper(a[i]));
printed.insert(toupper(a[i]));
}
}
return 0;
}
简化代码
- string 也可以用 find 查找字符，且由于每次插入前都检查是否已经出现，不会重复，可以用 string 替代 set 存储坏掉的字符
#include<iostream>
using namespace std;
int main()
{
string a, b, broken;
cin >> a >> b;
for (int i = 0; i < a.length(); i++)
if (b.find(a[i]) == b.npos && broken.find(toupper(a[i])) == broken.npos)
broken += toupper(a[i]);
cout << broken;
return 0;
}
题目思路
- 字母出现过即意味着没有坏掉，若之前在 broken 集合中要 erase 掉
- 遇到两字符串不匹配要检查是否在出现过的字母里，若不在就加到 broken 集合中
- 输出时要按顺序且只能输出一次，用集合记录输出过的，遍历字符串，若在 broken 中且没有输出过就输出。
#include<iostream>
#include<set>
using namespace std;
int main()
{
string a, b;
cin >> a >> b;
int p = 0;
set<char> broken, okay, printed;
for (int i = 0; i < a.length(); i++){
if (a[i] == b[p]){
p++;
okay.insert(toupper(a[i]));
if (broken.find(toupper(a[i])) != broken.end()) broken.erase(toupper(a[i]));
}
else if (okay.find(toupper(a[i])) == okay.end()) broken.insert(toupper(a[i]));
}
for (int i = 0; i < a.length(); i++){
if (broken.find(toupper(a[i])) != broken.end() && printed.find(toupper(a[i])) == printed.end()){
printed.insert(toupper(a[i]));
printf("%c", toupper(a[i]));
}
}
return 0;
}
1092 To Buy or Not to Buy (20)
#include<iostream>
#include<map>
using namespace std;
int main()
{
map<char,int> shop;
string s, e;
cin >> s >> e;
for (int i = 0; i < s.length(); i++) shop[s[i]]++;
int miss = 0;
for (int i = 0; i < e.length(); i++){
if (shop.find(e[i]) != shop.end() && shop[e[i]] > 0) shop[e[i]]--;
else miss++;
}
if (!miss) printf("Yes %d", s.length()-e.length());
else printf("No %d", miss);
return 0;
}
- 如果可以买，说明店主的珠子覆盖了想买的，则店主珠子数 – 想买珠子数 即为多余的
- 简化前代码如下：去除了想买的珠子后剩下的店主珠子和，不必要再算一遍
#include<iostream>
#include<map>
using namespace std;
int main()
{
map<char,int> shop;
string s, e;
cin >> s >> e;
for (int i = 0; i < s.length(); i++) shop[s[i]]++;
int extra = 0, miss = 0;
for (int i = 0; i < e.length(); i++){
if (shop.find(e[i]) != shop.end() && shop[e[i]] > 0) shop[e[i]]--;
else miss++;
}
if (!miss){
for (auto it = shop.begin(); it != shop.end(); it++) extra += it->second;
printf("Yes %d", extra);
}
else printf("No %d", miss);
return 0;
}
1116 Come on! Let’s C (20)
题目思路
- 按顺序接收 ranklist 输入，将 id 和名次放入 map，由于只需要查询 id 对应的名次不需要排序，用 unordered_map 更快
- 每次接收新的查询 id 先到 map 中查找是否在 ranklist 中，再到 set 中查找是否已经查询过。
- 若未查询过，放入 set，再按照对应名次输出奖品。
- 注意：不在 ranklist 输出优先级更高，若一个不在 ranklist 中的 id 之前被检查过，应当输出 Are you kidding? 而非 Checked，所以先查 map 后查 set
#include<unordered_map>
#include<iostream>
#include<set>
using namespace std;
bool isPrime(int n){
if (n <= 1) return false;
for (int i = 2; i * i <= n; i++)
if (n % i == 0) return false;
return true;
}
int main()
{
int n, k, id;
scanf("%d", &n);
unordered_map<int,int> rank;
for (int i = 0; i < n; i++){
scanf("%d", &id);
rank.insert({id,i+1});
}
set<int> checked;
scanf("%d", &k);
for (int i = 0; i < k; i++){
scanf("%d", &id);
if (rank.find(id) == rank.end()) printf("%04d: Are you kidding?\n", id);
else {
if (checked.find(id) != checked.end()) printf("%04d: Checked\n", id);
else {
checked.insert(id);
if (rank[id] == 1) printf("%04d: Mystery Award\n", id);
else if (isPrime(rank[id])) printf("%04d: Minion\n", id);
else printf("%04d: Chocolate\n", id);
}
}
}
return 0;
}
map.insert({key,value})map 插入值可直接用 {} 括起来，省去写 pair 的麻烦
1121 Damn Single (25)
题目思路
- 开大数组记录每个人的伴侣编号
- 将受到邀请的客人全部放到一个 set 中，以便于后面查找一个客人的伴侣是否在场
- 遍历 guests 集合，couple 数组对应值为 -1（无伴侣） 或 伴侣不在场的压入 vector
- 有可能在场没有单身狗，要先检查 lonely 是否为空
- lonely 不为空则对 lonely 排序后集中输出
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
int couple[100000];
int main()
{
int n, m, a, b;
scanf("%d", &n);
fill(couple,couple+100000,-1);
for (int i = 0; i < n; i++){
scanf("%d%d", &a, &b);
couple[a] = b;
couple[b] = a;
}
scanf("%d", &m);
set<int> guests;
for (int i = 0; i < m; i++){
scanf("%d", &a);
guests.insert(a);
}
vector<int> lonely;
for (auto it = guests.begin(); it != guests.end(); it++)
if (couple[*it] < 0 || guests.find(couple[*it]) == guests.end()) lonely.push_back(*it);
if (lonely.empty()) printf("0\n");
else{
sort(lonely.begin(),lonely.end());
printf("%d\n%05d",lonely.size(), lonely[0]);
for (int i = 1; i < lonely.size(); i++) printf(" %05d",lonely[i]);
}
return 0;
}
memset(数组名, 值, sizeof(数组名);在<cstring>中，建议只用来赋 0 或 -1fill(first, last, value );在<algorithm>中，可将 first-last 范围内填充为 value 值set.find (value);在集合中查找 value 值，找到返回 iterator，否则返回set::end.
