Reorganized String
2018-02-15 本文已影响8人
gattonero
问题
字符串问题，给定一个字符串，输出任何一种该字符串的重新排列，使得没有相邻的相同字符，否则输出""
解决方案
- 尝试使用回溯的方法，这里注意回溯中遍历顺序应该按出现频数次数倒序（不然就TLE了），因为Map不能直接按值来排序（按键排序只要实现SortedMap就可以了），那么我们需要一个辅助的排序数组
- 文章中给出的 Sort By Count 方法，大体思路是先排序频数数组，再根据特定的间隔（1），将字符填入结果字符串中，其中的counts数组，实际上就是一个map（因为键不可能超过26，所以用一种特殊的方法保存在int数组中，也就是Encoded counts[i] = 100*(actual count) + (i)），优先队列的解法也是类似的思路
