當(dāng)前位置:高考升學(xué)網(wǎng) > 招聘筆試題 > 正文
二、編程題
1、數(shù)組乘積(15分)
輸入:一個長度為n的整數(shù)數(shù)組input
輸出:一個長度為n的整數(shù)數(shù)組result,滿足result[i] = input數(shù)組中除了input[i]之外所有數(shù)的乘積(假設(shè)不會溢出)。比如輸入:input = {2,3,4,5},輸出result = {60,40,30,24}
程序時間和空間復(fù)雜度越小越好。
C/C++:
int cal(int input , int n);
Java:
int[] cal(int[] input);
[cpp] view plaincopy
int cal(int input , int n)
{
int i ;
int result = new int[n];
result[0] = 1;
for(i = 1 ; i < n ; ++i)
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、異形數(shù)(25分)
在一個長度為n的整形數(shù)組a里,除了三個數(shù)字只出現(xiàn)一次外,其他的數(shù)字都出現(xiàn)了2次。請寫程序輸出任意一個只出現(xiàn)一次的數(shù)字,程序時間和空間復(fù)雜度越小越好。
例如: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 plaincopy
// lowbit表示的是某個數(shù)從右往左掃描第一次出現(xiàn)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];
// 三個數(shù)兩兩的異或后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; // 假設(shè)三個只出現(xiàn)一次的其中一個數(shù)為b
b = 0;
for(i = 0 ; i < n ; ++i)
{
if(lowbit(xors ^ a[i]) == fips)
b ^= a[i];
}
// 成功找到三個數(shù)中一個數(shù)
cout<
}
3、朋友圈(25分)
假如已知有n個人和m對好友關(guān)系(存于數(shù)字r)。如果兩個人是直接或間接的好友(好友的好友的好友...),則認(rèn)為他們屬于同一個朋友圈,請寫程序求出這n個人里一共有多少個朋友圈。
假如:n = 5 , m = 3 , r = {{1 , 2} , {2 , 3} , {4 , 5}},表示有5個人,1和2是好友,2和3是好友,4和5是好友,則1、2、3屬于一個朋友圈,4、5屬于另一個朋友圈,結(jié)果為2個朋友圈。
最后請分析所寫代碼的時間、空間復(fù)雜度。評分會參考代碼的正確性和效率。
C/C++:
int friends(int n , int m , int r[]);
Java:
int friends(int n , int m , int[][] r);
[cpp] view plaincopy
// 簡單的并查集應(yīng)用
int set[10001];
inline int find(int x) //帶路徑優(yōu)化的并查集查找算法
{
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) //優(yōu)化的并查集歸并算法
{
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) //初始化并查集,各點(diǎn)為孤立點(diǎn),分支數(shù)為n
set[i] = i;
for(i = 0 ; i < m ; ++i)
merge(r[i][0] , r[i]);
count = 0;
for(i = 1 ; i <= n ; ++i)
{
if(set[i] == i)
++count;
}
return count;
}
2020年河北新聞網(wǎng)兩學(xué)一做
時間:2023-09-18 07:0:242020年河北新聞網(wǎng)兩學(xué)一做
時間:2023-09-15 11:0:59兩學(xué)一做學(xué)習(xí)教育知
時間:2023-09-21 06:0:302020年開展兩學(xué)一做學(xué)習(xí)教
時間:2023-09-19 21:0:30