| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 3719 人关注过本帖, 1 人收藏
标题:两道面试题的解答,找工作的兄弟看过来~~~
只看楼主 加入收藏
hahayezhe
Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
来 自:湖南张家界
等 级:贵宾
威 望:24
帖 子:1386
专家分:6999
注 册:2010-3-8
收藏
得分:5 
楼主是来骗作业的 code里面什么都没有

第二题 如果是0-99个100个连续的数字里存在相同的两个数并少一个数 还可以做做 1-99那面试官脑袋进水了

鄙视下
2010-05-01 19:02
Devil_W
Rank: 10Rank: 10Rank: 10
等 级:青峰侠
威 望:9
帖 子:1160
专家分:1797
注 册:2009-9-14
收藏
得分:2 
太基本的题目, 你看看你的第一个题目的答案还对?

第2个题目,直接我可以在最坏的效率O(n)里面求出来。

太简单了。

程序代码:
#include<iostream>
#include<cstring>
#include<climits>
#define LEN(x) ((strlen(x))-0)
using namespace std;
class LCS{
private:
    char * str1;
    char * str2;
    int **c;
    int **b;
protected:
    void Print(int i,int j)
    {
        if( i==0 || j == 0)
        return;
        if( b[i][j]== 0)
        {
        Print(i-1,j-1);
        cout<<str1[i];
        }
        else if( b[i][j] == -1)
        Print(i,j-1);
        else
        Print(i-1,j);
    }
public:
    LCS(){
    str1=" adbccadebbca";
    str2=" edabccadece";
    c=new int * [LEN(str1)+1];
    b=new int * [LEN(str1)+1];
    for(int i=0;i<LEN(str1)+1;i++)
    {
        c[i]=new int[LEN(str2)+1];
        b[i]=new int[LEN(str2)+1];
    }
    }
    ~LCS()
    {
        for(int i=0;i<LEN(str1)+1;i++)
        {
        delete [] c[i];
        delete [] b[i];
        }
        delete [] c;
        delete [] b;
    }
    int LCS_Lenth()
    {
        for(int i=0;i<=LEN(str1);i++)
        {
        c[i][0]=0;
        }
        for(int j=0;j<=LEN(str2);j++)
        {
        c[0][j]=0;
        }
        for(int i=1;i<=LEN(str1);i++)
        {
        for(int j=1;j<LEN(str2);j++)
            c[i][j]=INT_MIN;
        }
        for(int i=1;i<LEN(str1);i++)
        {
        for(int j=1;j<LEN(str2);j++)
        {
            if( str1[i]==str2[j])
            {
            c[i][j]=c[i-1][j-1]+1;
            b[i][j]=0;
            }
            else if( c[i-1][j]<c[i][j-1])
            {
            c[i][j]=c[i][j-1];
            b[i][j]=-1;
            }
            else
            {
            c[i][j]=c[i-1][j];
            b[i][j]=1;
            }
         
        }
        }
        return c[LEN(str1)-1][LEN(str2)-1];
    }
    void LCS_Path(){
    Print(LEN(str1)-1,LEN(str2)-1);
    cout<<endl;
    }
};
int main()
{
    LCS lcs;
    cout<<lcs.LCS_Lenth()<<endl;
    lcs.LCS_Path();
    return 0;
}

2010-05-01 19:58
Devil_W
Rank: 10Rank: 10Rank: 10
等 级:青峰侠
威 望:9
帖 子:1160
专家分:1797
注 册:2009-9-14
收藏
得分:0 
第2个题目,直接顺序查找,如果先查A[0], 假设A[0]=k,接着查A[k],并把A[0]做个mark,表示查过了。

接着再差A[A[k]]以此类退,重复Mark的那个就是重复的数字了。

这种低级的问题,你也就只能跟菜鸟秀秀了。
2010-05-01 20:01
hahayezhe
Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
来 自:湖南张家界
等 级:贵宾
威 望:24
帖 子:1386
专家分:6999
注 册:2010-3-8
收藏
得分:0 
我就不明白了 所谓术业有专攻
你在算法上确实强 可以其他呢 汇编 C C++ SDK MFC .net 数据库你都学通了
怎么老喜欢拿自己的长处来比呢!
2010-05-01 20:21
Devil_W
Rank: 10Rank: 10Rank: 10
等 级:青峰侠
威 望:9
帖 子:1160
专家分:1797
注 册:2009-9-14
收藏
得分:0 
以下是引用hahayezhe在2010-5-1 20:21:32的发言:

我就不明白了 所谓术业有专攻
你在算法上确实强 可以其他呢 汇编 C C++ SDK MFC .net 数据库你都学通了
怎么老喜欢拿自己的长处来比呢!

我不找你麻烦,你也别自讨没趣。
2010-05-01 20:27
BlueGuy
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:29
帖 子:4476
专家分:4055
注 册:2009-4-18
收藏
得分:0 
回复 11楼 hahayezhe
你很聪明,

我就是真命天子,顺我者生,逆我者死!
2010-05-01 20:43
wsj3000
Rank: 3Rank: 3
等 级:论坛游侠
威 望:1
帖 子:78
专家分:161
注 册:2009-8-4
收藏
得分:0 
回复 10楼 hahayezhe
题目我也是在网上找到的,原题就是这样的,可能是要考您的洞察能力吧~~~,不太清楚;这可能是最简单的方法了~~~~
2010-05-01 20:44
wsj3000
Rank: 3Rank: 3
等 级:论坛游侠
威 望:1
帖 子:78
专家分:161
注 册:2009-8-4
收藏
得分:0 
回复 11楼 hahayezhe
恩,,没话说了,我居然没有发现这个,汗~~~,不好意思,按你说的改了。~~~ths
2010-05-01 20:48
wsj3000
Rank: 3Rank: 3
等 级:论坛游侠
威 望:1
帖 子:78
专家分:161
注 册:2009-8-4
收藏
得分:0 
回复 12 13楼 Devil_W
不好意思,看不懂c++;恩,说下大致思路好吗?

恩,第二题的思路:
第2个题目,直接顺序查找,如果先查A[0], 假设A[0]=k,接着查A[k],并把A[0]做个mark,表示查过了。
接着再差A[A[k]]以此类退,重复Mark的那个就是重复的数字了。

按照你的思路,如果k=0呢? 或则A[A[k]]=0呢,又回去查啊A[0]了,还好打了标记,所以可以继续向后查,但是却重复查找了!
应该是从a[0]到a[99],把a[k]打标记,而且打标记的方法是加上模100,取得时候全部按模100取值,然后哪个取值前大于等于100了,就是重复的那个。

[ 本帖最后由 wsj3000 于 2010-5-1 23:28 编辑 ]
2010-05-01 20:55
BlueGuy
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:29
帖 子:4476
专家分:4055
注 册:2009-4-18
收藏
得分:0 
回复 12楼 Devil_W
你的代码也很牛B

我就是真命天子,顺我者生,逆我者死!
2010-05-01 20:55
快速回复:两道面试题的解答,找工作的兄弟看过来~~~
数据加载中...
 
   



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

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