Дана двоичная строка со всеми 0, чтобы скрыть ее в целевой строке

Question

Дана двоичная строка, которая представляет целевое состояние.Минимальное количество сальто, необходимое для преобразования двоичной строки одинакового размера (со всеми 0) в целевое состояние.Отражение также приводит к переворачиванию всех правильных битов.

например,

Ввод: 00101 (представляет цель)

Выход: 3

Объяснение:

00000 -> 00111 -> 00100 -> 00101

Answer 1

Два наблюдения:

1. Перевороты являются коммутативными.Вы получите один и тот же результат, независимо от того, в каком порядке вы их выполняете.

2. В какой-то момент вам нужно щелкнуть самый значимый бит, который не соответствует

Это дает нам удобный жадный аргумент.Мы всегда найдем оптимальное решение, щелкнув самый левый бит, который нужно перевернуть.В какой-то момент мы должны перевернуть этот бит, и порядок не имеет значения, поэтому мы могли бы сделать это в первую очередь.

Реализация этого, чтобы быть O(N) может быть хитрой - если мы перевернем все наивно, мы получим переворот O(N), который дает решение O(N^2).Мы можем отметить, что при определении истинного значения текущего бита, мы заботимся только о количестве переворотов, которые уже произошли.Если это число нечетное, то значение этого бита переворачивается.В противном случае оно не изменяется.

Затем мы можем сделать последнее замечание, чтобы сделать жизнь намного проще:

Отражения отменяют друг друга.Вместо того, чтобы спрашивать, сколько флипов требуется, чтобы добраться от 0 до цели, давайте спросим, ​​сколько флипов требуется, чтобы добраться от цели до 0. Когда истинное значение бита не равно нулю, мы просто добавляем флип.

Псевдокод:

result = 0
// most to least significant
for bit in bits:
    if result%2 == 0:
        if bit != 0: result += 1
    else:
        if not bit != 0: result += 1
print(result)

И чтобы быть более кратким:

bits = [0, 0, 1, 0, 1]
result = 0
for bit in bits: result += (result%2)^bit
print(result)

Вывод:

3