| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 3719 人关注过本帖, 1 人收藏
标题:两道面试题的解答,找工作的兄弟看过来~~~
只看楼主 加入收藏
hfzhang77
该用户已被删除
收藏
得分:0 
回复 36楼 kingsroot
提示: 作者被禁止或删除 内容自动屏蔽
2010-05-02 18:00
wsj3000
Rank: 3Rank: 3
等 级:论坛游侠
威 望:1
帖 子:78
专家分:161
注 册:2009-8-4
收藏
得分:0 
回复 40楼 StarWing83
恩,如果arr[34]=0;运算结果为:34,应该是0,请再修改下~~~~
2010-05-02 18:22
jcslt
Rank: 8Rank: 8
来 自:90-xx.com
等 级:蝙蝠侠
帖 子:251
专家分:975
注 册:2009-10-10
收藏
得分:0 
ACM的东东,还以为什么呢!顶Devil_W的。。。

www.
2010-05-02 18:33
StarWing83
Rank: 8Rank: 8
来 自:仙女座大星云
等 级:贵宾
威 望:19
帖 子:3951
专家分:748
注 册:2007-11-16
收藏
得分:0 
回复 42楼 wsj3000
恩,第一版本是有问题,现在是对的了,你看看。

专心编程………
飞燕算法初级群:3996098
我的Blog
2010-05-02 19:00
wsj3000
Rank: 3Rank: 3
等 级:论坛游侠
威 望:1
帖 子:78
专家分:161
注 册:2009-8-4
收藏
得分:0 
回复 44楼 StarWing83
嗯,正确了~~~~,嗯,顺便写下思路把,我比较笨看不太懂代码----顺便方便大伙~~~~
还有,第一题用dp算法写出来把,最大公串,不允许分开,呵呵,我的算法是完全自己想的,可能不是太高级~~~~
2010-05-02 19:56
BlueGuy
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:29
帖 子:4476
专家分:4055
注 册:2009-4-18
收藏
得分:0 
回复 45楼 wsj3000
没难度啊,
#include <stdio.h>
#include <string.h>
{
    char *blue = "adbccadebbca";
    char *guy = "adabccadece";

    int i, j, k, flag, max, count;

    flag = max = count = 0;
   
    for (i = 0; blue[i]; i++)
    {
        k = i;
        for (j = 0; guy[j] && guy[k]; )
        {
            
            if (guy[k++] == blue[k++])
            {
               
                count++;
                if (count > max)
                {
                    flag = i;
                    max = count;
                    count = 0;
                }
               
            }
            
            else
            {
                k = i;
                j++;
            }
        }
    }

    for (i = flag; i < flag+max; i++)
        printf("%c", blue[i]);
   
    return 0;
}

[ 本帖最后由 BlueGuy 于 2010-5-2 20:10 编辑 ]

我就是真命天子,顺我者生,逆我者死!
2010-05-02 20:08
StarWing83
Rank: 8Rank: 8
来 自:仙女座大星云
等 级:贵宾
威 望:19
帖 子:3951
专家分:748
注 册:2007-11-16
收藏
得分:0 
额,我写出来一个分开的,发现如果不分开得统计每一段的长度= =发现写起来有点麻烦= =||||所以想看看有没有别的方法。

专心编程………
飞燕算法初级群:3996098
我的Blog
2010-05-02 20:30
wsj3000
Rank: 3Rank: 3
等 级:论坛游侠
威 望:1
帖 子:78
专家分:161
注 册:2009-8-4
收藏
得分:0 
回复 46楼 BlueGuy
额,请先编译运行下吧,我编译测试结果是不对的~~~~
2010-05-02 21:24
StarWing83
Rank: 8Rank: 8
来 自:仙女座大星云
等 级:贵宾
威 望:19
帖 子:3951
专家分:748
注 册:2007-11-16
收藏
得分:0 
对于第一题,可以构建trie,复杂度是O(|A|^2 + |B|^2),不知道有没有更好的……

专心编程………
飞燕算法初级群:3996098
我的Blog
2010-05-03 00:00
StarWing83
Rank: 8Rank: 8
来 自:仙女座大星云
等 级:贵宾
威 望:19
帖 子:3951
专家分:748
注 册:2007-11-16
收藏
得分:5 
我觉得自己脑残了…………第一题有非常非常简单的DP方法…………

程序代码:
#include <stdio.h>
#include <string.h>

int main(void)
{
    char *a = "adbccadebbca", *b = "edabccadece";
    int i, j;
    int len_a = strlen(a), len_b = strlen(b);
    int dp[2][101] = {};
    int max_begin, max_len = 0;

    for (i = 1; i <= len_a; ++i)
        for (j = 1; j <= len_b; ++j)
        {
            int i_idx = i%2;

            if (a[i-1] == b[j-1])
            {
                dp[i_idx][j] = dp[(i-1)%2][j-1] + 1;
                if (dp[i_idx][j] > max_len)
                {
                    max_begin = i - dp[i_idx][j];
                    max_len = dp[i_idx][j];
                }
            }
            else
                dp[i_idx][j] = 0;
        }
   
    printf("%.*s\n", max_len, a + max_begin);
    return 0;
}


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



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

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