Python: даны 2 двоичные строки s и t, выведите минимальное количество соседних свопов для преобразования s в t - PullRequest
Новая
       24

Python: даны 2 двоичные строки s и t, выведите минимальное количество соседних свопов для преобразования s в t

1 голос
/ 11 июля 2020

Например, если 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)

1 Ответ

3 голосов
/ 11 июля 2020

Вот код. Идея состоит в том, что вы подсчитываете расположение единиц, а затем вычисляете разницу между парами. Временная сложность 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
...