2022春网易インターネットフロントエンド夏季インターンシップ筆記試験

筆記試験の 3 日後に面接のメールが届きました。フロントエンドの要求は高くありません。

質問問題 1 問（10 点の追加点）
- デザインパターンについて、2 種類の構造型 / 行動型デザインパターンを原理、使用シーン、個人的理解を含めて記述してください。
プログラミング問題 4 問
- モンスターを倒す（AC 100%）
- 文字列の最大スコアを求める (25 点、AC 37.5%)
- 完全二分木を構築する (25 点、まだ未実施，0%)
- 地図から出る最短時間を求める (30 点、AC 100%)

モンスターを倒す (20 点、AC 100%)#

2 体のモンスターがいて、それぞれの生命値は a と b です。
あなたには 2 つのスキルがあります。

1 つは単体攻撃で、ダメージは x です。
もう 1 つは群体攻撃で、ダメージは y です。
与えられた a, b, x, y を使って、最小限のスキルで 2 体のモンスターを倒すことができるか求めてください。

入力例：5 3 3 2
出力例：3

入力例 2：20 20 5 2
出力例 2：8

入力例 3：20 20 1 2
出力例 3：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%)#

小文字の文字列が与えられ、隣接する 2 つの文字が等しいか、アルファベット順で隣接している場合、それらはスコアを貢献できます。'a' は 1 点、'b' は 2 点.....'z' は 26 点を貢献します。各文字は 1 回しか使用できません。
入力 "aca" 出力 0 隣接する文字はアルファベット順で隣接していないし、等しくもない。
入力 "abb" 出力 4 ab のスコアは 3、bb のスコアは 4 ですが、各文字は 1 回しか使用できないため、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 (前のマークされた最大スコア，前の未マークの最大スコア + 現在マークした 2 つの文字のスコア)

完全二分木を構築する (25 点、まだ未実施)#

整数 n が与えられ、1、2、3...n の n 個の数を使用して完全二分木を構築し、すべてのノードと親ノードの積が偶数であることを満たします（根ノードを除く、親ノードがないため）。構築した二分木のレベル順遍歴の結果を出力します。答えは一意ではありません。
入力 4 出力 1 2 4 3

思路#

シミュレーションで奇数を葉ノードに配置し、残りは適当に配置するという考えがあります。

地図から出る最短時間を求める (30 点、AC 100%)#

m 行 n 列からなる地図が与えられ、地図には 0 と 1 があり、0 は土地、1 は沼地を示します。

土地から土地、または沼地から沼地に移動するのに 1 単位の時間がかかります。
土地から沼地、または沼地から土地に移動するのに 2 単位の時間がかかります。
同じ移動は 1 単位、異なる移動は 2 単位の時間がかかります。
毎回下、左、右にしか移動できず、左上から右下に移動するのに必要な最小の時間を求めます。
eg:
入力

出力

思路#

下、左、右にしか移動できず、左に移動しても時間が減らないため、左に移動する必要はなく、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;
}