本文介紹 C++ 經(jīng)典算法集錦 三
C++ 經(jīng)典算法集錦 三
本文由在當?shù)剌^為英俊的男子金天大神原創(chuàng)灭贷，版權所有习贫，歡迎轉載歉井，本文首發(fā)地址 https://jinfagang.github.io 送挑。但請保留這段版權信息绑莺，多謝合作，有任何疑問歡迎通過微信聯(lián)系我交流：
jintianiloveu
Algorithm 6. 字符串算法
既然字符串經(jīng)常出現(xiàn)惕耕，那我就記錄一些字符串算法紊撕。
首先是，用hash表查找赡突，比如給一個字符串fierjggooi要找出第一個重復的字符对扶，這里應該是i，因為i出現(xiàn)了兩次惭缰，而且是首次出現(xiàn)浪南。要怎么寫呢？
#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表络凿，記錄每個字符對應出現(xiàn)的次數(shù)即可。說白了就是一個字典昂羡，只不過這里更加底層一些絮记。
