一道笔试题求解，求出处


2


题意大概含义：给你一个只包含0或者1的字符串，每次只允许交换相邻的两个数，求最小的交换次数，使得0和1交替排列，如果不存在则输出-1

输入：
0110
输出：
1



提问于15天前
12015


2 个问答


2

暴力做法：
假设0的数量大于1的数量，那么1所在的位置就必须在偶数位。
记录下1所在位置的所有下标，然后从最大开始遍历，如果不是在目标位置，则移动。
以0111000为例，记录下1的下标为：2，3，4。然后从最大的下标4开始遍历，其是第3个1，我们知道，应该在6的位置，因此需要移动2位其到6；再遍历下一个，第2个1，其应该在4的位置，因此需要移动1位到4；最后遍历第1个1，位置正确，不用移动。一共需要3步。
对于1的数量大于0到数量，思考方式类似。
数量相同的，则1在偶数和奇数都思考一下。

回答于13天前
3316
谢谢大佬！我明白了 –  sep   12天前

0

口胡一下 : 首先根据数量判断-1,然后又因为需要交替出现,所以只可能是两种情况1010,0101 ,因此1的位置显然是可以固定下来的, 显然对于前面的1必然要放到前面,也就是如果00001这种情况,1必然放在01000这样子,同理对于0000101也必然要将这个1放在前面,为什么这样子是最小的嘞,因为前面没有补的你必然要用最近的一个来补所以最小。

回答于13天前
30291
@Gzm1317:  谢谢大佬解答！但我还是没明白该咋做，你的意思是先找到所有1应该在位置，然后将离这个位置最近的1移过来是嘛 –  sep   13天前
才发现问的是出处,LC上面就有https://leetcode.cn/problems/minimum-number-of-swaps-to-make-the-binary-string-alternating/,没记错CF也有 但是是好几个月的题了 –  Gzm1317   13天前
我来回答