筛选用户名

题面

参见 http://www.jisuanke.com/course/35/5428

解法

直接使用jisuanke CS261实现的HashTable类
其Hashing计算公式为：

int hash(string &index) {
        int code = 0;
        for (size_t i = 0; i < index.length(); i++) {
            code = (code * 256 + index[i] + 128) % size;
        }
        return code;
}

对于所有输入的字符串，首先进行一次统一的大小写转换，全都转化成小写再来进行判断。

代码

#include <iostream>
#include <string>
using namespace std;
class HashTable {
private:
    string *elem;
    int size;
public:
    HashTable() {
        size = 200000;
        elem = new string[size];
        for (int i = 0; i < size; i++) {
            elem[i] = "#";
        }
    }
    ~HashTable() {
        delete[] elem;
    }
    int hash(string &index) {
        int code = 0;
        for (size_t i = 0; i < index.length(); i++) {
            code = (code * 256 + index[i] + 128) % size;
        }
        return code;
    }
    bool search(string &index, int &pos, int &times) {
        pos = hash(index);
        times = 0;
        while (elem[pos] != "#" && elem[pos] != index) {
            times++;
            if (times < size) {
                pos = (pos + 1) % size;
            }
            else {
                return false;
            }
        }
        if (elem[pos] == index) {
            return true;
        }
        else {
            return false;
        }
    }
    int insert(string &index) {
        int pos, times;
        if (search(index, pos, times)) {
            return 2;
        }
        else if (times < size / 2) {
            elem[pos] = index;
            return 1;
        }
        else {
            return 0;
        }
    }

};
string toLower(string &input) {
    string output=input;
    for (size_t i = 0; i<input.length(); i++) {
        if (input[i] >= 'A'&&input[i] <= 'Z') {
            output[i] = input[i] - 'A' + 'a';
        }

    }
    return output;
}
int main() {
    HashTable hashtable;
    string buffer;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> buffer;
        string input = toLower(buffer);
        int ans = hashtable.insert(input);
        if (ans == 1) {
            cout << "No" << endl;
        }
        if (ans == 2) {
            cout << "Yes" << endl;
        }
    }

    return 0;
}