贪心

贪心

问题：拼接字符串获得最低字典序

给定一个字符串类型的数组 strs，找到一种拼接方式，使得把所有字符串拼接起来之后形成的字符串具有最低的字典序。

分析

此题的比较策略即为贪心策略，但是不一定其它也是两者一样的。

贪心方案一（错误）：按照每个字符串字典序排序然后进行合并，例 “b” “ba” 排完之后是 “b”,”ba”，合并是：”bba”，但是实际上最小的是 “bab”;

贪心方案二：若 “str1 str2“ 拼接结果 <= “str2 str1” 拼接结果，则 str1 放在前面。

判断自定义比较器的正确性

自定义比较器正确的前提是：具有传递性并且结果值唯一，同时可以比较出所有值的大小，

例如：甲乙比较：甲 < 乙；乙丙比较：乙 < 丙；甲丙比较：丙 < 甲，结果具有随机性，就是比较不出来结果；

应该具有传递性，例如：甲 < 乙，乙 < 丙，然后甲 < 丙；

字典序比较

• 如果两个比较对象长度相等，这直接比较；
• 如果两个对象长度不等，短的后面补 ASCII 最小值，然后比较；

证明比较器的传递性

• 前言

  12,23 两个数字拼接为 1223，即 $$12 * 10^2 + 23$$，即 12 向左位移两位然后加上 23；

  a,b 两个字符串拼接为 ab，将字符串理解为 K 进制数，即 a 向左位移 b 的长度那么多位数然后加上 b 的值；

  所以：ab = $$a * k^{b 长度} + b$$，其中设 $$m(b) = k^{b 长度}$$，同理 $$m(c) = k^{c 长度}$$

证明过程：因为 ab <= ba，bc <= cb，证明：ac <= ca

因为 ab <= ba，所以 a * m(b) + b <= b * m(a) + a，等式两边同时减去 b 然后乘 c 得到：a * m(b) *c <=(b * m(a) +a -b) * c

因为 bc <= cb，所以 b * m(c) + c <= c * m(b) + b，等式两边同时减去 b 然后乘 a 得到：(b * m(c) +(-b)) *a <= c * m(b) * a

从上面两个等式推出：(b * m(c) + (-b)) * a <= (b * m(a) + a - b) * c，然后两边化简并且除以 b ，并且两边同时加上 a 和 c 之后得到 a * m(c) + c <= c * m(a) + a)，即 ac <= ca，证毕。

证明任意两个交换都比现在的字典序大

原来的：………k1 m1 m2 ………….mk k2…….

交换后：………k2 m1 m2 ………… mk k1…….

证明：因为 k1 m1 <= m1 k1 所以：

………k1 m1 m2 ………….mk k2……. 小于等于

………m1 k1 m2 ………….mk k2……. 小于等于

………m1 m2 k1 ………….mk k2……. 小于等于

。。。。。。。。。。。

………m1 m2 ………….mk k2 k1……. 小于等于

………m1 m2 ………….k2 mk k1……. 小于等于

。。。。。。。。。。。

………k2 m1 m2 ………….mk k1…….

证毕，并可以证明多个数交换也符合（可以化简到两个元素交换）。

判断贪心方案的正确性

做题的时候不要妄图验证贪心方案的正确性，直接使用小数据样本输入该贪心方案和对数器的结果比较，如果小样本验证是正确的则默认该方案就是正确的。

class Solution {

    public static String minNumber(int[] nums) {
        if (nums == null || nums.length == 0) {
            return "";
        }
        String res = "";
        List<String> list = new ArrayList<>();
        for (int num : nums) {
            list.add(num + "");
        }
        list.sort((s1, s2) -> (s1 + s2).compareTo(s2 + s1));
        for (String s : list) {
            res += s;
        }
        return res;
    }

}