当前位置：首页 > ds >正文

《算法笔记》4.2小节——算法初步-＞哈希

ds 2025/5/8 23:51:04

谁是你的潜在朋友

在这里插入图片描述

#include <iostream>
using namespace std;int main() {int n,m,favobook;while(cin>>n>>m){int book[210]={0},reader[210]={0};for (int i = 1; i <= n; ++i) {cin>>favobook;book[favobook]++;reader[i]=favobook;}for (int i = 1; i <= n; ++i) {if(book[reader[i]]>1){cout<<book[reader[i]]-1<<endl;}else{cout<<"BeiJu"<<endl;}}}return 0;
}

分组统计

在这里插入图片描述

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;int main(){int m;cin>>m;for (int i = 0; i < m; ++i) {int n;cin>>n;int num[n],col[n];for (int j = 0; j < n; ++j) {cin>>num[j];}for (int j = 0; j < n; ++j) {cin>>col[j];}int max_num=*max_element(num,num+n);int max_col=*max_element(col,col+n);int hash_table[max_col+1][max_num+1];memset(hash_table,0,sizeof(hash_table));for (int j = 0; j < n; ++j) {hash_table[col[j]][num[j]]++;}vector<int> num2;sort(num,num+n);unique_copy(num,num+n, back_inserter(num2));vector<int> col2;sort(col,col+n);unique_copy(col,col+n, back_inserter(col2));for (int j = 0; j < col2.size(); ++j) {cout<<col2[j]<<"={";for (int k = 0; k < num2.size(); ++k) {cout<<num2[k]<<'='<<hash_table[col2[j]][num2[k]];if(k<num2.size()-1) cout<<',';}cout<<'}'<<endl;}}return 0;
}

Be Unique (20)

在这里插入图片描述

#include <iostream>
#include <cstring>
using namespace std;int main() {int n;while(cin>>n){int m;int hash_table[10010],num[100010];memset(hash_table,0,sizeof (hash_table));for (int i = 0; i < n; ++i) {cin>>m;num[i]=m;hash_table[m]++;}bool flag=false;for (int i = 0; i < n; ++i) {if(hash_table[num[i]]==1){cout<<num[i]<<endl;flag= true;break;}}if(!flag)  cout<<"None"<<endl;}return 0;
}

String Subtraction

在这里插入图片描述

#include <iostream>
using namespace std;int main(){string str1,str2;getline(cin,str1);getline(cin,str2);bool hashtable[128]={false};for(char c:str2){hashtable[c]= true;}for(char c:str1){if(!hashtable[c])cout<<c;}cout<<endl;return 0;
}

暴力算法，时间超限，没有通过测试

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;int main() {string str1, str2;getline(cin, str1);getline(cin, str2);for (int i = 0; i < str1.size(); ) {int j;for (j = 0; j < str2.size(); ++j) {if(str1[i]==str2[j])str1.erase(i,1);break;}if(j==str2.size()) i++;}cout<<str1<<endl;return 0;
}