som*_*321 7 string algorithm dynamic-programming
我正在尝试用字符串解决一个非常复杂的问题:
给定的字符串最多包含100000个字符,仅包含两个不同的字符"L"和"R".序列"RL"被认为是"坏",并且必须通过应用交换来减少这种情况.
但是,该字符串应被视为循环,因此即使字符串'LLLRRR'也具有由最后'R'和第一'L'形成的'RL'序列.
可以进行两个连续元素的交换.因此,如果n是字符串的长度(字符串为0索引),我们只能交换位置i和i + 1或位置0和n-1上的元素.
目标是找到在字符串中只留下一个错误连接所需的最小交换次数.
对于字符串'RLLRRL',只需一次交换即可解决问题:交换第一个和最后一个字符(因为字符串是圆形的).因此,该字符串将变为具有一个错误连接的"LLLRRR".
我的想法是使用动态编程,并计算任何给定的'L'需要多少交换才能将所有其他'左'放到'L',或者,在'L'的右边.对于任何'R',我计算相同.
该算法在O(N)时间内工作,但不能给出正确的结果.
当我必须交换第一个和最后一个元素时,它不起作用.我应该在算法中添加什么才能使其适用于那些交换？
这个问题可以在线性时间内解决.
只有一个坏连接的目标是说L字母应该全部组合在一起的另一种方式,以及R字母(在圆形字符串中)
让一组表示一系列随后不能变大的字母(因为周围的字母不同).通过组合单个交换,您可以使用一个或多个"步骤""移动"一个组.一个例子 - 我会写,.而不是L更容易阅读:
RRR...RR....
有4个团体在这里:RRR,...,RR和.....假设您要在上面的字符串中加入两个"R"组和左侧"R"组.然后你可以通过执行6次交换来"移动"中间组,向左移动3个步骤:
RRR...RR....
RRR..R.R....
RRR..RR.....
RRR.R.R.....
RRR.RR......
RRRR.R......
RRRRR.......
这6次互换构成了一个小组的举动.移动的成本是6,并且是组(2)的大小和它行进的距离(3)的乘积.请注意,此移动与我们将具有三个"L"字符(参见点)的组移动到右侧时的移动完全相同.
我将在这个意思中使用"移动"这个词.
总有一种解决方案可以表示为一系列组移动,其中每组移动减少具有两组的组数,即每次移动时,两个R组合并为一组,因此也合并两个L组.换句话说,总有一种解决方案,其中没有一个组必须分开,其中一部分向左移动而另一部分向右移动.我不会在这里提供这种说法的证明.
总有一个解决方案有一个根本不会移动的组:所有其他相同字母的组将向它移动.因此,还有一组相反的字母不会移动,在圆圈的另一端.再说一次,我不会在这里证明这一点.
这个问题等同于最小化代表两个字母之一的组的移动的总成本(交换)(所有组的一半).另外一半的组同时移动,如上例所示.
算法可以像这样:
创建一个整数数组,其中每个值表示一个组的大小.该数组将按照它们出现的顺序列出组.这会考虑循环属性,因此第一个组(索引为0)也会考虑字符串最后一个与第一个字母相同的字母.因此,在偶数指数中,您将拥有表示一个特定字母的计数的组,而在奇数指数处,将存在另一个字母的计数.它们所代表的两个字母中的哪一个并不重要.组数组将始终具有偶数条目.这个数组就是我们解决问题所需要的.
选择第一个组(索引0),并假设它不会移动.称之为"中间组".确定哪一个是相反颜色的组(具有奇数索引),也不必移动.将此其他组称为"拆分组".该拆分组将剩余的奇数组拆分为两个部分,其中值(总和)的总和小于或等于两个总和的总和.这表示即使是在一个方向上移动也比在另一个方向上移动以便与索引0处的组合并更便宜的事实.
现在确定将所有偶数组移向中间组的成本(交换次数).
这可能是也可能不是解决方案,因为中间组的选择是任意的.
对于任何其他偶数组被视为中间组的情况,必须重复上述情况.
现在算法的本质是避免在将另一个组作为中间组时重做整个操作.事实证明,可以将下一个偶数组作为中间组(在索引2处),并以恒定时间(平均值)调整先前计算的成本,以得出中间组的这种选择的成本.为此,必须在存储器中保留一些参数:在左方向上执行移动的成本,以及在正确方向上执行移动的成本.此外,需要为两个方向中的每个方向保持偶数组大小的总和.最后,对于两个方向,也需要保持奇数组的总和.当将下一个偶数组作为中间组时,可以调整这些参数中的每一个.通常也必须重新识别相应的拆分组,但也可以在固定时间内平均发生.
不用深入研究,这是一个简单的JavaScript工作实现:
function minimumSwaps(s) {
var groups, start, n, i, minCost, halfSpace, splitAt, space,
cost, costLeft, costRight, distLeft, distRight, itemsLeft, itemsRight;
// 1. Get group sizes
groups = [];
start = 0;
for (i = 1; i < s.length; i++) {
if (s[i] != s[start]) {
groups.push(i - start);
start = i;
}
}
// ... exit when the number of groups is already optimal
if (groups.length <= 2) return 0; // zero swaps
// ... the number of groups should be even (because of circle)
if (groups.length % 2 == 1) { // last character not same as first
groups.push(s.length - start);
} else { // Ends are connected: add to the length of first group
groups[0] += s.length - start;
}
n = groups.length;
// 2. Get the parameters of the scenario where group 0 is the middle:
// i.e. the members of group 0 do not move in that case.
// Get sum of odd groups, which we consider as "space", while even
// groups are considered items to be moved.
halfSpace = 0;
for (i = 1; i < n; i+=2) {
halfSpace += groups[i];
}
halfSpace /= 2;
// Get split-point between what is "left" from the "middle"
// and what is "right" from it:
space = 0;
for (i = 1; space < halfSpace; i+=2) {
space += groups[i];
}
splitAt = i-2;
// Get sum of items, and cost, to the right of group 0
itemsRight = distRight = costRight = 0;
for (i = 2; i < splitAt; i+=2) {
distRight += groups[i-1];
itemsRight += groups[i];
costRight += groups[i] * distRight;
}
// Get sum of items, and cost, to the left of group 0
itemsLeft = distLeft = costLeft = 0;
for (i = n-2; i > splitAt; i-=2) {
distLeft += groups[i+1];
itemsLeft += groups[i];
costLeft += groups[i] * distLeft;
}
cost = costLeft + costRight;
minCost = cost;
// 3. Translate the cost parameters by incremental changes for
// where the mid-point is set to the next even group
for (i = 2; i < n; i += 2) {
distLeft += groups[i-1];
itemsLeft += groups[i-2];
costLeft += itemsLeft * groups[i-1];
costRight -= itemsRight * groups[i-1];
itemsRight -= groups[i];
distRight -= groups[i-1];
// See if we need to change the split point. Items that get
// at the different side of the split point represent items
// that have a shorter route via the other half of the circle.
while (distLeft >= halfSpace) {
costLeft -= groups[(splitAt+1)%n] * distLeft;
distLeft -= groups[(splitAt+2)%n];
itemsLeft -= groups[(splitAt+1)%n];
itemsRight += groups[(splitAt+1)%n];
distRight += groups[splitAt];
costRight += groups[(splitAt+1)%n] * distRight;
splitAt = (splitAt+2)%n;
}
cost = costLeft + costRight;
if (cost < minCost) minCost = cost;
}
return minCost;
}
function validate(s) {
return new Set(s).size <= 2; // maximum 2 different letters used
}
// I/O
inp.oninput = function () {
var s, result, start;
s = inp.value;
start = performance.now(); // get timing
if (validate(s)) {
result = minimumSwaps(s); // apply algorithm
} else {
result = 'Please use only 2 different characters';
}
outp.textContent = result;
ms.textContent = Math.round(performance.now() - start);
}
rnd.onclick = function () {
inp.value = Array.from(Array(100000), _ =>
Math.random() < 0.5 ? "L" : "R").join('');
if (inp.value.length != 100000) alert('Your browser truncated the input!');
inp.oninput(); // trigger input handler
}
inp.oninput(); // trigger input handlerinput { width: 100% }<p>
<b>Enter LR series:</b>
<input id="inp" value="RLLRRL"><br>
<button id="rnd">Produce random of size 100000</button>
</p><p>
<b>Number of swaps: </b><span id="outp"></span><br>
<b>Time used: </b><span id="ms"></span>ms
</p>预处理(创建groups数组等),以及第一组是中间组时的成本计算,都包含最多n次迭代的非嵌套循环,所以这部分是O(n).
当中间组是任何其他偶数组时的成本的计算包括循环(用于选择中间组)和用于调整分组的选择的另一内循环.即使这个内部循环可以迭代多次外部循环的一次迭代,总的来说这个内部循环不会有比n更多的迭代,所以这个外部循环的总执行时间仍然是O(n).
因此,时间复杂度为O(n).
请注意,字符串为100 000个字符的结果是在几分之一秒内计算出来的(请参阅上面代码段显示的毫秒数).