免费注册 查看新帖 |

Chinaunix

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

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

论坛徽章:
0
发表于 2016-06-12 14:43 |显示全部楼层
感觉挺简单啊,这么长时间还有回复。1算出俩个数组和 的差值 2.将差值除以2(每次交换差值会缩小2倍)3.找到小于差值的最近的交换。
例如 a {1 2 3 4 } b{6 7 8 9}
一、suma =10 sumb=30   (sumb-suma)/2 =10
9 -1 =8 <10 交换 a{9 2 3 4} b{6 7 8 1}
二、suma =18 sumb=22   (sumb-suma)/2 =2
8 最小差4 ;7最小差3 ;6最小差2
正好交换6 和4 即可
a{9 2 3 6} b{4 7 8 1}
三、 suma = sumb =20

论坛徽章:
0
发表于 2016-06-19 14:29 |显示全部楼层
分析:
        当前数组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])
           = A - 2 (a - b[j])
        设x = a - 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为止。
---------------------------------------------------------------------------------------------------------------------------------------------------------------------
上面的分析过程是网上找来的,这里说明下为什么是要接近A/2? <总体思想:一元二次方程求最值>

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

这是交换a和b[j]之后的表达式,交换a和b[j]的条件是:交换之后的 |A'| 比 |A|小,也即交换之后两数组元素和的差减小了。即|A| - |A'| > 0, 等价于|A| - |A-2x| > 0

==> |A| > |A-2x|   ==>两边取平方去掉绝对值符号,x*x - Ax<0, 令f(x) = x*x - Ax ,求f(x)小于零的极值,正好是在x = A/2处,当A>0时,在区间(0, A/2)之间

逼近A/2;当当A>0时,在区间(A/2, 0)之间逼近A/2。

---------------------------------------------------------------------------------------------------------------------------------------------------------------------
实现的代码自己去网上搜去。

另外,“先整体排序,再交叉取数”这种方法是不正确的,比如排序之后,第一个最大的放到一个数组里面,第二个和第三个的数的和如果比第一个最大的数小很多,那么第二个,第三个都要放到同一个数组里面。交叉取数就不对了。


论坛徽章:
0
发表于 2016-10-08 09:28 |显示全部楼层
回复 31# greensky_34

数组a,数组b,然后a.b.数组里元素全部排序后存放在数组c中。数组a、b依次取一个值并比较大小,然后再取一个值比较大小,此时数组a若满足两次大于或者小于数组b,则交换第二次所取得元素。这样就可以啦。

论坛徽章:
0
发表于 2016-12-01 16:16 |显示全部楼层
本帖最后由 dd8924 于 2016-12-02 13:49 编辑

无聊翻个老贴,我的思路是:
1:2个数组元素组个新数组并排序
2:先把最大的数丢到一个数组里
3:开始循环,分别计算每个数组的和,倒序把新数组的元素丢到和较小的那个数组里.
欢迎指正.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define ARR_LEN                (5)
#define ARR_AREA        (100)

static int *g_pArra = NULL, *g_pArrb = NULL;

static int arrInit (const int **ppAddr, int len, int size)
{        
        int nRet = 0;

        if (NULL == ppAddr || !len || !size) {
                perror ("bad param!");
                nRet = -1;
                return nRet;
        }
        *ppAddr = calloc (len, size);
        if (NULL == ppAddr)        {
                perror ("ppAddr calloc err!");
                nRet = -1;
                return nRet;        
        }
        return nRet;
}

static int arrElementGet (void)
{
        int nElement = 0;

        //srand ((int)time(NULL));
        nElement = rand () % ARR_AREA;
        //printf ("get new element [%d]\n", nElement);

        return nElement;
}

static arrFill (int len)
{
        int nRet = 0;
        int i = 0;
        for (i = 0; i < len; ++i)        {
                g_pArra = arrElementGet();
                g_pArrb = arrElementGet();
        }

        return nRet;
}

static int arrPrint (const int *pArrd, int len)
{
        int i = 0;
        for (i = 0; i < len; ++i)        {
                printf ("%d ", pArrd);
        }
        printf ("\n");
}

static int arrCmp(const void *a, const void *b)
{
     return(*(int *)a-*(int *)b);
}

static int arrSumGet (const int *pAddr, int len)
{
        int i = 0, sum = 0;
        for (i = 0; i < len; ++i)        {
                sum += pAddr;
        }
        return sum;
}

int main (int argc, char *argv[])
{
        int nRet = 0;
        int i = 0, j = 0, k = 0;
        int *pArrTmp = NULL;
        int nTatolSum = 0;
        int nAvg = 0;
        int sumA = 0, sumB = 0;

do {
        nRet = arrInit (&g_pArra, ARR_LEN, sizeof(int));
        if (nRet)        {
                perror ("g_pArra arrInit error!!!");
                break;
        }

        nRet = arrInit (&g_pArrb, ARR_LEN, sizeof(int));
        if (nRet)        {
                perror ("g_pArrb arrInit error!!!");
                break;
        }

        nRet = arrFill (ARR_LEN);

        printf ("arr a:");
        arrPrint (g_pArra, ARR_LEN);
        printf ("arr b:");
        arrPrint (g_pArrb, ARR_LEN);

        // make a new array
        nRet = arrInit (&pArrTmp, ARR_LEN * 2, sizeof(int));
        if (nRet)        {
                perror ("pArrTmp arrInit error!!!");
                break;
        }
        // fill element from array a and b
        for (i = 0; i < ARR_LEN * 2; ++i)        {
                pArrTmp = (ARR_LEN <= i) ? g_pArrb[i - ARR_LEN] : g_pArra;
        }
        printf ("arr tmp:");
        arrPrint (pArrTmp, ARR_LEN * 2);
        
        // sort
        qsort (pArrTmp, ARR_LEN * 2, sizeof (int), arrCmp);

        printf ("\nsort arr tmp:");
        arrPrint (pArrTmp, ARR_LEN * 2);

        nTatolSum = arrSumGet (pArrTmp, ARR_LEN * 2);
        nAvg = nTatolSum / 2;
        printf ("nTatolSum=%d nAvg=%d \n", nTatolSum, nAvg);

        memset (g_pArra, 0x0, ARR_LEN*4);
        memset (g_pArrb, 0x0, ARR_LEN*4);

        // fill the max element
        g_pArra[ARR_LEN - 1] = pArrTmp[ARR_LEN*2 - 1];
        j = ARR_LEN - 2; k = ARR_LEN - 1;
        for (i = ARR_LEN * 2 - 2; i > 0; --i)        {
                sumA = arrSumGet (g_pArra, ARR_LEN);
                sumB = arrSumGet (g_pArrb, ARR_LEN);
                //arrPrint (g_pArra, ARR_LEN);
                //arrPrint (g_pArrb, ARR_LEN);
                printf ("pArrTmp=%d sumA=%d, sumB=%d \n", pArrTmp, sumA, sumB);
                if (sumA >= sumB)        {
                        g_pArrb[k] = pArrTmp;
                        --k;
                }
                else        {
                        g_pArra[j] = pArrTmp;
                        --j;
                }
        }
        printf ("after change arr a:");
        arrPrint (g_pArra, ARR_LEN);
        printf ("after change arr b:");
        arrPrint (g_pArrb, ARR_LEN);
        sumA = arrSumGet (g_pArra, ARR_LEN);
        sumB = arrSumGet (g_pArrb, ARR_LEN);
        printf ("sumA=%d, sumB=%d diff=%d \n", sumA, sumB, sumA-sumB);
}while (0);
        if (g_pArra)        {
                free (g_pArra);
        }
        if (g_pArrb)        {
                free (g_pArrb);
        }

        printf ("app exit!\n");
        return nRet;
}

