猿辅导2020秋招笔试真题
猿辅导2020秋招笔试真题
1、小猿的迷宫之旅
【题目描述】有一个N*M大小的迷宫矩阵，迷宫的每一个格子有一个数值（a[i][j] <10^9）。小猿在迷宫中发现，它只能朝着上下左右四个方向的相邻格子前进，并且只能进入比当前位置数值更大的格子。但是小猿有个紧急呼救按钮，他可以通过按下按钮，强行进入到不满足数值大小要求的相邻格子，可惜这个按钮只能按K次。请问小猿从这个迷宫任选一个格子出发，在紧急呼救按钮的帮助下，最多能走多少步（开始位置计入步数，即站在起点是步数为1）。
输入描述
第一行输入三个数N, M, K。接下来N行，每行M个数，表示迷宫中每个格子的值。
1≤N≤500
1≤M≤500
0≤K≤10
输出描述
输出小猿在迷宫中能走的最大步数
示例1
输入
3 3 1 1 3 3 2 4 9 8 9 2
输出
6
说明
其中一种行走方案：(0, 0) -> (0, 1) -> (0, 0) -> (1, 0) -> (2, 0) -> (2, 1)
【解题思路】
Bfs搜索迷宫问题。
【参考代码】
#include <bits/stdc++.h>
using namespace std;
int n, m, k;
const int maxn = 500 + 5, maxk = 10 + 1;
int a[maxn][maxn];
int mem[maxn][maxn];
int tmp[maxn][maxn];
struct state {
int x, y;
bool operator<(const state rhs) const {
if (a[x][y] != a[rhs.x][rhs.y])
return a[x][y] < a[rhs.x][rhs.y];
if (x != rhs.x)
return x < rhs.x;
return y < rhs.y;
}
} sts[maxn * maxn];
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
int bfs() {
if (n == 1 && m == 1) {
return 1;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
sts[i * m + j] = {i, j};
mem[i][j] = 0;
}
}
sort(sts, sts + n * m);
for (int kk = 0; kk <= k; kk++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
tmp[i][j] = mem[i][j];
for (int d = 0; d < 4; d++) {
const int tx = i + dx[d];
const int ty = j + dy[d];
if (tx >= 0 && tx < n && ty >= 0 && ty < m) {
tmp[i][j] = max(mem[tx][ty] + 1, tmp[i][j]);
}
}
}
}
memcpy(mem, tmp, sizeof(tmp));
for (int t = 0; t < n * m; t++) {
for (int d = 0; d < 4; d++) {
const int tx = sts[t].x + dx[d];
const int ty = sts[t].y + dy[d];
if (tx >= 0 && tx < n && ty >= 0 && ty < m &&
a[tx][ty] > a[sts[t].x][sts[t].y]) {
mem[tx][ty] = max(mem[tx][ty], mem[sts[t].x][sts[t].y] + 1);
}
}
}
}
int ret = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
ret = max(ret, mem[i][j]);
}
}
return ret;
}
int main() {
while (~scanf("%d%d%d", &n, &m, &k)) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf("%d", a[i] + j);
}
}
printf("%d\n", bfs());
}
}
2、解压字符串
【题目描述】猿辅导APP需要下发一些宣传文本给学生，工程师们使用了一种字符压缩算法，为简单起见，假设被压缩的字符全部为大写字母序列，A,B,C,D....Z,压缩规则如下：
1.AAAB可以压缩为A3B (单字符压缩不加括号)
2.ABABA可以压缩为(AB)2A （多字符串压缩才加括号）
输入数据保证不会出现冗余括号，且表示重复的数字一定合法且大于1，即不会出现：
1.（A)2B ------- （应为：A2B）
2.((AB))2C,-----(应为：（AB)2C)
3.（A)B ----- （应为：AB）
4.A1B，（AB)1C，（应为 AB，ABC）
注意：数字可能出现多位数即A11B或者(AB)10C或者A02这种情况。
A11B = AAAAAAAAAAAB
(AB)10C = ABABABABABABABABABABC
A02 = AA
数据分布：
对于60%的数据，括号不会出现嵌套，即不会有 ((AB)2C)2这种结构。
对于80%的数据，括号最多只嵌套一层，即不会有 (((AB)2C)2D)99 这种结构。
对于100%的数据，括号可以嵌套任意层。
输入描述
第一行是正整数C(C<=100)，表示下面有C组数据。之后C行，每行为一组数据，每组数据为一个字符串。
每个字符串由A-Z,数字0-9和(,)组成表示一个压缩后的串，保证输入数据一定合法且字符串长度小于50。
输出描述
输出C行，每行对应一个数据的输出结果，表示压缩前的字符串，保证每个字符串展开后的长度不超过10^6。
示例1
输入
5 A11B (AA)2A ((A2B)2)2G (YUANFUDAO)2JIAYOU A2BC4D2
输出
AAAAAAAAAAAB AAAAA AABAABAABAABG YUANFUDAOYUANFUDAOJIAYOU AABCCCCDD
【解题思路】
关键是对括号的处理，由于要先处理最里层的括号，再处理最外层的括号，符合栈的性质。因此用一个栈来保存字符串开始重复的索引，也可以用搜索递归的性质解决。
【参考代码】
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
bool isdigit(char c) { return c >= '0' && c <= '9'; }
bool isalpha(char c) { return c >= 'A' && c <= 'Z'; }
int findRight(string str) {
int num = 0;
int len = str.length();
for (int i = 0; i < len; ++i) {
if (str[i] == '(') {
num++;
} else if (str[i] == ')') {
num--;
}
if (str[i] == ')' && num == 0) {
return i;
}
}
return len - 1;
}
string getMultiStr(string str, int num) {
string ans = "";
while (num--) {
ans += str;
}
return ans;
}
string dfs(string str) {
int len = str.length();
if (len == 0)
return "";
string temp = "";
int num = 0;
int index = 0;
if (str[0] == '(') {
int right = findRight(str);
temp = dfs(str.substr(1, right - 1));
index = right + 1;
while (index < len) {
if (isdigit(str[index])) {
num = num * 10 + str[index] - '0';
} else {
break;
}
index++;
}
if (num == 0)
num = 1;
return getMultiStr(temp, num) + dfs(str.substr(index));
} else {
if (index +
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
<p> 本专刊由牛客官方团队打造，主要讲解名企校招技术岗位的笔试题。 内容中包含多个名企的笔试真题，附有题目思路及参考代码 本专刊购买后即可解锁所有章节，故不可以退换哦~ <
查看6道真题和解析