天空一声巨响，迪宝闪亮登场。哈哈哈数据结构刷题又来了。实践是检验真理的唯一标准，最近感觉到自己的代码功底越来越深了，看来多写代码确实很有帮助。这次又带来最新的五道题目，来跟我一起去看看把。（顺便提一下，现在我在PTA上浙大《数据结构》这个题库已经排名1/3105了哦！！！）

电话聊天狂人

这道题我就是使用了哈希函数+分离链接法，然后第一次还超时了，后来将哈希函数改了后，降低了装填因子，就AC了。整体难度不大。
此题代码如下：

  1. #include<iostream>
  2. #include<string>
  4. using namespace std;
  6. class Node{
  7.     public:
  8.     string s;
  9.     long int value;
  10.     Node* next;
  11.     Node(){ next = NULL;value = 0; }
  12.     long int Getvalue() { return this->value; }
  13.     Node* Getnext() { return this->next; }
  14.     void Setvalue(long int num) { value = num; }
  15.     void Setnext(Node* a) { next = a; }
  16. };
  18. class Nodearray{
  19.     public:
  20.     Node* head;
  21.     Node* tail;
  22.     int total;
  23.     Nodearray(){
  24.         head = NULL;
  25.         tail = NULL;
  26.         total = 0;
  27.     }
  28.     void Addnum(string num){
  29.         if (head == NULL){
  30.             head = new Node;
  31.             head->s = num;
  32.             head->Setvalue(1);
  33.             head->Setnext(NULL);
  34.             tail = head;
  35.         }
  36.         else{
  37.             Node* p = this->head;
  38.             Node* tempp = p;
  39.             while(p != NULL){
  40.                 if(num > p->s){
  41.                     tempp = p;
  42.                     p = p->Getnext();
  43.                 }
  44.                 else{
  45.                     Node* temp;
  46.                     temp = new Node;
  47.                     temp->s = num;
  48.                     temp->Setvalue(1);
  49.                     if(p == this->head){
  50.                         temp->Setnext(p);
  51.                         this->head = temp;
  52.                         return;
  53.                     }else{
  54.                         temp->Setnext(p);
  55.                         tempp->Setnext(temp);
  56.                         return;
  57.                     }
  58.                 }
  59.             }
  60.             tempp->Setnext(new Node);
  61.             tempp = tempp->Getnext();
  62.             tempp->s = num;
  63.             tempp->Setvalue(1);
  64.             tempp->Setnext(NULL);
  65.             return;
  66.         }
  67.     }
  68.     bool Findnum(string num){
  69.         Node* p1 = head;
  70.         Node* p2 = head;
  71.         if (head == NULL){
  72.             return false;
  73.         }
  74.         else{
  75.             if (head->s == num){
  76.                 head->value ++;
  77.                 return true;
  78.             }
  79.             else
  80.                 p2 = p2->Getnext();
  81.             while (p2 != NULL){
  82.                 if (p2->s == num){
  83.                     p2->value ++;
  84.                     return true;
  85.                 }
  86.                 p1 = p1->Getnext();
  87.                 p2 = p2->Getnext();
  88.             }
  89.         }
  90.         return false;
  91.     }
  92. };
  95. int N,index;
  96. string s,s2;
  97. Nodearray a[8020];
  98. Node* temp;
  99. long int maxlen,maxnum;
  101. int Hash(string ss);
  103. int main(){
  104.     cin >> N;
  105.     for(int i = 0;i < N;i++){
  106.         cin >> s;
  107.         index = Hash(s);
  108.         if(a[index].Findnum(s) == false)
  109.             a[index].Addnum(s);
  110.         cin >> s;
  111.         index = Hash(s);
  112.         if(a[index].Findnum(s) == false)
  113.             a[index].Addnum(s);
  114.     }
  115.     maxnum = -1;
  116.     maxlen = 0;
  117.     for(int i = 0;i < 8020;i++){
  118.         if(a[i].head == NULL)
  119.             continue;
  120.         temp = a[i].head;
  121.         while(temp != NULL){
  122.             if(maxnum == -1){
  123.                 s2 = temp->s;
  124.                 maxlen = 1;
  125.                 maxnum = temp->Getvalue();
  126.             }
  127.             else if(temp->Getvalue() > maxnum){
  128.                 s2 = temp->s;
  129.                 maxlen = 1;
  130.                 maxnum = temp->Getvalue();
  131.             }
  132.             else if(temp->Getvalue() == maxnum){
  133.                 maxlen ++;
  134.                 if(temp->s < s2)
  135.                     s2 = temp->s;
  136.             }
  137.             temp = temp->Getnext();
  138.         }
  139.     }
  140.     cout<<s2<<' '<<maxnum;
  141.     if(maxlen != 1)
  142.         cout<<' '<<maxlen;
  143.     return 0;
  144. }
  146. int Hash(string ss){
  147.     int num = 0;
  148.     for(int i = 0;i < ss.size();i++)
  149.         num += ((int)ss[i] - 48)*((int)ss[i] - 48)*((int)ss[i] - 48);
  150.     return num;
  151. }

