Daily LeetCode 179. Largest Number

https://leetcode.com/problems/largest-number/

Medium

问题描述：

Given a list of non negative integers, arrange them such that they form the largest number.

Example 1:

Input: [10,2]
Output: "210"

Example 2:

Input: [3,30,34,5,9]
Output: "9534330"

Note: The result may be very large, so you need to return a string instead of an integer.

题目分析：

给定一个正数列表，用这些正数组成一个最大的数。

起初我的思路是将正数列表转换为字符串列表，按照字典序对列表进行排序，再将排完序的列表拼接返回即可，但这种方法不能处理例如[18,180]这样的例子，正确答案应该是18180，但实际会输出18018。

我们可以用类似于冒泡排序的思路来解决这个问题，冒泡排序是比较前后两个数的大小，在这个问题中，由于要保证最终组成的数最大，因此对于[a, b]，我们需要比较a+b与b+a之间的关系，这里的加法指的是字符串加法，即我们需要比较是a在前比较大还是b在前比较大。通过自定义比较函数来实现上述比较，关于python自定义比较函数，可以查看这篇文章：Python Tricks and Tips(Continually updated)

还有一个注意点是对元素全部为0的列表的处理，我们可以调用lstrip()方法将所得字符串左边的0全部去除，在返回结果时，若字符串为空，则直接返回'0'。

代码：

from functools import cmp_to_key

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        def ch_cmp(a, b):
            return int(b + a) - int(a + b)
        
        nums = sorted([str(num) for num in nums], key=cmp_to_key(ch_cmp))
        res = ''.join(nums)
        
        return res.lstrip('0') or '0'