| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 3719 人关注过本帖, 1 人收藏
标题:两道面试题的解答,找工作的兄弟看过来~~~
只看楼主 加入收藏
kingsroot
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:1
帖 子:284
专家分:1159
注 册:2010-3-28
收藏
得分:0 
你可以吧代码编译了  自己运行  看对头不 ~~~~
2010-05-01 23:33
kingsroot
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:1
帖 子:284
专家分:1159
注 册:2010-3-28
收藏
得分:0 
如果你还没理解  我建议你加我QQ  我慢慢给你解释~~~(什么是数学里面的构造数~~~~~~)你的第1个问题 我明天给你贴个代码  个人觉得比你的那个好  嘿嘿
2010-05-01 23:53
Devil_W
Rank: 10Rank: 10Rank: 10
等 级:青峰侠
威 望:9
帖 子:1160
专家分:1797
注 册:2009-9-14
收藏
得分:0 
你们真的是一叶遮目,第一题就是一DP求解,代码我已经贴了。O(n^2)的效率。你们那贴的能叫代码啊?
2010-05-02 00:50
wsj3000
Rank: 3Rank: 3
等 级:论坛游侠
威 望:1
帖 子:78
专家分:161
注 册:2009-8-4
收藏
得分:0 
回复 32 33楼 Devil_W
32楼:
这样吧,你补全下面的search_same(int arr[], int n);函数的定义:
程序代码:
#include <stdio.h>

int search_same(int arr[], int n);

int main()
{
    int arr[100];
    int i;

    for(i=0; i<100; i++){
        arr[i] = i;
    }
    arr[34] = 58;

    fprintf(stdout, "The same one:%d\n", search_same(arr, 100));

    return 0;
}
上面缺失34,重复58,请写出你的算法找出重复的数58.

33楼:
我编译了你写的程序,用 ,“adbccadebbca”和“edabccadece”测试,得到结果:dbccadec
恩,这个结果是不对的,可以看出来正确的是:bccade 建议你再改改代码,正确了再发上来好吗?
2010-05-02 09:57
Devil_W
Rank: 10Rank: 10Rank: 10
等 级:青峰侠
威 望:9
帖 子:1160
专家分:1797
注 册:2009-9-14
收藏
得分:0 
程序代码:
#include <vector>
#include <string>
#include <iostream>

template <typename T>
void LCS(const T& s1, const T& s2, T& s3)
{
    const size_t len1 = s1.size();
    const size_t len2 = s2.size();
    std::vector< std::vector<unsigned int> > d(len1 + 1, std::vector<unsigned int>(len2 + 1));
    std::vector< std::vector<unsigned int> > b(len1 + 1, std::vector<unsigned int>(len2 + 1));
    const int w = 1;
    const int n = 2;
    const int nw = 3;
    for(int i = 1; i <= len1; ++i)
    {
    for(int j = 1; j <= len2; ++j)
    {  
        if (s1[i-1] == s2[j-1])
        {
        d[i][j] = d[i-1][j-1]+1;
        b[i][j] = nw;
        }
        else
        {  
        if (d[i-1][j] >= d[i][j-1])
        {
            d[i][j] = d[i-1][j];
            b[i][j] = n;
        }
        else
        {
            d[i][j] = d[i][j-1];
            b[i][j] = w;
        }
        }
    }
    }
    s3.resize(d[len1][len2]);
    int i=len1;
    int j=len2;
    int k=d[len1][len2]-1;
    while ( k>=0 && i>0 && j>0 )
    {
    if ( b[i][j] == nw )
    {
        s3[k--] = s1[i-1];
        i -- ;
        j -- ;
    }      
    else if (b[i][j] == n)
        i -- ;
    else if (b[i][j] == w)
        j --;
    else
        break;
    }
}
int main(int argc, char * argv[])
{  
    std::string s1("adbccadebbca");
    std::string s2("edabccadece");
    std::string s3;
    LCS(s1, s2, s3);
    std::cout<< s3 <<std::endl;
    return 0;
}
2010-05-02 12:40
kingsroot
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:1
帖 子:284
专家分:1159
注 册:2010-3-28
收藏
得分:0 
  我错了  我原来的代码始终把相同的数放在最后一位上,这样无形中固定了一个变元,所以可以求得出来,但是如果相同数不在最后一位的话 相当于解2个变元, 没办法求解  
2010-05-02 16:40
wsj3000
Rank: 3Rank: 3
等 级:论坛游侠
威 望:1
帖 子:78
专家分:161
注 册:2009-8-4
收藏
得分:0 
回复 35楼 Devil_W
我再次编译了你写的程序,还是用“adbccadebbca”和“edabccadece”测试,得到结果:abccadec
恩,这个结果是不对的,可以看出来正确的是:bccade 建议你再改改代码,测试正确了再发上来好吗?
2010-05-02 17:04
StarWing83
Rank: 8Rank: 8
来 自:仙女座大星云
等 级:贵宾
威 望:19
帖 子:3951
专家分:748
注 册:2007-11-16
收藏
得分:0 
devil求的是最长公共子序列,子序列的定义是“顺序一致的字符序列”,可以分隔来,而LZ的题目要求必须不可分隔,哈哈~~

专心编程………
飞燕算法初级群:3996098
我的Blog
2010-05-02 17:17
Devil_W
Rank: 10Rank: 10Rank: 10
等 级:青峰侠
威 望:9
帖 子:1160
专家分:1797
注 册:2009-9-14
收藏
得分:0 
以下是引用StarWing83在2010-5-2 17:17:15的发言:

devil求的是最长公共子序列,子序列的定义是“顺序一致的字符序列”,可以分隔来,而LZ的题目要求必须不可分隔,哈哈~~

 哼哼, 懂我的,这里只有几个人而已。

 跟智商低的人,不必要求的太高。

 他也许这辈子都不知道什么是DP.

[ 本帖最后由 Devil_W 于 2010-5-2 17:35 编辑 ]
2010-05-02 17:32
StarWing83
Rank: 8Rank: 8
来 自:仙女座大星云
等 级:贵宾
威 望:19
帖 子:3951
专家分:748
注 册:2007-11-16
收藏
得分:8 
先给出一个第二题的代码吧:

程序代码:
int search_same(int arr[], int n)
{
    int i, xor = 0, a = 0, b = 0;

    for (i = 0; i < n; ++i)
        xor ^= arr[i] ^ i;
    xor -= xor & (xor - 1);

    for (i = 0; i < n; ++i)
    {
        (void)((i & xor) ? (a ^= i) : (b ^= i));
        (void)((arr[i] & xor) ? (a ^= arr[i]) : (b ^= arr[i]));
    }

    /* notice that onluy one number in a and b is the dupicate one */
    for (i = 0; i < n; ++i)
        if (arr[i] == a)
            return a;
    return b;
}

第一题还在写……好久没写DP了,汗……(其实devil的代码稍微改一点点就可以做第一题了)


[ 本帖最后由 StarWing83 于 2010-5-2 18:06 编辑 ]

专心编程………
飞燕算法初级群:3996098
我的Blog
2010-05-02 17:48
快速回复:两道面试题的解答,找工作的兄弟看过来~~~
数据加载中...
 
   



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

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