擅长:python、mysql、java
<p>如果我理解正确,你首先需要构造输入序列的所有循环置换,然后确定(按字典顺序)最小的元素。这是符号循环的根。
试试这个:</p>
<pre><code>def normalized(s):
L = [s[i:] + s[:i] for i in range(len(s))]
return sorted(L)[0]
</code></pre>
<p>这段代码只处理字符串,而不像代码中那样在队列和字符串之间进行转换。快速计时测试显示此代码在30-50%的时间内运行。
知道应用程序中<code>s</code>的长度是很有趣的。由于所有排列都必须临时存储len(s),临时列表<code>L</code>需要^2个字节。希望这不是你的限制。在</p>
<p><strong>编辑:</strong>
今天我无意中发现,如果你把原来的字符串连在一起,它将包含所有的旋转作为子串。所以代码是:</p>
^{pr2}$
<p>这确实会运行得更快,因为只有一个合并加上n个滑动。在我的机器上,使用10到10**5的stringlength,运行时间在55%到66%之间,而带有生成器的min()版本则是这样。在</p>
<p>请注意,您在内存消耗(2倍)上牺牲了速度,这在这里并不重要,但在不同的设置下可能会这样做。在</p>