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)，space 复杂度 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

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

Python: Given 2 binary strings s and t, print minimum number of adjacent swaps to convert s to t

python-3.x

string

binary-string