猿辅导2019.8.3笔试(超详细的解法!!!)
in 笔试 with 0 comment

猿辅导2019.8.3笔试(超详细的解法!!!)

in 笔试 with 0 comment

0x01

猿辅导APP需要下发一些宣传文本给学生,工程师使用了一种字符压缩算法,为简单起见,假设被压缩的字符全部为大写字母序列,规则如下:

输入数据保证不会出现冗余括号,且表示重复的数字一定合法且大于1,即不会出现:

注意:数字可能出现多位数即A11B或者(AB)10C或者A02这种情况。

输入描述:

第一行是正整数C(C <= 100),表示下面有C组数据。之后C行,每行为一组数据,每组数据为一个字符串。
每个字符串由A-Z,数字0-9和()组成表示一个压缩后的串,保证输入数据一定合法且字符串长度小于50。

输出描述:

输出C行,每行对应一个数据的输出结果,表示压缩后的字符串,保证每个字符串展开后的长度不超过10^6。

示例:

5
A11B
(AA)2A
((A2B)2)2G
(YUANFUDAO)2JIAYOU
A2BC4D2

输出:

AAAAAAAAAAAB
AAAAA
AABAABAABAABG
YUANFUDAOYUANFUDAOJIAYOU
AABCCCCDD

解题思路

这个问题和之前的字节跳动2019笔试:字符串展开(超详细的解法!!!)非常类似,使用递归调用即可。

#include <iostream>
using namespace std;
int c, n, u;
string str;

string dfs() {
    int num = 0;
    string res;
    while (u < n) {
        if (str[u] >= '0' && str[u] <= '9') {
            num = num * 10 + str[u++] - '0';
            while (u < n && str[u] >= '0' && str[u] <= '9') {
                num = num * 10 + str[u++] - '0';
            }
            res += string(num - 1, res.back());
            num = 0; --u;
        } else if (str[u] == '(') {
            ++u;
            res += dfs();
        } else if (str[u] == ')') {
            ++u;
            while (u < n && str[u] >= '0' && str[u] <= '9') {
                num = num * 10 + str[u++] - '0';
            }
            --u;
            string t;
            for (int i = 0; i < num; ++i) t += res;
            return t;
        } else res += str[u];
        u++;
    }
    return res;
}

int main()
{
    cin >> c;
    for (int i = 0; i < c; ++i) {
        cin >> str;
        n = str.size(), u = 0;
        cout << dfs() << endl;
    }
}

0x02

有一个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 6
8 9 2

输出:

6

说明:其中一种方案是(0,0)(0,1)(0,0)(1,0)(2,0)(2,1)

解题思路

显然这是一个dfs加记忆化搜索的问题,这种问题使用python写会简洁一些。

from functools import lru_cache
n, m, k = list(map(int, input().split()))
data = []
for _ in range(n):
    data.append(list(map(int, input().split())))

@lru_cache(None)
def dfs(x, y, k):
    res = 0
    for i, j in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
        nx, ny = i + x, j + y
        if nx >= 0 and nx < n and ny >= 0 and ny < m:
            if data[x][y] < data[nx][ny]:
                res = max(res, dfs(nx, ny, k) + 1)
            elif data[x][y] >= data[nx][ny] and k > 0:
                res = max(res, dfs(nx, ny, k - 1) + 1)
    return res

res = 0
for i in range(n):
    for j in range(m):
        res = max(res, dfs(i, j, k))
print(res + 1)

0x03

K(K>=3)个猿辅导的老师们在玩一个击鼓传花的小游戏,每击一次鼓,拿着花的老师要将花交给别人,不能留在自己手中。游戏开始前花在小猿手中,求击鼓N次后,这朵花又回到小猿手中的方案数,请输出这个数的模1e9+7

输入描述:

输入两个数N, K。
3 <= N <= 1e9  3 <= K <= 1e9

输出描述:

输出方案数模1e9+7后的结果

示例1:

3 3

输出:

2

解题思路

经典的动态规划问题,我们可以定义函数$f(i,p)$表示击鼓i次后是不是在手里,p==0表示在手里,p==1不在手里。那么

说明一下上面的式子,当$f(i,0)$表示第$i$个状态的时候在手里,那么$i-1$状态的时候一定不在手里,总共有$k-1$种情况(可能在$k-1$个人手中)。如果$f(i,1)$表示第$i$个状态不在手里,那么$i-1$状态的时候可以在手里,也可以不在手里,在手里只有$1$种情况,不在手里有$k-2$种情况。

考虑边界问题,当n==1的时候,此时只能在手中,也就是$f(0,0)=1,f(0,1)=0$。

n, k = list(map(int, input().split()))
MOD = 10**9 + 7
mem = [[1, 0] for _ in range(n)]
for i in range(1, n):
    mem[i][0] = mem[i-1][1]*(k - 1)%MOD
    mem[i][1] = (mem[i-1][1]*(k - 2)%MOD + mem[i-1][0])%MOD
print(mem[n-1][0])

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses