相信数学-相信科学==leetcode 179 最大数

leetcode 179 最大数

https://leetcode.cn/problems/largest-number/description/

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。
示例 1：
输入：nums = [10,2]
输出："210"
示例 2：
输入：nums = [3,30,34,5,9]
输出："9534330"

我这是通过愚蠢的观察得出的规律， 答案的题解里有另外一种方法和证明。
我的主题思路是排序，不过怎么排是关键， 设两个排序string分别是A， B
名词说明：

• 可比较范围内： 两个值都没有越界

首先， 对于在彼此可比较范围内，如果出现不一样的字符，则他们的顺序就是这两个不同字符的顺序: order(A,B) = order(char_A,char_B)

当超出某个的可比较范围， 则来到了某个长数组的地方， 设长的为lon， 短的为shor, 并且当来到此种情况是， shor一定是lon的前缀，且lon = y * shor + x * CHAR 其中 y >= 1, 0 <= x <= len(shor)
则对于shor 与 lon的比较其实是 : shor + lon 与 lon + shor 的比较, 粗略上来讲，可以直接比较：shor + lon 与 lon + shor 也可以比较 shor 与 x*CHAR

shor + long = shor shor shor x*Char
long + shor = shor shor x*Char shor

所以： 如果shor == xCHAR 则相等， 如果 shor > xCHAR 则 shor + long 更大， 则shor 更大， 如果 shor < x*CHAR , 则lon + shor 更大，则 lon 更大。

（所以，这里的代码其实写复杂了）

class Solution {
    public String largestNumber(int[] nums) {
        String[] ss = new String[nums.length];
        for(int i =0;i < nums.length; ++ i) {
            ss[i] = String.valueOf(nums[i]);
        }

        Arrays.sort(ss, new Comparator<String>() {
            public int compare(String a, String b) {
                int i = 0;
                for( ; i < a.length() && i < b.length(); ++ i) {
                    if(a.charAt(i) != b.charAt(i)) {
                        return ( a.charAt(i) - b.charAt(i));
                    }
                }
                if(i == a.length() && i == b.length()) {
                    return 0;
                }
                String lon =  i != a.length() ? a:b;
                String shor = i == a.length() ? a:b;
                int j = i;
                while( j < lon.length() && lon.charAt(j % i) == lon.charAt(j)) {
                    j ++;
                }
                if(j < lon.length()) { // lon.charAt(j % i) != lon.charAt(j)
                    int v = lon.charAt(j) - lon.charAt(j % i);
                    // v > 0 lon is bigger, v < 0 shor is bigger
                    return v > 0 ? (a == lon ? 1 : -1) : (a == shor ? 1 : -1);
                }
                // j == lon.length()
                int t = j % i;
                char shorLeadingCharToCompare = '\0';
                char lonLeadingCharToCompare = '\0';
                while( t < i) {
                    shorLeadingCharToCompare = lon.charAt(t % i);
                    lonLeadingCharToCompare = lon.charAt(t - j%i);
                    if(shorLeadingCharToCompare - lonLeadingCharToCompare != 0) {
                        break;
                    }
                     ++ t;
                }
                if(t == i) {
                    return 0;
                }
                //char shorLeadingCharToCompare = lon.charAt(j % i); 
                //char lonLeadingCharToCompare = lon.charAt(0);

                int v = shorLeadingCharToCompare - lonLeadingCharToCompare;
                // v > 0  shor is bigger   v < 0 lon is bigger
                return v > 0 ? (a == shor ? 1 : -1) : (a == lon ? 1 : -1);
            }
        });

        System.out.println(Arrays.deepToString(ss));
        StringBuilder sb = new StringBuilder();

        for(int i = ss.length-1; i >= 0; -- i) {
            sb.append(ss[i]);
        }
        String tmpAns= sb.toString();
        int i = 0;
        boolean startingWith0 = true;
        for(; i < tmpAns.length() - 1;  ++i) {
            if(startingWith0  && tmpAns.charAt(i) == '0'){

            }else {
                break;
            }
        }
        return tmpAns.substring(i);

    }
}