【每日一题】- 2020-08-21 about fe-interview HOT 3 CLOSED

思路

因为每场模拟赛都要包含 Easy，Medium，Hard 三种难度的题目各一道，能出多少场模拟赛就取决于这三者的短板，数量最少的题目决定了模拟赛的场次。

除了 E, M, H 三种难度确定的题目外，还有 EM 道可以是 E 或 M 的题目以及 MH 道可以是 M 或 H 的题目。我们可以用两层循环来枚举所有把 EM 分配给 E 和 M，以及把 MH 分配给 M 和 H 的情况。

复杂度

• 时间复杂度：$O(EM*MH)$。
• 空间复杂度：$O(1)$。

代码

JavaScript Code

function t(E, EM, M, MH, H) {
    let ans = 0;
    for (let i = 0; i <= EM; i++) {
        for (j = 0; j <= MH; j++) {
            ans = Math.max(ans, Math.min(E + i, M + (EM - i) + j, H + (MH - j)));
        }
    }
    return ans;
}

t(2, 2, 1, 2, 2); // 3

from fe-interview.

暴力

思路

代码（JS）

function t(E, EM, M, MH, H) {
 if (E < 1 && EM < 1) return 0
 if (EM < 1 && M < 1 && MH < 1) return 0
 if (H < 1) return 0
 return 1 + max(六种情况)
}

复杂度分析

• 时间复杂度：$O(6 ^ N)$，其中 N 为 min(E, EM, M, MH, H)
• 空间复杂度：$O(6 ^ N)$，其中 N 为 mim(E, EM, M, MH, H)

记忆化递归（略）

复杂度分析

• 时间复杂度：$O(E * EM * M * MH * H)$
• 空间复杂度：$O(E * EM * M * MH * H)$

动态规划（略）

复杂度分析

• 时间复杂度：$O(E * EM * M * MH * H)$
• 空间复杂度：$O(E * EM * M * MH * H)$

贪心

思路

我们可以将 EM 到题 分为 i 道 E 和 EM - i 道 M。同理 MH 也是一样的。 因此总的可能就是 EM * MH。 我们暴力枚举所有可能求最大即可。

代码

function t(E, EM, M, MH, H) {
    let ans = 0
    for (let i = 0; i <= EM; i++) {
        for (j = 0; j <= MH; j++) {
            ans = Math.max(ans, Math.min(E + i, M + EM - i + j, H + MH - j))
        }
    }
    return ans
}

复杂度分析

• 时间复杂度：$O(EM * MH)$
• 空间复杂度：$O(1)$

from fe-interview.

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

from fe-interview.