PAT甲级 散列题_C++题解

散列

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;
}

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 或 -1
  • fill(first, last, value ); 在<algorithm>中,可将 first-last 范围内填充为 value 值
  • set.find (value); 在集合中查找 value 值,找到返回 iterator,否则返回 set::end.
上一篇:解决Cygwin中vim的backspace不能正常使用(转)


下一篇:[No0000132]正确使用密码加盐散列[译]