程序员进阶之算法练习（二十八）
前言
四道题，分别锻炼哈希、贪心、贪心+排序、二分四个能力。
第一题较为简单，后续的题目都需要一定的基础。
贪心是最基础的能力，codeforce有专门的
Tag用以描述，叫做greedy；
二分是常用的一种降低时间复杂度方法，前提的要求是单调性；
哈希和排序是工程中常见的处理，前者用于映射，后者用于数据有序化。
这四个能力也多用于面试的算法题，因为其属于基础能力。
正文
1.Santa Claus and Keyboard Check
题目链接
题目大意：
小明把键盘的键都卸下来清洗，在装回去后，发现有些键装错了。
他看着键盘，打出一个字符串str，在屏幕显示出来一个字符串str';
现在他可以选择任意两个键，交换它们的位置，但是每个键只能交换一次；
问，小明是否能复原正确的键盘？
如果可以，先输出交换次数，接下来每行输出每次交换的字母；（顺序无关）
如果不可以，直接输出-1。
输入数据：
str长度不超过1000；
Examples
input
helloworld
ehoolwlroz
output
3
h e
l o
d z
input
merrychristmas
christmasmerry
output
-1
题目解析：
题目有个很重要的条件，每个键只能使用一次。
那么每次当遇到字符不同的时候，这两个字符就必须交换；如果这个字符已经交换过，那么无解。
实现逻辑，可以用一个简单字符hash来实现，对str的字符，每次先判断是有hash字符，如果有则转成hash后的符；
如果没有，添加hash[c]=c; 保证下次再遇到不会出错；
然后进行判断，如果hash后的字符和str'上的不对应，则无解；
2.Santa Claus and Robot
题目链接
题目大意：
有一个机器人，在一个网格的网格线上行走，每次有L/R/U/D四个方向；
当机器人从点p1走到点p2时，它会走最短的路径。
如果有3个点p1、p2、p3，机器人会按照最短的路径走向p1点，到达后再走向p2点，再到p3点；
现在假设机器人在原点，已知机器人走的序列（长度为n），求最少有几个点，可以满足机器人走的序列。
输入数据：
n (1 ≤ n ≤ 2·105)
Examples
input
6
RRULDD
output
2
input
26
RRRULURURUULULLLDLDDRDRDLD
output
7
题目解析：
看似很难，仔细分析一下，只要找到两点之间路径的规律即可。
当出现过R之后，本次路径，就不允许再出现L，同理L、U、D;
这样，R、L之间算一条路径，U、D之间算一条路径，加起来就是需要的最小点数。
3.Santa Claus and a Palindrome
题目链接
题目大意：
k个字符串，长度均为n；
每个字符串有一个权值a[i]；
现在可以从k个字符串中，选择若干个字符串拼成一个新的回文串str，要求每个字符串只能用一次，并且不能改变原有字符串的字符排列顺序；
str的权值为所有拼成的串的权值和，求str的最大权值。
（注意，空串也是回文串，所有str的最大权值不小于0）
输入数据：
1 ≤ k, n ≤ 100 000; n·k ≤ 100 000
- 10 000 ≤ a[i] ≤ 10 000
Examples
input
7 3
abb 2
aaa -3
bba -1
zyz -4
abb 5
aaa 7
xyx 4
output
12
样例解释：最后的结果是abbaaaxyxaaabba，组合第5, 2, 7, 6 和 3字符串。
题目解析：
每个字符串分两种，第一种是自身为回文，第二种是自身不为回文。
自身为回文串有两种选择，放在中心点（单独一个）和不放在中心点（两两配对分在左右）；
自身不为回文串的字符串str，可以和str的reverse组合回文串；（比如abc和cba）
我们把字符串相同的放到同一个桶，把桶按照字符串是否为回文分成两类。
对于非回文串str，每次从str的桶里找一个最大的key值x，再从reverse(str)的桶里找一个最大的key值y，只要x+y>0，那么就组成一个匹配；
对于回文串paliStr，每次从paliStr的桶里找key值最大的两个x和y，如果x+y>0，那么就组成一个匹配；
这里有个trick：因为paliStr还可以单独放在中间，如果paliStr的两个权值是-3和5，那么选中-3其实是不划算的。
但是如果只选择x>0&&y>0的话，假设有多个-3和5的组合，就会失去-3+5=2的额外收益。
抉择是根源是在于paliStr可以选择放在中间！但是中间其实只能有一个字符串。
于是可以采取额外补偿的方式，我们还是采用x+y>0的选择，但是保留一个addition的收益，类似-3和5的组合，addition的收益是3；
同理，如果只剩下一个回文串，那么addition的收益是该回文串。
最后计算所有的收益和+addition收益得到答案。
思考🤔：
更好理解addition的方式，是把组合看成单体的，比如说pair(-3, 5), pair(2, 3)；把剩下的单个，也视为单体；
然后从所有的单体中选择一个，放入中间的收益。
4.Santa Claus and Tangerines
题目链接
题目大意：
给出n个数字a[i]，要分给k个人；
数字a[i]可以平分，如果是奇数，那么会分成a[i]/2 和 a[i]/2 + 1;
每个人只能分得一个数字，问所有人中最小的数字的最大值是多少？
如果不够分，那么输出-1；
输入数据：
n and k (1 ≤ n ≤ 1e6, 1 ≤ k ≤ 2·1e9)
1 ≤ a[i] ≤ 1e7
Examples
input
3 2
5 9 3
output
5
input
2 3
1 1
output
-1
题目解析：
分出k个数，保证最小值尽可能大；
第一想法是二分答案，假设最后的结果是ans，对于数字x，while(x/2>=ans)，对数字x进行平分；
假设num[x]表示数字x的数量，如果x/2>=ans，那么有num[x/2] += num[x], num[x - x/2] += num[x];
最后再统计所有数字比ans大的数字数量，判断是否大于k；
复杂度为二分复杂度log(1e7) * 枚举平分复杂度(1e7) =24*1e7=2.4e8的复杂度；
因为题目给的时限为2s，勉强可以完成；
思考🤔：
另一种更优雅的方案。
以数字21为例，如果ans∈[11, 21]这一区间，>ans的数字只有一个；
如果ans=10时，就能算两个数字；（因为21可以拆分为10+11）
数字x，可以切分为数字较小的部分x/2和数字较大的部分(x-x/2)，我们用a[x]来表示数字x的个数，b[x]表示当x拆分时(x-x/2)的数量；
当ans>(x-x/2)时，x的拆分没有额外收益；
当ans<=x/2时，x的拆分相当于多出来一个数字a[x/2]；
于是有：
a[x/2] += a[x]+b[x];
b[x-x/2] += a[x]+b[x];
核心代码很短，如下：
for (lld i = maxAns; i > 0; --i) {
total += a[i];
if (total >= k) {
cout << i << endl;
return 0;
}
else {
a[i / 2] += a[i] + b[i];
b[i - i / 2] += a[i] + b[i];
}
}
总结
基础能力在做一线开发的时候极为重要，往往决定了综合能力的天花板。
实际开发中的各种性能优化，功能系统的时间空间复杂度分析，都是基于基本的算法能力。
算法是编程能力提升的必要条件，做题只是学算法的一种实践手段。
而在业余时间越来越少的现在，做题占用的是我的娱乐时间和学习时间。如果一直停留在重复做类似题的境界，对我的能力提升微乎其微。
所以我现在在做的事情是尝试用规范的方式去解决、思考问题，然后把这个过程用文字描述出来。在保持思考习惯的同时，提升描述能力和锻炼耐力。
试试新分支（自家的社区），邀请大家来围观
https://cloud.tencent.com/developer/support-plan?invite_code=1dftf9prp3wx5