Hashing

代码如下：

  1. #include <iostream>
  2. #include <cmath>
  3. using namespace std;
  4. const int maxn = 100005;
  5. typedef long long ll;
  6. int TableSize;
  7. bool a[maxn];
  8. bool isPrime(int m) { 
  9.     if(m <= 1) return false; 
  10.     int k = (int)sqrt(m);
  11.     for(int i = 2; i <= k; ++i) {
  12.         if(m % i == 0) return false;
  13.     }
  14.     return true;
  15. }
  16. int NextPrime(int m) {
  17.     if(m % 2 == 0 || m == 1)
  18.         m++;
  19.     while(!isPrime(m)) m += 2;
  20.     return m;
  21. }
  22. int Hash(int x) {
  23.     return x % TableSize;
  24. }
  25. void Insert(int x) {
  26.     int p = Hash(x);
  27.     if(!a[p]) { //该位置没有元素
  28.         a[p] = true;
  29.         cout << p;
  30.     } else {
  31.         int newp = p;
  32.         int i;
  33.         for(i = 1; i <= TableSize; ++i) {
  34.             newp = (p+i*i) % TableSize;
  35.             if(!a[newp]) {
  36.                 a[newp] = true;
  37.                 cout << newp;
  38.                 return;
  39.             }
  40.         }
  41.         cout << '-';
  42.     }
  43. }
  44. int main() {
  45.     int M, N, x;
  46.     cin >> M >> N;
  47.     TableSize = NextPrime(M);
  48.     for(int i = 0; i < N; ++i) {
  49.         cin >> x;
  50.         Insert(x);
  51.         if(i == N-1) cout << endl;
  52.         else cout << ' ';
  53.     }
  54.     return 0;
  55. }

QQ账号的登录

