首页 > 代码库 > 剑指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‘;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。