2022春暑期实习-网易互联网前端-暑期实习笔试

编程题4道（20、25、25、30），问答题1道（10分附加分）

笔试完第三天就收到约面邮件了，前端要求不高

• 问答题1道（10分附加分）

  • 问的设计模式，写两种结构型/行为型设计模式，包括原理、使用场景和个人理解

• 编程题4道

  • 打怪（AC 100%）

  • 求字符串的最大分数 (25分，AC 37.5%)

  • 构造完全二叉树 (25分，还没做, 0%)

  • 走出地图的最短时间 (30分，AC 100%)

打怪 (20分，AC 100%)

两个怪兽，生命值分别是a和b 你有两个技能

• 一个是单体攻击，伤害是x

• 另一个是群体攻击，伤害是y

• 给定 a, b, x, y 求使用最少几个技能可以杀死两个怪兽。

输入样例：5 3 3 2 输出样例：3

输入样例2：20 20 5 2 输出样例2：8

输入样例2：20 20 1 2 输出样例2：10

思路

DFS剪剪枝就过了。另外也可以贪心（

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int a, b, x, y;
int dfs(int a, int b, int cnt) {
    if(a <= 0 && b <= 0) return cnt;
    else if(a <= 0) a = 0;
    else if(b <= 0) b = 0;
    int higher = max(a, b);
    if(y >= x) return higher%y == 0? higher/y: (higher/y)+1;
    int minx;
    if(a <= 0) minx = dfs(a, b-x, cnt+1);
    else if(b <= 0) minx = dfs(a-x, b, cnt+1);
    else minx = min(dfs(a-x, b, cnt+1), dfs(a, b-x, cnt+1));
    int miny = dfs(a-y, b-y, cnt+1);
    return min(minx, miny);
}
int main() {
    cin >> a >> b >> x >> y;
    cout << dfs(a, b, 0) << endl;
    return 0;
}

求字符串的最大分数 (25分，AC 37.5%)

给定一个全是小写字母的字符串，如果字符串中相邻的两个字母相等或者在字母表中的位置相邻，那么他们两个可以贡献分数。其中'a'贡献1分，'b'贡献2分.....'z'贡献26分。每个字母只能使用一次。 输入 "aca" 输出0 因为相邻的字母没有在字母表中相邻 也不相等 输入 "abb" 输出4 因为ab分值是3，bb分值是4，但是每个字母只能使用一次，因此选择bb

思路

好，我的思路完全是错的就不放代码了，说大佬的思路：

• dp[0][i]表示不标记第 i 个字母的最大分数

• dp[1][i]表示标记第 i 个字母的最大分数。

• 转移方程为

  • dp[0][i] = max(dp[0][i-1], dp[1][i-1]) 不标记则为上一个的最大分数

  • dp[1][i] = max(dp[1][i-1], (dp[0][i-1]+ s[i]-'a'+1 +s[i-1]-'a'+1)*(abs(s[i]-s[i-1]) <= 1)) 标记则为max(上一个被标记了的最大分数, 上一个未被标记的最大分数+当前标记这两个字母后的分数)

构造完全二叉树 (25分，还没做)

给你一个整数n，使用1，2，3...n这n个数构造完全二叉树，满足所有节点和父节点的乘积是偶数(根节点除外，因为他没有父节点)，输出构造的二叉树层序遍历的结果。答案不唯一。 输入 4 输出 1 2 4 3

思路

看到有思路说就是个模拟，将奇数都放到叶子节点然后剩下的随便放就行。

走出地图的最短时间 (30分，AC 100%)

给你两个整数m,n，表示有m行n列组成的地图，地图中有0和1，其中0表示土地，1表示沼泽

• 从土地移动到土地或从沼泽移动到沼泽耗时1单位

• 从土地移动到沼泽或从沼泽移动到土地耗时为2单位

• 也就是相同耗时为1，不同耗时为2

• 每次只能向下，向左，向右移动，求从左上角移动到右下角需要的最少的时间 eg: 输入

3 3
1 0 0
1 1 1
0 0 1

输出

4

思路

• 因为只能向下，向左，向右移动，且向左不会减少耗时也就是根本不用往左走，所以只需要dp，记录当前位置的上侧和左侧的最小耗时即可

代码

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int maxn = 510;
int n, m;
int map[maxn][maxn];
int dp[maxn][maxn];
int main() {
    cin >> n >> m;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j)
            cin >> map[i][j];
    }
    for(int i = 1; i < n; ++i) 
        dp[i][0] = dp[i-1][0] + (map[i-1][0] == map[i][0] ? 1: 2);
    for(int i = 1; i < m; ++i) 
        dp[0][i] = dp[0][i-1] + (map[0][i-1] == map[0][i] ? 1: 2);
    for(int i = 1; i < n; ++i) {
        for(int j = 1; j < m; ++j) {
            int top = dp[i-1][j] + (map[i-1][j] == map[i][j] ? 1: 2);
            int left = dp[i][j-1] + (map[i][j-1] == map[i][j] ? 1: 2);
            dp[i][j] = min(top, left);
        }
    }
    cout << dp[n-1][m-1] << endl;
    return 0;
}