字符串中字符出现次数的相关题目

淡淡的烟草味﹌ 2022-08-26 13:20 204阅读 0赞

在字符串问题中，当题目考查设计字符串中字符出现的次数（或是否出现）时，可以采用哈希表，因为字符最多256个，最多开辟一个大小为256的辅助数组。

题目1：设计一个算法移除字符串中的重复字符，并写出测试用例

思路：普通的循环扫描时间复杂度为O(n^2)，下述算法借助辅助空间hashtable\[ \]，使时间复杂度为O(n)

/*
    	设计一个算法移除字符串中的重复字符，并写出测试用例
     */
    
    #include<cstdio>
    #include<cstring>
    using namespace std;
    
    void Remove(char * str)
    {
    	if(str==NULL) return;
    	int len = strlen(str);
    	if(len<2) return;
    	bool hashtable[256]={0};
    	hashtable[str[0]]=true;
    	int tail = 1;
    	for(int i =1;i<len;i++)
    	{
    		if(!hashtable[str[i]])
    		{
    			str[tail] = str[i];
    			tail++;
    			hashtable[str[i]] = true;
    		}
    	}
    	str[tail]=0;
    }
    
    int main()
    {
    	char str[1000];
    	while(gets(str))
    	{
    		Remove(str);
    		printf("%s\n",str);
    	}
    }

题目2：假设有一个各种字母组成的字符串s1,假设还有另外一个字符串s2,而且s2字符串里的字母数相对少一些。 从算法上讲，什么方法能最快查出s2中的字母是否在s1中都有？（谷歌面试题）  
注意：当短字符串字母有重复时，长字符串需满足对应字符重复个数大于等于短字符串中相应字符出现的次数。  
这里假设字母都由大写字母组成。

解法1：如果可以改变原始字符串，可以先对这两个字符串的字母进行排序，然后同时对两个字符串依次轮询。排序需要O(m logm)+O(n logn)次操作，之后线性扫描需O(m+n)次操作。

解法2：哈希表。时间O(m+n)，但是需要空间代价。

/*
    	题目：假设有一个各种字母组成的字符串s1,假设还有另外一个字符串s2,而且s2字符串里的字母数相对少一些。
    	从算法上讲，什么方法能最快查出s2中的字母是否在s1中都有？（谷歌面试题）
    	注意：当短字符串字母有重复时，长字符串需满足对应字符重复个数大于等于短字符串中相应字符出现的次数。
    	这里假设字母都由大写字母组成。
     */
    
    #include<cstdio>
    #include<cstring>
    using namespace std;
    
    bool isExist(char * s1,char * s2)
    {
    	//非法字符判断
    	if(s1==NULL||s2==NULL) return false;
    	int len1 = strlen(s1);
    	int len2 = strlen(s2);
    	for(int i =0;i<len1;i++)
    		if(s1[i]<'A'||s1[i]>'Z')
    			return false;
    	for(int i =0;i<len2;i++)
    		if(s2[i]<'A'||s2[i]>'Z')
    			return false;
    
    	int hashtable[26] = {0};	
    	int index = 0;
    	for(int i = 0;i<len1;i++)
    	{
    		index = s1[i]-'A';
    		hashtable[index]++;
    	}
    
    	for(int i =0 ;i<len2;i++)
    	{
    		index = s2[i]-'A';
    		if(hashtable[index]<=0)
    			return false;
    		else hashtable[index]--;
    	}
    	return true;
    }
    
    int main()
    {
    	char s1[100];
    	char s2[100];
    	while(gets(s1))
    	{
    		gets(s2);
    		if(isExist(s1,s2))
    			printf("YES\n");
    		else printf("NO\n");
    	}
    }