第一次笔试没有参加,但是牛客上已经有题了,很遗憾只做出前两道.感觉有很多要注意的地方,要不然根本做不完啊.
编码
复制代码
1
2
3题目1: 给定一个字符串，请你将字符串重新编码，将连续的字符替换成“连续 出现的个数+字符”。比如字符串AAAABCCDAA会被编码成4A1B2C1D2A。
.统计连续出现的字符数目.注意数字字符串之间转换,别要在这些细节上浪费太多时间,要不然后边题没时间做!代码:
复制代码
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
#include<iostream>
#include<sstream>
int main()
{
std::string s ;
std::cin >> s;
std::string res="";
if(s==""){
std::cout <<"";
return 0;
}
// kong zi fu
int
cnt =1 ;
for(int i =1 ; i< s.length(); i++)
if(s[i-1]==s[i])cnt++;
else
{
std::stringstream ss;
std::string str;
ss<<cnt;
ss>>str;
res = res + str + s[i-1];
cnt=1;
}
std::stringstream ss;
std::string str;
ss<<cnt;
ss>>str;
res = res +str +s[s.length()-1];
std::cout <<res;
return 0;
}简单搜索:
复制代码
1
2
3
.题目2:
在一个N*N的数组中寻找所有横，竖，左上到右下，右上到左下，四种方向的直线连续D个数字的和里面最大的值
分析
.可优化之处在于”连续” N 个数字和,N大于等于D,每次当和中包含的数字第一次大于N时,要想得到当前和，只需要减去上一次最后一个
值再加上当前的值就可以了, 每次遍历求和时间O(n),横竖斜着遍历去找就可，总时间Ｏ（ｎ＾２）
考察编程熟练啊,被bug卡住就杯具了
.代码;
复制代码
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include<iostream>
#include<vector>
using std::cin;
using std::cout;
using std::vector;
using std::endl;
int main()
{
/*
4 2
87 98 79 61
10 27 95 70
20 64 73 29
71 65 15 0
*/
// input:
int N , D;
cin>>N>>D;
vector<vector<int>> mm(N , vector<int>(N, 0)) ;
for(int i =0 ; i< N ; i++)
for(int j =0 ; j< N ; j++)
cin>>mm[i][j];
int maxsum =0;
for(int i =0 ; i < N ; i++)
{
int csum =0;
for(int j =0 ; j < N ; j++)
{
csum = j < D? csum + mm[i][j]
:
csum + mm[i][j] - mm[i][j-D];
if(j>=D-1)
maxsum = maxsum < csum? csum : maxsum;
}
csum =0 ;
for(int j =0 ; j < N ; j++)
{
csum = j < D? csum + mm[j][i]
: csum + mm[j][i] - mm[j-D][i];
if(j>=D-1)
maxsum = maxsum < csum? csum : maxsum;
}
}
int i = N-1
, j = 0;
while(i>=0){
int m = i , n =j;
int cnt =0;
int csum =0;
while(n<N&&m<N)
{
csum = cnt < D ? csum + mm[m][n]:csum+mm[m][n] - mm[m-D][n-D];
if(cnt>=D-1)maxsum = maxsum<csum? csum: maxsum;
m++;n++;cnt++;
}
i--;
}
i = 0;j = 1;
while(j<N)
{
int m = i , n = j;
int cnt =0 ;
int csum =0 ;
while(m < N && n < N)
{
csum = cnt < D ? csum + mm[m][n] : csum+mm[m][n] - mm[m-D][n-D];
if(cnt >= D-1)maxsum = maxsum< csum?csum: maxsum;
m++; n++;cnt++;
}
j++;
}
i =0 ; j = 0;
while(j<N)
{
int m = i , n = j;
int cnt =0;
int csum =0 ;
while(m<N&&n>=0)
{
csum = cnt < D ? csum +mm[m][n] : csum + mm[m][n] - mm[m-D][n+D];
if(cnt >= D-1) maxsum = maxsum < csum?csum:maxsum;
m++;n--;cnt++;
}
j++;
}
i = 1; j =N-1;
while(i < N)
{
int m = i , n = j;
int cnt = 0;
int csum = 0;
while(m<N&&n>=0)
{
csum = cnt <D? csum + mm[m][n] :csum +mm[m][n] - mm[m-D][n+D];
if(cnt >= D-1) maxsum = maxsum <csum ? csum:maxsum;
m++;n--;cnt++;
}
i++;
}
cout <<maxsum;
return 0;
}推箱子
复制代码
1
2
3
4
5
6
7
8
9
10
.题目3:
大家一定玩过“推箱子”这个经典的游戏。具体规则就是在一个N*M的地
图上，有1个玩家、1个箱子、1个目的地以及若干障碍，其余是空地。
玩家可以往上下左右4个方向移动，但是不能移动出地图或者移动到障
碍里去。如果往这个方向移动推到了箱子，箱子也会按这个方向移动一
格，当然，箱子也不能被推出地图或推到障碍里。当箱子被推到目的地
以后，游戏目标达成。现在告诉你游戏开始是初始的地图布局，请你求
出玩家最少需要移动多少步才能够将游戏目标达成。
.输入格式代码注释里有,*表示箱子,X表示人,@表示目的地,#表示障碍
分析
.后来做才发现这是宽度优先的题目,在一个图结构当中如果每条边权重是1的话,宽度优先搜索第一次到达目的地步数就是到此位置的最小代价. 分析这道题最好的方式就是画出状态转移关系,小人和箱子的位置确定了当前玩家的一个状态,下一步要去往的状态无非是这么两种情况:
. 人走到另一个空地,箱子没动
.人推箱子前进一步
实现简述
复制代码
1
2
3
4
5
6
.声明一个四位数组来st,当前状态表示为st[x][x][bx][bx]:人位
置(x,y),箱子位置(bx,by),并将初始位置数组值设为1,将初始值压
入一个队列中
.每次从队列中取出一个元素,宽度优先下一个未曾到达的状态(以上分
析的两种)判断箱子是否到达终点.如果是打印路长并退出.
.没有找到相关路径打印-1.复制代码
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<iostream>
#include<vector>
#include<queue>
using std::cin ;
using std::cout;
using std::vector;
using std::endl;
using std::queue;
/*
4 4
....
..*@
....
.X..
*/
int st[10][10][10][10];
int x,y,bx,by,tx,ty;
int m ,
n ;
vector<vector<char>> mm ;
bool valid(int x,int y ){
//cout <<m<<" "<<n<<"-"<<endl;
if(x>=0&&x<m&&y>=0&&y<n&&mm[x][y]!='#')return true;
return false;
}
int main(){
cin >> m >>n;
mm= vector<vector<char>>(m , vector<char>(n ,' ' ));
for(int i =0 ; i < m ; i++)
for(int j=0 ; j< n ; j++)
{
char t ;
cin >>t;
if(t=='X'){
x = i;y = j;
// cout <<x<<" "<<y<<endl;
}
if(t == '*'){
bx = i ;by = j;
}
if(t == '@'){
tx = i ; ty = j;
}
mm[i][j] = t;
}
//
record every state of the
vector<vector<int>> next= {{-1, 0},{1,0},{0,1},{0,-1}};
queue<vector<int>> que ;
que.push({x,y,bx,by});
st[x][y][bx][by] =1 ;
while(!que.empty())
{
vector<int> t = que.front();
que.pop();
x =
t[0];
y = t[1];
bx=t[2]; by = t[3];
for(int i =0 ; i < next.size() ; i++)
{
int nx = x+next[i][0],ny =y+next[i][1];
int nnx = nx+next[i][0],nny =ny+next[i][1];
if(valid(nx,ny)&&(nx!=bx||ny!=by)&&st[nx][ny][bx][by]==0)
{
st[nx][ny][bx][by]= st[x][y][bx][by]+1;
que.push({nx,ny,bx,by});
continue;
}else if(nx==bx&&ny==by&&valid(nnx,nny)&&st[nx][ny][nnx][nny]==0){
st[nx][ny][nnx][nny] = st[x][y][bx][by]+1;
if(mm[nnx][nny]=='@'){cout<<st[nx][ny][nnx][nny]-1;return 0;}
que.push({nx,ny,nnx,nny});
}
}
}
cout <<-1;
return 0;
}赛马
复制代码
1
2
3
4
5
6
.题目4:
在一条无限长的跑道上，有N匹马在不同的位置上出发开始赛马。当开
始赛马比赛后，所有的马开始以自己的速度一直匀速前进。每匹马的速
度都不一样，且全部是同样的均匀随机分布。在比赛中当某匹马追上了
前面的某匹马时，被追上的马就出局。 请问按以上的规则比赛无限长
的时间后，赛道上剩余的马匹数量的数学期望是多少分析
.开始认为几匹快马速度一样才可能同时留下来,没好好读题,其实人家说了马的速度都不一样.假设几匹马的速度是 a1<a2<a3<...<an ,ai匹马留下概率是P(i), P（i）=1/i , 因为只有在第一匹快马后面才能留下来,这是i种情况之一, 第i匹马留下期望 0∗(i−1)/i+1/i ,由 E(X+Y)=E(X)+E(Y) 得到所有马期望和1 + 1 / 2 + 1 / 3 + 1 / 4 + … + 1 / N，就是调和级数。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<stdio.h>
#include<math.h>
using std::cin;
using std::cout;
int main(){
int n ;
cin >>n;
if(n==0)
{
cout <<0;
return 0;
}
float sum =0.0;
for(int i =1 ; i<=n ; i++)
{
sum+= 1.0/i;
}
printf("%.4f",sum);
return 0;
}最后
以上就是强健大地最近收集整理的关于网易雷火盘古实习2018笔试题编码简单搜索:推箱子赛马的全部内容，更多相关网易雷火盘古实习2018笔试题编码简单搜索内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复