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);
}
}
