2022.3.27

第一题

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

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

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

数据量：均小于20

我的思路：一开始贪心70%多，后来发现数据量不到20，直接暴力a了。

第二题

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

输入：abb

输出：4（标记bb）

我的思路：一开始用堆，放进去，然后从大到小一个个挑，过了40%。这种方法的缺点是bcded这样的序列可能会取bcde而非cded。

之后改成单调栈，如果+1或相等就入栈，-1则开始弹栈并计分，若都不满足则直接弹栈计分，结果也就46%。。。

第三题

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

• 一共n个节点，包含1~n。

• 除了根节点，每个节点和其父节点的乘积为偶数。

输入：4

输出：2 4 1 3（输出一个符合条件的即可）

我的思路：一层奇一层偶，想不到别的了，65%。

第四题

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

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

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

输入：3 3

1 0 0

1 1 1

0 0 1

输出：4（一直在沼泽里移动即可）

我的思路：做过最简单的笔试最后一题，dp即可a。

问答题

讲讲你熟悉的两种行为型或者设计型（好像是这个）设计模式，说说它的原理、使用和个人理解。

我的思路：问就是单例和工厂。