免费注册 查看新帖 |

Chinaunix

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

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

论坛徽章:
0
发表于 2006-11-14 15:18 |显示全部楼层
以下思路如何, 先把a,b合成一个2n的数组C, 然后按照如下规则选取。
  1. a[0] = c [2n-1], b[0] = c[2n-2]
  2. 按照suma>sumb, 取剩下的最大的给b,最小的给a; 反之最大的给a,最小的给b。

程序如下:

#include <stdio.h>
#include <stdlib.h>

static int
intcompare(const void *p1, const void *p2)
{
    int i = *((int *)p1);
    int j = *((int *)p2);

    if (i > j)
        return (1);
    if (i < j)
        return (-1);
    return (0);
}

int change(int *a, int *b, int size)
{
    int *c = (int*) malloc(2*size);
    int pos_a,pos_b,pos_c,pos_cend;
    int sum_a,sum_b;
    int i;

    memcpy(c, a, sizeof(int)*size);
    memcpy(c+size, b, sizeof(int)*size);
   
    qsort((void *)c, 2*size, sizeof (int), intcompare);

    pos_a=pos_b=pos_c=0;
    pos_cend = 2*size-1;
    a[pos_a++] = c[pos_cend--];
    b[pos_b++] = c[pos_cend--];
    sum_a = a[0];
    sum_b = b[0];
   
    while (pos_cend > pos_c ) {
        if (sum_a > sum_b) {
            a[pos_a++] = c[pos_c++];
            b[pos_b++] = c[pos_cend--];
            sum_a += a[pos_a-1];
            sum_b += b[pos_b-1];
        } else {
            a[pos_a++] = c[pos_cend--];
            b[pos_b++] = c[pos_c++];
            sum_a += a[pos_a-1];
            sum_b += b[pos_b-1];
        }
    }
}

int main (int argc, char **argv)
{
    int a[6]= {1, 2, 3,4,5,6};
    int b[6]= {7, 8, 9,10,11,12};
    int i;
   
    change(a,b,6);


    printf("a=");
    for(i=0; i <6; i++)
        printf("%d,",a[i]);
    printf("\n");
    printf("b=");
    for(i=0; i< 6; i++)
        printf("%d,", b[i]);
    printf("\n");
}

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

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

|A| - |A'| = |A| - |A-2x|

假设A > 0,

当x 在 (0,A)之间时,做这样的交换才能使得交换后的a和b的和之差变小,x越接近A/2效果越好,

如果找不到在(0,A)之间的x,则当前的a和b就是答案。

所以算法大概如下:

在a和b中寻找使得x在(0,A)之间并且最接近A/2的i和j,交换相应的i和j元素,重新计算A后,重复前面的步骤直至找不到(0,A)之间的x为止。

[[i] 本帖最后由 xmyth 于 2006-11-14 20:45 编辑 [/i]]

论坛徽章:
0
发表于 2006-11-14 17:42 |显示全部楼层
xmyth 快四年一贴啊.

你说的我看懂了

论坛徽章:
0
发表于 2006-11-14 19:42 |显示全部楼层
原帖由 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,A)之间的x呢?
比如:
1,2,3,4,5,12
最佳方案好像是:
4,5,3
1,2,12

那么0<(3-2)<(15-12)

好像不行呀?
是不是要改进一下结束的条件?
我考虑的对不对?
高手看看!
谢谢!!

论坛徽章:
0
发表于 2006-11-14 20:44 |显示全部楼层
这个结束条件应该是没有问题的

在你说的这个例子里,已经满足了我所提出的结束条件

前面我假设了A>0 (如果A不大于0,对换一下就好了)

所以这里a = {1,2,12}; b = {4,5,3};

x=a[i]-b[j]

所有的x应该都不能满足(0, 3)的条件了,所以满足结束条件了。

论坛徽章:
0
发表于 2006-11-14 20:52 |显示全部楼层
真的只有八分钟吗?字都打不完啊。

论坛徽章:
0
发表于 2006-11-14 20:58 |显示全部楼层
原帖由 xmyth 于 2006-11-14 20:44 发表
这个结束条件应该是没有问题的

在你说的这个例子里,已经满足了我所提出的结束条件

前面我假设了A>0 (如果A不大于0,对换一下就好了)

所以这里a = {1,2,12}; b = {4,5,3};

x=a-b[j]

所有的x ...


