【总结向】PAT甲级 哈希表 1048 1063 1078 1120 1137 1144 1145 1149

【总结向】PAT甲级 哈希表 20200518

本周值得关注的题目

• 1048找硬币：这题可以双指针去做，这里用哈希表提供另一种思路
• 1078模拟哈希表：平方寻址法
• 1145哈希表查找：1078的升级版，哈希表这样一个性质，查询不存在的数找到空位或命中该数，查询结束。

一、重点题目

1.1048 Find Coins
思路：
这题可以双指针去做，这里用哈希表提供另一种思路
维护一个哈希表，存之前看过的数，如果当前的数与之前看过的数之和=M，那么找到该数，若该数更小则更新

代🐎:

// 这题可以双指针去做，这里用哈希表提供另一种思路
// 维护一个哈希表，存之前看过的数，如果当前的数与之前看过的数之和=M，那么找到该数，若该数更小则更新
#include 
#include 
#include 
using namespace std;
int main()
{unordered_set<int> S;int n, m;cin >> n >> m;int x, y;int v1 = 1e9, v2 = 0;while(n --){   cin >> x;y = m - x;if(S.count(y)){S.insert(x);if(x > y) swap(x, y);if(x < v1) v1 = x, v2 = m - x;}else S.insert(x);}if(v1 == 1e9) cout << "No Solution" << endl;else cout << v1 << " " << v2 << endl;return 0;
}

3.1078 Hashing
思路：
模拟即可, 隐藏条件，二次探测基h是不变的，h+1，h+4，h+9都是相较h的，error才想出来

代🐎:

