标题:腾讯的一道面试题??欢迎讨论
只看楼主
zzgzzg00
Rank: 7Rank: 7Rank: 7
等 级:黑侠
威 望:2
帖 子:388
专家分:627
注 册:2010-8-2
得分:1 
感觉2楼的方法很有道理啊

粗心是大敌
2011-01-10 20:27
BlueGuy
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:29
帖 子:4476
专家分:4055
注 册:2009-4-18
得分:0 
以下是引用马后炮在2011-1-10 20:17:28的发言:

统计法本来就是一种最简单的hash形式(hash函数是f(x) = x),请见5楼代码,可以参考,就是用的统计法,不过只统计了字母,你可以改写为全部字符
这个见解很有深度  /

我就是真命天子,顺我者生,逆我者死!
2011-01-10 20:29
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
马后炮
Rank: 7Rank: 7Rank: 7
等 级:黑侠
帖 子:156
专家分:560
注 册:2010-12-17
得分:0 
谢谢

樱之雪,晓之车
2011-01-10 20:34
点线面
Rank: 8Rank: 8
来 自:NO.-1
等 级:蝙蝠侠
帖 子:525
专家分:980
注 册:2011-1-3
得分:1 
有23楼的思想,不过迟了写

小代码,大智慧
2011-01-10 20:53
zdcko
Rank: 1
等 级:新手上路
帖 子:1
专家分:1
注 册:2011-1-10
得分:1 
  菜鸟阅
2011-01-10 20:54
qq1023569223
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:湖南科技大学
等 级:贵宾
威 望:26
帖 子:2753
专家分:13404
注 册:2010-12-22
得分:1 
我来看热闹的。

   唯实惟新 至诚致志
2011-01-10 21:27
huangapple
Rank: 10Rank: 10Rank: 10
等 级:青峰侠
帖 子:545
专家分:1790
注 册:2010-12-30
得分:0 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void Sort(char *str)//对数组排序
{
    int i,j,n;
    char c;
    for (i=0;str[i]!='\0';++i);
    n=i-1;
    for (j=0;j<n;++j)
    {
        for(i=0;i<n-j;++i)
        {
            if(str[i]>str[i+1])
            {
                c=str[i];
                str[i]=str[i+1];
                str[i+1]=c;
            }
        }
    }
}
bool Is_Mach(char *str1,char *str2)//判断数组是否相同
{
    if(strcmp(str1,str2)==0)
        return 1;//相同返回1;
    else
        return 0;
}
int main()
{   
    char str1[10]={"asxfghjkl"},str2[10]={"lkjhgfdsa"};//一个例子。。你自己可以改,可以改大小,也可以改成自己输入的。。。
    Sort(str1);
    Sort(str2);
    if(Is_Mach(str1,str2))
        printf("Yes\n");
    else
        printf("No\n");
    return 0;
}

勤能补拙,熟能生巧!
2011-01-10 22:27
xdzsm
Rank: 2
等 级:论坛游民
帖 子:137
专家分:99
注 册:2010-10-26
得分:1 
强大!思维的火花!
2011-01-10 22:42
freemacom
Rank: 1
来 自:圣雪山
等 级:新手上路
帖 子:10
专家分:6
注 册:2010-8-28
得分:1 
我觉得二楼的方法好,以前看数据结构书有类似的题,解法也类似二楼

泪舞城下雪,风吹河上春。
回首镜花月,东水笑红尘。
2011-01-10 22:49



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-330905-1-1.html




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

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