[关闭]
@spiritnotes 2016-03-05T08:40:28.000000Z 字数 1237 阅读 1574

数排列形成最大值

编程题


题目

已知有一些数(大小不限定,不一定为个位数),如何将这些数排列在一起构成的数值最大?

分析

针对这个题目,最简单的办法就是通过全排列来查找最大值,不过我们可以看到依次选择最大的字面数来从左到右构成数即可保证最大值(因为所有能够形成的数的位数都是一样的,从左到右依次比较肯定能够满足最大),由于在从左到右依次选择时可能出现多条路径,因此需要考虑多种可能。

解答

  1. def get_max_num(numbers):
  2. """
  3. 对一些数字寻找最大排列
  4. """
  5. str_numbers =[str(i) for i in numbers]
  6. digit_num = sum(len(i) for i in str_numbers)
  7. seqs = [NumChooseSeq('', '', str_numbers)]
  8. for _ in range(digit_num):
  9. new_seqs = []
  10. for seq in seqs:
  11. new_seqs += list(seq.choose_next())
  12. max_num = max(i.curr_num for i in new_seqs)
  13. new_seqs = [i for i in new_seqs if i.curr_num == max_num]
  14. seqs = new_seqs
  15. return int(seqs[0].curr_num)
  16. class NumChooseSeq():
  17. def __init__(self, curr_num, follow, unused):
  18. self.curr_num = curr_num
  19. self.unused = unused
  20. self.follow = follow
  21. def choose_next(self):
  22. if self.follow:
  23. yield NumChooseSeq(self.curr_num+self.follow[0], self.follow[1:], self.unused)
  24. else:
  25. max_num = max(i[0] for i in self.unused)
  26. for index,num_ in enumerate(self.unused):
  27. if num_[0] == max_num:
  28. rest = self.unused[:index] + self.unused[index+1:]
  29. yield NumChooseSeq(self.curr_num+num_[0], num_[1:], rest)
  30. def show(self):
  31. print('curr', self.curr_num, 'follow',self.follow, 'unused', self.unused)
  32. def test():
  33. assert(get_max_num([1,2,3]) == 321)
  34. assert(get_max_num([1,10,1]) == 1110)
  35. assert(get_max_num([958,9,5,6]) == 995865)
  36. assert(get_max_num([30,31,3,2]) == 331302)
  37. if __name__ == '__main__':
  38. test()
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注