免费注册 查看新帖 |

Chinaunix

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

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

论坛徽章:
0
发表于 2006-11-14 00:28 |显示全部楼层
原帖由 s5unty 于 2006-11-13 22:43 发表


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


  1. #include <iostream>

  2. using namespace std;

  3. void change(int* a, int* b) {
  4.     int t = *b;
  5.     *a = t;
  6.     *b = * ...
复制代码


完整的程序是这样的,可以参考一下

  1. #include <stdio.h>
  2. #include <math.h>

  3. #define N 10

  4. void ary_init(int a[], int b[]){ //初始化数组
  5.     int i;
  6.     for (i=0; i<N; i++){
  7.         a[i] = rand()%100;
  8.     }
  9.     for (i=0; i<N; i++){
  10.         b[i] = rand()%100;
  11.     }
  12.     return;
  13. }
  14. long sum(int a[]){ //数组求和
  15.     int i;
  16.     int s;
  17.     for (s=0,i=0; i<N; i++){
  18.         s += a[i];
  19.     }
  20.     return s;
  21. }

  22. void change(int *a, int *b){ //数组元素交换
  23.     int tmp;
  24.     tmp = *a;
  25.     *a = *b;
  26.     *b = tmp;
  27.     return;
  28. }

  29. void prt_ary(int a[], int b[]){ //列印两数组元素及各自元素和
  30.     int i;
  31.     for(i=0; i<N; i++){
  32.         printf("%5d   ", a[i]);
  33.     }
  34.     printf("\n");
  35.     for(i=0; i<N; i++){
  36.         printf("%5d   ", b[i]);
  37.     }
  38.     printf("\n");
  39.     printf("%d\n", sum(a));
  40.     printf("%d\n", sum(b));
  41. }

  42. int main(){
  43.     int i;
  44.     int j;
  45.     int a[N];
  46.     int b[N];
  47.     int a_sum;
  48.     int b_sum;
  49.     int tmp;
  50.     int ab_diff;

  51.     ary_init(a,b);//初始化
  52.     prt_ary(a, b);//列印当前数组状态
  53.     ab_diff = abs(sum(a)-sum(b));
  54.     for (i=0; i<N; i++){//交换数组元素
  55.         for (j=0; j<N; j++){
  56.             change(a+i, b+j);
  57.             if (abs(sum(a)-sum(b)) > ab_diff){
  58.                 change(b+j, a+i);
  59.             }
  60.             else{
  61.                 ab_diff = abs(sum(a)-sum(b));
  62.             }
  63.         }
  64.     }
  65.     prt_ary(a, b);//列印交换后数组状态
  66.     getch();
  67. }
复制代码

[ 本帖最后由 greensky_34 于 2006-11-14 00:30 编辑 ]

论坛徽章:
0
发表于 2006-11-14 00:31 |显示全部楼层

12楼的错误举例:

比如说总共加起来为数组:1,2,3,4,5,6

如果算6-5,4-3,2-1(12楼的算法),然后求和结果最小差是3

但我可以这样分组(1,6)一组,(2,5)一组,4,3分到两个组,结果最小差才是1

论坛徽章:
0
发表于 2006-11-14 08:53 |显示全部楼层

最笨的才是最好的

首先可以用穷举的方式来实现该方法
在此基础上再优化算法(即排除没有必要的计算),最后必然可以得到想要的结果

论坛徽章:
0
发表于 2006-11-14 09:16 |显示全部楼层
原帖由 mill888 于 2006-11-13 17:29 发表
8分钟就能写出正确方法的人,建议就不要去华为了,应当去更好的公司。
招聘中,建议华为公司应当定好自己的位。

共鸣

论坛徽章:
0
发表于 2006-11-14 09:25 |显示全部楼层
可以用背包算法

轮流取数、按差值取数都不能保证正确性

比如对于原始数组:
a[]={1,2,3}
b[]={4,10,20}

或者:
a[]={1,29,30}
b[]={50,90,100}

论坛徽章:
0
发表于 2006-11-14 09:32 |显示全部楼层

我认为不要写程序,写个算法就好啦,不知道我的对不对,

首先看图片信息-------这个题不一定就能交叉,你们能确定交叉就对吗,不对的,这也是我刚开始错误的思路,哈哈
我很就没写程序了,我是个做网页的,现在也不知道用哪种语言表达了,希望写程序比较好的朋友,把程序写出来把,就一个函数,我认为就能解决这个问题,

你们的程序中只要不区分当N为奇数还是偶数的情况,你们的算法就是错误的,我可以这么肯定的说,

你们只需要看N的判断,就可以知道这个算法的正确还是错误,

我个人认为,写程序,未必一定要用,英语来表达,
这样会达不到让看的人明白的效果的,  

呵呵,一个没编过程的人,不知道说的对不对,但是我看过LINUX 内核和STL,自认为比别人懂模式。



我确定这个绝对正确,我用了10分钟


然后,将a,b数组合并,成一个数组C,

排序C,
然后将C中的数组

这个时候要看N为奇数还是偶数了 ,分析如图

这样就应该可以了把,



例如;

C数组;123456
那么A,B将取如下图

[ 本帖最后由 banboy 于 2006-11-14 10:10 编辑 ]
suanfa.gif
suanfa111111.gif

论坛徽章:
0
发表于 2006-11-14 09:35 |显示全部楼层
这样一定不行

论坛徽章:
0
发表于 2006-11-14 09:37 |显示全部楼层
小弟想到一个算法,,大家给点意见
   定义一个c[2N]数组,将A数组和B数组里面的元素都放到C数组中,然后对C数组小到大排序,排好后在取数,在定义一个的D[N]数组,将C的第一个加上C的第2N个放到D[0]中,C的第二个加上C的第2N-1个放到D[1]中。。。。放好后,再将D数组从小到大排序,在又按照上面的方法,第一个加上最后一个放到另一个数组的第一个中,第2个加到数第二个放到另一个数组的第2个中。。。以这中思路一直排下去,最后得到一个两个元素的数组,那这数组中的两个元素的差应该就是最小的了。。。
这个数组中的两个元素中的每一个都是由N个数加起来的,所以在一开始放数的时候要对这些数进行记录。。。得到后便可以将这2N个数分配给A数组和B数组了.....
     这种方法应该是可行的。。。。高手指点下....

论坛徽章:
0
发表于 2006-11-14 09:37 |显示全部楼层
greensky 的算法很不错啊~~~大家看看可否再优化!?

论坛徽章:
0
发表于 2006-11-14 09:38 |显示全部楼层
QUOTE:
原帖由 zhhui2000 于 2006-11-13 07:54 发表
先各自排序,再交叉存放较大无素
这个基本可行,但不是交叉存放较大元素,而是哪边的和小就一直放大元素,直到n,然后把剩下的扔到另一组中就ok了。


同意,但不应该是哪边小就一直放大元素,直到n, 应该是直到这个组元素的和大于另一组元素和时,再将下一元素放到令一组,若两组之和相等时,将下一元素放到元素最多的那个组,然后以同样的方法继续剩下元素的放置,直到有一个组为n,然后把剩下的放到另一个组。
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

SACC2019中国系统架构师大会

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

限时8.5折扣期:2019年9月30日前


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

大会官网>>
  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP