筆試完第三天就收到約面郵件了，前端要求不高
- 問答題 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;
}