Leetcode 179. 最大数(贪心算法+sorted)

Leetcode 179. 最大数(贪心算法+sorted)

1.题目

链接:https://leetcode-cn.com/problems/largest-number/

题目
给定一组非负整数 nums,重新排列每个数的顺序(每个数不可拆分)使之组成一个最大的整数。
注意:输出结果可能非常大,所以你需要返回一个字符串而不是整数。

示例 1
输入:nums = [10,2]
输出:“210”

示例 2
输入:nums = [3,30,34,5,9]
输出:“9534330”

2.解题

方法1:贪心算法

  • 基本思路:创建新列表,用于存储
class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        strs = map(str, nums)    # 哈希
        def cmp(a,b):            #cmp -- 比较的函数,必须遵守的规则为:
                                 #大于则返回1,小于则返回-1,等于则返回0。
            if a + b == b + a:
                return 0
            elif a + b > b + a:
                return 1
            else:
                return -1 
        strs = sorted(strs,key=functools.cmp_to_key(cmp),reverse=True) #reverse = True 降序 , reverse = False 升序(默认)
        return ''.join(strs) if strs[0] !='0' else '0'

参考文章链接:
1. 【宫水三叶の相信科学系列】为什么根据「拼接结果的字典序大小」决定「其在序列里的相对关系」

上一篇:Bandwidth(爆搜)


下一篇:跨届训练赛 5.2