网易2017春招笔试真题编程题集合

题目来源：牛客网 https://www.nowcoder.com/profile/7952866/test/7811777/83061

1、双核处理

题目描述

一种双核CPU的两个核能够同时的处理任务，现在有n个已知数据量的任务需要交给CPU处理，假设已知CPU的每个核1秒可以处理1kb，每个核同时只能处理一项任务。n个任务可以按照任意顺序放入CPU进行处理，现在需要设计一个方案让CPU处理完这批任务所需的时间最少，求这个最小的时间。

输入描述

输入包括两行：第一行为整数n(1 ≤ n ≤ 50)

　　　　　　第二行为n个整数lengthi，表示每个任务的长度为length[i]kb，每个数均为1024的倍数。

输出描述：输出一个整数，表示最少需要处理的时间

输入例子：5

　　　　　3072 3072 7168 3072 1024

输出例子： 9216

思路分析：

题意很清晰，就是给一个数组，要我们把他分成两份并分别求和，使得这两个和的最大值最小。我下意识的想法是枚举出所有有可能的和，但是复杂度大概是O(2^n) ，貌似会超时。可是仔细一看，length[i] 的取值在[1, 4096] 之间，那么最多n个数的和的范围肯定在[n, 4096n] 之间。

代码：

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<set>
 4 using namespace std;
 5 int n;
 6 int a[51];
 7 set<int>s;
 8 int sum = 0;
 9 int main()
10 {
11     cin >> n;
12     for (int i = 0; i<n; i++)
13     {
14         int tmp;
15         cin >> tmp;
16         a[i] = tmp / 1024;
17         sum += a[i];
18     }
19     s.insert(0);
20     for (int i = 0; i<n; i++)
21     {
22         set<int>added;
23         for (set<int>::iterator it = s.begin(); it != s.end(); it++)
24         {
25             added.insert(*it + a[i]);
26         }
27         s.insert(added.begin(), added.end());
28     }
29     int ans = sum;
30     for (set<int>::iterator it = s.begin(); it != s.end(); it++)
31     {
32         ans = min(ans, max(*it, sum - *it));
33     }
34     cout << ans * 1024 << endl;
35 }

结果：

2、赶去公司

题目描述

终于到周末啦！小易走在市区的街道上准备找朋友聚会，突然服务器发来警报,小易需要立即回公司修复这个紧急bug。假设市区是一个无限大的区域，每条街道假设坐标是(X，Y)，小易当前在(0，0)街道，办公室在(gx,gy)街道上。小易周围有多个出租车打车点，小易赶去办公室有两种选择，一种就是走路去公司，另外一种就是走到一个出租车打车点，然后从打车点的位置坐出租车去公司。每次移动到相邻的街道(横向或者纵向)走路将会花费walkTime时间，打车将花费taxiTime时间。小易需要尽快赶到公司去，现在小易想知道他最快需要花费多少时间去公司。输入描述: 输入数据包括五行:

第一行为周围出租车打车点的个数n(1 ≤ n ≤ 50)

第二行为每个出租车打车点的横坐标tX[i] (-10000 ≤ tX[i] ≤ 10000)

第三行为每个出租车打车点的纵坐标tY[i] (-10000 ≤ tY[i] ≤ 10000)

第四行为办公室坐标gx,gy(-10000 ≤ gx,gy ≤ 10000),以空格分隔

第五行为走路时间walkTime(1 ≤ walkTime ≤ 1000)和taxiTime(1 ≤ taxiTime ≤ 1000),以空格分隔

输出描述: 输出一个整数表示，小易最快能赶到办公室的时间

输入例子: 2

　　　　-2 -2

　　　　0 -2

　　　　-4 -2

　　　　15 3

输出例子: 42

思路分析

基础题，先算步行的时间，再枚举每个打车点算出打的时间，找到时间最短的即可。直接进行比较就可以，没有复杂的过程。

