2022年の春、NetEaseのインターネットフロントエンド夏期インターンシップの筆記試験

筆記試験の 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 つの文字が等しいか、アルファベットの位置が隣接している場合、それら 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)) マークする場合は、マークされた最大スコアとマークされていない最大スコア + 現在の 2 つの文字のスコアを比較します

完全二分木を構築する（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 です。
下方向、左方向、右方向にのみ移動できます。左方向には時間がかかりませんので、左に進む必要はありません。したがって、dp だけで十分で、現在の位置の上側と左側の最小時間を記録すればよいです。

入力例：

出力例：

アイデア#

下方向、左方向、右方向にのみ移動できるため、左に進む必要はなく、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;
}