依旧是哈希函数+分离链接法解决冲突，40分钟AC。
代码如下：

  1. #include<iostream>
  2. #include<string>
  4. using namespace std;
  6. class Node{
  7.     public:
  8.     string s;
  9.     long int value;
  10.     Node* next;
  11.     Node(){ next = NULL;value = 0; }
  12.     long int Getvalue() { return this->value; }
  13.     Node* Getnext() { return this->next; }
  14.     void Setvalue(long int num) { value = num; }
  15.     void Setnext(Node* a) { next = a; }
  16. };
  18. class Nodearray{
  19.     public:
  20.     Node* head;
  21.     Node* tail;
  22.     int total;
  23.     Nodearray(){
  24.         head = NULL;
  25.         tail = NULL;
  26.         total = 0;
  27.     }
  28.     void Addnum(long int num,string pa){
  29.         if (head == NULL){
  30.             head = new Node;
  31.             head->Setvalue(num);
  32.             head->s = pa;
  33.             head->Setnext(NULL);
  34.             tail = head;
  35.         }
  36.         else{
  37.             Node* p = this->head;
  38.             Node* tempp = p;
  39.             while(p != NULL){
  40.                 if(num > p->Getvalue()){
  41.                     tempp = p;
  42.                     p = p->Getnext();
  43.                 }
  44.                 else{
  45.                     Node* temp;
  46.                     temp = new Node;
  47.                     temp->s = pa;
  48.                     temp->Setvalue(num);
  49.                     if(p == this->head){
  50.                         temp->Setnext(p);
  51.                         this->head = temp;
  52.                         return;
  53.                     }else{
  54.                         temp->Setnext(p);
  55.                         tempp->Setnext(temp);
  56.                         return;
  57.                     }
  58.                 }
  59.             }
  60.             tempp->Setnext(new Node);
  61.             tempp = tempp->Getnext();
  62.             tempp->s = pa;
  63.             tempp->Setvalue(num);
  64.             tempp->Setnext(NULL);
  65.             return;
  66.         }
  67.     }
  68.     bool Findnum(long int num){
  69.         Node* p1 = head;
  70.         Node* p2 = head;
  71.         if (head == NULL){
  72.             return false;
  73.         }
  74.         else{
  75.             if (head->Getvalue() == num){
  76.                 return true;
  77.             }
  78.             else
  79.                 p2 = p2->Getnext();
  80.             while (p2 != NULL){
  81.                 if (p2->Getvalue() == num){
  82.                     return true;
  83.                 }
  84.                 p1 = p1->Getnext();
  85.                 p2 = p2->Getnext();
  86.             }
  87.         }
  88.         return false;
  89.     }
  90.     void Checknum(long int num,string pa){
  91.         Node* p1 = head;
  92.         Node* p2 = head;
  93.         if (head == NULL)
  94.             return;
  95.         else{
  96.             if (head->Getvalue() == num){
  97.                 if(head->s == pa)
  98.                     cout<<"Login: OK"<<endl;
  99.                 else
  100.                     cout<<"ERROR: Wrong PW"<<endl;
  101.                 return;
  102.             }
  103.             else
  104.                 p2 = p2->Getnext();
  105.             while (p2 != NULL){
  106.                 if (p2->Getvalue() == num){
  107.                     if(p2->s == pa)
  108.                         cout<<"Login: OK"<<endl;
  109.                     else
  110.                         cout<<"ERROR: Wrong PW"<<endl;
  111.                     return;
  112.                 }
  113.                 p1 = p1->Getnext();
  114.                 p2 = p2->Getnext();
  115.             }
  116.         }
  117.         return;
  118.     }
  119. };
  121. int N,index;
  122. char c;
  123. long int t;
  124. string temp2,temp3;
  125. Nodearray a[8020];
  127. int Hash(string ss);
  129. int main(){
  130.     cin >> N;
  131.     for(int n = 0;n < N;n++){
  132.         cin >> c >> t >> temp3;
  133.         temp2 = to_string(t);
  134.         index = Hash(temp2);
  135.         if(c == 'N'){
  136.             if(a[index].Findnum(t) == true)
  137.                 cout<<"ERROR: Exist"<<endl;
  138.             else{
  139.                 a[index].Addnum(t,temp3);
  140.                 cout<<"New: OK"<<endl;
  141.             }
  142.         }
  143.         else{
  144.             if(a[index].Findnum(t) == false)
  145.                 cout<<"ERROR: Not Exist"<<endl;
  146.             else
  147.                 a[index].Checknum(t,temp3);
  148.         }
  149.     }
  150.     return 0;
  151. }
  153. int Hash(string ss){
  154.     int num = 0;
  155.     for(int i = 0;i < ss.size();i++)
  156.         num += ((int)ss[i] - 48)*((int)ss[i] - 48)*((int)ss[i] - 48);
  157.     return num;
  158. }

Hashing-Hard Version

