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

west3316

12013396 发表于 2006-11-13 10:47
设一个变量，类似于天平的指针,就像用天平称东西一样，只不过用变量来记录他们之间的差。然后，根据这个差对 ...

谢谢你点醒了我，可以用模拟天枰来实现。天枰上的两个盘，我暂时称它们为左边盘和右边盘。
   我的思路是：1. 初始化右边盘可以放入的砝码为a,b数组中除去左边盘第1个被放入的元素a[0]这样的数组（应该用list容器较好）；
                    2.大循环依次遍历a数组的元素（模拟放入到左边盘）；
                    3.在步骤2的循环内实现右边盘砝码放入，做法是：遍历步骤1的list容器，找出放入右边盘后与左边盘总重量最小差值的元素放入右边盘，然后将该元素从步骤1的list中删除。

ggzwtj

没有说清楚题目哇，是交换同一个下标的？还是可以交换任意位置的。

如果可以交换任意位子的？
数组里面是整数？会不会是负数？

如果都是正整数：用背包。
如果可能是负数，只能交换同一位子：动态规划。
如果还可能是浮点：暴力减枝吧。

readheart

1.假设这两个数组是 a， b
2.把他们都放到一个数组c中
3.把c按从小到大的顺序排序
4.设两个临时变量 suma, sumb，都初始化为0
5.取c中尾部两个放到a、b中， 并且suma，sumb都取a、b数组中各元素的和
6.比较suma，sumb， suma > sumb, 则a从c前边取数，b从c的尾部取数， suma<sumb，则反之， 如果相等，则都从前边取。

rxraoxin

/*
    求解思路：

    当前数组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为止。

*/

