网易雷火实习生招聘编程题

题目来源：牛客网/profile/7952866/test/7775568/76265

1.字符串编码

给定一个字符串，请你将字符串重新编码，将连续的字符替换成“连续出现的个数+字符”。比如字符串AAAABCCDAA会被编码成4A1B2C1D2A。

输入例子:

AAAABCCDAA

输出例子:

4A1B2C1D2A

思路比较简单，只需要遍历字符串，对每一个单独的字符设置一个初始值为1的计数器，然后比较它和相邻的字符是否相同，如果相同则加1，直到遇到不同的字符，输出当前计数器的值并重置为1。

测试代码如下：

#include <cstdio>#include <string>#include <iostream>using namespace std;string num = "0123456789";string intToString(int n) {//int转成string，比如 12转为‘12’string str = "";while (n) {str = num[n % 10] + str;n = n / 10;}return str;}string solve(string str) {int len = str.size();int i = 0;char cur;int cnt;string ans = "";//从字符串头部开始依次遍历while (i < len) {cur = str[i];cnt = 0;int j = 0;for (j = i; j < len; j++) { // 从当前位置开始检索if (str[j] == cur) {cnt++;}else if (str[j] != cur) {ans = ans + intToString(cnt);ans = ans + cur;i = j; // 从i = j这个位置再开始检索break;}}if (j == len) {ans = ans + intToString(cnt);ans = ans + cur;break;}}return ans;}int main(){string str;while (cin >> str){string ans = solve(str);cout << ans << endl;}return 0;}

测试结果：

2.赛马

在一条无限长的跑道上，有N匹马在不同的位置上出发开始赛马。当开始赛马比赛后，所有的马开始以自己的速度一直匀速前进。每匹马的速度都不一样，且全部是同样的均匀随机分布。在比赛中当某匹马追上了前面的某匹马时，被追上的马就出局。 请问按以上的规则比赛无限长的时间后，赛道上剩余的马匹数量的数学期望是多少

输入描述:

每个测试输入包含1个测试用例

输入只有一行，一个正整数N

1 <= N <= 1000

输出描述:

输出一个浮点数，精确到小数点后四位数字，表示剩余马匹数量的数学期望

输入例子:

1

2

输出例子:

1.0000

1.5000

思路分析：题目看上去有点费解，个人更感觉像是一道智力题。我们假设有N匹马赛跑，最后剩下的那个是冠军。注意题目中说每个马的速度不一样，这就说明最后只会剩下一个马，不可能出现并列的情况。另外数学期望的意思就是如果这匹马的编号是i，那P（i）表示i是冠军的概率，就是数学期望。可以这样想一下：如果只有一匹马，那么这匹马肯定是冠军，数学期望显然是1。如果有两匹马，那么某一匹马是冠军的概率是0.5，某一时刻其中一个马被淘汰了，那么另一个马的数学期望变成1，相加就是1.5。依次类推，如果刚开始有N匹马，P（i） = 1 / N，某一时刻P（i） = 1 / （N - 1）、1/（N - 2）......所以这道题的答案就是计算1 + 1 / 2 + 1 / 3 + 1 / 4 + ... + 1 / N的和，就是调和级数。

测试代码如下：

#include <cstdio>//调和级数int main() {int n;while (scanf_s("%d", &n) != EOF){double sum = 0.0;for (int i = 1; i <= n; i++) {sum = sum + 1.0 / i;}printf("%.4lf\n", sum);}return 0;}

测试结果：

3.最大和

在一个N*N的数组中寻找所有横，竖，左上到右下，右上到左下，四种方向的直线连续D个数字的和里面最大的值

输入描述:

每个测试输入包含1个测试用例，第一行包括两个整数 N 和 D :

3 <= N <= 100

1 <= D <= N

接下来有N行，每行N个数字d:

0 <= d <= 100

输出描述:

输出一个整数，表示找到的和的最大值

输入例子:

4 2

87 98 79 61

10 27 95 70

20 64 73 29

71 65 15 0

输出例子:

193

思路：直接从行、列、左上到右下，右上到左下，四种方向暴力搜索

测试代码：

#include <iostream>#define MAX 100 + 10int Max = 0;bool check1(int x, int y, int d, int n) {if (x + d - 1 > n) return false;if (y + d - 1 > n) return false;return true;}bool check2(int x, int y, int d, int n) {if (x + d - 1 > n) return false;if (y - d < 0)return false;return true;}int main() {int n, d;while (scanf_s("%d%d", &n, &d) != EOF) {Max = 0;int arr[MAX][MAX];for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {scanf_s("%d", &arr[i][j]);}}// 先从每行开始找for (int row = 1; row <= n; row++){for (int i = 1; i <= n - d + 1; i++){int sum = 0;for (int j = i; j < d + i; j++) {sum = sum + arr[row][j];}if (sum > Max)Max = sum;}}// 再从每列开始找for (int col = 1; col <= n; col++) {for (int i = 1; i <= n - d + 1; i++){int sum = 0;for (int j = i; j < d + i; j++){sum = sum + arr[j][col];}if (sum > Max) Max = sum;}}// 再从左上到右下对角线开始找for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {// 从i,j起点开始找int x = i;int y = j;if (check1(x, y, d, n)) {int cnt = 0;int sum = 0;while (cnt < d) {sum = sum + arr[x][y];cnt++;x++;y++;}if (sum > Max)Max = sum;}}}// 再从右上到左下对角线开始找for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {// 从i,j起点开始找int x = i;int y = j;if (check2(x, y, d, n)) {int cnt = 0;int sum = 0;while (cnt < d){sum = sum + arr[x][y];cnt++;x++;y--;}if (sum > Max) Max = sum;}}}printf("%d\n", Max);}return 0;}

