华为面试题(8分钟写出代码)

feng_yu00

回复 1# forrestgang


    我觉得排序没有什么意义的，因为这两个数组里面的值肯定会交换，交换完了之后还是乱序的。
这是小弟我写的，自测没有什么问题。

1. 
   
2. #include <stdlib.h>
   
3. #include <stdio.h>
   
4. 
   
5. #define ARRAY_NUM   3
   
6. 
   
7. int a[ARRAY_NUM] = {1,2,3};
   
8. int b[ARRAY_NUM] = {4,5,6};
   
9. void swap(int* a, int* b)
   
10. {
    
11.         int t = *a;
    
12.         *a = *b;
    
13.         *b = t;
    
14. }
    
15. 
    
16. int sum(int a[], int num)
    
17. {
    
18.         int sum = 0;
    
19.         int i = 0;
    
20.         for(i = 0; i < num; i++)
    
21.         {
    
22.                 sum += a[i];
    
23.         }
    
24.         return sum;
    
25. }
    
26. 
    
27. 
    
28. void func(int a[], int b[], int num)
    
29. {
    
30.         int sum_a = sum(a, num);
    
31.         int sum_b = sum(b, num);
    
32. 
    
33.         int b_swap = 0;
    
34.         int i = 0;
    
35.         int j = 0;
    
36.         int sum_diff = sum_a - sum_b;
    
37.         printf("diff:%d\n", sum_diff);
    
38.         while (1)
    
39.         {
    
40.                 for (i = 0; i < num; i++)
    
41.                 {
    
42.                         for(j = 0; j < num; j++)
    
43.                         {
    
44.                                 int diff = a[i] - b[j];
    
45.                                 if (abs(sum_diff) > abs(sum_diff - (2 * diff)))
    
46.                                 {
    
47.                                         swap(a + i, b + j);
    
48.                                         b_swap = 1;
    
49.                                         sum_diff = sum_diff - (2 * diff);
    
50.                                         printf("diff:%d\n", sum_diff);
    
51.                                         break;
    
52.                                 }
    
53.                         }
    
54.                         if(b_swap > 0)
    
55.                         {
    
56.                                 break;
    
57.                         }
    
58.                 }
    
59.                 if (0 == b_swap)
    
60.                 {
    
61.                         break;
    
62.                 }
    
63.                 else
    
64.                 {
    
65.                         b_swap = 0;
    
66.                 }
    
67.         }
    
68. }
    
69. 
    
70. void _print()
    
71. {
    
72.         int i = 0;
    
73.         printf("array a:\n");
    
74.         for(i = 0; i < ARRAY_NUM; i++)
    
75.         {
    
76.                 printf("%d ", a[i]);
    
77.         }
    
78.         printf("\n");
    
79. 
    
80.         printf("array b:\n");
    
81.         for(i = 0; i < ARRAY_NUM; i++)
    
82.         {
    
83.                 printf("%d ", b[i]);
    
84.         }
    
85.         printf("\n");
    
86. }
    
87. 
    
88. int main()
    
89. {
    
90.         printf("before:\n");
    
91.         _print();
    
92. 
    
93.         func(a, b, ARRAY_NUM);
    
94.         printf("\n\n");
    
95.         printf("after:\n");
    
96.         _print();
    
97. 
    
98.         return 0;
    
99. }

复制代码

tcwm1_cu

lz看下这组测试数据 {10000,1005，105,10} {10004,1000,100,14} 貌似你的贪婪只适合特殊情况

Forif

absuma-sumbhalfdiff
     翪sumasumba[n]ab[1]bСhalfdiffбСa[n]b[1]òa[n]-b[2]halfdiffa[n]-b[3]ia[n]-b[i]Сhalfdiffa[n]-b[i]halfdifftempdiffa[n-1]-b[1]tempdiffСa[j]b[i]нtempdiff0
     halfdiffhalfdiffС0tempdiff0

Forif

开始先分别将a、b两个数组排序，然后算出两个数组的累和之差suma-sumb的一半，就记作halfdiff吧，开始循环
     比如开始时suma大于sumb，那就用a[n]（a中最大）减去b[1]（b中最小），将这个差值与halfdiff进行比较，如果小于，则交换a[n]和b[1]，交换时也要保证两个数组仍然有序，可以用插入排序；如果大于，则用a[n]-b[2]再与halfdiff比较，如果仍大于，再用a[n]-b[3]…一直找到一个i使a[n]-b[i]小于halfdiff，将a[n]-b[i]与halfdiff的差值存入tempdiff，接着用a[n-1]-b[1]…即找到使tempdiff最小的a[j]和b[i]进行交换（仍保持有序）；如果tempdiff为0，则幸运结束。
     再计算新的halfdiff，进行下一轮循环，直到halfdiff最小或为0或tempdiff为0。

Sevk

一个一个取出，天平左边重就放右边，右边重就放左边。

ks9960

..这个挖坟也挖的太厉害了吧。

第一步 取TotalA-TotalB的绝对值，设为Difference
第二步 如果TotalA>TotalB，a[n]中每个元素减去b[n]中每个元素，大于0放到GTmp[n][n]，小于0放到LTmp[n][n]，为0的丢弃
第三步 GTmp[n][n]中取1,.....n个元素的所有组合，组合中元素的总和Total与Difference比较，如果为0则得出最优解，否则取最小偏差为LikelyAnswer1，
          保存Total到GResult[x]
第四步 LTmp[n][n]中取1,.....n个元素的所有组合，组合中元素的总和Total保存到LResult[y]
第五步 遍历GResult[x]和LResult[x]各取1个元素进行求和，将求和结果与Difference比较，如果为0则得出最优解，否则取最小偏差为LikelyAnswer2
第六步 比较LikelyAnswer1和LikelyAnswer2，取小值作为最优解

cj_gameboy

汗，真的是华为面试题？？
前两天去了南京华为的面试，面试上机题比这个简单多了，题目是：
有一个数组，已知长度大于2，然后要求完成一个函数，入参为那个数组和两个指针，取得数组中最大和次大的两个数并用指针返回。

j3kljs02398j

思路：将ab统一排序，然后在成对分发回ab，相对大的放在a，另一个放在b。

1. #include <stdlib.h>
   
2. #include <stdio.h>
   
3. #include <time.h>
   
4. #define LENGTH 3000
   
5. /*
   
6. * 有两个数组a,b，大小为n, 无序
   
7. * 通过交换a,b中的元素，使数组a元素和数组b元素之间的差最小
   
8. */
   
9. int cmp(const void *a1, const void *a2)
   
10. {
    
11.         int v1 = *((int *)a1);
    
12.         int v2 = *((int *)a2);
    
13. 
    
14.         if (v2 == v1)
    
15.                 return 0;
    
16.         return v2 > v1 ? 1 : -1;
    
17. }
    
18. 
    
19. int main(void)
    
20. {
    
21.         int a[LENGTH];
    
22.         int b[LENGTH];
    
23.         int *tmp = NULL;
    
24.         int i, j;
    
25.         int result;
    
26. 
    
27.        /*随机初始化数组a,b 别且打印a，b */
    
28.         srand((unsigned int )time(NULL));
    
29.         for (i = 0; i < LENGTH; i++)  {
    
30.                 a[i] = rand()%1000;
    
31.                 b[i] = rand()%1000;
    
32.         }
    
33. 
    
34.         /* 把ab放到一个数组中,然后整体排序*/
    
35.         if ((tmp = (int *)malloc(sizeof(int) * LENGTH * 2)) == NULL) {
    
36.                 fprintf(stderr, "malloc failed\n");
    
37.                 exit(1);
    
38.         }
    
39.         for (i = j = 0; i < LENGTH * 2;j++) {
    
40.                 tmp[i++] = a[j];
    
41.                 tmp[i++] = b[j];
    
42.         }
    
43.         /*对a,b各自排序*/
    
44.         qsort(tmp, LENGTH * 2, sizeof(int), cmp);
    
45.         /* 排序后在分别放回ab 成对分发，大的在a中 */
    
46.         for (i = j = 0; i < LENGTH; i++) {
    
47.                 a[i] = tmp[j++];
    
48.                 b[i] = tmp[j++];
    
49.         }
    
50.         free(tmp);
    
51.        /* 打印下结果 */
    
52.         for (i = 0, result = 0; i < LENGTH; i++)
    
53.                 result += a[i] - b[i];
    
54.         printf("sum a - sum b is %d\n", result);
    
55. 
    
56.         return 0;
    
57. }

复制代码

贴出来之后，发现这种思路不对。a{5 5 5} b{10 0 0}

enough_zerg

没找到在哪设置代码格式的啊

思路就是先求出2个数组和的差，然后从数组a开始逐个把数组b的元素替换过来加一下，要是差比原先小的话就真正的换
直到换完，或者遇到差变成0了就不搞了

1 #include <stdio.h>
  2 #include <assert.h>
  3 #include <math.h>
  4
  5 void * swap(int *a, int *b, int n)
  6 {
  7     assert(a != NULL && b != NULL);
  8
  9     int suma = 0;
10     int sumb = 0;
11     int count = 0;
12
13     int k = 0;
14     for (; count < n; count++)
15     {
16         suma += a[count];
17     }
18     for (count = 0; count < n; count++)
19     {
20         sumb += b[count];
21     }
22
23     int diff = abs(suma - sumb);
24
25     int midiff = 0;
26
27     for (count = 0; count < n; count++)
28     {
29         for (; k < n; k++)
30         {
                 //这里把b数组里的对应元素加过来置换作下运算，根据结果决定要不要真的换
31             midiff = abs(suma - a[count] + b[k] - sumb + b[k] - a[count]);
32             if (midiff < diff)
33             {
34                 int tmp = a[count];
35                 a[count] = b[k];
36                 b[k] = tmp;
37                 diff = midiff;
38             }
39             if (midiff == 0)
40                 break;
41         }
42     }
43 }

老蒋

这道题目非常的难，要写出精妙的算法实属不易！