Максимальное количество смежных битов, переворачивающих только один

Question

Эта проблема возникла при предварительном опросе онлайн-теста кодирования. Я попытался полностью изменить сценарий & любую несущественную информацию, чтобы не допустить, чтобы кто-либо принимал упомянутый тест, обнаруживая этот пост.

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

ie 101110 будет иметь 4 смежные пары, если вы перевернули второй бит.

Мне был предоставлен код, который, как представляется, решил проблему, и попросил исправить ее, заменив до трех строк. К сожалению, я не смог найти ошибку. Ее было расстраивает меня некоторое время теперь ..

Прилагаемый код (составитель и побежал на приводимый пример отлично)

int sol(int[] Arr): 
    int l = len(Arr) 
    int t = 0 
    for i 0..(l-2): 
     if A[i] = A[i+1]: 
      t += 1 
    int r = 0 
    for i 0..(l-1): 
     int c = 0 
     if i > 0: 
      if A[i-1] != A[i]: 
       c++ 
      else: 
       c-- 
     if i < (l-1): 
      if A[i+1] != A[i]: 
       c++ 
      else: 
       c-- 
     r = Max(r, c); 
return t+r 

Есть идеи?

Answer 1

Чтобы найти ошибку или и использовать я могу попытаться понять код первый:

первого цикл подсчет числа пар в последовательности («00» или «11») в т

for i 0..(l-2): 
    if A[i] = A[i+1]: 
     t += 1 

затем второй взгляд петля для специфических последовательностей:

1. «101» или «010», то с = 2
2. «01» или «10», то с = 1 (только при взгляде на первый или последний б она)
3. другие последовательности с = 0 или -1 или -2

и сохранить высокое значение между С и г в г так что любое значение С меньше 0 не имеет значения.

int r = 0 
for i 0..(l-1): 
    int c = 0 
    if i > 0: 
     if A[i-1] != A[i]: 
      c++ 
     else: 
      c-- 
    if i < (l-1): 
     if A[i+1] != A[i]: 
      c++ 
     else: 
      c-- 
    r = Max(r, c); 

Чтобы найти ошибку, вы можете просто эксплуатировать первый цикл разбора длинную «11001100110011001100 ...» последовательности, вы найдете значение половины длины последовательности, деленную на 2, когда реальное значение должно быть равно 2.

Это может быть только половина ответа, потому что я не мог найти исправление, изменяющее только 3 строки, но, возможно, по мере изменения кода вы также меняете количество строк, которые принимают некоторые инструкции, или порядок нескольких строк.

Я чувствую, что исправление включает объединение двух циклов и использование t в max с несколькими другими изменениями, но это изменило бы более 3 строк.

Answer 2

Это потому, что количество примыкающих может спуститься. Например: (0, 0, 0, 0, 0, 0). Это 5 смещений. Если вы переворачиваете любой из них, количество падает до 4, но представленный вами алгоритм позволяет увеличить количество, потому что стартовое значение c равно нулю, а вы - max().