免费注册 查看新帖 |

Chinaunix

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

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

论坛徽章:
1
荣誉会员
日期:2011-11-23 16:44:17
发表于 2006-11-13 20:20 |显示全部楼层
原帖由 zhhui2000 于 2006-11-13 07:54 发表
先各自排序,再交叉存放较大无素

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

论坛徽章:
0
发表于 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, 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 编辑 ]

论坛徽章:
0
发表于 2006-11-13 21:36 |显示全部楼层
我有个想法,利用天平的原理:

1.两端各有n个元素.其总重分别为:W1, W2,差为diff_w(W1,W2)


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

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

论坛徽章:
0
发表于 2006-11-13 21:43 |显示全部楼层
原帖由 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++)
   ...



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

论坛徽章:
0
发表于 2006-11-13 22:14 |显示全部楼层
原帖由 ccjjhua 于 2006-11-13 11:42 发表
把a,b 2数组的元素放到数组3(2n大小) 中进行排序,
a 先取最小的,b先取次小的,
然后根据a,b已取元素和的大小来决定谁来取剩下元素中最小的。策略是,已取得的所有元素之和大的来取C中剩下元素中的最小者。如 ...


这种方法似乎很可行

论坛徽章:
0
发表于 2006-11-13 22:32 |显示全部楼层
我写了80分钟,未果
当时心想,TMD,难道这是google面试题吗

论坛徽章:
0
发表于 2006-11-13 22:36 |显示全部楼层
小弟觉得这个题目应用动态规化来解:

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

有一组数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}

这是大概思想,如有错误望请正!

论坛徽章:
0
发表于 2006-11-13 22:43 |显示全部楼层
原帖由 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. #include <iostream>

  2. using namespace std;

  3. void change(int* a, int* b) {
  4.     int t = *b;
  5.     *a = t;
  6.     *b = *a;
  7. }

  8. int diff(int a, int b) {
  9.     return abs(a - b);
  10. }

  11. int main() {
  12.     const int N = 3;
  13.     int a[] = {1, 2, 3};
  14.     int b[] = {0, 0, 99};
  15.     const int sum_a = 6;
  16.     const int sum_b = 99;

  17.     int ab_diff = abs(sum_a - sum_b);
  18.     for (int i=0; i<N; i++) {
  19.         for (int j=0; j<N; j++) {
  20.             change(a+i, b+j);
  21.             if (abs(sum_a - sum_b) > ab_diff)
  22.             {
  23.                 change(b+j, a+i);//如果不能使差值变小,则交换回去,也就是说不交换
  24.             }
  25.             else
  26.             {
  27.                 ab_diff = abs(sum_a - sum_b);//更新差值
  28.             }
  29.         }
  30.     }

  31.     for (int i = 0; i < N; ++i) {
  32.         cout << a[i] << " ";
  33.     }
  34.     cout << endl;

  35.     for (int i = 0; i < N; ++i) {
  36.         cout << b[i] << " ";
  37.     }
  38.     cout << endl;
  39. }
复制代码

论坛徽章:
0
发表于 2006-11-13 23:12 |显示全部楼层

回复 1楼 forrestgang 的帖子

>>有两个数组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 即所求的情况。
:)。
大概就是这样的,用循环,呵呵。

论坛徽章:
0
发表于 2006-11-14 00:06 |显示全部楼层
1.  求和并除二, 记为 AVG
2.  用短的数组长度个的数字排列组合, 找最接近 AVG 的.
3.  把这几个数填入短数组, 其余填入长数组.

不知道这道题中是否要求输出换的步骤, 如果需要, 小 CASE. 不说了.
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

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