我一眼就感觉你那公式很可能是对的
这种类似的题很多的
比如100个红包,7个人分,怎么分才最均匀,是不是更头疼?

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

我也来出个题

论坛徽章:
0
发表于 2006-11-14 21:18 |显示全部楼层
用二重循环把a中的每个元素和b中的每个元素逐个“尝试交换”,
如果是差值变小就维持交换,否则就交换回去,也就是不交换,
每有一次交换,“尝试交换”的二重循环就重新从头开始,
直到没有任何交换使差值变小为止。
这种方法不是很简洁,但的确是可行的。
前边贴出代码的算法,有过一次交换后,循环没有从头开始,所以是错误的。例如a[1]和b[j]交换后,b中的元素改变了,不能再保证a[0]和b[ i ]交换不会使差值变小,这时循环必须从头开始。

  1. #include <stdio.h>
  2. #include <math.h>

  3. #define N 10

  4. void ary_init(int a[], int b[]){ //初始化数组
  5.     int i;
  6.     for (i=0; i<N; i++){
  7.         a[i] = rand()%10000;
  8.     }
  9.     for (i=0; i<N; i++){
  10.         b[i] = rand()%100;
  11.     }
  12.     return;
  13. }
  14. long sum(int a[]){ //数组求和
  15.     int i;
  16.     int s;
  17.     for (s=0,i=0; i<N; i++){
  18.         s += a[i];
  19.     }
  20.     return s;
  21. }

  22. void change(int *a, int *b){ //数组元素交换
  23.     int tmp;
  24.     tmp = *a;
  25.     *a = *b;
  26.     *b = tmp;
  27.     return;
  28. }

  29. void prt_ary(int a[], int b[]){ //列印两数组元素及各自元素和
  30.     int i;
  31.     for(i=0; i<N; i++){
  32.         printf("%5d   ", a[i]);
  33.     }
  34.     printf("\n");
  35.     for(i=0; i<N; i++){
  36.         printf("%5d   ", b[i]);
  37.     }
  38.     printf("\n");
  39.     printf("%d\n", sum(a));
  40.     printf("%d\n", sum(b));
  41. }
  42. int slove(int a[], int b[]){
  43.     int i;
  44.     int j;
  45.     int is_swap = 0;//是否修交换过数据标志
  46.     int ab_diff;

  47.     ab_diff = abs(sum(a)-sum(b));
  48.     for (i=0; i<N; i++){
  49.         for (j=0; j<N; j++){
  50.             change(a+i, b+j);
  51.             if (abs(sum(a)-sum(b)) < ab_diff){//判断是否需要交换元素
  52.                 is_swap = 1; //置位交换标志
  53.                 ab_diff = abs(sum(a)-sum(b)); //更新差值
  54.             }
  55.             else{
  56.                 change(b+j, a+i);//不交换

  57.             }
  58.         }
  59.     }
  60.     return is_swap;
  61. }
  62. int main(){

  63.     int a[N];
  64.     int b[N];

  65.     ary_init(a,b);//数组元素初始化
  66.     prt_ary(a, b);//列印当前数组状态
  67.     while (slove(a, b));//处理数组
  68.     prt_ary(a, b);//列印交换后数组状态
  69.     getch();
  70. }
复制代码

[ 本帖最后由 greensky_34 于 2006-11-14 21:20 编辑 ]

论坛徽章:
0
发表于 2006-11-14 23:14 |显示全部楼层
原帖由 xmyth 于 2006-11-14 20:44 发表
这个结束条件应该是没有问题的

在你说的这个例子里,已经满足了我所提出的结束条件

前面我假设了A>0 (如果A不大于0,对换一下就好了)

所以这里a = {1,2,12}; b = {4,5,3};

x=a-b[j]

所有的x ...


哦,明白了,如果(sum(a) - sum(b)) > (a -b[j]) > 0的话,也就是数组a的和比数组b的和大,
而数组b中有比数组a中小的元素,如果把a和b[j]交换,就可以把数组a和数组b的差缩小,又因为
(sum(a) - sum(b)) > (a -b[j]) ,所以交换后不会出现sum(a) < sum(b)的情况。这样循环调整后,
当整体上sum(a)  > sum(b))时,局部上(数组元素)无法交换了,也就是无法找到符合条件的x了。

呵呵,本人天生比较笨,要想一想才能明白!

谢谢xmyth的解释!
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

SACC2019中国系统架构师大会

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




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

大会官网>>
  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP