提问人：snowcoffeebean 提问时间：10/21/2023 更新时间：10/23/2023 访问量：56
要排序的二进制字符串的最小替换项
Minimum replacements for binary string to be sorted
问：
给定一个二进制字符串 0 和 1，例如。"001010".
您可以将 0 替换为 1，或将 1 替换为 0。
编写一个算法，该算法给出了要对二进制字符串进行排序的最小替换次数（所有 0 都排在 1 之前）。
例如。
“0011110010” --> 3.
“0011110” --> 1
“1010110111” --> 3
我找到了 1 和 0 的计数。我试图使用当前计数 0 找到一个枢轴位置，超过该计数都应该是 1，并计算背离的数量，即我们发现 0 而不是 1 的实例。但是，我没有得到正确的结果。
答：
2赞
S H
10/21/2023
#1
让我们从左到右迭代表单，同时跟踪左边的 1 和右边的 1 个数字，现在如果你在某个索引上想要排序，你应该把它左边的所有 1 都改成零，把它右边的所有零都改成 1，所以它的答案将是这 2 的总和。
现在你需要跟踪它们，跟踪零只是一个计数器，要计算右边的 1，你可以先计算 1 的总数，然后减去不右边的 1 的数量。
评论
0赞
snowcoffeebean
10/22/2023
非常感谢！！我试过了，它有效。:D
0赞
Cary Swoveland
10/22/2023
您能举一个例子来说明所涉及的步骤吗？例如，对于字符串 .'1011010101'
0赞
snowcoffeebean
10/22/2023
@CarySwoveland 这将需要 4 次更换。将所有 0 替换为 1。
0赞
Cary Swoveland
10/23/2023
你总是以全零或全一结束吗？如果字符串是 .仅仅用一个 1 替换最后一个 0 就足够了吗？我想知道获得示例解决方案所需的步骤，以便理解您提出的算法。'0001101'
0赞
S H
10/24/2023
很乐意帮助@snowcoffeebean，如果这对您有帮助，请考虑将答案标记为已接受。
0赞
Cary Swoveland
10/22/2023
#2
我们得到一个长度的字符串，每个字符是 或 。如果所有字符都或所有字符都完蛋，我们就完成了。因此，我假设它至少包含一个和一个.strn > 0'0''1''0''1'str'0''1'
设置。count = 0
该算法分为两个步骤。
第 1 步
确定第一个的索引和最后一个的索引i'1'j'0'
如果我们完成了（因为所有零都先于所有一），那么我们就会返回;否则转到步骤 2。j <= icount
步骤 2
在索引和 ;那是ij
str[i] = '0'
str[j] = '1'
并递增 。count2
此时等于 ，并等于 。str[k]'0'0 <= k <= istr[k]'1'j <= k <= n-1
转到步骤 1。
观察
在第一次之后的每次迭代中：
确定第一个的索引需要从索引开始的线性搜索，其中是在上一次迭代中找到的第一个索引;和
'1'i+1i'1'确定最后一个的索引需要从索引开始的线性搜索，其中是在上一次迭代中找到的最后一个索引。
'0'j-1j'0'
请注意，在步骤 1 中，可以确定字符串是包含所有 s 还是在第一次迭代中包含所有 s。'0''1'
因此，该算法的时间复杂度为 O（）。n
示例 1
0123456789
str = '0101001010'
count = 0
第一次迭代
i = 1 # first '1'
j = 9 # last '0'
str[1] = '0'
str[9] = '1'
count = count + 2 #=> 2
0123456789
str #=> '0001001011'
第二次迭代
i = 3 # first '1'
j = 7 # last '0'
str[3] = '0'
str[7] = '1'
count = count + 2 #=> 4
0123456789
str #=> "0000001111"
第三次迭代
i = 6 # first '1'
j = 5 # last '0'
由于我们完成了并返回（）。j <= i4count
示例 2
0123456789
str = '1011010101'
count = 0
第一次迭代
i = 0 # first '1'
j = 8 # last '0'
str[0] = '0'
str[8] = '1'
count = count + 2 #=> 2
0123456789
str #=> '0011010111'
第二次迭代
i = 2 # first '1'
j = 6 # last '0'
str[2] = '0'
str[6] = '1'
count = count + 2 #=> 4
0123456789
str #=> '0001011111'
第三次迭代
i = 3 # first '1'
j = 4 # last '0'
str[3] = 0
str[4] = 1
count = count + 2 #=> 6
0123456789
str #=> '0000111111'
第四次迭代
i = 4 # first '1'
j = 3 # last '0'
由于我们完成了并返回（）。j <= i6count
评论
"0011110" --> 1'0''1''0''1'