分享一个大牛的人工智能教程。零基础通俗易懂风趣幽默希望你也加入到人工智能的队伍中来请轻击人工智能教程大家好欢迎来到我的网站 人工智能被认为是一种拯救世界、终结世界的技术。毋庸置疑人工智能时代就要来临了科… 继续阅读 前言https://www.captainai.net/troubleshooterpackage live.every.day.ProgrammingDesign.CodingInterviewGuide.String; import java.util.Arrays; import java.util.Comparator; /** * 拼接所有字符串产生字典顺序最小的大写字符串 * * 【题目】 * 给定一个字符串类型的数组strs请找到一种拼接顺序使得将所有的宇符串拼接起来组成的大写字符串是所有可能性中字典顺序最 * 小的并返回这个大写字符串。 * * 【难度】 * 困难 * * 【解答】 * 有一种思路为先把strs中的字符串按照字典顺序排序然后将串起来的结果返回。这么做是错误的比如题目中的例子2按照字典 * 排序结果是B、BA串起来的大写字符串为BBA但是字典顺序最小的大写字符串是BAB所以按照单个字符串的字典顺序进行排 * 序的想法是行不通的。如果要排序应该按照下文描述的标准进行排序。 * * 假设有两个字符串分别记为a和ba和b拼起来的字符串表示为a.b。那么如果a.b的字典顺序小于b.a就把字符串a放在前面否 * 则把字符串b放在前面。每两个字符串之间都按照这个标准进行比较以此标淮排序后再依次串起来的大写字符串就是结果。这样做 * 为什么对呢当然需要证明。 * * 证明的关键步骤是证明这种比较方式具有传递性。假设有a、b、c三个字符串它们有如下关系 * a.bb.a * b.cc.b * 如果能够根据上面两式证明出a.cc.a说明这种比较方式具有传递性证明过程如下 * 字符串的本质是K进制数比如只由字符a~z组成的字符串其实可以看作26进制的数。那么字符串a.b这个数可以看作a这个数 * 是它的高位b是低位即a.ba*K的b长度次方b。 * * 证明传递性后还需要证明通过这种比较方式排序后如果交换任意两个字符串的位置所得到的总字符串将拥有更大的字典顺序。现 * 在需要证明交换之后的总字符串字典顺序大于交换之前的。 * * 那么整个解法的时间复杂度就是排序本身的复杂度即O(NlogN)。具体请参看如下代码中的lowestString方法。 * * 本题的解法看似非常简单但解法有效性的证明却比较复杂。在这里不得不提醒读者这道题的解题方法可以划进贪心算法的范畴这 * 种有效的比较方式就是我们的贪心策略。 * 正如本题所展示的一样贪心策略容易大胆假设但策略有效性的证明可就不容易求证了。在面试中如果哪一个题目决定用贪心方法 * 求解则必须用较大的篇幅去证明你提出的贪心策略是有效的。所以建议面试准备时间不充裕的读者不要轻易去啃有关贪心策略的题目 * 那将占用大量的时间和精力。 * 在面试中实际上也较少出现需要用到贪心策略的题目造成这个现象有两个很重要的原因其一是考查贪心策略的面试题目关键点 * 在于数学上对策略的证明过程偏离考查编程能力的面试初衷。其二是纯用贪心策略的面试题解法的正确性完全在于贪心策略的成败 * 而缺少其他解法的多样性这样就会使这一类面试题的区分度极差所以往往不会成为大公司的面试题。贪心策略在算法上的地位当然 * 重要但对初期准备代码面试的读者来说性价比不高。 * * author Created by LiveEveryDay */ public class ConcatenateAllStringProduceDictOrder implements ComparatorString { Override public int compare(String a, String b) { return (a b).compareTo(b a); } public static String lowestString(String[] strs) { if (strs null || strs.length 0) { return ; } // 根据新的比较方式排序 Arrays.sort(strs, new ConcatenateAllStringProduceDictOrder()); StringBuilder res new StringBuilder(); for (int i 0; i strs.length; i) { res.append(strs[i]); } return res.toString(); } public static void main(String[] args) { String[] strs {b, ba}; System.out.printf(The lowest string is: %s, lowestString(strs)); } } // ------ Output ------ /* The lowest string is: bab */