代码：

 1 #include<iostream>
 2 #include<vector>
 3 using namespace std;
 4 int main()
 5 {
 6     int n;
 7     cin >> n;
 8     vector<int> taxiX(n, 0);
 9     vector<int> taxiY(n, 0);
10     for (int i = 0; i < n; i++)
11         cin >> taxiX[i];
12     for (int i = 0; i < n; i++)
13         cin >> taxiY[i];
14     int gx, gy;
15     cin >> gx >> gy;
16     int taxiTime, walkTime;
17     cin >> walkTime >> taxiTime;
18     int ans = walkTime*(abs(gx) + abs(gy)); //不打车所用的时间
19     for (int j = 0; j < n; j++)
20     {
21         int tmp = walkTime*(abs(taxiX[j]) + abs(taxiY[j])) + taxiTime*(abs(gx - taxiX[j]) + abs(gy - taxiY[j]));
22         if (tmp < ans)
23             ans = tmp;
24     }
25     cout << ans << endl;
26     return 0;
27 }

结果：

3、调整队形

题目描述

在幼儿园有n个小朋友排列为一个队伍，从左到右一个挨着一个编号为(0~n-1)。其中有一些是男生，有一些是女生，男生用’B’表示，女生用’G’表示。小朋友们都很顽皮，当一个男生挨着的是女生的时候就会发生矛盾。作为幼儿园的老师，你需要让男生挨着女生或者女生挨着男生的情况最少。你只能在原队形上进行调整，每次调整只能让相邻的两个小朋友交换位置，现在需要尽快完成队伍调整，你需要计算出最少需要调整多少次可以让上述情况最少。例如： GGBBG -> GGBGB -> GGGBB 这样就使之前的两处男女相邻变为一处相邻，需要调整队形2次输入描述: 输入数据包括一个长度为n且只包含G和B的字符串.n不超过50.

输出描述: 输出一个整数，表示最少需要的调整队伍的次数

输入例子: GGBBG

输出例子: 2

思路分析：

我们对于串中第一个’B’然后计算把它swap到第一个位置需要多少次,第二个’B’swap到第二个位置需要多少次…依次类推..
然后对于’G’同理, 最后取个较小值即为答案。

代码：

 1 #include<iostream>
 2 #include<string>
 3 #include<algorithm>
 4 #include<cmath>
 5 using namespace std;
 6 
 7 int main()
 8 {
 9     string str;
10     cin >> str;
11     int boyCount = 0, girlCount = 0, boy = 0, girl = 0;
12     for (int i = 0; i < str.size(); i++)
13     {
14         if (str[i] == 'B')
15         {
16             boyCount += i - boy;
17             boy++;
18         }
19         else
20         {
21             girlCount += i - girl;
22             girl++;
23         }
24     }
25     cout << min(boyCount, girlCount) << endl;
26 }

结果：

4、魔力手环

题目描述

小易拥有一个拥有魔力的手环上面有n个数字(构成一个环),当这个魔力手环每次使用魔力的时候就会发生一种奇特的变化：每个数字会变成自己跟后面一个数字的和(最后一个数字的后面一个数字是第一个),一旦某个位置的数字大于等于100就马上对100取模(比如某个位置变为103,就会自动变为3).现在给出这个魔力手环的构成，请你计算出使用k次魔力之后魔力手环的状态。

输入描述: 输入数据包括两行：第一行为两个整数n(2 ≤ n ≤ 50)和k(1 ≤ k ≤ 2000000000),以空格分隔第二行为魔力手环初始的n个数，以空格分隔。范围都在0至99.

输出描述: 输出魔力手环使用k次之后的状态，以空格分隔，行末无空格。

输入例子: 3 2

　　　　 1 2 3

输出例子: 8 9 7

思路分析：

直接按逻辑进行运算，比较费时，推荐使用快速矩阵幂算法，这里采用的是直接算。

代码：

 1 #include<iostream>
 2 #include<vector>
 3 
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     int n, k;
 9     cin >> n >> k;
10     vector<long> arr ;
11     for (int i = 0; i <= n; i++)
12         arr.push_back(0);
13     for (int i = 1; i <= n; i++)
14         cin >> arr[i];
15     vector<long> tmp = arr;
16     for (int j = 1; j <= k; j++)
17     {
18         int i = 1;
19         while (i < n )
20         {
21             tmp[i] += arr[i + 1];
22             if (tmp[i]>100)
23                 tmp[i]%= 100;
24             i++;
25         }
26         while (i==n)
27         {
28             tmp[i] += arr[1];
29             if (tmp[i]>100)
30                 tmp[i] %= 100;
31             i++;
32         }
33         arr = tmp;
34     }
35     cout << arr[1];
36     for (int i = 2; i <= n; i++)
37         cout <<" "<< arr[i];
38     cout << endl;
39     return 0;
40 }

