免费注册 查看新帖 |

Chinaunix

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

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

论坛徽章:
0
发表于 2006-11-14 12:48 |显示全部楼层
t1=a1的和+a2的和;
结果数组=空数组;
循环开始(所有的数组组合情况)
{
  t2=绝对值(新数组a-新数组b);
  if( t2< t1)
  {
       t1=t2;
       结果数组CLEAR();
       结果数组ADD(t2);
  } else if(t2==t1)
  {
      结果数组ADD(t2);
  }
}
return 结果数组;

如果有完善的数据结构开发包。3分钟就够了。其中30秒用来考虑,2分用来写程序,30秒用来编译运行

论坛徽章:
0
发表于 2006-11-14 13:35 |显示全部楼层
原帖由 seaway 于 2006-11-14 12:48 发表
t1=a1的和+a2的和;
结果数组=空数组;
循环开始(所有的数组组合情况)
{
  t2=绝对值(新数组a-新数组b);
  if( t2< t1)
  {
       t1=t2;
       结果数组CLEAR();
       结果数组ADD(t2 ...



高,实在是高,
呵呵,把所有的组合都试一遍,差最小的组合记下来,
不就行了?
不过要麻烦一下计算机大哥了,
可以算一下一共有多少种组合,
如果两个数组元素和是n,那么全面覆盖的次数大概是:
n+n*(n-1)+n*(n-1)*(n-2)...

这个对不对?要怎么算呢?大学的课程都忘光了!
如果要短时间内完成的话,这可能是个好办法!

论坛徽章:
0
发表于 2006-11-14 13:59 |显示全部楼层
应该是将两个数组作为一个数组进行冒泡排序。
a[0],b[0],a[1],b[1],......

论坛徽章:
0
发表于 2006-11-14 14:11 |显示全部楼层
原帖由 sithui 于 2006-11-13 09:33 发表
先整体排序,再交叉取数

英雄所见略同。

论坛徽章:
0
发表于 2006-11-14 14:17 |显示全部楼层
n+n*(n-1)+n*(n-1)*(n-2)...

这个好像算错了,是不是要除个2?

排列组合,忘光了!

:)

论坛徽章:
0
发表于 2006-11-14 14:19 |显示全部楼层
原帖由 seaway 于 2006-11-14 12:48 发表
t1=a1的和+a2的和;
结果数组=空数组;
循环开始(所有的数组组合情况)
{
  t2=绝对值(新数组a-新数组b);
  if( t2< t1)
  {
       t1=t2;
       结果数组CLEAR();
       结果数组ADD(t2 ...


你做的很快,但计算机恐怕要累死了

论坛徽章:
0
发表于 2006-11-14 14:26 |显示全部楼层
方案1.将a、b两个数组合成一个数组c(无需排序),清空a、b两数组。任取c中一个数据i,然后在c中查找与i差值最小的j,i放入a中,就放入b中,然后在c中去掉i和j;再次在c中任取一个数据i,然后在c中查找与i差值最小的j,i放入b中,j放入a中。(即奇数次取在数组a中,偶数次取在数组b中)。(注,两个n相加一定为偶数)

方案2. 将a、b两个数组合成一个数组c(2n个数据,无需排序),将所有数据相加,然后除以2,值记为i,然后随意组合n个数据相加,取和最接近i的组合为a,余下为b


[ 本帖最后由 dalianpansky 于 2006-11-14 15:01 编辑 ]

论坛徽章:
1
IT运维版块每日发帖之星
日期:2016-06-18 06:20:00
发表于 2006-11-14 14:38 |显示全部楼层

经过简单的验证,发现greensky_34的算法是对的啊。

原帖由 greensky_34 于 2006-11-14 00:28 发表


完整的程序是这样的,可以参考一下
[code]
#include <stdio.h>
#include <math.h>

#define N 10

void ary_init(int a[], int b[]){ //初始化数组
    int i;
    for (i=0; i<N; i ...



经过简单的验证,发现greensky_34的算法是对的啊。大家不要想得太复杂了。
{1,2,3}  {0,0,999}
{1,2,3,4,5,6} {7,8,9,10,11,12}

[ 本帖最后由 crazy_li 于 2006-11-14 14:39 编辑 ]

论坛徽章:
0
发表于 2006-11-14 14:44 |显示全部楼层
可以先做好个大致差不多的,再进行微调

论坛徽章:
0
发表于 2006-11-14 15:13 |显示全部楼层
假设sum(a)>sum(b)
(1)选取a中第i个数,b中第j个数,满足ai-bj < sum(a)-sum(b)。交换ai和bj。
(2)重新计算sum(a)和sum(b)
(3)重复步骤1和2直到条件1不能再满足。
(4)输出a和b
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

SACC2019中国系统架构师大会

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

限时8.5折扣期:2019年9月30日前


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

大会官网>>
  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP