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

yuxh

原帖由 zhhui2000 于 2006-11-13 07:54 发表
先各自排序,再交叉存放较大无素

这个基本可行，但不是交叉存放较大元素，而是哪边的和小就一直放大元素，直到n，然后把剩下的扔到另一组中就ok了。

greensky_34

for (i=0; i<N; i++)
    {
        for (j=0; j<N; j++)
        {
            change(a+i, b+j);
            if (abs(sum(a)-sum(b)) > ab_diff)
            {
                change(b+j, a+i);//如果不能使差值变小，则交换回去，也就是说不交换
            }
            else
            {
                ab_diff = abs(sum(a)-sum(b));//更新差值
            }
        }
    }

TC2测试

原帖由 namtso 于 2006-11-13 17:16 发表
我相信，这个题在8分钟内能写出代码来的人，绝对是大大的牛人。

我觉得应该这样：
a和b 分别求出累加和，得出累加和的差c1，然后循环查找找a中的某个元素a，使得a与b中的某个元素b[j]交换之后，得出一个 ...

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

lebk

我有个想法，利用天平的原理：

１．两端各有n个元素．其总重分别为：W1, W2,差为diff_w(W1,W2)


２．结束条件是，diff_w(W1,W2)小于等于左右两边中任意元素之差的最小值．

３．如果不满足上述条件则进行置换，置换的规则是，将上述两边任意二元素之差最接近diff(w1,w2)得元素进行置换．.再重复上述步骤．

windy2335

原帖由 hithotwinds 于 2006-11-13 10:16 发表
刚学编程两个月，不知道思路是否正确，错就一定有的。

#include"stdio.h"
com(int a[2000],int n)
{int i,j,p,q,s;
for(i=0;i<2*n-1;i++)
  {
a[0]=q,p=i;
  for(j=i+1;j<2*n;j++)
   ...

才两个月能写出这么长的程序还是不错滴。。。
                                        加油！！

apzc2529

原帖由 ccjjhua 于 2006-11-13 11:42 发表
把a,b 2数组的元素放到数组3（2n大小） 中进行排序，
a 先取最小的，b先取次小的，
然后根据a,b已取元素和的大小来决定谁来取剩下元素中最小的。策略是，已取得的所有元素之和大的来取C中剩下元素中的最小者。如 ...

这种方法似乎很可行

s5unty

我写了80分钟，未果
当时心想，TMD，难道这是google面试题吗

qqq112233g

小弟觉得这个题目应用动态规化来解：

原问题与下问题应该属同类。

有一组数a1,a2,a3,...,an. 求出一个子串，其各元素的和总元素和的一半差值最小！设总元素和为sum，

子串和为s_sub.  差值为dis[i][j],表示第 i个元素到j 个元素之间的子串和。每个元素有两种状态，1为选，0为不选。  
   
         当 i==j 时 dis[i][j] = a[i] = a[j]
         当 i<j  时 dis[i][i] = min{sum-s_sub-a[i], sum-s_sub}

这是大概思想，如有错误望请正！

s5unty

原帖由 greensky_34 于 2006-11-13 20:25 发表
for (i=0; i<N; i++)
    {
        for (j=0; j<N; j++)
        {
            change(a+i, b+j);
            if (abs(sum(a)-sum(b)) > ab_diff)
            {
                change(b+j, ...

不行阿，我理解后用c实现，结果不正确，可能是我理解有问题？

1. 
   
2. #include <iostream>
   
3. 
   
4. using namespace std;
   
5. 
   
6. void change(int* a, int* b) {
   
7.     int t = *b;
   
8.     *a = t;
   
9.     *b = *a;
   
10. }
    
11. 
    
12. int diff(int a, int b) {
    
13.     return abs(a - b);
    
14. }
    
15. 
    
16. int main() {
    
17.     const int N = 3;
    
18.     int a[] = {1, 2, 3};
    
19.     int b[] = {0, 0, 99};
    
20.     const int sum_a = 6;
    
21.     const int sum_b = 99;
    
22. 
    
23.     int ab_diff = abs(sum_a - sum_b);
    
24.     for (int i=0; i<N; i++) {
    
25.         for (int j=0; j<N; j++) {
    
26.             change(a+i, b+j);
    
27.             if (abs(sum_a - sum_b) > ab_diff)
    
28.             {
    
29.                 change(b+j, a+i);//如果不能使差值变小，则交换回去，也就是说不交换
    
30.             }
    
31.             else
    
32.             {
    
33.                 ab_diff = abs(sum_a - sum_b);//更新差值
    
34.             }
    
35.         }
    
36.     }
    
37. 
    
38.     for (int i = 0; i < N; ++i) {
    
39.         cout << a[i] << " ";
    
40.     }
    
41.     cout << endl;
    
42. 
    
43.     for (int i = 0; i < N; ++i) {
    
44.         cout << b[i] << " ";
    
45.     }
    
46.     cout << endl;
    
47. }
    

复制代码

kongqiang

>>有两个数组a,b，大小都为n,数组元素的值任意，无序；
>>要求：通过交换a,b中的元素，使数组a元素的和与数组b元素的和之间的差最小

这个与下面的等效。
数组 a:  a1,  a2, a3, ... an;
        b:  b1, b2, b3, ...  bn;
先从 a 中取 x 个元素， 再和 b 中的 n-x 个元素，把他们的值相加， 得 sumi;   
再从 a 中取剩下的 n-x 个元素， 和 b 中的 x 个元素，把他们的值相加， 得 sumj;
取 |sumi - sumj| 的绝对值为 subsum;

x 从 0 开始取到 n, 每次得到一个 subsum, 最小的那个 subsum 即所求的情况。
：）。
大概就是这样的，用循环，呵呵。

chouy

1.  求和并除二, 记为 AVG
2.  用短的数组长度个的数字排列组合, 找最接近 AVG 的.
3.  把这几个数填入短数组, 其余填入长数组.

不知道这道题中是否要求输出换的步骤, 如果需要, 小 CASE. 不说了.