| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 6505 人关注过本帖
标题:腾讯的一道面试题??欢迎讨论
只看楼主 加入收藏
missiyou
Rank: 5Rank: 5
等 级:贵宾
威 望:16
帖 子:531
专家分:218
注 册:2007-10-9
收藏
得分:0 
以下是引用BlueGuy在2011-1-14 14:45:06的发言:

你上次发的那个流程图工具能再共享一次吗 ??

那个我也不用! 感觉没啥用! 我都不知道扔那去了!
2011-01-14 17:21
马后炮
Rank: 7Rank: 7Rank: 7
等 级:黑侠
帖 子:156
专家分:560
注 册:2010-12-17
收藏
得分:0 
以下是引用missiyou在2011-1-14 17:16:31的发言:

bool Is_Mach(char *str1,char *str2)  
{  
    int length1, length2;  
    length1 = length2 =  0;  
 
    if(str1 == NULL || str2 == NULL)  
        return false;  
    if(strlen(str1) == strlen(str2))  
    {  
        int len = strlen(str1);
        if (str1[len -1] == str2[len -1])
        {
            len = len -1;
        }
        while(*str1 != '\0')  
        {  
            if(*str1 != *str2)
            {   
                length2 += *str2 % len;
                length1 += *str1 % len;  
            }
            ++str1;  
            ++str2;  
        }  
        if(length1 == length2)  
            return true;  
    }  
    return false;  
}
传最后一次修改! 总之就是针对出现问题去改进!  
小小测试一下,没出问题!在贴上来,请求数据验证!
一个数字上证明这个算法是错误的办法:
整数length1和length2,最多能表示2^32种不种的结果
而一个字符串,一个字符有255种结果,5个字符的串的组合结果就超过2^32,那么,根据抽屉原理,
必定可以从两个不同的5字符组成的字符串中找到一对结果,能使你的算法是错的

事实上你这个只能验证不match,不能验证一定match,之前我说过了


[ 本帖最后由 马后炮 于 2011-1-14 17:28 编辑 ]

樱之雪,晓之车
2011-01-14 17:27
马后炮
Rank: 7Rank: 7Rank: 7
等 级:黑侠
帖 子:156
专家分:560
注 册:2010-12-17
收藏
得分:0 
#include <string.h>
bool Is_Mach(char *str1,char *str2)
{
    int length1, length2;
    length1 = length2 =  0;

    if(str1 == NULL || str2 == NULL)
        return false;
    if(strlen(str1) == strlen(str2))
    {
        int len = strlen(str1);
        if (str1[len -1] == str2[len -1])
        {
            len = len -1;
        }
        while(*str1 != '\0')
        {
            if(*str1 != *str2)
            {
                length2 += *str2 % len;
                length1 += *str1 % len;
            }
            ++str1;
            ++str2;
        }
        if(length1 == length2)
            return true;
    }
    return false;
}

#include <stdio.h>
int main()
{
    char a[] = "acacacac";
    char b[] = "bbbbbbbb";
    int ret = Is_Mach(a, b); //按要求,理应返回false,不匹配
    printf("%d\n", ret); //按整数输出结果,这里运行得到1,即算法错误
    return 0;
}

//以上是测试代码,再次轻松找到反例,还是请参考我二楼的做法吧

樱之雪,晓之车
2011-01-14 17:34
missiyou
Rank: 5Rank: 5
等 级:贵宾
威 望:16
帖 子:531
专家分:218
注 册:2007-10-9
收藏
得分:0 
我需要数据,理论与实践是有距离的!
2011-01-14 17:35
马后炮
Rank: 7Rank: 7Rank: 7
等 级:黑侠
帖 子:156
专家分:560
注 册:2010-12-17
收藏
得分:0 
如果前面63楼那组不够,再来一个
"adadadad", "bcbcbcbc"
这种组合要多少有多少
关键是,所有的Hash都只是用来验证,而不是证明,只是用特别长的结果降低碰撞的机会,用复杂的迭代让规律难以寻找,像MD5/SHA
而你的Hash方式,要构造碰撞太容易了,规律性太强

樱之雪,晓之车
2011-01-14 18:01
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
收藏
得分:0 
回复 65楼 马后炮
冒昧问一句,为什么不排序呢?

欢迎来到我的博客:http://blog..cn/noisunyuhong
2011-01-14 18:10
马后炮
Rank: 7Rank: 7Rank: 7
等 级:黑侠
帖 子:156
专家分:560
注 册:2010-12-17
收藏
得分:0 
以下是引用sunyh1999在2011-1-14 18:10:53的发言:

冒昧问一句,为什么不排序呢?
如果字符串长度小于64,我就考虑用排序吧,加个if判断一下长度就好了

樱之雪,晓之车
2011-01-14 18:39
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
收藏
得分:0 
如果超过64个为什么就不行了呢?

欢迎来到我的博客:http://blog..cn/noisunyuhong
2011-01-15 09:22
missiyou
Rank: 5Rank: 5
等 级:贵宾
威 望:16
帖 子:531
专家分:218
注 册:2007-10-9
收藏
得分:0 
回复 65楼 马后炮

类似的问题是很多,我已经找到解决的办法,就是奇偶性的问题。我只要加一句话就行了
bool Is_Mach(char *str1,char *str2)
{
    int length1, length2;
    length1 = length2 =  0;

    if(str1 == NULL || str2 == NULL)
        return false;
    if(strlen(str1) == strlen(str2))
    {
        int len = strlen(str1);
        //if (str1[len -1] == str2[len -1])
        //{
        //    len = len -1;
       // } //这里已经是一个奇偶的一个小判断!但不行
      len = len%2==0 ? len + 1 : len; //就这一句就行了
        while(*str1 != '\0')
        {
            if(*str1 != *str2)
            {
                length2 += *str2 % len;
                length1 += *str1 % len;
            }
            ++str1;
            ++str2;
        }
        if(length1 == length2)
            return true;
    }
    return false;
}

这样这个方法,就可以解决上面任何类似的问题了
2011-01-15 09:35
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
收藏
得分:0 
程序代码:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void Qsort(char *string,int startPos,int endPos)
{
    int  i,j,temp;
    temp=string[startPos];
    i=startPos,j=endPos;
    while(i<j)
    {
    while(temp<=string[j]&&i<j)j--;
    string[i]=string[j];
    while(temp>=string[i]&&i<j)i++;
    string[j]=string[i];
    }
    string[i]=temp;
    if(i-1>startPos)Qsort(string,startPos,i-1);
    if(i+1<endPos)Qsort(string,i+1,endPos);
}
int Is_match(char *a,char *b)
{
    int ok=0,i;
    if(strlen(a)!=strlen(b)||strlen(a)==0||strlen(b)==0)
        return 0;
    Qsort(a,0,strlen(a)-1);
    Qsort(b,0,strlen(b)-1);
    for(i=0;i<strlen(a);i++)
    {
    if(a[i]==b[i])
    ok=1;
    else
    return 0;
    }
    return ok;
}
int main()
{
    char a[1000],b[1000];
    int ans=0;
    gets(a);gets(b);
    ans=Is_match(a,b);
    printf("%d\n",ans);
    system("pause");
    return 0;
}
写好了,有什么问题吗?

欢迎来到我的博客:http://blog..cn/noisunyuhong
2011-01-15 09:52
快速回复:腾讯的一道面试题??欢迎讨论
数据加载中...
 
   



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

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