本文介绍 C++ 经典算法集锦 三

C++ 经典算法集锦 三

本文由在当地较为英俊的男子金天大神原创，版权所有，欢迎转载，本文首发地址 https://jinfagang.github.io 。但请保留这段版权信息，多谢合作，有任何疑问欢迎通过微信联系我交流：jintianiloveu

Algorithm 6. 字符串算法

既然字符串经常出现，那我就记录一些字符串算法。
首先是，用hash表查找，比如给一个字符串fierjggooi要找出第一个重复的字符，这里应该是i，因为i出现了两次，而且是首次出现。要怎么写呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <vector>
using namespace std;
// define a hash table struct
typedef struct Hash{
    char c;
    int times;
};
int find_first_repeat(string s) {
    // find the first repeat char in s
    // we have all 52 chars
    int n = 52;
    Hash *HashTable;
    HashTable = new Hash[n];
    for (int i = 0; i < s.size(); ++i) {
        int pos = islower(s[i])? (s[i] - 'a'): (s[i] - 'A' + n/2);
        if (!HashTable[pos].c) {
            HashTable[pos].c = s[i];
            HashTable[pos].times = 1;
        } else {
            HashTable[pos].times++;
        }
    }
    for (int j = 0; j < s.size(); ++j) {
        int pos = islower(s[j])? (s[j] - 'a'): (s[j] - 'A' + n/2);
        if (HashTable[pos].times > 1) {
            cout << "hash c: " << HashTable[pos].c << endl;
            cout << "s: " << s[j] << endl;
            cout << j << endl;
            return j;
        }
    }
    return -1;
}
int main()
{
    string a = "goigygyvtuty";
    // should get 'u'
    int p = find_first_repeat(a);
    if (p >= 0) {
        cout << "first repeat char is: " << a[p] << endl;
    } else {
        cout << "no repeat char.\n";
    }
    return 0;
}

其实也非常简单，只需要写一个hash表，记录每个字符对应出现的次数即可。说白了就是一个字典，只不过这里更加底层一些。