Python:给定2个二进制字符串s和t，打印最小数量的相邻交换以将s转换为t

Question

例如，如果s = "1000000111"和t = "0111000001"，则输出应为11。下面是我的解决方案，但它给出了一个超过时间限制的错误，所以我正在寻找一个更快的方法。字符串的长度小于10^6。

T = int(input())
for _ in range(0,T):
n = int(input())
s = input()
source = []
for letter in s:
source.append(letter)
#source[0],source[1] = source[1],source[0]
#print(source)
t = input()
target = []
for letter in t:
target.append(letter)
if source.count("1") != target.count("1") or source.count("0") != target.count("0"):
print(-1)
continue
else:
ans = 0
for i in range(0,n):
if source[i] != target[i]:
#print("".join(source),"".join(target))
if source[i] == "0":
j = i
while source[j] != "1":
j += 1
ans += j-i
source[i],source[j] = source[j],source[i]
else:
#print(source)
j = i
while source[j] != "0":
#print(j,ans)
j+=1
ans += j-i
source[i],source[j] = source[j],source[i]
print(ans)

Answer 1

下面是代码。这个想法是计算"1"的位置，然后计算这对之间的差。时间复杂性O(n(，空间复杂性O(n(，但可以通过仔细的索引来完成O(1(。

def foo(str1, str2):
if len(str1) != len(str2):
return -1
n = len(str1)

arr1 = [i for i in range(n) if str1[i] == '1']
arr2 = [i for i in range(n) if str2[i] == '1']

if len(arr1) != len(arr2):
return -1

res = 0
for i in range(len(arr1)):
res += abs(arr1[i] - arr2[i])
return res