结果：

5、集合

题目描述

小易最近在数学课上学习到了集合的概念,集合有三个特征：1.确定性 2.互异性 3.无序性. 小易的老师给了小易这样一个集合： S = { p/q | w ≤ p ≤ x, y ≤ q ≤ z } 需要根据给定的w，x，y，z,求出集合中一共有多少个元素。小易才学习了集合还解决不了这个复杂的问题,需要你来帮助他。

输入描述: 输入包括一行：一共4个整数分别是w(1 ≤ w ≤ x)，x(1 ≤ x ≤ 100)，y(1 ≤ y ≤ z)，z(1 ≤ z ≤ 100).以空格分隔

输出描述: 输出集合中元素的个数

输入例子: 1 10 1 1

输出例子: 10

思路分析

题意就是给分数判重，显然我们不能直接算，因为浮点数是不精确的，乘以1.0000就可以了，然后丢进set里就好了。

代码：

 1 #include<iostream>
 2 #include<set>
 3 using namespace std;
 4 int getSetNum(int w, int x, int y, int z)
 5 {
 6     int count = 0;
 7     set<double> s;
 8     for (int i = w; i <= x; i++)
 9         for (int j = y; j <= z; j++)
10         {
11             s.insert(i*1.0000 / j);
12         }
13     count = s.size();
14     return count;
15 }
16 int main()
17 {
18     int w, x, y, z;
19     cin >> w >> x >> y >> z;
20     int ans;
21     ans = getSetNum(w, x, y, z);
22     cout << ans << endl;
23     return 0;
24 }

结果：

6、奇怪的表达式求值

题目描述

常规的表达式求值，我们都会根据计算的优先级来计算。比如/的优先级就高于+-。但是小易所生活的世界的表达式规则很简单，从左往右依次计算即可，而且小易所在的世界没有除法，意味着表达式中没有/，只有(+, - 和 )。现在给出一个表达式，需要你帮忙计算出小易所在的世界这个表达式的值为多少

输入描述: 输入为一行字符串，即一个表达式。其中运算符只有-,+,*。参与计算的数字只有0~9. 保证表达式都是合法的，排列规则如样例所示。

输出描述: 输出一个数，即表达式的值

输入例子: 3+5*7

输出例子: 56

思路分析：

关键之处在于：输入的一个数字和下一个数字之间肯定隔着一个操作符，所以在第一个for循环的时候i=i+2，依次取数，再取操作符进行运算。

代码：

#include<iostream>
#include<string>
using namespace std;

int main()
{
    string str;
    cin >> str;
    int ans = str[0] - '0';
    for (int i = 1; i < str.length() - 1; i += 2)
    {
        //关键之处i+=2
        if (str[i] == '*')
            ans = ans * (str[i + 1] - '0');
        else if (str[i] == '+')
            ans = ans + (str[i + 1] - '0');
        else 
        {
            ans = ans - (str[i + 1] - '0');
        }
    }
    cout << ans << endl;
    return 0;
}

结果：

7、小易记单词

题目描述

小易参与了一个记单词的小游戏。游戏开始系统提供了m个不同的单词，小易记忆一段时间之后需要在纸上写出他记住的单词。小易一共写出了n个他能记住的单词，如果小易写出的单词是在系统提供的，将获得这个单词长度的平方的分数。注意小易写出的单词可能重复，但是对于每个正确的单词只能计分一次。

输入描述: 输入数据包括三行：

　　第一行为两个整数n(1 ≤ n ≤ 50)和m(1 ≤ m ≤ 50)。以空格分隔

　　第二行为n个字符串，表示小易能记住的单词，以空格分隔，每个单词的长度小于等于50。

　　第三行为m个字符串，系统提供的单词，以空格分隔，每个单词的长度小于等于50。

输出描述: 输出一个整数表示小易能获得的分数

输入例子: 3 4

　　　　apple orange strawberry strawberry orange grapefruit watermelon

输出例子: 136

思路分析

