【LeetCode】179. 最大数

1 题目

这题如果是第一次做，还是有点儿难度的，关键是如何想到一个比较的原则？ 我们可以想到在冒泡排序中，我们比较的是两个数的大小，如果前者较大，则交换，使得较大的那个数放到后面。不停的操作使得每轮中的最大数放到最后一位，代码如下：

for i in range(len(nums)):
    for j in range(len(nums)-i-1): # 表示已经排好的
        # 按照大小排序，两两交换
        if nums[j] > nums[j+1]:
            nums[j],nums[j+1] = nums[j+1],nums[j]

但是本题是来找如何拼凑得到最大的一个数，比较的原则不再是两个数孰大孰小了，而是两个数的拼接的结果是孰大孰小？

2 思想

类似冒泡排序，不过比较的原则是是否可以组成一个更大数。

3 代码

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        # 将最大的放在最后，然后翻转一下数组
        for i in range(len(nums)):
            for j in range(len(nums)-i-1): # 表示已经排好的
                # 按照大小排序，两两交换
                if int(str(nums[j]) + str(nums[j+1])) > int(str(nums[j+1]) + str(nums[j])):
                    nums[j],nums[j+1] = nums[j+1],nums[j]
        nums = list(reversed(nums))
        res = ""
        for i in nums:
            res+=str(i)
        # 需要去除前导0
        res = res.lstrip("0")
        if res == "":
            return "0"
        return res