上周六投了美团的安全工程师实习，今天笔试。最近没空也没心情刷题背八股，直接裸考，没指望能过，就当体验一下大厂笔面流程了。本以为安全这种岗位会出一些相关的选择或简答题，没想到上来就只有5道算法。结果两个小时的时间里我只做出了一道题。当然我原本对于笔试情况的期望也没多高，只是遗憾没有其他题目类型。除了美团我目前还没投其他厂，由于之前的博客没了，我的简历上又少了一项东西，实在可惜。
最后分享一下今天的笔试题目。
双色球
小团的桌子上有一列球。每个球要么是红色的要么是蓝色的。小团的口袋里也有一些球，这些球也都涂上了红色或蓝色。小团不喜欢看到相同颜色的球相邻，因此他希望将口袋里的一些球插入桌上的这列球使得相同颜色的球不相邻。现在他想知道，如果他能够达成他的期望，则达成时桌上这列球最短有多长？如果这是不可能的，他想知道他还需要多少个红球以及多少个蓝球才能达成他的期望。
第一行有三个正整数，n，b，r，分别代表桌上球的数量，口袋里蓝球的数量，和口袋里红球的数量。这三个数的大小均不超过100000。 第二行有一个长度为n的仅由r和b组成的字符串。第i 个字符代表桌上这一列球中的第 i 个的颜色是红色还是蓝色；红色则为r，蓝色则为b。
若可以通过将口袋里的一些球插入桌上的这列球使得相同颜色的球不相邻，则输出达成这一目标后桌上球的最少数量。否则输出两个数，空格隔开，代表还需要至少多少个蓝球和多少个红球才能达成这一目标。
示例：
输入：
5 2 1
rrbbr
输出：
7
单峰数组
小美有一个长度为n的数组。小美觉得如果一个数组可以从中切开，使得前一段严格递增且后一段严格递减，那么这个数组是好的。
现在小美想通过往她所有的数组的某些元素上加上总和尽可能小的一些正整数从而让这个数组变好。
请你求出她需要加上总和至少为多少的正整数才能使数组变好。
一个数组是严格递增的当且仅当其中除第一个元素以外的任意一个元素都大于其前一个元素。
一个数组是严格递减的当且仅当其中除第一个元素以外的任意一个元素都小于其前一个元素。
第一行有一个正整数n(1<=n<=100000)，代表小美所有的数组的长度。
第二行有n个空格隔开的正整数，代表小美所拥有的数组。
输出一个整数，代表小美需要往她的数组中的某些元素上加上总和至少为多少的正整数才能使数组变好。
示例：
输入：
5
1 2 1 2 1
输出：
2
标语
小团接到了一个宣传任务。他需要根据给定的核心思想设计一条宣传标语。如果把核心思想和宣传标语都视为字符串，则他认为一条标语的有力程度体现在该标语有多少个连续子串中包含了核心思想作为其子序列。现在给出他收到的核心思想和他设计的标语，他想知道这条标语的有力程度。
一个字符串s的连续子串即从s的开头和结尾分别删去数个（可以是零个）字符所得的字符串。对于两个连续子串，即使逐字符相等，从开头和结尾分别删除的字符数量不同则被视为不同的连续子串。如abab有a,b,a,b,ab,ba,ab,aba,bab,abab这十个连续子串。
一个字符串s的子序列则是从s中删去一些（可以是零个，不能是所有）字符后所得的字符串。对于两个子序列，即使逐字符相等，删除的字符位置不同则被视为不同的子序列。如aba有a,b,a,ab,aa,ba,aba这7个子序列。
输入由两行字符串组成，第一行是小团设计的标语，第二条是小团收到的核心思想。
字符串均非空且仅由小写英文字母组成。标语的长度不超过5000，核心思想的长度不超过100。
输出一个整数，代表小团设计的标语的有力程度。
示例：
输入：
acac
ac
输出：
5
负载均衡
小团从某海鲜市场买到了一块3核CPU来应对他需要进行的高性能计算任务。小团一共有n个计算任务，编号分别为1到n。编号为i的任务需要运行ai秒。为了避免进程切换带来的开销，小团只能同时运行三个任务。也就是说，他需要将这n个任务分成三组，并分别分配到CPU的三个核心上。现在他想知道完所有任务至少需要多少秒。
第一行有一个正整数n(1<=n<=100)，代表计算任务的数量。
第二行有n个大小不超过1000的正整数，空格隔开，分别代表编号为1到n的计算任务所需的运行时长。
输入数据保证答案不超过1000。
输出一个正整数，代表完成所有任务所需要的时间。
示例：
输入：
7
5 4 6 6 8 3 7
输出：
13
可旋转矩阵
n×n 个整数，排成n行，每行n个，这样就组成了一个方阵。小团喜欢无论从四个方向看上去都一模一样的方阵，也就是说，把这个方阵旋转90度若干次，它都和旋转前一模一样。
而小美有能力改变方阵里面数的值，但这需要花费一定时间。每把一个位置的数增大或减小1，所花费的时间都是1秒。现在小美想要改到这个矩阵让小团满意，但她也希望节省自己的时间，请计算要达到目标，所需要的最短时间。
第一行一个整数 n，1 <= n <= 100;
后面n行，每行n个空格隔开的整数 aij，0 <= aij <= 109。
输出一个整数，表示所需要的最小时间
示例：
输入：
3
2 1 2
1 1 3
2 1 1
输出：
3