论坛徽章:
6
摩羯座
日期:2013-08-24 10:43:10狮子座
日期:2013-08-25 10:27:06天秤座
日期:2013-09-11 20:28:44午马
日期:2014-09-28 16:06:0015-16赛季CBA联赛之八一
日期:2016-12-19 13:55:0515-16赛季CBA联赛之天津
日期:2016-12-20 14:01:23
发表于 2016-12-09 18:44 |显示全部楼层
本帖最后由 cao627 于 2016-12-09 22:38 编辑
  1. #include <stdio.h>
  2. #include <math.h>
  3. #define N 7

  4. int sumd(int a[N], int b[N]);

  5. int main()
  6. {
  7.     int a[] = {2,6,7,9,22,11,34};
  8.     int b[] = {55,35,64,28,12,5,8};
  9.     int i, j, n, m;
  10.     int x, y;
  11.     int t;
  12.     int tmp;
  13.     int f;
  14.     while ( 1) {
  15.         f = 1;
  16.         x = sumd(a, b)/2;                                                    //求得两数组和的差值的中点,每一轮数组a和b元素的交换应尽可能靠近这个中点。
  17.         t = abs(x);
  18.         printf("%d\n", x);
  19.         for (i=0; i<N; i++){
  20.             for (j=0; j<N; j++){
  21.                 y = a[i] - b[j];
  22.                 if (abs(x-y) < abs(x) && abs(x-y) <  t){       //遍历数组a中的每一个元素与数组b中的每一个元素做差值,每一轮遍历求得最合适的两数做交换。
  23.                     t = abs(x-y);
  24.                     m = i;
  25.                     n = j;
  26.                     f = 0;
  27.                 }
  28.             }
  29.         }
  30.         if (f) break;
  31.         tmp = a[m];
  32.         a[m] = b[n];
  33.         b[n] = tmp;

  34.     }

  35.     for (i=0; i<N; i++){
  36.     printf("a[%d]=%d b[%d]=%d\n", i,a[i],i,b[i]);
  37.     }
  38.     return 0;
  39. }

  40. int sumd(int a[], int b[])
  41. {
  42.     int i, s=0;
  43.     for (i=0; i<N; i++){
  44.         s += a[i] - b[i];
  45.     }
  46.     return s;
  47. }

  48.                                                                            
复制代码


论坛徽章:
0
发表于 2016-12-14 13:14 |显示全部楼层
本帖最后由 zoujh2000 于 2016-12-14 13:16 编辑

整体排序、交叉分配的误区就不分析了,太简单。
看到很多根据sum(a)-sum(b)交换元素的例子,这些方法对下面的数组仍然是错的:
数组a {1, 20, 30, 40}
数组b {10, 10, 25, 44}
原因是那些方法只考虑互换一个元素以减小差值,但有时候得互换一组(多个)元素。
比如上例中已无可换的单个元素,差值为2。但将 a 的 {1, 20} 与 b 的 {10, 10} 互换,差值为0才是正确结果。

论坛徽章:
0
发表于 2016-12-14 23:43 |显示全部楼层
本帖最后由 gameas 于 2016-12-15 00:07 编辑

我还没看完贴呢,再看发现自己错了。

论坛徽章:
0
发表于 2017-01-05 22:56 |显示全部楼层
本帖最后由 forxy 于 2017-01-05 23:01 编辑

有两个贪心的人a和b,瓜分偶数堆钱,你觉得他们会怎么做?总有一个先选,比如a,他选最大的,然后轮到b,不用说,b也选最大的。剩下一个问题,后面的怎么分?第三轮,上帝觉得b不爽了,于是让b先选,第四轮,上帝觉得a或者b不爽,让不爽的人先选…直到选完为止。
其实第一轮选完后,后面的问题有点像递归了。
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

SACC2019中国系统架构师大会

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

限时七折期:2019年8月31日前


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

大会官网>>
  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP