2017年小米校园招聘笔试题

概要：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; // 假设三个只出现一次的其中一个数为bb = 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 ，

2017年小米校园招聘笔试题,标签：笔试大全,http://www.88haoxue.com

　　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;

　　}

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

　　{

　　int i , count;

　　for(i = 1 ; i <= n ; ++i) //初始化并查集，各点为孤立点，分支数为n

　　set[i] = i;

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

　　merge(r[i][0] , r[i][1]);

　　count = 0;

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

　　{

　　if(set[i] == i)

　　++count;

　　}

　　return count;

　　}

上一页  [1] [2]