AB城市道路攻陷问题 拼接所有字符串产生字典顺序最小的大字符串 package test; import java.util.Arrays; import java.util.Comparator; class MergeComparator implements Comparator<String> { @Override public int compare(String arg0, String arg1) { return (arg0 + arg1).compareTo(arg1 + arg0); } } public class MergeStringsLowestLexicography { public static String lowestString(String[] strs) { Arrays.sort(strs, new MergeComparator()); String res = ""; for (int i = 0; i != strs.length; i++) { res += strs[i]; } return res; } public static void main(String[] args) { String[] strArr = { "jibw", "ji", "jp", "bw", "jibw" }; String result = lowestString(strArr); System.out.println(result); } } 证明最关键的步骤是证明这种比较的方式具有传递性。 假设有a,b,c三个字符串，他们有如下的关系： a.b < b.a b.c < c.b 所谓传递性证明是指，如果有以上的两个关系，能否证明 a.c < c.a 证明传递性过程： 字符串a,b的连接记为a.b，如果将字符串看做一个K进制数，那么字符串之间的加减乘除都可以按照数字的方式进行。 那么a.b这个字符串中a作为高位，b作为低位，可以进行如下的替换 a.b = a*(K^length(b))+b。其中a*(K^length(b))表示，a这个K进制数，向左位移了b的长度。 我们现在把K^length(b)记为moveBit(b)，则a.b = a*moveBit(b)+b，那么 a.b < b.a => a*moveBit(b)+b < b*moveBit(a)+a 不等式1 b.c < c.b => b*moveBit(c)+c < c*moveBit(b)+b 不等式2 现在要证明a.c < c.a，也就是证明a*moveBit(c)+c < c*moveBit(a)+a 我们把不等式1的左右两边同时减去b再乘以c，则不等式1可以变形为： a*moveBit(b)*c < b*moveBit(a)*c+a*c-b*c 我们把不等式2的左右两边同时减去b再乘以a，则不等式2可以变形为： b*moveBit(c)*a+c*a-b*a < c*moveBit(b)*a 现在a,b,c都是K进制数，所以服从乘法交换律。 所以不等式1中的a*moveBit(b)*c等于不等式2中的c*moveBit(b)*a。 所以，b*moveBit(c)*a+c*a-b*a < b*moveBit(a)*c+a*c-b*c 所以，b*moveBit(c)*a-b*a < b*moveBit(a)*c-b*c 所以，a*moveBit(c)-a < c*moveBit(a)-c 所以，a*moveBit(c)+c < c*moveBit(a)+a => a.c < c.a 证明a.c < c.a完成。 现在我们知道这种比较大小的方式是有传递性的，那么根据这种传递性可知，在一个排序过的序列中，任意两个字符串Str1与Str2，只要Str1排在Str2的前面，就有Str1.Str2 < Str2.Str1。 好，现在我们有了传递性，接下来需要证明：在通过这种排序方式之后所得到的字符串序列中，交换任意两个字符串之后的那个总字符串，都会比未交换前的那个总字符串，拥有更大的字典顺序。 假设通过如上的比较方式，我们得到了一组字符串的序列：…A.M1.M2…M(n-1).M(n).L…，该序列表示，代号为A的字符串之前和代号为L的字符串之后都有若干字符串，A和L中间有若干字符串（用M1..M(n)表示）。 现在我们交换A和L这两个字符串，那么交换之前和交换之后两个总字符串就分别为： …A.M1.M2…M(n-1).M(n).L… 换之前 …L.M1.M2…M(n-1).M(n).A… 换之后 现在我们需要证明换之后的总字符串字典顺序大于换之前的。 证明： 因为在原始序列中，M1排在L的前面，所以有M1.L<L.M1，所以有…L.M1.M2…M(n-1).M(n).A… > …M1.L.M2…M(n-1).M(n).A… 因为在原始序列中，M2排在L的前面，所以有M2.L<L.M2，所以有…M1.L.M2…M(n-1).M(n).A… > …M1.M2.L…M(n-1).M(n).A… … 所以有：…M1.M2…M(n-1).M(n).L.A… > …M1.M2…M(n-1).M(n).A.L… 因为在原始序列中，A排在M(n)的前面，所以有A.M(n)<M(n).A，所以有…M1.M2…M(n-1).M(n).A.L… > …M1.M2…M(n-1).A.M(n).L… … 所以有：…M1.A.M2…M(n-1).M(n).L… > …A.M1.M2…M(n-1).M(n).L… 通过上面不等式之间的连接，可证明换之后>换之前，证明结束，该方法有效。 那么整个解法的时间复杂度就是排序本身的复杂度，O(N*logN)。 本题的解法非常简单，但是该题的重点，解法有效性的证明确比较复杂。在这里不得不向读者进行一点提醒，这道题的解题方法，可以划进贪心算法的范畴，这种有效的比较方式，就是我们的贪心策略。 所以算法的时间复杂度就是排序的时间复杂度，O(N*logN) 正如本题所展示的一样，稍微了解过贪心算法的朋友都知道，贪心策略容易大胆假设，策略有效性的证明可就不容易求证了。在面试中，如果哪一个题目你决定用贪心方法求解，那你必须用较大的篇幅去证明你提出的贪心策略是有效的。 所以我建议面试准备时间不充裕的同学，不要轻易去啃有关贪心策略的题目，那将占用你大量的时间和精力。实际上在面试中也较少出现需要用到贪心策略的题目，造成这个现象有两个很重要的原因，其一是考察贪心策略的面试题目，关键点在于数学上对策略的证明过程，偏离考察编程能力的面试初衷；其二是纯用贪心策略的面试题，解法的正确性完全在于贪心策略的成败，而缺少其他解法的多样性，这样就会使这一类面试题的区分度极差。 贪心策略在算法上的地位当然重要，但是对于准备代码面试的同学来说，性价比不高，慎用。  以此提醒学生，不要刷ACM重量级题目，不要先刷贪心算法的题目。并说明原因 并讲述一下代码面试题目的特点