由于放原题的话文章实在太长，所以题多的话我只放思路和题解，大家请前往相应的网站查看题目呀0.0
🧑🏻作者简介：一个从工业设计改行学嵌入式的年轻人
✨联系方式：2201891280(QQ)
📔源码地址：https://gitee.com/xingleigao/algorithm-notes
⏳全文大约阅读时间： 30min
全文目录
🍕4.2小节——算法初步->哈希
问题 A: 谁是你的潜在朋友
问题 B: 分组统计
问题 C: Be Unique (20)
问题 D: String Subtraction (20)
B1029 旧键盘 (20 分)
B1033 旧键盘打字 (20 分)
B1038 统计同成绩学生 (20 分)
A1092 To Buy or Not to Buy (20 分)
B1042 字符统计 (20 分)
B1043 输出PATest (20 分)
A1041 Be Unique (20 分)
A1050 String Subtraction (20 分)
B1005 继续(3n+1)猜想 (25 分)
A1048 Find Coins (25 分)
🍕4.2小节——算法初步->哈希
地址合集：《算法笔记》4.2小节——算法初步->哈希
问题 A: 谁是你的潜在朋友
直接hash表统计就好了。
#include <cstdio> #include <cstring> int main(){ int m,n; const char zero[6] = "BeiJu"; while(scanf("%d %d",&n, &m) != EOF){ int hash[m+1]; //书籍的hash表 int peo[n]; //人员列表 memset(hash,0,sizeof(hash)); for(int i = 0;i < n ;++i) scanf("%d",&peo[i]),hash[peo[i]]++; for(int i = 0;i < n ;++i) if(hash[peo[i]] > 1) printf("%d\n",hash[peo[i]] - 1); else printf("%s\n",zero); } return 0; }
问题 B: 分组统计
建个二维hash表就好了，但是要注意的是，可能有的组号一个元素都没有是不需要打印的，大坑，调了半小时。。。
#include <cstdio> #include <cstring> int hash[101][2000]; //保存每组的数字个数 注意到组号不为0 可以利用0组保存所有的元素表 int num[110]; //保存所有的数字 int main(){ int m, n; while(scanf("%d" , &m) != EOF){ while(m--){ memset(hash, 0, sizeof(hash)); scanf("%d", &n); int max_num = 0; for(int i = 0;i < n;++i){ scanf("%d",&num[i]),hash[0][num[i]] = 1;//读入第一行元素 if(num[i] > max_num) max_num = num[i]; } int max_group = 0; for(int i = 0;i < n;++i){ //读入第二行元素并设置相应的hash表 int tmp; if(max_group < tmp) max_group = tmp; scanf("%d", &tmp), hash[tmp][num[i]]++; hash[tmp][0] = 1; //记录出现的组号 会跳组号 尼玛 离谱-。- } for(int i = 1;i <= max_group;++i){ if(hash[i][0]){ printf("%d={",i);//输出前面的数据 for(int j = 0;j < max_num;j++){ if(hash[0][j]) printf("%d=%d,",j,hash[i][j]); } printf("%d=%d}\n",max_num,hash[i][max_num]);//输出后面的数据 } } } } return 0; }
问题 C: Be Unique (20)
借用宇哥的话，这个就是paper tiger，花里胡哨的，其实很简答的。
#include <cstdio> #include <cstring> short hash[10010]; char *s = "None"; int num[1000005]; int main(){ int n; while(scanf("%d",&n) != EOF){ memset(hash, 0, sizeof(hash)); for(int i = 0;i < n;i++) scanf("%d",&num[i]),hash[num[i]]++; //读入数据,设置hahs表 int j ; for(j = 0;j < n;j++) if(hash[num[j]] == 1){ printf("%d\n",num[j]); break; } if(j == n) printf("%s\n",s); } return 0; }
问题 D: String Subtraction (20)
#include <iostream> #include <cstring> using namespace std; char s1[10008],s2[10008]; unsigned char Hash[128]; int main(){ while(cin.getline(s1,10008)){ cin.getline(s2, 10008); memset(Hash, 0, sizeof(Hash)); for(int i = 0;s2[i];++i) Hash[s2[i]] = 1; for(int i = 0;s1[i];++i) if(!Hash[s1[i]]) putchar(s1[i]); puts(""); } }
B1029 旧键盘 (20 分)
地址：A1084 Broken Keyboard (20 分) B1029 旧键盘 (20 分)
就是hash表记录一下坏的按键控制只输出一次就好了。
#include <cstdio> #include <cstring> #include <iostream> using namespace std; int Hash[128]; int main(){ char s1[88],s2[88]; while(cin.getline(s1,88)){ cin.getline(s2,88); memset(Hash, 0, sizeof(Hash));//全局变量初始化 for(int i = 0,j = 0;s1[i];i++){ if(s1[i] != s2[j]){ //判断是否输入成功 unsigned char tmp = (s1[i] <= 'z' && s1[i] >= 'a') ? s1[i] - ' ':s1[i];//转成大写 if(!Hash[tmp]){ Hash[tmp] = 1; putchar(tmp); } } else j++;//没坏往后走 } puts(""); //补个格式 } return 0; }
B1033 旧键盘打字 (20 分)
地址：B1033 旧键盘打字 (20 分)
其实思路和上面的差不多，记录坏按键，坏的不打印就好了。
#include <cstdio> #include <cstring> #include <iostream> using namespace std; int Hash[128]; int main(){ char s1[88]; while(cin.getline(s1,88)){ memset(Hash, 0, sizeof(Hash));//全局变量初始化 char TOP = 1; for(int i = 0;s1[i];++i){ //写Hash表 if(s1[i] == '+') TOP = 0; else if(s1[i] <= 'Z' && s1[i] >= 'A') Hash[s1[i] + ' '] = 1; else Hash[s1[i]] = 1; } char c; while((c = getchar()) != '\n'){ if(c >= 'A' && c <= 'Z') //大写需要大写能打开并且按键没坏 if(TOP && !Hash[c + ' ']) putchar(c); else continue; //如果想省略括号这个else必须写 没办法。。。。不然下一个else识别成这个 else if(!Hash[c]) putchar(c); //没坏才能输出 } puts(""); //补个格式 } return 0; }
B1038 统计同成绩学生 (20 分)
地址:B1038 统计同成绩学生 (20 分)
思路其实就是先统计，这里根本不用读入所有数据，直接统计就好了。
#include <cstdio> #include <cstring> int main(){ int n; while(scanf("%d", &n) != EOF){ int Hash[101],tmp,k; memset(Hash, 0 , sizeof(Hash)); //初始化 栈内存不给初始化 太难了。。。。 while(n--){ //填充Hash表 scanf("%d", &tmp); Hash[tmp]++; } scanf("%d", &k); for(int i = 0;i < k; ++i){ scanf("%d", &tmp); printf("%d", Hash[tmp]); if(i != k-1) printf(" ");//格式控制 } puts(""); } return 0; }
A1092 To Buy or Not to Buy (20 分)
地址:A1092 To Buy or Not to Buy (20 分)|B1039 到底买不买 (20 分)
其实思路还是很简单的，就是一个简单的hash表。需要注意一个点就是，不如边做事边计算长度，因为strlen这个库函数也是不断的往后读读到\0，所以如果用库函数 复杂度会成倍增长。
#include <iostream> #include <cstdio> #include <cstring> using namespace std; int Hash[128]; char s1[1001], s2[1001]; int main(){ while(cin.getline(s1,1001)){ memset(Hash, 0 , sizeof(Hash)); int count = 0; cin.getline(s2,1001); for(int i = 0;s2[i] ;++i) ++Hash[s2[i]],++count;//设置hash表 int count1 = count, count2 = 0; for(int i = 0;s1[i];++i){ ++count2; if(Hash[s1[i]]) --Hash[s1[i]],--count;//查看是否满足要求 } if(count != 0) printf("No %d\n",count); //还有未满足的珠子 else printf("Yes %d\n",count2 - count1); //全满足之间就是两串差 } return 0; }
B1042 字符统计 (20 分)
地址:B1042 字符统计 (20 分)
#include <cstdio> #include <iostream> #include <cstring> using namespace std; char s[1009]; int Hash[128]; //Hash表 int main(){ while(cin.getline(s,1009)){ memset(Hash, 0, sizeof(Hash)); char max = 0; for(int i = 0;s[i];++i){ if(s[i] <= 'Z' && s[i] >= 'A') s[i] += ' '; //大写转换成小写 else if(s[i] > 'z' || s[i] < 'a') continue; //不是字母 直接下一个 ++Hash[s[i]]; //Hash统计 if(Hash[s[i]] > Hash[max] || (Hash[s[i]] == Hash[max] && s[i] < max)) max = s[i]; //记录出现最多的字母 } printf("%c %d\n",max, Hash[max]); } return 0; }
B1043 输出PATest (20 分)
地址:B1043 输出PATest (20 分)
#include <cstdio> #include <cstring> int Hash[128]; //Hash表 const char ans[7] = "PATest"; int main(){ int c,count = 0; while((c = getchar()) != EOF){ char tmp = c; for(int i = 0; ans[i];++i) if(tmp == ans[i]) ++Hash[tmp], ++count; //插入hash表 } while(count){ for(int i = 0; ans[i];++i) //按序输出 if(Hash[ans[i]]) --Hash[ans[i]],putchar(ans[i]), --count; } puts(""); return 0; }
A1041 Be Unique (20 分)
地址:A1041 Be Unique (20 分)
看题目C…这玩意竟然一样 ，我惊了。
A1050 String Subtraction (20 分)
地址:A1050 String Subtraction (20 分)
看题目D…行吧，水题。。。。
B1005 继续(3n+1)猜想 (25 分)
地址:B1005 继续(3n+1)猜想 (25 分)
把3n+1猜想搬过来改改完事0.0
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int Hash[10000];//HASH表 int ans[101]; //记录所有数字 bool cmp(int a, int b ){return a > b;} void kan(int n){ Hash[n]++; if(Hash[n] > 1) return; if(n%2==1) kan((3*n+1)/2); if(n%2==0) kan(n/2); } int main(){ int n; while(scanf("%d",&n) != EOF){ memset(Hash, 0, sizeof(Hash)); Hash[1] = 1; for(int i = 0;i < n;++i){ scanf("%d",&ans[i]); kan(ans[i]); } int zhan[100],top = 0; for(int i = 0;i < n;++i) if(Hash[ans[i]] == 1){ zhan[top++] = ans[i]; } sort(zhan, zhan + top, cmp); for(int i = 0;i < top;++i){ printf("%d",zhan[i]); if(i != top - 1) printf(" "); } puts(""); } return 0; }
A1048 Find Coins (25 分)
地址:A1048 Find Coins (25 分)
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int Hash[1000]; int main(){ int n, m; while(scanf("%d %d", &n, &m) != EOF){ memset(Hash, 0, sizeof(Hash)); int min = 501; while(n--){ int tmp; scanf("%d",&tmp); Hash[tmp]++; if(tmp + tmp == m){ //刚好一半 不能用m/2 这俩加和可能不能与m。。。。 因为是向下取整 你们懂的 if(Hash[tmp] > 1) min = tmp < min ? tmp: min; } else if(Hash[m - tmp]) if(tmp <= m/2) min = tmp < min ? tmp: min; //挑小的 else min = (m - tmp) < min ? (m - tmp) :min; } if(min != 501) printf("%d %d\n",min, m - min); else printf("No Solution\n"); } return 0; }
