所以我受到了this answer的启发，请先阅读那个答案，它所属的问题基本上与这个问题相同，只是在这个问题中输入字符串是循环的。那个答案中的关键思想是，为了找到将所有1分组所需的最小交换次数，我们只需要得到一个包含所有1索引的数组，该数组的中心始终保持中心索引，然后按照以下算法计算最小交换次数，时间复杂度为O(n)：
oneIndices = array of indices of all 1's in the input
middleOfOnesIndices = round(oneIndices.length/2)-1 // index to the center index
minimumSwaps = 0
foreach index i of oneIndices
minimumSwaps += aboluteValue(oneIndices[middleOfOneIndices]-oneIndices[i])-absoluteValue(middleOfOneIndices-i);
基于这个答案，这个问题的一个快速解决方案是在某个点上打破圆形并将其拉伸成一条直线，假设为str，然后对其应用上述算法，然后我们找到str的最小交换次数。让n为输入循环字符串的长度，则有n个点可以打破圆形，此解决方案的最终时间复杂度将为O(n^2)。
因此，我试图提出一个需要O(n)时间复杂度的解决方案。在上面的算法中，决定交换次数的是中间1和其他1之间的相对距离。既然我们已经计算出了str的最小交换次数，那么我们是否可以在其他情况下重复使用它？这样我们就不必在每种情况下进行for循环来计算最小交换次数，那么时间复杂度将为O(n)。
在所有可能的断点中，有些是我们不需要的。以输入的循环字符串100011为例，我们在两个不同的点上断开它，一个是在索引0和1之间，另一个是在1和2之间，然后我们会得到：
000111 and 001110
在上述算法中，我们只需要计算其他 1 距离中间的 1 的相对距离。在这两种情况下，决定最小交换次数的是它们包含所有 1 的公共子串，即为 111。因此，为了避免重复计算同一结果的情况，我们只在每个 1 后立即打破循环。
为了重用上一次的结果，我们按照从左到右的顺序依次在每个 1 后打破循环。以 011010110001 为例，我们首先计算最小交换次数，然后在索引 1 和 2 之间打破循环。为了简单起见，在将循环拉成一条直线时，在打破循环点之前仍将数字保持为 0。
011010110001 <
00101011000101 <
^^ <
as unchanged, so we can reuse last result handily.
the array of all indices of 1's:
[1,2,4,6,7,11] <----before
[2,4,6,7,11,13] <----after break it between indices 1 and 2
我的最终解决方案是用JavaScript编写的，时间复杂度为O(n)：
function getOneIndices(inputString) {
var oneIndices = [];
for (var i=0; i<inputString.length; i++) {
if (inputString.charAt(i) === "1") {
oneIndices.push(i);
}
}
return oneIndices;
}
function getSwapInfo(inputString) {
var oneIndices = getOneIndices(inputString);
if(oneIndices.length < 2) return 0;
var minSwaps = Number.MAX_VALUE;
var distanceInInput = 0, distanceInOneIndices = 0;
var middleOfOneIndices = Math.round(oneIndices.length/2)-1;
for (var i=0; i<oneIndices.length; i++) {
distanceInInput += Math.abs(oneIndices[middleOfOneIndices]-oneIndices[i]);
distanceInOneIndices += Math.abs(middleOfOneIndices-i);
}
for(var i = 0, lastOneIndexMoved = -1, endIndexInInput = inputString.length - 1;
i <= oneIndices.length; i++){
var curSwaps = distanceInInput - distanceInOneIndices;
if(curSwaps < minSwaps) minSwaps = curSwaps;
var lastMiddleIndex = oneIndices[middleOfOneIndices];
var firstOneIndex = oneIndices[0];
oneIndices.splice(0, 1);
var lastOneIndex = endIndexInInput + firstOneIndex - lastOneIndexMoved;
oneIndices.push(lastOneIndex);
var diff = oneIndices[middleOfOneIndices] - lastMiddleIndex;
distanceInInput += middleOfOneIndices * diff
- (oneIndices.length - middleOfOneIndices - 1) * diff
- Math.abs(lastMiddleIndex - firstOneIndex)
+ Math.abs(oneIndices[middleOfOneIndices] - lastOneIndex);
lastOneIndexMoved = firstOneIndex;
endIndexInInput = lastOneIndex;
}
return minSwaps;
}
console.log("minimum swaps for '111111': " + getSwapInfo("111111"));
console.log("minimum swaps for '111011': " + getSwapInfo("111011"));
console.log("minimum swaps for '010001': " + getSwapInfo("010001"));
console.log("minimum swaps for '011010110001': " + getSwapInfo("011010110001"));
console.log("minimum swaps for '10000000000000011101': " + getSwapInfo("10000000000000011101"));
console.log("minmum swaps for '01001001100': " + getSwapInfo("01001001100"));
1000111是一个有效的序列吗？ - Damien