用户名: 密码: 企业 个人
当前位置:89学习网范文文章招聘应聘笔试2017年小米校园招聘笔试题» 正文

2017年小米校园招聘笔试题

[05-15 14:50:43]   来源:http://www.89xue.com  笔试   阅读:90
摘要:result[i] = result[i-1]*input[i-1];result[0] = input[n-1];for(i = n-2 ; i > 0 ; --i){result[i] *= result[0];result[0] *= input[i];}return result;}2、异形数(25分)在一个长度为n的整形数组a里,除了三个数字只出现一次外,其他的数字都出现了2次。请写程序输出任意一个只出现一次的数字,程序时间和空间复杂度越小越好。例如: a = {1,3,7,9,5,9,4,3,6,1,7},输出4或5或6C/C++:void find(int* a , int n);Java:v。
2017年小米校园招聘笔试题,标签:笔试范文,http://www.89xue.com

  result[i] = result[i-1]*input[i-1];

  result[0] = input[n-1];

  for(i = n-2 ; i > 0 ; --i)

  {

  result[i] *= result[0];

  result[0] *= input[i];

  }

  return result;

  }

  2、异形数(25分)

  在一个长度为n的整形数组a里,除了三个数字只出现一次外,其他的数字都出现了2次。请写程序输出任意一个只出现一次的数字,程序时间和空间复杂度越小越好。

  例如: a = {1,3,7,9,5,9,4,3,6,1,7},输出4或5或6

  C/C++:

  void find(int* a , int n);

  Java:

  void find(int[] a);

  [cpp] view plaincopyprint?

  // lowbit表示的是某个数从右往左扫描第一次出现1的位置

  int lowbit(int x)

  {

  return x&~(x-1);

  }

  void find(int* a , int n)

  {

  int i , xors;

  xors = 0;

  for(i = 0 ; i < n ; ++i)

  xors ^= a[i];

  // 三个数两两的异或后lowbit有两个相同,一个不同,可以分为两组

  int fips = 0;

  for(i = 0 ; i < n ; ++i)

  fips ^= lowbit(xors ^ a[i]);

  // 表示的是:flips=lowbit(a^b)^lowbit(a^c)^lowbit(b^c)

  int b; // 假设三个只出现一次的其中一个数为b

  b = 0;

  for(i = 0 ; i < n ; ++i)

  {

  if(lowbit(xors ^ a[i]) == fips)

  b ^= a[i];

  }

  // 成功找到三个数中一个数

  cout<

  }

  // lowbit表示的是某个数从右往左扫描第一次出现1的位置

  int lowbit(int x)

  {

  return x&~(x-1);

  }

  void find(int* a , int n)

  {

  int i , xors;

  xors = 0;

  for(i = 0 ; i < n ; ++i)

  xors ^= a[i];

  // 三个数两两的异或后lowbit有两个相同,一个不同,可以分为两组

  int fips = 0;

  for(i = 0 ; i < n ; ++i)

  fips ^= lowbit(xors ^ a[i]);

  // 表示的是:flips=lowbit(a^b)^lowbit(a^c)^lowbit(b^c)

  int b; // 假设三个只出现一次的其中一个数为b

  b = 0;

  for(i = 0 ; i < n ; ++i)

  {

  if(lowbit(xors ^ a[i]) == fips)

  b ^= a[i];

  }

  // 成功找到三个数中一个数

  cout<

  }

  3、朋友圈(25分)

  假如已知有n个人和m对好友关系(存于数字r)。如果两个人是直接或间接的好友(好友的好友的好友...),则认为他们属于同一个朋友圈,请写程序求出这n个人里一共有多少个朋友圈。

  假如:n = 5 , m = 3 , r = {{1 , 2} , {2 , 3} , {4 , 5}},表示有5个人,1和2是好友,2和3是好友,4和5是好友,则1、2、3属于一个朋友圈,4、5属于另一个朋友圈,结果为2个朋友圈。

  最后请分析所写代码的时间、空间复杂度。评分会参考代码的正确性和效率。

  C/C++:

  int friends(int n , int m , int* r[]);

  Java:

  int friends(int n , int m , int[][] r);

  [cpp] view plaincopyprint?

  // 简单的并查集应用

  int set[10001];

  inline int find(int x) //带路径优化的并查集查找算法

  {

  int i , j , r;

  r = x;

  while(set[r] != r)

  r = set[r];

  i = x;

  while(i != r)

  {

  j = set[i];

  set[i] = r;

  i = j;

  }

  return r;

  }

  inline void merge(int x , int y) //优化的并查集归并算法

  {

  int t = find(x);

  int h = find(y);

  if(t < h)

  set[h] = t;

  else

  set[t] = h;

上一页  [1] [2] [3]  下一页


Tag:笔试笔试范文招聘应聘 - 笔试