把算法大概实现了一下，程序如下：
  1  int  test( float  a[],  float  b[],  int  n)
  2  {
  3       float  sumA, sumB;  // sumA为数组a总和，sumB为数组b总和
  4       float  sum_diff, num_diff;  // sum_diff为a,b总和差， num_diff为a,b中各选的两个数之差
  5       float  temp1, temp2;     // temp1为 每轮sum_diff/2， temp2为每轮所选两个数之差于temp1最接近的那个
  6       int  i, j;
  7       float  temp;  // 用于对调a,b间数
  8       int  tempi, tempj;     // 每轮所选两个数之差于temp1最接近的那组数
  9      unsigned  int  flag_sum  =   0 , flag_num  =   0 ;   // flag_sum为1， sumA大于sumB; flag_num为1, 此轮存在两个数之差小于sum_diff
10  
11  
12         
13  
14       while ( 1 ){
15  
16           // 算出a,b数组和
17          sumA  =   0 ;
18          sumB  =   0 ;
19           for (i = 0 ;i  <  n;i ++ )
20          {
21              sumA  +=  a;
22              sumB  +=  b;
23          }
24  
25           if (sumA  >=  sumB){
26              sum_diff  =  sumA  -  sumB;
27              flag_sum  =   1 ;
28          }
29           else
30              sum_diff  =  sumB  -  sumA;   
31      
32          temp1  =  sum_diff / 2 ;
33          temp2  =  temp1;
34          tempi  =   0 ;
35          tempj  =   0 ;   
36      
37           // 找出a,b间差值最接近sum_diff/2的那一对数
38           if (flag_sum  ==   1 ){     // sumA > sumB
39               for (i = 0 ; i  <  n; i ++ )
40                   for (j = 0 ; j  <  n; j ++ )
41                  
42                       if (a  >  b[j]){
43                          num_diff  =  a  -  b[j];
44                           if (num_diff  <  sum_diff){
45                              flag_num  = 1 ;
46                               if (num_diff  >=  temp1){
47                                   if (num_diff - temp1  <  temp2){
48                                      temp2  =  num_diff - temp1;
49                                      tempi  =  i;
50                                      tempj  =  j;
51                                  }
52                              }
53                               else {
54                                   if (temp1  -  num_diff  <  temp2){
55                                      temp2  =  temp1  -  num_diff;
56                                      tempi  =  i;
57                                      tempj  =  j;
58                                  }
59                              }
60                          }
61                      }
62          }
63           else {
64               for (i = 0 ; i  <  n; i ++ )
65                   for (j = 0 ; j  <  n; j ++ )
66                  
67                       if (a  <  b[j]){
68                          num_diff  =  b[j]  -  a;
69                           if (num_diff  <  sum_diff){
70                              flag_num  = 1 ;
71                               if (num_diff  >=  temp1){
72                                   if (num_diff - temp1  <  temp2){
73                                      temp2  =  num_diff - temp1;
74                                      tempi  =  i;
75                                      tempj  =  j;
76                                  }
77                              }
78                               else {
79                                   if (temp1  -  num_diff  <  temp2){
80                                      temp2  =  temp1  -  num_diff;
81                                      tempi  =  i;
82                                      tempj  =  j;
83                                  }
84                              }
85                          }
86                      }
87          }
88  
89           if (flag_num  ==   0 )
90               break ;
91  
92          temp  =  a[tempi];
93          a[tempi]  =  b[tempj];
94          b[tempj]  =  temp;
95      
96          flag_num  =   0 ;
97          flag_sum  =   0 ;
98      }
99         
100       for (i = 0 ; i  <  n;i ++ )
101          printf( " %f/t " ,a);
102  
103      printf( " /n " );
104  
105       for (i = 0 ; i  <  n;i ++ )
106          printf( " %f/t " ,b);
107  
108      printf( " /n " );   
109      
110       return   0 ;
111  }
112  
113  
114  int  main( int  argc,  char   * argv[])
115  {
116  
117       float  a[ 3 ]  =  { 4 , 5 , 12 };
118       float  b[ 3 ]  =  { 1 , 2 , 3 };
119  
120      test(a, b,  3 );
121  
122       return   0 ;
123  }
124   

  1  int  test( float  a[],  float  b[],  int  n)
  2  {
  3       float  sumA, sumB;  // sumA为数组a总和，sumB为数组b总和
  4       float  sum_diff, num_diff;  // sum_diff为a,b总和差， num_diff为a,b中各选的两个数之差
  5       float  temp1, temp2;     // temp1为 每轮sum_diff/2， temp2为每轮所选两个数之差于temp1最接近的那个
  6       int  i, j;
  7       float  temp;  // 用于对调a,b间数
  8       int  tempi, tempj;     // 每轮所选两个数之差于temp1最接近的那组数
  9      unsigned  int  flag_sum  =   0 , flag_num  =   0 ;   // flag_sum为1， sumA大于sumB; flag_num为1, 此轮存在两个数之差小于sum_diff
10  
11  
12         
13  
14       while ( 1 ){
15  
16           // 算出a,b数组和
17          sumA  =   0 ;
18          sumB  =   0 ;
19           for (i = 0 ;i  <  n;i ++ )
20          {
21              sumA  +=  a;
22              sumB  +=  b;
23          }
24  
25           if (sumA  >=  sumB){
26              sum_diff  =  sumA  -  sumB;
27              flag_sum  =   1 ;
28          }
29           else
30              sum_diff  =  sumB  -  sumA;   
31      
32          temp1  =  sum_diff / 2 ;
33          temp2  =  temp1;
34          tempi  =   0 ;
35          tempj  =   0 ;   
36      
37           // 找出a,b间差值最接近sum_diff/2的那一对数
38           if (flag_sum  ==   1 ){     // sumA > sumB
39               for (i = 0 ; i  <  n; i ++ )
40                   for (j = 0 ; j  <  n; j ++ )
41                  
42                       if (a  >  b[j]){
43                          num_diff  =  a  -  b[j];
44                           if (num_diff  <  sum_diff){
45                              flag_num  = 1 ;
46                               if (num_diff  >=  temp1){
47                                   if (num_diff - temp1  <  temp2){
48                                      temp2  =  num_diff - temp1;
49                                      tempi  =  i;
50                                      tempj  =  j;
51                                  }
52                              }
53                               else {
54                                   if (temp1  -  num_diff  <  temp2){
55                                      temp2  =  temp1  -  num_diff;
56                                      tempi  =  i;
57                                      tempj  =  j;
58                                  }
59                              }
60                          }
61                      }
62          }
63           else {
64               for (i = 0 ; i  <  n; i ++ )
65                   for (j = 0 ; j  <  n; j ++ )
66                  
67                       if (a  <  b[j]){
68                          num_diff  =  b[j]  -  a;
69                           if (num_diff  <  sum_diff){
70                              flag_num  = 1 ;
71                               if (num_diff  >=  temp1){
72                                   if (num_diff - temp1  <  temp2){
73                                      temp2  =  num_diff - temp1;
74                                      tempi  =  i;
75                                      tempj  =  j;
76                                  }
77                              }
78                               else {
79                                   if (temp1  -  num_diff  <  temp2){
80                                      temp2  =  temp1  -  num_diff;
81                                      tempi  =  i;
82                                      tempj  =  j;
83                                  }
84                              }
85                          }
86                      }
87          }
88  
89           if (flag_num  ==   0 )
90               break ;
91  
92          temp  =  a[tempi];
93          a[tempi]  =  b[tempj];
94          b[tempj]  =  temp;
95      
96          flag_num  =   0 ;
97          flag_sum  =   0 ;
98      }
99         
100       for (i = 0 ; i  <  n;i ++ )
101          printf( " %f/t " ,a);
102  
103      printf( " /n " );
104  
105       for (i = 0 ; i  <  n;i ++ )
106          printf( " %f/t " ,b);
107  
108      printf( " /n " );   
109      
110       return   0 ;
111  }
112  
113  
114  int  main( int  argc,  char   * argv[])
115  {
116  
117       float  a[ 3 ]  =  { 4 , 5 , 12 };
118       float  b[ 3 ]  =  { 1 , 2 , 3 };
119  
120      test(a, b,  3 );
121  
122       return   0 ;
123  }

回复 1# forrestgang


   

yuanhaosh

8min怎么搞？我觉得先分别求出他们的和，然后算差值，再大的一方减去小的一方的最小值得到a值，在大的一方中找一个和a值差不多的数移到小的一方，同时小的一方将他最小的移给大的。
大概想法 没实践

leeXsen

1. a = [1,2,3]
   
2. b = [4,5,6]
   
3. c = []
   
4. 
   
5. for i in a:
   
6.     c.append(i)
   
7. for i in b:
   
8.     c.append(i)
   
9. 
   
10. c.sort()
    
11. 
    
12. j = 0
    
13. 
    
14. for i in range(0, len(c), 2):
    
15.     n = c[i]
    
16.     x = c[i+1]
    
17. 
    
18.     if (j % 2) != 0:
    
19.         n ^= x
    
20.         x ^= n
    
21.         n ^= x
    
22. 
    
23.     a[j] = n
    
24.     b[j] = x
    
25.     j += 1
    
26. 
    
27. print a, '-', b
    
28. print abs(sum(a)-sum(b))

复制代码

才开始学Python，所以代码写的很丑，不知道这样行不行？

水平狠一般

redpigcool 发表于 2012-04-22 05:10
balanced partition.

动态规划问题。

感谢你的提醒，确实是动态规划问题。一般情况的问题是NP Complete （所以大家不要浪费时间想简单答案了）。简单的排序或者挑选只能给出近似解。元素个数不多或者元素数值比较小的话，精确解能用动态规划给出。

不过这个问题不是一般的平均划分(balanced partition）问题，因为它多了一个限制，即划分的两个子集必须要同样的大小。但是这只要对平均划分问题的动态规划解法的递推关系做一个小改动就行了（我觉得这是一个有意思的小改动，所以不直接说出答案了，请大家思考吧）

除了上面mit的那个讲解，Wikipedia上讲的也很清楚 （这是个“最简单的困难问题 ” "The Easiest Hard Problem"）：

http://en.wikipedia.org/wiki/Partition_problem

pitonas

我觉得这是一个有意思的困难问题

xueskyjian

大家都只考虑交换一个数据了，有没有考虑交换两个，三个，四个......数据的？ 比如sumA=110,sumB=100,   (交换差)exchengediff=(sumA-sumB)/2=5, 如果A中有个 10，B中有个5，这两个数据交换就可以了。但是如果A中有两个数相加为10，比如 3，7。B中两个数相加为5，比如1，4。那么这两组数据交换后也能使得数组A，和数组B的和之差最小的。 同样道理，有可能A中3个数只和减去B中三个数之和等于exchengediff，或很接近exchengediff. 如果只考虑一个数据交换还是比较简单的。  一点理解，望见谅~~~~~~~~~

1053304571

坟贴
int     count_min_squ(int *arr1,int *arr2,int  n){
///////////////////////////////////////////////////////////////////////
//数组为已排序的，小->大
        int     i;
        int     arr1_sum;//arr1的和
        int     arr2_sum;//arr2的和
        int     tp1;//临时变量
        int     tp2;
        if(arr1 == NULL || arr2 == NULL || n < 0){//如果参数出错，则返回非0
                return  !0;
        }
        //开始比对交换
        arr1_sum = arr1[0];
        arr2_sum = arr2[0];
        for(i = 1; i < n ;i++){
                tp1 = arr1_sum-arr2_sum;
                tp2 = arr1 - arr2;
                if( abs(tp1+tp2) > abs(tp1-tp2) ){
                        tp1 = arr1;
                        arr1 = arr2;
                        arr2 = tp1;
                }
                arr1_sum += arr1;
                arr2_sum += arr2;
        }
}