首页 > 代码库 > 剑指offer (35) 第一个只出现一次的字符 字符哈希表

剑指offer (35) 第一个只出现一次的字符 字符哈希表

题目:在字符串中找出第一个只出现一次的字符

 

题解分析:用空间换时间,使用哈希表,key为字符,value是该字符出现的次数

字符是一个长度为8的数据类型,因此总共只有256种可能,我们可以创建一个长为256的数组,

每个字符根据其ASCII码值作为数组的下标,即哈希表的key,而相应数组位置存储每个字符出现的次数,即哈希表的value

 

char GetFirstOnce(const char* str) {    assert(str != NULL);    const int hashSize = 256;    int hash[hashSize] = { 0 };    const char* cur = str;    while (*cur != \0) {        hash[*cur]++;        ++cur;    }        cur = str;    while (*cur != \0) {        if (hash[*cur] == 1) {            return *cur;        }        ++cur;    }    return \0;}

 

相关问题:

1. 输入两个字符串,从第一个字符串中删除在第二个字符串中出现过的所有字符

void Delete(char* str1, const char* str2) {    assert(str1 != NULL || str2 != NULL);    const int hashSize = 256;    int hash[hashSize] = { 0 };    const char* cur2 = str2;    while (*cur2 != \0) {        hash[*cur2] = 1;        ++cur2;    }        char* cur1 = str1;    while (*str1 != \0) {        if (hash[*str1] == 0) {  // 没有出现在str2中,依次保存            *cur1 = *str1;            ++cur1;        }         ++str1;    }    *cur1 = \0;}

 

2. 删除字符串中重复出现的字符,例如 “google”,执行函数之后应该是“gole”

首先将哈希表中所有value设为false,第一次扫描到‘g‘时,ASCII码下标对应的value为false,表示第一次出现,加入到res中,然后将value设为true,其后扫描到‘g‘时直接跳过

void DelDup(char* str) {    assert(str != NULL);    const int hashSize = 256;    bool hash[hashSize] = { false };        char* cur = str;    char* res = str;    while (*cur != \0) {        if (hash[*cur] == false) {            *res = *cur;            ++res;            hash[*cur] = true;        }         ++cur;    }    *res = \0;}