这道题需要动点脑子，想清楚过程和规则后再下手。这里我先使用了希尔排序进行排序，再用查表的方式+某种判断算法来判断出下一个填入的数字是什么。
代码如下：

  1. #include<iostream>
  2. #include<cmath>
  4. using namespace std;
  5. int N,start,index;
  6. int total = 0;
  7. int *a,*b;
  8. int c[100000];
  10. void HSort1(int *H,int n);
  12. int main(){
  13.     cin >> N;
  14.     a = new int[N];
  15.     b = new int[N];
  16.     for(int i = 0;i < N;i++){
  17.         cin >> a[i];
  18.         b[i] = a[i];
  19.     }
  20.     HSort1(b,N);
  21.     for(int i = 0;i < N;i++){
  22.         if(b[i] != -1){
  23.             start = i;
  24.             break;
  25.         }
  26.     }
  27.     int flag;
  28.     while(total != N - start + 1){
  29.         flag = 0;
  30.         for(int i = start;i < N;i++){
  31.             if(c[b[i]] == 1)
  32.                 continue;
  33.             index = b[i] % N;
  34.             if(a[index] == b[i]){
  35.                 c[b[i]] = 1;
  36.                 if(total == 0)
  37.                     cout<<b[i];
  38.                 else
  39.                     cout<<' '<<b[i];
  40.                 break;
  41.             }
  42.             for(int j = index;j < index + N;j++){
  43.                 if(c[a[j % N]] != 1 && a[j % N] != b[i])
  44.                     break;
  45.                 if(a[j % N] == b[i]){
  46.                     c[b[i]] = 1;
  47.                     if(total == 0)
  48.                         cout<<b[i];
  49.                     else
  50.                         cout<<' '<<b[i];
  51.                     flag = 1;
  52.                     break;
  53.                 }
  54.             }
  55.             if(flag == 1)
  56.                 break;
  57.         }
  58.         total++;
  59.     }
  60.     return 0;
  61. }
  63. void HSort1(int *H,int n){
  64.     int count = 1;
  65.     while((int)pow(2,count) - 1 < n)
  66.         count++;
  67.     count--;
  68.     int D;
  69.     for(int i = count;i > 0;i--){
  70.         D = (int)pow(2,i) - 1;
  71.         for(int j = 0;j < D;j++){
  72.             for(int k = j;k < n;k += D){
  73.                 if(k == j)
  74.                     continue;
  75.                 int t1 = H[k];
  76.                 for(int p = j;p < k;p += D){
  77.                     if(t1 < H[p]){
  78.                         for(int s = k;s > p;s -= D)
  79.                             H[s] = H[s-D];
  80.                         H[p] = t1;
  81.                         break;
  82.                     }
  83.                 }
  84.             }
  85.         }
  86.     }
  87. }

KMP串的模式匹配

代码如下：

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
#define div 1000000007
const int maxn = 1000005;
const int inf  = 0x3f3f3f;
int N,M;
int nxt[maxn];
void getnxt(string t) {
    int len = t.length();
    int i = 0, j = -1; 
    nxt[0] = -1;
    while (i < len) {
        if (j == -1 || t[i] == t[j]) {
            i++, j++;
            if (t[i] == t[j])
                nxt[i] = nxt[j]; // next数组优化
            else
                nxt[i] = j;
        } else
            j = nxt[j];
    }
}

int KMP(string s, string t) {//s为文本串，t为模式串(短的那个)
    getnxt(t);
    int len1 = s.length();
    int len2 = t.length();
    int i = 0, j = 0, ans = 0;
    while (i < len1) {
        if (j == -1 || s[i] == t[j]) {
            i++, j++;
            if (j >= len2) {
                return i-j;
            }
        } else
            j = nxt[j];
    }
    return -1;
}
int main(){
    ios::sync_with_stdio(false);
    string String, Pattern;
    cin >> String;
    cin >> N;
    for(int i = 0; i < N; ++i) {
        memset(nxt, 0, sizeof(nxt));
        cin >> Pattern;
        int k = KMP(String, Pattern);
        if(k == -1) cout << "Not Found" << endl;
        else cout << String.substr(k) << endl;
    }
    return 0;
}

总结

这次是散列查找和KMP的专场。散列查找的问题或者说散列查找、哈希表本身不是很难用代码实现的查找算法，但是哈希算法却是一个非常重要的查找方法，值得我们细细品味。
欢迎对ECE/CS/AI感兴趣的小伙伴关注我，如果你对我的内容有什么建议的话，或者你也对算法和数据结构感兴趣的话，可以单独找我讨论，也欢迎在评论区留下你的声音。