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


大家来讨论讨论吧,我觉得这个比较有意思,电子词典中就存在相似的问题。。
我想了好久也只想到一些基本的方法,效率也不高,还请大家来晒晒自己的方法吧???
搜索更多相关主题的帖子: 电子词典 字符串 腾讯 
2011-01-10 17:01
马后炮
Rank: 7Rank: 7Rank: 7
等 级:黑侠
帖 子:156
专家分:560
注 册:2010-12-17
收藏
得分:1 
分别统计一下两个字符串里各个字母出现多少次,然后比较次数就行

樱之雪,晓之车
2011-01-10 17:12
gavinsurekam
Rank: 2
等 级:论坛游民
帖 子:15
专家分:15
注 册:2010-12-25
收藏
得分:1 
好想法。
2011-01-10 17:15
huangapple
Rank: 10Rank: 10Rank: 10
等 级:青峰侠
帖 子:545
专家分:1790
注 册:2010-12-30
收藏
得分:1 
先排序,再用函数库中的一个比较两个字符串是否相同的那个strcmp()

勤能补拙,熟能生巧!
2011-01-10 17:35
gavinsurekam
Rank: 2
等 级:论坛游民
帖 子:15
专家分:15
注 册:2010-12-25
收藏
得分:0 
/*
根据楼主的一个简单实现。只做了字母与数字的匹配,读者可以根据你的需要加以更改,如有疑问可以QQ:153612021
愿大家共同进步。

假设两个字符串中所含有的字符和个数都相同我们就叫这两个字符串匹配,
比如:abcda和adabc,由于出现的字符个数都是相同,只是顺序不同,
所以这两个字符串是匹配的。。要求高效
现在需要你来实现下面的函数:
boolen Is_Mach(char *str1,char *str2)
*/

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <malloc.h>

#define MAX_INT 40


int stat(char *str1,int *data)
{
    int i;
    int temp;
    int length;

    if(str1==NULL ||data==NULL)
    {
        printf("point is NULL");
        return -1;
    }
   
    length =strlen(str1);
    for(i =0;i<length;i++)
    {
        if(isdigit(temp=*str1))
        {
            data[temp-'0']++;
        }else{
            if(isupper(temp)){           
                data[temp-'A'+10]++;
            }else{
                data[temp-'a'+10]++;
            }   
        }
        str1++;
    }
   
    for(i =0;i<MAX_INT;i++){
        printf("%d\t",data[i]);
    }
    printf("\n---------------\n");
    return 0;



}


int is_Mach(char *str1,char *str2){

    int a[MAX_INT]={0};
    int b[MAX_INT]={0};


    printf("str1:%s\nstr2:%s\n",str1,str2);
   

    if(strlen(str1)!=strlen(str2)){
        printf("length is not the same\n");
        return -1;
    }
    if(stat(str1,a)==-1 ||stat(str2,b)==-1)
    {
        printf("stat is error");
        return -1;
    }

    for(int i =0;i<MAX_INT;i++)
    {
        if(a[i]!=b[i])
            return -1;
    }
   

    return 0;
}


void main(int argc,char **argv)
{
    char *str1,*str2;
    char *str3 ="abcdefg";
    char *str4 ="bcdefag";

    if(  ((str1=(char*)malloc(sizeof(100*sizeof(char))))==NULL) ||
        ((str1=(char*)malloc(sizeof(100*sizeof(char))))==NULL) )
    {
        printf("malloc is error");

    }

    if(argc==3){
        str1=argv[1];
        str2=argv[2];

        if(is_Mach(str1,str2)==0){
            printf("match\n");
        }else{
            printf("no match\n");
        }
    }else{
        if(is_Mach(str3,str4)==0){
            printf("match\n");
        }else{
            printf("no match\n");
        }
    }



}

[ 本帖最后由 gavinsurekam 于 2011-1-10 18:21 编辑 ]
2011-01-10 18:16
xufan123
Rank: 5Rank: 5
等 级:职业侠客
帖 子:226
专家分:318
注 册:2010-11-15
收藏
得分:1 
四楼的方法不错 
2011-01-10 18:48
Devil_W
Rank: 10Rank: 10Rank: 10
等 级:青峰侠
威 望:9
帖 子:1160
专家分:1797
注 册:2009-9-14
收藏
得分:1 
楼上的,所有的 ,效率 太低了。

我可以做到 O(m+n)的效率。

直接 xor 看最后的结果是不是0.
2011-01-10 18:56
马后炮
Rank: 7Rank: 7Rank: 7
等 级:黑侠
帖 子:156
专家分:560
注 册:2010-12-17
收藏
得分:0 
以下是引用Devil_W在2011-1-10 18:56:34的发言:

楼上的,所有的 ,效率 太低了。
 
我可以做到 O(m+n)的效率。
 
直接 xor 看最后的结果是不是0.
真可惜,这种做法有不低的机率是错的,就是说这种做法只能判断不匹配,而不能判断匹配

樱之雪,晓之车
2011-01-10 19:15
Devil_W
Rank: 10Rank: 10Rank: 10
等 级:青峰侠
威 望:9
帖 子:1160
专家分:1797
注 册:2009-9-14
收藏
得分:0 
以下是引用马后炮在2011-1-10 19:15:39的发言:

真可惜,这种做法有不低的机率是错的,就是说这种做法只能判断不匹配,而不能判断匹配

程序代码:
#include<iostream>
#include<cassert>
#include<cstring>
bool is_Match(const char * str1 , const char * str2)
{
    assert( NULL != str1 && NULL != str2);
    if ( strlen( str1) != strlen( str2 ) )
    {
        return false;
    }
    int ret = static_cast<int>(str1[0]);
    for ( int i=1 ; str1[i] != '\0' ; i ++)
    {
        ret ^= static_cast<int>(str1[i]);
    }
    for ( int i = 0; str2[i] != '\0' ; i ++)
    {
        ret ^= static_cast<int>(str2[i]);
    }
    return ret == 0 ? true:false;
}

int main()
{
    const char *str1 = "abc";
    const char *str2 = "cba";
    if (! is_Match(str1,str2) )
    {
        std::cout<<"Do not Matches"<<std::endl;
    }
    return 0;
}


[ 本帖最后由 Devil_W 于 2011-1-10 19:26 编辑 ]
2011-01-10 19:20
马后炮
Rank: 7Rank: 7Rank: 7
等 级:黑侠
帖 子:156
专家分:560
注 册:2010-12-17
收藏
得分:0 
以下是引用Devil_W在2011-1-10 19:20:08的发言:

 
#include
#include
#include
bool is_Match(const char * str1 , const char * str2)
{
    assert( NULL != str1 && NULL != str2);
    if ( strlen( str1) != strlen( str2 ) )
    {
        return false;
    }
    int ret = static_cast(str1[0]);
    for ( int i=1 ; str1 != '\0' ; i ++)
    {
        ret ^= static_cast(str1);
    }
    for ( int i = 0; str2 != '\0' ; i ++)
    {
        ret ^= static_cast(str2);
    }
    return ret == 0 ? true:false;
}
 
int main()
{
    const char *str1 = "abc";
    const char *str2 = "cba";
    if ( is_Match(str1,str2) )
    {
        std::cout<<"Matches"<

哎,原来是一个自以为是的家伙。。。无语了

    const char *str1 = "abcaa";
    const char *str2 = "cba";
拿去试

或者
    const char *str1 = "abcaa";
    const char *str2 = "cbabb";

随便你

樱之雪,晓之车
2011-01-10 19:25
快速回复:腾讯的一道面试题??欢迎讨论
数据加载中...
 
   



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

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