把能记住的单词丢进set里，可以去除重复单词，合理利用set的insert函数，然后判断每一个是不是在系统提供的集合里即可。

代码：

 1 #include<iostream>
 2 #include<string>
 3 #include<algorithm>
 4 #include<set>
 5 //为了避免重复，将单词放入set里
 6 using namespace std;
 7 
 8 int main()
 9 {
10     int n, m;
11     cin >> n >> m;
12     set<string> str1, str2;
13     for (int i = 0; i<n; i++)
14     {
15         //读入小易记住的单词
16         string str;
17         cin >> str;
18         str1.insert(str);
19     }
20     for (int i = 0; i<m; i++)
21     {
22         //读入系统提供的单词
23         string str;
24         cin >> str;
25         str2.insert(str);
26     }
27     int ans = 0;
28     for (set<string>::iterator it = str1.begin(); it != str1.end(); it++)
29     {
30         if (str2.find(*it) != str2.end())
31         {
32             //find()函数返回指向查找元素的迭代器,如果不存在返回set的end()迭代器.
33             ans += it->length() * it->length();//计算分数：单词长度的平方
34         }
35     }
36     cout << ans << endl;
37 }

结果：

8、消除重复元素

题目描述

小易有一个长度为n序列，小易想移除掉里面的重复元素，但是小易想是对于每种元素保留最后出现的那个。小易遇到了困难,希望你来帮助他。

输入描述:

输入包括两行：第一行为序列长度n(1 ≤ n ≤ 50)

　　　　　　第二行为n个数sequencei，以空格分隔

输出描述: 输出消除重复元素之后的序列，以空格分隔，行末无空格

输入例子: 9

　　　　100 100 100 99 99 99 100 100 100

输出例子: 99 100

思路分析

从后向前先判重后加入即可，合理利用集合set的insert函数，去除重复元素

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<vector>
 4 #include<set>
 5 
 6 //从后向前先判重后加入即可。
 7 using namespace std;
 8 int main()
 9 {
10     int n;
11     cin >> n;
12     int a[51] = { 0 };
13     vector<int> arr;
14     set<int> s;
15     for (int i = 0; i < n; i++)
16         cin >> a[i];
17     for (int i = n - 1; i >= 0; i--)
18     {
19         if (s.find(a[i]) == s.end())
20         {
21             s.insert(a[i]);
22             arr.push_back(a[i]);
23         }
24     }
25     cout << arr[arr.size() - 1];
26     for (int i = arr.size() - 2; i >= 0; i--)
27     {
28         cout << " " << arr[i];
29     }
30     cout << endl;
31     return 0;
32 }

结果：

9、涂棋盘

题目描述

小易有一块n*n的棋盘，棋盘的每一个格子都为黑色或者白色，小易现在要用他喜欢的红色去涂画棋盘。小易会找出棋盘中某一列中拥有相同颜色的最大的区域去涂画，帮助小易算算他会涂画多少个棋格。

输入描述: 输入数据包括n+1行：

　　第一行为一个整数n(1 ≤ n ≤ 50),即棋盘的大小

　　接下来的n行每行一个字符串表示第i行棋盘的颜色，’W’表示白色，’B’表示黑色

输出描述: 输出小易会涂画的区域大小

输入例子: 3

　　　　 BWW

　　　　 BBB

　　　　 BWB

输出例子: 3

思路分析：

注意，只是找某一列的最大区域，并不是整个棋盘的最大区域，所以比较简单。

代码：

 1 #include<iostream>
 2 #include<string>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     string str[52];
 9     int n;
10     cin >> n;
11     for (int i = 0; i < n; i++)
12         cin >> str[i];
13     int maxCnt = 0;//保存最大区域的值
14     for (int j = 0; j < n; j++)
15     {
16         int cnt = 1;//临时保存每一列的最大区域的值
17         for (int i = 1; i < n; i++)
18         {
19             if (str[i][j] == str[i - 1][j])
20             {
21                 cnt++;
22             }
23             else
24             {
25                 maxCnt = max(maxCnt, cnt);
26                 cnt = 1;
27             }
28 
29         }
30         maxCnt = max(maxCnt, cnt);
31     }
32     cout << maxCnt << endl;
33     return 0;
34 }