程序员进阶之算法练习（三十一）
前言
BAT常见的算法面试题解析：
程序员算法基础——动态规划
程序员算法基础——贪心算法
工作闲暇也会有在线分享，算法基础教程----腾讯课堂地址。
正文
1.Mahmoud and a Triangle
题目链接
题目大意：
给出n个线段，每个线段长度为a[i];
从中选出3个线段，组成一个三角形；
如果可以，输出YES；
如果不可以，输出NO；
输入数据：
第一行，整数n (3 ≤ n ≤ 1e5)
第二行，n个整数 a1, a2, ..., an (1 ≤ ai ≤ 1e9)
Examples
input
5
1 5 3 2 4
output
YES
input
3
4 1 2
output
NO
题目解析：
这个题的题意很清晰， 我们知道三角形的性质是：两边之和大于第三边；
暴力的做法是：枚举两条边，再遍历每一条边，通过上面的性质，判断是否为三角形；
但是因为n较大，暴力枚举不可行；
假设三条边分别是a,b,c，并且a<=b<=c，那么只需满足 a+b>c的条件即可；
那么先对数组a排序，然后枚举两条边，假设是a[i]和a[j]，且(i < j)
容易知道，对于第三条边，必然是a[j+1]；（证：如果存在k>j+1，且a[i]+a[j]>a[k],那么必然有a[i]+a[j]>a[j+1]);
同理，我们知道j必然等于i+1；
这样我们可以知道，只需枚举i，就能知道另外两条边；
复杂度降到O(N);
思考🤔：
2. The Queue
题目链接
题目大意：
小明要去一个地方办业务，业务员上班时间是Ts到Td；
办业务的人很多，排成一列，业务员为每个人办业务都需要时间Tf;
已知n个人的到达时间a[i]；（a[i]为正整数，a[i] < a[i+1] ）
小明可以在任何非负整数的时间到达，如果和其他人同时到达，小明会让其他人先，自己排队；
现在小明希望排队时间最短，问：他应该在哪个时间点到达；如果有多个答案，输出任何一个；
输入数据：
第一行 三个整数，Ts、Td和Tf（Ts和Td最大不超过1e12）
第二行，数字n (0 ≤ n ≤ 100 000)
第三行，n个数字，表示n个人的到店时间；
Examples
input
10 15 2
2
10 13
output
12
input
8 17 3
4
3 4 5 8
output
2
题目解析：
从题意知道，小明如果0点就到达，一定可以得到服务，故答案必然有解；
用贪心的思想，所有的情况可以分为两种：
1、小明可以在某个人到达的时间的前一秒钟到达；
2、小明在所有人办理业务完成后再到达；
于是枚举a[i]-1到达的时间的最小等待时间，并且再统一考虑最后一种情况即可。
时间复杂度O(N)；
思考🤔：
3.Garland
题目链接
题目大意：
小明有一群羊，羊之间用绳子连接起来，最前面的羊由小明牵着，每只羊有一个价值a[i]；
小明还有两个朋友，他希望和他们平分这群羊，并且三个人至少有一只羊，三个人分到的羊的总价值相同；
小明只能剪断两条绳子，问是否存在合适解？
如果不存在输出-1；
如果存在，则输出两只羊的序号，表示应该剪断牵着这两只羊的绳子；
输入数据：
第一行 数字n (3 ≤ n ≤ 1e6)
接下来n行，每行两个数字x和t；第i行的x表示第i只被第x只羊用绳子牵着（x=0表示被小明牵着），第i行的y表示第i只羊的价值；(-100<=t<=100)
Examples
input
6
2 4
0 5
4 2
2 1
1 1
4 2
output
1 4
样例解释：如图，应该剪断牵着1、4号羊的绳子，这样可以得到价值5的三个羊群。
题目解析：
抽象一下，就是把一棵树分成3部分，并且每部分的节点之和相等。
注意到题目一个很重要的条件，三个人的价值相同。
而且注意到只能减两次，那么必然有一个是子树；
于是遍历整个树，当遇到一个子树的节点和满足条件时，把这个子树从树中剔除；
再遍历整棵树，找到另外一颗子树，节点和满足条件即可。
思考🤔：
优化： 两次dfs合并成一次，当找到被剔除的节点时，return的sum=0即可。
4.Cartons of milk
题目链接
题目大意：
小红很喜欢喝牛奶，每天最多能喝k瓶牛奶；
小红有n瓶牛奶，每瓶牛奶都有一个有效时间f[i]，表示需要在f[i]天内喝完；
同时商店里有m瓶牛奶，每瓶牛奶的有效时间是g[i];
小红很讨厌浪费，所以她希望能全部喝完自己的牛奶；
同时小红很喜欢牛奶，她希望尽可能喝更多的牛奶；
问小红最多能买多少瓶牛奶，保证牛奶都在保质期内喝完。
如果小红无法保证所拥有牛奶都在保质期内喝完，则输出-1；
如果小红可以保证所拥有牛奶都在保质期内喝完，则输出小红可以买的牛奶数量x；
接下来一行输出x个数字，表示小红应该买的商店牛奶序号。
输入数据：
第一行 n, m, k (1 ≤ n, m ≤ 1e6, 1 ≤ k ≤ n + m)
第二行 n个数字f[i]，表示小红n瓶牛奶的保质期； (0 ≤ f[i] ≤ 1e7)
第三行 m个数字g[i]，表示商店m瓶牛奶的保质期；（0 ≤ g[i] ≤ 1e7)
Examples
input
3 6 2
1 0 1
2 0 2 0 0 2
output
3
1 2 3
题目解析：
可以知道，小红必须是先满足喝完自己的牛奶，再尽可能去喝商店里的牛奶；
小红的策略应该是每天尽可能喝有效时间最短的牛奶，并且每天都喝k瓶；
考虑一个简单的做法：
把小红所有的牛奶排序，按照有效时间从小到大遍历每瓶牛奶，可以容易判断小红自己的牛奶是否能全部喝完；
再来考虑商店里的牛奶：假如小红能喝完数量为i+1瓶的牛奶，那么必然能喝完i瓶牛奶，具有单调性；
二分mid，表示小红能喝完mid瓶商店里的牛奶；
再使用贪心策略，从商店里选择mid瓶有效时间最长的牛奶，混入小红必须喝完的列表，然后排序；
总得复杂度O(logMNLogN)；
但没想到tle了，因为N=106，加上logM和logN，复杂度要加220 * 2 = 400，大概有4 * 10^8的复杂度；
于是采用优化的方案，在二分完mid之后，不与小红已有的牛奶混合排序；
用two pointers 的方法进行判断。
5. From Y to Y
题目链接
题目大意：
有一个字符数组，长度为n；（全部是小写字母）
现在有一个操作：从数组中取出两个元素s和t，把字符s和t进行合并，得到新的字符串str，然后把str放入数组；
每次操作的代价是，对于所有字母x∈{a,b,c...z}，字母x在两边s出现的次数的乘积的和；
比如说：aab+aab, 代价就是(22) + (11) = 5；
现在给出数字k，要求构造一个字符集合s，将s合并为一个字符串的最小代价刚好是k；
输入数据：
第一行，整数k (0 ≤ k ≤ 100 000)
Examples
input
12
output
abababab
样例解释：
对于字符集合 {'a', 'b', 'a', 'b', 'a', 'b', 'a', 'b'}，其中一个最小代价的方案是：
{"ab", "a", "b", "a", "b", "a", "b"}，代价是0；
{"aba", "b", "a", "b", "a", "b"}, 代价是1;
{"abab", "a", "b", "a", "b"}, 代价是1;
{"abab", "ab", "a", "b"}, 代价是0;
{"abab", "aba", "b"}, 代价是1;
{"abab", "abab"}, 代价是1;
{"abababab"}, 代价是8；
总得的最小代价是12；
题目解析：
对于代价的计算，我们看简单的例子：
aaaa的两种合并方式，
1、先(a,a)=aa, (a,a)=aa, 再(aa,aa)=aaaa；
2、先(a,a)=aa, 在(aa,a)=aaa, 再(aaa,a)=aaaa;
这两种的代价分别是1+1+4=6;
1+2+3=6;
容易知道，对于(aa,aa)的操作方式，我们可以看成是(aa,a) + (aa,a)，然后根据定义，我们可以知道(aa,a)+(a,a)=(aaa,a)；
其实合并方式1 和 合并方式2 是等价的；
再由定义，我们知道不同字母的代价计算是独立的；
对于一个字符集合s，其合并的最小代价∑x∈{a,b,c...z}, sum+=1+2+3+...+count(x-1);
这样可以得到一个快速的构造方案：
先尽可能填a，从1、2、3.... 直到不能再填，接着重复b的数量。
总结
这段时间忙完后，应该能有多余的时间，继续准备新的算法基础课程。
目前也在平衡一些职业上的选择，业余时间有限，是继续投在音视频方向，还是专注于当前的业务？
分享一些关于算法对学习和工作的帮助：在进行算法练习的时候，相当于把自己掌握的知识不断锤炼和组合出新的思路。
当我再学习新的一门技术的时候，我更倾向于先去掌握基础的知识，摸索基本的规律和原则，最后再尝试自己的一些组合与应用。期间不断优化自己对技术的积累与认知，最终通过较短的时间，可以深刻地理解技术。
而且在“爬过”华山之后，再去攀登小山峰的时候，会更加游刃有余。