// 模拟即可, 隐藏条件，二次探测基h是不变的，h+1，h+4，h+9都是相较h的，error才想出来
#include 
#include 
using namespace std;int n, m;
unordered_set<int> S;bool is_prime(int x)
{if(x == 1) return false; // 质数特判，PAT有个判题点for(int i = 2; i * i <= x; i ++)if(x % i == 0) return false;return true;
}int get_key(int x)
{int key = x % m;for(int k = 0; k < m; k ++){int i = (key + k * k) % m;if(!S.count(i)) return i;}return -1;
}int main()
{cin >> m >> n;while(!is_prime(m)) m ++;for(int i = 0; i < n; i ++){int x;cin >> x;int t = get_key(x);if(t == -1) cout << "-";else{S.insert(t);cout << t;}if(i != n - 1) cout << " "; // PAT不能有行末空格}return 0;
}

7.1145 Hashing - Average Search Time
思路：
算查询时间：哈希表这样一个性质，查询不存在的数找到空位或命中该数，查询结束。

代🐎:

#include 
#include 
using namespace std;const int N = 10010;
int h[N];
int msize, n, m;bool is_prime(int x)
{if(x == 1) return false;for(int i = 2; i <= x / i; i ++)if(x % i == 0) return false;return true;
}int insert(int x)
{int key = x % msize;for(int k = 0; k < msize; k ++){int n =  (key + k * k) % msize;if(!h[n]) {h[n] = x;return n;}}return -1;
}int find_n(int x)
{int key = x % msize;for(int k = 0; k < msize; k ++){int i =  (key + k * k) % msize;if(!h[i] || h[i] == x) return k + 1; // 查询时不存在的数找到空位算查询结束}return -1;
}int main()
{cin >> msize >> n >> m;while(!is_prime(msize)) msize ++;while(n --){int x; cin >> x;int p = insert(x);if(p == -1) cout << x << " cannot be inserted." << endl;}int ans = 0;for(int i = 0; i < m; i ++){int x;cin >> x;int re = find_n(x);if(re == -1) re = msize + 1;ans += re;}printf("%.1f", (double)ans * 1.0 / m);return 0;
}

二、看一眼就可以的题们

2.1063 Set Similarity
思路：
正常求两个集合交集并集元素数目，O(m^2 * k)，显然时间复杂度超了，因此时间换空间，用哈希存
可以优化到O(mk)=2e7，因为求集合交集，外循环O(km)，内循环查询是否存在O(1)即可，因为哈希读入时存过了

代🐎:

// 正常求两个集合交集并集元素数目，O(m^2 * k)，显然时间复杂度超了，因此时间换空间，用哈希存
// 可以优化到O(m*k)=2e7，因为求集合交集，外循环O(k*m)，内循环查询是否存在O(1)即可，因为哈希读入时存过了
#include 
#include 
#include 
using namespace std;const int N = 52;
unordered_set<int> S[N];int main()
{int n, m, k;cin >> n;for(int i = 1; i <= n; i ++){cin >> m;while(m --){int v;scanf("%d", &v);S[i].insert(v);}}cin >> k;while(k --){int a, b, nc = 0, nt = 0;cin >> a >> b;for(auto i : S[a]){if(S[b].count(i)) nc++;}nt = S[a].size() + S[b].size() - nc;printf("%.1lf%%\n", (double)nc / nt * 100);}return 0;
}

4.1120 Friend Numbers
思路：
模拟一下就好啦，注意PAT是不允许有行末空格的，因此要设置一个isFirst变量控制一下输出格式。

代🐎:

// 这里模拟一下就好了
#include 
#include 
#include 
using namespace std;set<int> S;int main()
{int n;cin >> n;while(n --){   int k;cin >> k;int py = 0, kk = k;while(kk){py += kk % 10;kk /= 10; }S.insert(py);}cout << S.size() << endl;bool isFirst = true;for(auto i : S){if(isFirst) cout << i, isFirst = false;else cout << " " << i ;}return 0;
}

5.1137 Final Grading
思路：
模拟题，这题要排序所以结果找一个vector数组存，然后字符串需要映射到id放一个哈希表unordered_map因为会有重复的学生要哈希去映射。

代🐎:

#include 
#include 
#include 
#include 
#include 
#include using namespace std;struct Student
{string id;int gp, gm, gf, g;Student(): gp(-1), gm(-1), gf(-1), g(0) {}void cal(){if(gm > gf) g = round(gm * 0.4 + gf * 0.6); //分数应四舍五入else g = gf;}bool operator< (const Student &t) const{if(g != t.g) return g > t.g;return id < t.id;}
};unordered_map<string, Student> M;
vector<Student> re;int main()
{int p, m, n;cin >> p >> m >> n;string s;int sc;while(p --){cin >> s >> sc;M[s].id = s;M[s].gp = sc;}while(m --){cin >> s >> sc;M[s].id = s;M[s].gm = sc;}while(n --){cin >> s >> sc;M[s].id = s;M[s].gf = sc;}for(auto item : M){auto s = item.second;s.cal();if(s.g >= 60 && s.gp >= 200) re.push_back(s);}sort(re.begin(), re.end());for(auto i : re){cout << i.id << " " << i.gp << " " << i.gm << " " << i.gf << " " << i.g << endl;}return 0;}

6.1144 The Missing Number
思路：大水题！
代🐎:

// ...
#include 
#include 
using namespace std;unordered_set<int> S;int main()
{int n;cin >> n;while(n --){int k;cin >> k;S.insert(k);}int i;for(i = 1; i < 1e6; i ++){if(!S.count(i)) break;}cout << i;return 0;
}

8.1149 Dangerous Goods Packaging
思路：
多次查询，空间换时间，哈希表。外循环：每一张清单，内循环：遍历全部的危险物品，看是否存在即可
时间复杂度O(mn) = 1e6

代🐎:

// 多次查询，空间换时间，哈希表。外循环：每一张清单，内循环：遍历全部的危险物品，看是否存在即可
// 时间复杂度O(mn) = 1e6
#include 
#include 
using namespace std;const int N = 10010;
int a[N], b[N];
unordered_set<int> S;int main()
{int n, m, k;cin >> n >> m;for(int i = 0; i < n; i ++){cin >> a[i] >> b[i];}while(m --){S.clear();cin >> k;while(k --){int v;cin >> v;S.insert(v);}bool re = true;for(int i = 0; i < n; i ++){if(S.count(a[i]) && S.count(b[i])){re = false;break;}}if(re) cout << "Yes" << endl;else cout << "No" << endl;}return 0;
}

Over.

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！