| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 6505 人关注过本帖
标题:腾讯的一道面试题??欢迎讨论
取消只看楼主 加入收藏
Charistain
Rank: 1
等 级:新手上路
帖 子:5
专家分:0
注 册:2011-1-10
结帖率:0
收藏
已结贴  问题点数:20 回复次数:4 
腾讯的一道面试题??欢迎讨论
假设两个字符串中所含有的字符和个数都相同我们就叫这两个字符串匹配,比如:abcda和adabc,由于出现的字符个数都是相同,只是顺序不同,所以这两个字符串是匹配的。。要求高效
现在需要你来实现下面的函数:
boolen Is_Mach(char *str1,char *str2)


大家来讨论讨论吧,我觉得这个比较有意思,电子词典中就存在相似的问题。。
我想了好久也只想到一些基本的方法,效率也不高,还请大家来晒晒自己的方法吧???
搜索更多相关主题的帖子: 电子词典 字符串 腾讯 
2011-01-10 17:01
Charistain
Rank: 1
等 级:新手上路
帖 子:5
专家分:0
注 册:2011-1-10
收藏
得分:0 
回复 2楼 马后炮
这个方法效率最低,
2011-01-10 19:49
Charistain
Rank: 1
等 级:新手上路
帖 子:5
专家分:0
注 册:2011-1-10
收藏
得分:0 
回复 15楼 马后炮
如果字符串足够长的话,最糟糕的情况是字符串中的字符都不一样,这样的话你就需要不少的变量来记录字符个数,
不过我倒是觉得四楼的方法还是可以考虑一下
2011-01-10 20:01
Charistain
Rank: 1
等 级:新手上路
帖 子:5
专家分:0
注 册:2011-1-10
收藏
得分:0 
回复 17楼 马后炮
不过可以用hash算法来统计字符出现的频率。在让我想想
2011-01-10 20:11
Charistain
Rank: 1
等 级:新手上路
帖 子:5
专家分:0
注 册:2011-1-10
收藏
得分:0 
回复 19楼 马后炮
由于字符(char)是一个长度为8的数据类型,因此总共有可能256 种可能。于是我们创建一个长度为256的数组,每个字母根据其ASCII码值作为数组的下标对应数组的对应项,而数组中存储的是每个字符对应的次数。这样我们就创建了一个大小为256,以字符ASCII码为键值的哈希表。我们第一遍扫描这个数组时,每碰到一个字符,在哈希表中找到对应的项并把出现的次数增加一次。这样在进行第二次扫描时,就能直接从哈希表中得到每个字符出现的次数了
///////////////////////////////////////////////////////////////////////
// Find the first char which appears only once in a string
// Input: pString - the string
// Output: the first not repeating char if the string has, otherwise 0
///////////////////////////////////////////////////////////////////////
char FirstNotRepeatingChar(char* pString)
{
      // invalid input
      if(!pString)
            return 0;

      // get a hash table, and initialize it
      const int tableSize = 256;
      unsigned int hashTable[tableSize];
      for(unsigned int i = 0; i < tableSize; ++ i)
            hashTable[i] = 0;

      // get the how many times each char appears in the string
      char* pHashKey = pString;
      while(*(pHashKey) != '\0')
            hashTable[*(pHashKey++)] ++;

      // find the first char which appears only once in a string
      pHashKey = pString;
      while(*pHashKey != '\0')
      {
            if(hashTable[*pHashKey] == 1)
                  return *pHashKey;

            pHashKey++;
      }

      // if the string is empty
      // or every char in the string appears at least twice
      return 0;
}


2011-01-10 20:34
快速回复:腾讯的一道面试题??欢迎讨论
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.015169 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved