春暖花开

华为校招笔试总结

今天晚上参加了华为今年的校招笔试(软件类)。华为的笔试题只有三个算法题,与前两次腾讯和百度的算法题相比,华为的题要简单得多。总共两个小时的考试时间,最后用了一个半小时的时间 AC 了全部三个题。大概笔试不怎么刷人。下面简单记录一下题目。

1. n个人(n >= 1) 站成一个环,编号为 1 ~ n,即编号为 n 的人与编号为 1 的人相邻,从第一个人开始报数,假如编号为 x 的报数为 m ,则该人出局,出局后不再参加报数,出局这一个人的后面一个人从 1 开始继续报数,直到所有人都出局,要求输出出局的编号序列。

该题为著名的约瑟夫环问题,实现方法很多。可通过模拟,也可通过数学公式推导,网上有现成的代码,不过考试的时候我没有上网找,是自己实现的,算是一个数学推导的方法吧。

考试时的 AC 代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/*************************************************************************
> Filename: dele.cpp
> Author: Lv Feng
> Mail: lvfeng97@outlook.com
> Date: 2018-10-13
************************************************************************/
#include<bits/stdc++.h>
using namespace std;
void Solve(const int &n, const int &m){
vector<int> people;
for(int i = 1; i <= n; ++ i)
people.push_back(i);
vector<int>::iterator cur = people.begin();
int loc;
while(people.size() > 1){
loc = (cur - people.begin() + m) % people.size() - 1;
if (loc == -1){
loc = people.size() - 1;
}
cout << people[loc] << ' ';
cur = people.erase(people.begin() + loc);
}
cout << people[0] << endl;
}
int main(){
int num;
cin >> num;
int data[num][2];
for(int i = 0; i != num; ++i){
cin >> data[i][0] >> data[i][1];
}
for(int i = 0; i != num; ++i){
Solve(data[i][0], data[i][1]);
}
return 0;
}

n 个数用 vector 存储,每次确定一个出列的数,然后输出该数并将该数从 vector 中删除,算法时间复杂度为 O(n)。main 函数中的 num 变量表示测试数据的组数。

2. 给定一个 10X10 的方格,数组中的数均为 0 或 1,每一个为 1 的方格的面积为 1,要求求出 1 的连通区域的最大面积(连通区域由上下左右为 1 的方格组成,不包括对角线)

本题中,10x10 的方格可以看成是一个二维数组,每次从一个没有遍历过的为 1 的元素出发,向四周遍历,所有为 1 的元素都遍历一遍就可求出最大连通面积。

考试时的 AC 代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/*************************************************************************
> Filename: max.cpp
> Author: Lv Feng
> Mail: lvfeng97@outlook.com
> Date: 2018-10-13
************************************************************************/
#include<bits/stdc++.h>
using namespace std;
const int Len = 10;
int data[10][10];
int visited[Len][Len];
inline void input(){
for(int i = 0; i != Len; ++i)
for(int j = 0; j != Len; ++j)
cin >> data[i][j];
}
int getS(int m, int n){
int s = 0;
if(data[m][n] == 0 || visited[m][n])
return 0;
else{
s += 1;
visited[m][n] = 1;
if (m - 1 >= 0){
s += getS(m-1, n);
}
if (m + 1 < Len){
s += getS(m+1, n);
}
if (n - 1 >= 0){
s += getS(m, n-1);
}
if (n + 1 <Len){
s += getS(m, n+ 1);
}
}
return s;
}
void Solve(){
int maxS = 0;
int tmp;
int i, j;
for(i = 0; i != Len; ++i){
for(j = 0; j != Len; ++j){
memset(visited, 0, 100);
tmp = getS(i, j);
maxS = (tmp > maxS)? tmp: maxS;
}
}
cout << maxS <<endl;
}
int main(){
input();
Solve();
return 0;
}

上面的代码实现中,从每一个元素开始都进行了一次遍历,实际上是不需要的,比如,对于值为 0 的元素,不需要从它开始进行遍历,另外,对于每一个 1 ,实际上也只需要遍历一次,但这儿遍历了多次,因为从每一个 1 出发都进行了一次遍历,如果数组不是 10x10,比如是 1000x1000 ,那么这样可能会导致超时。

优化后的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/*************************************************************************
> Filename: max.cpp
> Author: Lv Feng
> Mail: lvfeng97@outlook.com
> Date: 2018-10-13
************************************************************************/
#include<bits/stdc++.h>
using namespace std;
const int Len = 10;
int data[10][10];
int visited[Len][Len];
inline void input(){
for(int i = 0; i != Len; ++i)
for(int j = 0; j != Len; ++j)
cin >> data[i][j];
}
int getS(int m, int n){
int s = 0;
if(!data[m][n] || visited[m][n])
return 0;
else{
s += 1;
visited[m][n] = 1;
if (m - 1 >= 0){
s += getS(m-1, n);
}
if (m + 1 < Len){
s += getS(m+1, n);
}
if (n - 1 >= 0){
s += getS(m, n-1);
}
if (n + 1 <Len){
s += getS(m, n+ 1);
}
}
return s;
}
void Solve(){
int maxS = 0;
int tmp;
int i, j;
for(i = 0; i != Len; ++i){
for(j = 0; j != Len; ++j){
if(!data[i][j] || visited[i][j])
continue;
tmp = getS(i, j);
maxS = (tmp > maxS)? tmp: maxS;
}
}
cout << maxS <<endl;
}
int main(){
input();
Solve();
return 0;
}

实际上,只是在 for 循环里面多了一个 if 判断,这样对于为 0 的元素,就不用进入函数,减少了函数调用的开销,同时,不需要从每一个 1 都开始进行一次遍历,因此,不需要每次循环都对 visited 数组进行一次 memset

3. 如果一个整数序列从前往后读和从后往前读序列相同,则称该序列为回文序列,如 (1),(1, 3, 1) ,(23, 25, 25, 23),给定一个整数序列,定义对该整数序列的一次操作如下:从该序列中选出两个数,将两个数相加,将相加后的和放入原来两个数在的位置(只放一个和),问任意给定一个序列,需要多少次这样的操作可将该序列变成一个回文序列。

例如,序列为 (1, 1, 1, 3),则两次操作可将其变为回文序列:(1, 1, 1, 3) ->(2, 1, 3) -> (3, 3),即先将 1,2 两个数相加,再将 1,2 两个数相加。显然任意给定一个包含 n 个数的序列,最多进行 n-1 次操作即可将其变为回文序列,此时,序列中只有一个数。

一个序列要是回文序列,那么前后的数要分别相同,因此,我们设置两个指针,分别指向第一个数和最后一个数,如果第一个数和最后一个数相同,那么第一个指针加一,第二个指针减一,继续判断,如果不等,则将小的哪一端的数加到与它相邻的数上面,并将指针加一… 重复下去,直到第一个指针不小于第二个指针为止,此时的序列即为回文序列,这样便可求出操作次数。

  • Input : data[n];
  • output : OpTime;
  1. Optime = 0; low = 0, high = n - 1;
  2. if (low < high)
    • if (data[low] == data[high]) low = low + 1, high = high - 1, goto 2;
    • else if (data[low] < data [high]) data[low + 1] = data[low+1] + data[low], OpTime = OpTime + 1, low = low + 1, goto 2;
    • else data[high - 1] = data[high-1] + data[high], OpTime = OpTime + 1, high = high - 1, goto 2
  3. else return OpTime;

AC 代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/*************************************************************************
> Filename: huiwen.cpp
> Author: Lv Feng
> Mail: lvfeng97@outlook.com
> Date: 2018-10-13
************************************************************************/
#include<bits/stdc++.h>
using namespace std;
int n;
const int MaxNum = 50;
int data[MaxNum];
void input(){
cin >> n;
for(int i = 0; i != n; ++i){
cin >> data[i];
}
}
int Solve(){
int Time = 0;
int low = 0, high = n - 1;
while(low < high){
if (data[low] == data[high]){
++low;
--high;
continue;
}
else if(data[low] < data[high]){
++Time;
data[low+1] += data[low];
++low;
continue;
}
else{
++Time;
data[high-1] += data[high];
--high;
}
}
return Time;
}
int main(){
input();
cout << Solve() <<endl;
return 0;
}
0%