#题目:
有n个正整数(每个数小于10亿),将它们表示成字符串形式。对每一个字符串s,
可以翻转为新字符串s’,如“1234”可以翻转成“4321”。现在,
将这n个字符串以任意顺序连成一个字符环,每个字符串可以选择是否翻转。在字符环中,
从任意一个位置开始,遍历整个环,得到一个长整数。请问,如何才能得到最大的长整数
举例:9,98,23,56,56,998 1
要反转的 :23->32 56->65
得到数组: 9 98 32 65 65 998 1
最后得到的最大的长整数是 9 998 98 65 65 32 1
#method 正确的解法:字符串排序
这题的考点是字符串排序,而非数字排序。
在排序过程中使用 Comparator 比较两个排序的字符串。
compareTo() 的返回值是 int, 它是先比较对应字符的大小( ASCII 码顺序)
- 如果字符串相等返回值0
- 如果第一个字符和参数的第一个字符不等,结束比较,返回他们之间的差值(ascii码值)(负值前字符串的值小于后字符串,正值前字符串大于后字符串)
- 如果第一个字符和参数的第一个字符相等,则以第二个字符和参数的第二个字符做比较,以此类推,直至比较的字符或被比较的字符有一方全比较完,这时就比较字符的长度.
对于 [830,8301],若纯粹使用 compareTo 方法无法得到正确解。
技巧在于先将两个字符串以不同的两种方式( right-to-left 或 left-to-right)连接后,再比较它们的大小。
#method
(这是错误的!!!)思路:建立一棵字典树 trie 比如:
我们可以把这一组数构建一棵字典树
字典树相当于二叉树的复杂版本
同时我们可以构建字典树的同时统计词的词频
构造好字典树后,我们采用遍历的方式来获取词以及词频,输出的数正好是我们需要的顺序
上代码:
我们可以看出来字典树可以大大压缩数据,节省空间,大树据处理的利器