https://leetcode.com/problems/largest-number
179. Largest Number
给一个非负整数列表 nums
将它排成最大的数字并回传它
因为数字可能很大 所以是回传字串而不是整数
Example 1:
Input: nums = [10,2]
Output: "210"
Example 2:
Input: nums = [3,30,34,5,9]
Output: "9534330"
Constraints:
* 1 <= nums.length <= 100
* 0 <= nums[i] <= 10^9
思路：
因为要数字开头越大越前面
原本想法很简单 根据每个数反转后排序
nums.sort(reverse=True, key=lambda x: str(x)[::-1])
结果马上就错了(
后来想说改为靠左对齐并在右边补0
nums.sort(reverse=True, key=lambda x: str(x).ljust(len_max, '0')
过了一些但还是错了
再研究发现并不是补0 而是要补两数间长度差的前n位数 才会知道大小
如 8308 跟 830 差1 会比较肯定是至少1个数相同
只补1个数的话两边都是 8308 看不出来 要补2个数变成
8308_8 跟 830_83 所以知道 8308 放前面
最后想说干脆逐个比对 超越不了再insert
Python Code:
class Solution:
def largestNumber(self, nums: List[int]) -> str:
if len(nums) == 1: return str(nums[0])
ans = [str(nums[0])]
for num in nums[1:]:
n = len(ans)
while n:
if f'{num}{ans[n-1]}' <= f'{ans[n-1]}{num}':
ans.insert(n, str(num))
break
n -= 1
else: # 检查到第0个都是比较大的话 就插到最前面
ans.insert(0, str(num))
return str(int(''.join(ans))) # 有 [0,0] 这种东西 ((
想了一个早上 比预期中难 不早早早了