免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
楼主: forrestgang

华为面试题(8分钟写出代码) [复制链接]

论坛徽章:
0
发表于 2006-11-14 09:42 |显示全部楼层

这次肯定对了,

我想删除这个回复,我的完整回复在前面,我不知道但是删除不掉,

大家不要看这个了,

我上面有个回复,大家可以看一下了,

我很久没写代码了,都在做网页,你们把代码写下吧

[ 本帖最后由 banboy 于 2006-11-14 10:04 编辑 ]
suanfa111111.gif

论坛徽章:
0
发表于 2006-11-14 09:58 |显示全部楼层
楼上的,解释一下,为什么这么取?

论坛徽章:
0
发表于 2006-11-14 09:58 |显示全部楼层
大侠们看这样可不可以:

1。先把两个数组相加,求平均数(a)。
2。在数组中取出和平均数差最小的一个或多个,如果是一个就分在一组,如果是多个就平均分(奇数个和偶数个一样)。
3。把剩下的元素排序,一次取两个元素(升序或降序),算一下两个元素的和(b)与差(c),取(b-a)和(c-a)绝对值小的那个,如果(b-a)小,把两个元素都加到和小的那个组中去,如果(c-a)小,把b和c中大的那个加到元素和小的那一组,把b和c中小的那个加到数组和大的那一组。

例如:
1,3,5
平均数:3
取3,分为第一组,
取1,5,因为((1+5)-3) > ((5-1)-3),把1分给和大的那组,也就是第一组,把5分给和小的那组,也就是第二组,因为其和为零。
这样,5-(1+3)=1

又例如:
1,5,10,15
平均数:7。75,
先取10,分为第一组,
然后取1,5,因为(7。75-(1+5)) < (7。75-(5-1)),所以把1与5都分给数组和小的那组,也就是第二组,然后取15分给和小的那组,(因为只剩15了)
最后得到:(10+1+5)-15 = 1
差最小。

类推:
1,2,3,4,5,6

分为:
3,1,2,5
4,6

差为:1

不知道这种分法怎么样?
大家参考一下!!

有不对的地方请高手指正!
谢谢!!

论坛徽章:
0
发表于 2006-11-14 10:18 |显示全部楼层
取出所有,大小排序,
最大减最小,
取最接近差值的元素,
放在较小的一组,
直到最后。

论证中。。。。

论坛徽章:
0
发表于 2006-11-14 10:31 |显示全部楼层
想想2个原始人,他们一起采集了一些土豆2n个,他们之前有一个协议,就是采集到的东西都要平分,最好他们会怎么分,会比较公平呢?土豆不进行切割。你拿一个,我拿一个,个数一样,要求分到的总重量差要最小。那他们应该先把所有的土豆按大小排序,某个人先拿最小的,另一个拿次小的放进自己的筐中。接着就是掂一下2个筐,觉得重些的那个人,先拿还没分掉的土豆中最小的。如此反复,直到土豆分完。
大家看看这个法子是不是最公平?

[ 本帖最后由 ccjjhua 于 2006-11-14 10:52 编辑 ]

论坛徽章:
0
发表于 2006-11-14 10:34 |显示全部楼层
原帖由 cMEr 于 2006-11-14 10:18 发表
取出所有,大小排序,
最大减最小,
取最接近差值的元素,
放在较小的一组,
直到最后。

论证中。。。。



这样好像不行,
比如:
1,2,3,4,5,6

结果是不是:
3,5,1
4,2,6

可是不是最佳方案。

论坛徽章:
0
发表于 2006-11-14 10:36 |显示全部楼层

回复 1楼 forrestgang 的帖子

先将数组排序(全排序,两个数组一起排),然后类似如下处理

#include    <iostream>

using namespace std;

void    swap(int &x, int &y)
{
    x = x ^ y;
    y = y ^ x;
    x = y ^ x;
}

int main()
{
    int a[] = {1, 13, 34, 44, 54, 58};
    int b[] = {3, 23, 45, 56, 67, 77};

    int i, sub;
    static  int total = 0;

    for(i = 5; i >=0 ; i--)
    {   
        sub = b - a;
        if(total)
        {
            if((total > 0 && sub > 0) || (total < 0 && sub < 0))
            {
                swap(a, b);
                total -= sub;
            }
            else if((total >0 && sub < 0) || (total < 0 && sub > 0))
                total += sub;

        }
        else
        {
            total = sub;
        }
    }

    cout << "a: " << endl;
    for(i = 0; i < 6; i++)
        cout << a << " " ;
    cout << endl;

    cout << "b: " << endl;
    for(i = 0; i < 6; i++)
        cout << b << " " ;
    cout << endl;

    cout << "total: " << total << endl;
}

[ 本帖最后由 chzht001 于 2006-11-14 10:49 编辑 ]

论坛徽章:
0
发表于 2006-11-14 10:38 |显示全部楼层
类似背包问题,用二叉树来表示,搜索一条从根到叶结点的权最小的路径,时间复杂度是2的n次方

论坛徽章:
0
发表于 2006-11-14 10:57 |显示全部楼层
原帖由 cuicp 于 2006-11-14 10:34 发表



这样好像不行,
比如:
1,2,3,4,5,6

结果是不是:
3,5,1
4,2,6

可是不是最佳方案。



相等时让原最小一组成为最大,不知可行吗?
1,4,7,8,9,11,18,19

1,18,11,7
19,9,8,4

论坛徽章:
0
发表于 2006-11-14 11:05 |显示全部楼层
原帖由 cMEr 于 2006-11-14 10:57 发表



相等时让原最小一组成为最大,不知可行吗?
1,4,7,8,9,11,18,19

1,18,11,7
19,9,8,4


那是因为还没有全排序,全排序时再结合我的处理方法才能得出结果
两数组和之差最小不一定是零,因为有两数组的数个数相同的约束

正确的处理应是先找出最大的和第二大的分别放入两个数组,然后再找除去这两个后的最大的和第二大的,再依据前一次
的差值确定第二次取的最大和第二大的数放进哪一个数组,依次类推

[ 本帖最后由 chzht001 于 2006-11-14 11:13 编辑 ]
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

SACC2019中国系统架构师大会

【数字转型 架构演进】SACC2019中国系统架构师大会
2019年10月31日~11月2日第11届中国系统架构师大会(SACC2019)将在北京隆重召开。四大主线并行的演讲模式,1个主会场、20个技术专场、超千人参与的会议规模,100+来自互联网、金融、制造业、电商等领域的嘉宾阵容,将为广大参会者提供一场最具价值的技术交流盛会。




----------------------------------------

大会官网>>
  

北京盛拓优讯信息技术有限公司. 版权所有 16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122
中国互联网协会会员  联系我们:huangweiwei@it168.com
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP