Por ejemplo, si s = "1000000111"y t = "0111000001"la salida debería ser 11. A continuación se muestra mi solución, pero da un error de límite de tiempo excedido, así que estoy buscando un método más rápido. La longitud de la cuerda es inferior a 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)
Aquí está el código. La idea es que cuentes la ubicación de los '1' y luego calcules la diferencia entre los pares. Complejidad temporal O (n), complejidad espacial O (n), pero se puede hacer O (1) con una indexación cuidadosa.
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
Este artículo se recopila de Internet, indique la fuente cuando se vuelva a imprimir.
En caso de infracción, por favor [email protected] Eliminar
Déjame decir algunas palabras