网易实习笔试题

---

第一题

两个怪物，一个a血，一个b血。

两个技能，一个单体x血，一个群体y血。

求最少需要放几次技能才能干掉怪物。

解答

数据较小，直接暴力。

就是假设m次y血，可以根据怪物的血量计算出需要x血技能的分别次数，加起来，比较，就可以了。

第二题

给一个字符串，里面都是小写字母，如果一个字母可以被标记（标记条件为隔壁字母和它相邻，相邻的意思就是b和a是相邻的，b和c是相邻的），那么就可以标记它和它隔壁的字母，获取它和隔壁的分数（a为1分，b为2分，以此类推），一个字母只能被标记一次。求最高分数。

输入：abb

输出：4

解答

没写出来。线性dp。dp[i]为字符串前i项获得的最大分数。

for (i = 1; i < s.length(); i++)
{
    dp[i + 1] = dp[i];
    if (abs(s[i] - s[i - 1]) <= 1)
    {
        dp[i + 1] = max(dp[i + 1], dp[i - 1] + (s[i] - 'a' + 1) + (s[i - 1] - 'a' + 1));
    }
}

第三题

生成一个二叉树，输出其层序遍历，要求：

• 一共n个节点，包含1~n。
• 除了根节点，每个节点和其父节点的乘积为偶数。

输入：4

输出：2 4 1 3

答案不唯一，输出一种即可。

解答

脑筋急转弯，只需要保证叶子节点都放置奇数就可以了，而叶子节点就是最后（n+1）/2个节点，所以只需要顺序输出1-n内的偶数，再输出1-n内的奇数就可以了。

第四题

在沼泽地中移动，1代表沼泽，0代表平地。

在相同的地方里移动消耗1，否则消耗2。

求从0，0处到n-1,m-1处最少消耗多少。

输入：3 3

1 0 0

1 1 1

0 0 1

输出：4

解答

直接广搜。

总结

这么一看的确不难。。。我就A了两个完整的，第一和第四题。