题型:sort
大意:将给定的一系列数组成新的数,并保证这个数最大
做法1:(直观)
1.1 对于两个不含有公共前缀的字符串,直接大小比较即可
1.2 对于两个含有公共前缀的字符串strx stry,则需要比较strx+stry和stry+strx这两个新字符串的大小
例如:98 9820 983
1.3 综合1.1和1.2的思想,第一步可以直接对数组转化为字符串数组,然后直接普通的大小排序;第二步每次取出一个“最大”的字符串,然后看剩下的和他有公共前缀的字符是否符合1.2的情况,有则直接取代当前“最大”字符串,否则略过
做法2:(证明详见 )
直接设定cmp函数进行sort
做法1 code:
1 class Solution(object): 2 def judge_prefix(self, strx, stry): 3 ''' 4 if the strx contain stry(stry is strx's prefix) 5 return len(stry) 6 ''' 7 for i in range(min(len(strx),len(stry))): 8 if strx[i] == stry[i]: 9 pass10 else:11 return i12 return min(len(strx),len(stry))13 14 def judge_large_small(self, strx, stry):15 prefix_len = self.judge_prefix(strx, stry)16 #eql17 if len(strx) == prefix_len and len(stry) == prefix_len:18 return 019 #left_strx = strx[prefix_len:]20 if strx+stry > stry+strx:21 return 122 else:23 return -124 25 def largestNumber(self, nums):26 """27 :type nums: List[int]28 :rtype: str29 """30 nums_strlist = []31 mp = {}32 for i in nums:33 mp[i] = 134 nums_strlist.append(str(i))35 nums_strlist.sort()36 #print nums_strlist37 ans = ''38 while True:39 i = len(nums_strlist) - 140 if i < 0:41 break42 cur = nums_strlist[i]43 #print 'pre cur:', cur44 flag = -145 for j in range(i-1, -1, -1):46 if self.judge_prefix(cur, nums_strlist[j]) > 0:47 if self.judge_large_small(cur, nums_strlist[j]) >= 0:48 pass49 else:50 cur = nums_strlist[j]51 flag = j52 else:53 break54 #print "last cur:", cur55 ans += cur56 if flag != -1:57 nums_strlist.pop(flag)58 else:59 nums_strlist.pop(i)60 ans = ans.lstrip('0')61 if ans == "":62 return "0"63 else:64 return ans
做法2 code:
1 def cmp(x, y): 2 if x+y > y+x: 3 return -1 4 else: 5 return 1 6 7 class Solution(object): 8 def largestNumber(self, nums): 9 nums_strlist = []10 for i in nums:11 nums_strlist.append(str(i))12 nums_strlist.sort(cmp)13 ans = ''14 for i in nums_strlist:15 ans += i16 ans = ans.lstrip('0')17 if ans == '':18 ans = '0'19 return ans