| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 6505 人关注过本帖
标题:腾讯的一道面试题??欢迎讨论
只看楼主 加入收藏
马后炮
Rank: 7Rank: 7Rank: 7
等 级:黑侠
帖 子:156
专家分:560
注 册:2010-12-17
收藏
得分:0 
以下是引用missiyou在2011-1-15 09:35:29的发言:


类似的问题是很多,我已经找到解决的办法,就是奇偶性的问题。我只要加一句话就行了
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;
}

这样这个方法,就可以解决上面任何类似的问题了
我无语了,你以为这样可以逃避吗???这样下去,你的算法依旧一直不正确,你只是无聊在消耗时间罢了,为什么就不听我说的?
而且你自己还懒得帮自己找反例,这是写程序的应该有的严谨态度吗?
反例拿去 "ACACE", "BBBBJ"

下不为例,请你自重

樱之雪,晓之车
2011-01-15 10:31
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
收藏
得分:0 
不知道这题有没有测试,我想腾讯不会要一个排序的吧。。。。。。

欢迎来到我的博客:http://blog..cn/noisunyuhong
2011-01-15 10:57
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
收藏
得分:0 
不排序也可以,开二个长度26的数组,然后如果是a就加1,以此类推,最后比较就行了

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

不知道这题有没有测试,我想腾讯不会要一个排序的吧。。。。。。
简单提醒你一句,在字符串较长的时候,排序比统计法慢了好几倍,越长越慢,只是增长比例不快,因为是logn的增长

樱之雪,晓之车
2011-01-15 11:01
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
收藏
得分:0 
是啊,所以我刚才就想到了统计法

欢迎来到我的博客:http://blog..cn/noisunyuhong
2011-01-15 11:02
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
收藏
得分:0 
统计法:
程序代码:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int Is_match(char a[1000],char b[1000])
{
    int word_a[26]={0},word_b[26]={0};
    int i,ok=0;
    if(strlen(a)!=strlen(b)||strlen(a)==0||strlen(b)==0)
    return 0;
    for(i=0;i<strlen(a);i++)
        word_a[a[i]-64]++;
    for(i=0;i<strlen(b);i++)
        word_b[b[i]-64]++;
    for(i=0;i<strlen(a);i++)
        if(word_a[i]==word_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",ans);
    system("pause");
    return 0;
}


欢迎来到我的博客:http://blog..cn/noisunyuhong
2011-01-15 11:18
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
收藏
得分:0 
回复 40楼 huangapple
冒泡也敢摆上来,汗

欢迎来到我的博客:http://blog..cn/noisunyuhong
2011-01-15 11:22
马后炮
Rank: 7Rank: 7Rank: 7
等 级:黑侠
帖 子:156
专家分:560
注 册:2010-12-17
收藏
得分:0 
int Is_match(char a[], char b[])
{
    int word[ 256 ] = {0};
    int i, len = strlen(a);
    if( len != strlen(b))
        return 0;
    // if (len < 64) return sortmatch(a, b); //这里再实现一个排序比较就好了,如果你觉得需要
    for(i = 0; i < len; i++)
        word[ a[i] ]++, word[ b[i] ]--;
    for(i = 1; i<256; i++)
        if(word[ i ] != 0)
            return 0;
    return 1;
}

A串的写法

樱之雪,晓之车
2011-01-15 11:41
BlueGuy
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:29
帖 子:4476
专家分:4055
注 册:2009-4-18
收藏
得分:0 
我觉得用冒泡排序解决这题就已经给足腾迅的面子了

我就是真命天子,顺我者生,逆我者死!
2011-01-15 11:50
菜鸟学c语言
Rank: 1
来 自:长沙
等 级:新手上路
帖 子:1
专家分:1
注 册:2011-1-16
收藏
得分:1 
以下是引用__c__在2011-1-10 23:39:44的发言:

2楼的方法好.按2楼的方法的一种实现
 int
is_match (const char *s1, const char *s2)
{
  signed int *pi;
  /* count用来记录各个字符的个数,是s1中的字符则加1,s2中的字符则减1.
   * 如果匹配成功,那么各个字符的数目应该是0。对于普通字符而言,只要
   * 数组有128个元素就可以了,分配129个元素并把第129个元素count[128]
   * 初始化为-1,这个元素起着哨兵的作用,在检查各个元素的数目是不是
   * 为0的时候,可以少一个if条件语句,可以少量提高效率。           */
  signed int count[129] = { [128]=-1 };
  
  for ( ; ; )
    {
    /*  */
    ++ count[ (int)(*s1) ];
    -- count[ (int)(*s2) ];
    ++ s1,  ++ s2;
  
    /* 使用&位运算 是为了尽可能的避免 && || if ?: 等语句引起的分支
     * 预测而降低效率 。
     * (*s1!=0) & (*s2!=0) 为1(真)时,表示s1和s2都没有到达字符串尾部。
     * (*s1==0) & (*s2==0) 为1(真)时, 表示s1和s2都刚好到达字符串尾部,
     *   这种情况表示s1和s2的长度是一样长,则退出循环, 进入下一步检验。
     * 如果上面2个if语句都不满足,则s1和s2的长度不一样,返回不匹配。  */
    if ((*s1!=0) & (*s2!=0)) continue;
    if ((*s1==0) & (*s2==0)) break;
    return 0;
    }
   
  /* 如果count数组的某个元素不为0,则退出for循环。当然这绝不会是死循环。
   * 不管s1和s2是不是能匹配,count[128]一定不为0(count[128]==-1)。
   * 如果s1和s2能匹配, 那么 pi 一定是因为指向了count[128]而退出了循环。
   * 也可以这样说,如果 pi没有因指向了count[128]而退出了循环, 则不匹配。
   * 这样 count[128]这个元素起到了哨兵的作用,这样可以少一个if 语句。   */
  for (pi = count; *++pi == 0; ) { }
 
  /* 如果pi指向了 count[128](等价于pi-count==128)
   * 那么返回匹配成功;             否则失败。    */
  return ((unsigned int)(pi - count) == 128);
}
这段代码不能处理空字符串。
如果s1和s2有一个是"\0" 则会出错。
还是这里高手多。

以后就在这里学习c语言了。希望高手不吝赐教。
顺便问下, 上面代码注释里面说到的 分支预测 和 哨兵 分别是什么意思。
哪个高手帮忙解释下,谢谢了先。
2011-01-16 15:35
快速回复:腾讯的一道面试题??欢迎讨论
数据加载中...
 
   



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

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