首页 > 代码库 > 哈希的妙用

哈希的妙用

2024-07-18 05:51:45   222人阅读

如果需要判断多个字符是不是在某个字符串里面出现过或者统计多个字符在某个字符串中出现的次数，我们可以考虑基于数组创建一个简单的hash表，这样可以用很小的空间消耗来换取时间效率的提升。

题目1：从第一个字符串中删除第二个字符串中出现的所有字符
思路：准备一个hash数组，遍历第二个串，并以每个字符所对应的asc码作为下标，值为是否出现，1代表出现。然后遍历第一个串，每遍历一个字符，就查询hash表（O（1）），若值为1，那么删除该字符。
/*
从第一个字符串中删除第二个字符串中出现的所有字符
by Rowandjj
2014/8/18
*/
#include<iostream>
#include<string.h>
using namespace std;
#define MAX_SIZE 256
//在串1中删除所有出现在串2中的字符
void DeleteChar(char *str1,char *str2)
{
	if(str1 == NULL || str2 == NULL)
	{
		return;
	}
	char table[MAX_SIZE];//准备一个哈希数组
	int i,j;
	for(i = 0; i < MAX_SIZE; i++)//初始化哈希数组
	{
		table[i] = 0;
	}
	for(i = 0; *(str2+i)!='\0';i++)//以每个字符的asc码对应的数字作为数组下标，值为1代表出现过
	{
		table[*(str2+i)] = 1;
	}
	for(i = 0; *(str1+i) != '\0'; i++)//遍历串1，删除在串2中出现的每个字符
	{
		if(table[*(str1+i)] == 1)
		{
			for(j = i+1;*(str1+j) != '\0';j++)//这里需要移动字符
			{//如果允许，可以使用空间换时间
				*(str1+j-1) = *(str1+j); 	
			}
			*(str1+j-1) = '\0';
		}
	}
}
int main()
{
	char str1[] = "We are students.";
	char *str2 = "aeiou";
	DeleteChar(str1,str2);
	cout<<str1<<endl;
	return 0;
}
题目2：判断两个单词是否是变位词。变位词指的是两个单词字母相同，只是顺序不同。
思路：准备一个hash数组记录每个字母出现的次数，对第一个单词，为hash表对应表项增1，对第二个单词则是减1，这样如果最终hash表每个值都是0，则说明是变位词。
代码：
/*
判断两个单词是否为变位词
by Rowandjj
2014/8/18
*/
#include<iostream>
#include<string.h>
using namespace std;
#define MAX_WORD_SIZE 256
bool isAnagram(char *str1,char *str2)
{
	if(str1 == NULL || str2 == NULL)
	{
		return false;
	}
	int len = strlen(str1);
	if(len != strlen(str2))
	{
		return false;
	}
	int i;
	int table[MAX_WORD_SIZE];//准备一个hash数组
	for(i = 0; i < MAX_WORD_SIZE; i++)
	{
		table[i] = 0;
	}
	for(i = 0; i < len; i++)//为hash表对应每个字母出现次数增1
	{
		table[*(str1+i)]++;
	}
	for(i = 0; i < len; i++)//为hash表对应每个字母出现次数减1
	{
		table[*(str2+i)]--;
	}
	for(i = 0; i < MAX_WORD_SIZE; i++)//如果hash每个值都为0，那么就是变位词
	{
		if(table[i] != 0)
		{
			return false;
		}
	}
	return true;
}	
int main()
{
	char *str1 = "evil";
	char *str2 = "live";
	if(isAnagram(str1,str2))
	{
		cout<<"YES"<<endl;
	}else
	{
		cout<<"NO"<<endl;
	}
	return 0;
}

题目3：删除字符串中所有重复出现的字符。
思路：准备一个hash表，下标代表字符的asc码，值代表是否重复，这样我们只需0（1）的时间即可判断一个字符是否在前面出现过。
代码：
/*
删除字符串中所有重复出现的字符
by Rowandjj
2014/8/18
*/
#include<iostream>
#include<string.h>
using namespace std;
#define MAX 256
//去掉重复字符
void deleteRepeatChar(char *str)
{
	if(str == NULL)
	{
		return;
	}
	int table[MAX];
	int i;
	for(i = 0; i < MAX; i++)//初始化哈希表
	{
		table[i] = 0;
	}
	int len = strlen(str);
	char *temp = (char*)malloc(sizeof(char)*len);//存放不带重复字符的新串，避免移动原串
	if(!temp)
	{
		exit(-1);
	}
	int j = 0;
	for(i = 0; i < len; i++)
	{
		if(table[*(str+i)] == 1)//该字符重复
		{
			continue;
		}else//该字符不重复
		{
			table[*(str+i)] = 1;
			temp[j++] = *(str+i);//复制到新串
		}	
	}
	for(i = 0; i < j; i++)//将新串中的字符复制到原始串中
	{
		str[i] = temp[i];
	}
	*(str+i) = '\0';//别忘了还要复制结束符
	free(temp);
}
int main()
{
	char str[] = "google";
	deleteRepeatChar(str);
	cout<<str<<endl;
	return 0;
}


联系
我们