字典序最小问题_思路

57 阅读 0 评论 38 点赞

我是靠谱客的博主欢喜帽子，最近开发中收集的这篇文章主要介绍字典序最小问题_思路，觉得挺不错的，现在分享给大家，希望可以做个参考。

给定长度为N的字符串S，要构造一个长度为N的字符串T。期初，T是一个空串，随后反复进行下列任意操作：

1>从S的头部删除一个字符，加到T的尾部；
2>从S的尾部删除一个字符，加到T的尾部。

目标是要构造字典序尽可能小的字符串T。

比如当N=6，S=”ACDBCB”时，程序应输出ABCBCD。

思路：
将S反转后的字符串定为S’，比较S和S’的字典序，如果S较小则从S开头取字符加到T的末尾，反之从S末尾取字符加到T的末尾。字典序相同时两者等价，取哪个都行。

字典排序（lexicographical order）是一种对于随机变量形成序列的排序方法。其方法是，按照字母顺序，或者数字小大顺序，由小到大的形成序列。

比如说有一个随机变量X包含{1 2 3}三个数值。
　　
其字典排序就是{} {1} {1 2} {1 2 3} {2} {2 3} {3}

找本英汉字典，和那个排序方法一样。
对于字符串，先按首字符排序，如果首字符相同，再按第二个字符排序，以此类推。
如aa,ab,ba,bb,bc就是一个字典序。

以上就是欢喜帽子为你收集整理的字典序最小问题_思路的全部内容，希望文章能够帮你解决字典序最小问题_思路所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。