免费注册 查看新帖 |

Chinaunix

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

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

论坛徽章:
0
发表于 2006-11-15 15:43 |显示全部楼层
原帖由 mill888 于 2006-11-13 17:29 发表
8分钟就能写出正确方法的人,建议就不要去华为了,应当去更好的公司。
招聘中,建议华为公司应当定好自己的位。


华为一直都“定得好好”的...

华为有限两次打电话叫我去面试都是催我还债的口气。真让人恶心。

论坛徽章:
0
发表于 2006-11-15 16:06 |显示全部楼层
原帖由 xmyth 于 2006-11-14 17:04 发表
当前数组a和数组b的和之差为
A = sum(a) - sum(b)

a的第i个元素和b的第j个元素交换后,a和b的和之差为
A' = sum(a) - a + b[j] - (sum(b) - b[j] + a)
       = sum(a) - sum(b) - 2 (a - b[j]) ...



牛逼。这种从数学角度来讲述算法的思路非常严谨而且语言直白。受教了。

论坛徽章:
0
发表于 2006-11-15 16:27 |显示全部楼层
for (i = 0; i < n; i++) {
      for (j = 0; j < i; j++)
            if (a[i] < a[j]) {
                tmp[i] = a[j];
                a[i] = b[j];
                b[j] = tmp[i];
            }
      sa += a[i];
      sb += b[i];
}

equal = sa - sb;

论坛徽章:
0
发表于 2006-11-15 18:19 |显示全部楼层
原帖由 hawk2012 于 2006-11-15 11:08 发表
是的, 是这个题目出的有问题,应该说是a b数组和的差的绝对值最小才对,不然我的算法就是最小的。


我说是你的理解有问题,a和b两个数之间的差值就一定是a-b?应该说它们的差值不要存在负数。
就比如说我们之间的年龄差,这是一个正数,地球人都知道

[ 本帖最后由 zwylinux 于 2006-11-15 18:22 编辑 ]

论坛徽章:
0
发表于 2006-11-15 20:14 |显示全部楼层
上面我有发表我的算法,但是有些错误没改过来,现在这个是改进的,应该没什么问题了
#include<stdio.h>
#define SIZE 3
int
sumb (int m[], int n)
{
  int i;
  int sum = 0;
  for (i = 0; i < n; i++)
    sum += m[ i ];
  return sum;
}

main ()
{
  int min;
  int tmp;
  int i;
  int j;
  int this;
  int a[SIZE] = {
    1, 7, 3
  };
  int b[SIZE] = {
    10, 15, 4
  };

  min = sumb (a, SIZE) - sumb (b, SIZE);
  min = min > 0 ? min : (-1) * min;//初始化min,此时min为两个数组总和之差
  for (i = 0; i < SIZE; i++)
    for (j = 0; j < SIZE; j++)
      {
        this = sumb (a, SIZE) - sumb (b, SIZE) + 2 * (b[ j ] - a[ i ]);
        this = this >= 0 ? this : (-1) * this;
        if (this < min)//如果this不小于min的话就不进行交换
          {
            min = this;
            if (min == 0)//如果找到差值为0的组合,则提前退出
              break;
            tmp = a[ i ];
            a[ i ] = b[ j ];
            b[ j ] = tmp;
          }
      }
  printf ("Min=%d\n", min);
}

论坛徽章:
0
发表于 2006-11-15 21:00 |显示全部楼层
先放在用Temp组,放上2组数,然后相加,看看和除以2为多少,然后排序,从大的,开始交叉给数,到最后的时候,参考和除以2这个数,再用小值分配。

论坛徽章:
0
发表于 2006-11-15 22:21 |显示全部楼层
就不能定义个数字??然后取a中与这个数字的差值,再取b中与这个数字的差值然后相加求最小值

论坛徽章:
0
发表于 2006-11-16 08:44 |显示全部楼层
我的想法,先全部加起来求和然后除以2,然后从中找出离sum/2最小的和的数字存放在A数组中,剩下的放在B数组中。
kanwairen 该用户已被删除
发表于 2006-11-16 10:23 |显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽

论坛徽章:
0
发表于 2006-11-16 17:13 |显示全部楼层
原帖由 kevert 于 2006-11-16 08:44 发表
我的想法,先全部加起来求和然后除以2,然后从中找出离sum/2最小的和的数字存放在A数组中,剩下的放在B数组中。


赞成这种方法:

suma = ave + Da
sumb = ave + Db
Da = -Db = (a - b) / 2
ave = (a + b) / 2

找一个数组,其元素之和最接近ave,找寻的方法可以采用回溯法吧
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP