拼多多服务端笔试0822

4道100%，欢迎讨论交流
T1
是否能在K次替换后使得字符串回文。作为第一题就有大歧义实在不应该，根据用例提交情况可知题目指的是“K次替换内”使得字符串回文。这样就很简单了，查找破坏回文的字符数量即可。
时间复杂度O(n)，空间复杂度O(1)。

T2
红白球摆放，要求红色不相邻。动态规划，维护变量分别表示最后一个球是红/白球的种类数，遍历转移即可。
时间复杂度O(n)，空间复杂度O(1)。

T3
数组中求满足条件的对数：相同的数字或和能被m整除。
如果只有和能被m整除，我们可以维护一个长为m的数组mod_cnts，将数字按照模m的余数分组，然后遍历即可。
现在多了一个可能的条件，我们可以把这个条件用另一个长为m的数组rep_cnts记录下来，rep_cnts[i]表示模m余i的数字中，两两相同的对数有多少。
那么当处理模m余i的数字时，和它成对的数要么在模m余i的集合中，要么在模m余m-i的集合中；对于模m余m-i的数字同理。那么我们优先让模m余i的数字和模m余m-i的数字两两结合，剩余的数字依据rep_cnts让它跟自己结合。
时间复杂度O(max(m, n))，空间复杂度O(max(m, n))。

T4
T2的plus版，思想是一样的。两个长为n的数组，同位置元素可以交换。要求两数组各自的差值数组之和加起来最大，求最小的交换次数。
首先注意我们的主要目标是差值数组之和最大，交换次数最小只是其次。
同样使用动态规划，sums_n, sums_y分别表示末尾元素保持原位置和交换的情况下最大的差值数组之和，cnts_n, cnts_y对应二者的交换次数。
设join_n， join_y分别是当前元素保持原位置和交换的情况下和上一个元素的差值之和，那么根据上一个元素是否交换，有转移方程
sums_n = max(sums_n + join_n, sums_y + join_y)
sums_y = max(sums_n + join_y, sums_y + join_n)
而cnts_n, cnts_y跟着赋值即可，如果括号里二者相等，在优先选择交换次数较小的。
注意sums_n/sums_y逻辑上同时计算，使用临时变量避免前者的计算影响后者。
时间复杂度O(n)，空间复杂度O(1)。