测试结果如下：

4.推箱子

大家一定玩过“推箱子”这个经典的游戏。具体规则就是在一个N*M的地图上，有1个玩家、1个箱子、1个目的地以及若干障碍，其余是空地。玩家可以往上下左右4个方向移动，但是不能移动出地图或者移动到障碍里去。如果往这个方向移动推到了箱子，箱子也会按这个方向移动一格，当然，箱子也不能被推出地图或推到障碍里。当箱子被推到目的地以后，游戏目标达成。现在告诉你游戏开始是初始的地图布局，请你求出玩家最少需要移动多少步才能够将游戏目标达成。

输入描述:

每个测试输入包含1个测试用例

第一行输入两个数字N，M表示地图的大小。其中0<N，M<=8。

接下来有N行，每行包含M个字符表示该行地图。其中 . 表示空地、X表示玩家、*表示箱子、#表示障碍、@表示目的地。

每个地图必定包含1个玩家、1个箱子、1个目的地。

输出描述:

输出一个数字表示玩家最少需要移动多少步才能将游戏目标达成。当无论如何达成不了的时候，输出-1。

输入例子:

4 4

....

..*@

....

.X..

6 6

...#..

......

#*##..

..##.#

..X...

.@#...

输出例子:

3

11

思路：利用BFS，每一步有4中情况，用四维数组记录每一个人和箱子所在位置的状态，如果之前出现过这种状态，直接跳过，否则计数加一，一直遍历，若队列为空还没有输出，则无法到达。否则可以到达。by：/njudongchen/article/details/61415043

测试代码如下：

#include <iostream>#include <string>#include <queue>#include <vector>using namespace std;struct humanbox{//创建一个结构体：人和箱子的坐标int hx, hy, bx, by;humanbox(int x, int y, int bbx, int bby) :hx(x), hy(y), bx(bbx), by(bby){};};int main(){int n, m;cin >> n >> m;vector<vector<int>> map(n, vector<int>(m, 0));int hx, hy; //玩家起点坐标int bx, by; //箱子坐标int endx, endy; //目的地坐标for (int i = 0; i != n; ++i){//更新地图mapstring str;cin >> str;for (int j = 0; j != m; ++j){if (str[j] == 'X'){map[i][j] = 'X';hx = i;hy = j;}else if (str[j] == '#')map[i][j] = '#';else if (str[j] == '@'){map[i][j] = '@';endx = i;endy = j;}else if (str[j] == '*'){map[i][j] = '*';bx = i;by = j;}}}//枚举四个方向：向右走、向左走、向下走、向上走int stepx[4] = { 0, 0, 1, -1 };int stepy[4] = { 1, -1, 0, 0 };//更新步数int count[10][10][10][10] = { 0 };queue<humanbox> que;que.push(humanbox(hx, hy, bx, by));count[hx][hy][bx][by] = 1;while (!que.empty()){humanbox top_que = que.front();que.pop();if (top_que.bx == endx&&top_que.by == endy){//到达终点cout << (count[top_que.hx][top_que.hy][top_que.bx][top_que.by]) - 1;//输出减1是因为起始从1开始cout<< endl;return 0;}for (int i = 0; i != 4; ++i){int hnx = top_que.hx + stepx[i];int hny = top_que.hy + stepy[i];if (hnx<0 || hny<0 || hnx >= n || hny >= m || map[hnx][hny] == '#')//当越界或者遇到障碍物continue;if (hnx == top_que.bx&&hny == top_que.by){//当玩家遇到箱子int bnx = top_que.bx + stepx[i];int bny = top_que.by + stepy[i];if (bnx<0 || bny<0 || bnx >= n || bny >= m || map[bnx][bny] == '#') //当箱子越界或者遇到障碍物continue;if (count[hnx][hny][bnx][bny]) continue;count[hnx][hny][bnx][bny] = count[top_que.hx][top_que.hy][top_que.bx][top_que.by] + 1;que.push(humanbox(hnx, hny, bnx, bny));}else{if (count[hnx][hny][top_que.bx][top_que.by])continue;count[hnx][hny][top_que.bx][top_que.by] = count[top_que.hx][top_que.hy][top_que.bx][top_que.by] + 1;que.push(humanbox(hnx, hny, top_que.bx, top_que.by));}}}cout << -1 << endl;return 0;}

测试结果：