笔试完第三天就收到约面邮件了，前端要求不高
- 问答题 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;
}