tgoop.com/leetcode_bytes_you/4
Last Update:
Separate Black and White Balls
Два типа "шаров". Всех 2ого типа нужно переместить в правую часть делая перестановки с ближайшим.
Кажется, что такую задачу мне давали в Т-банке.
Ниткод рассказал бодро и понятно. Но ничего не понятно.
Пока понятно, что можно и не свапать.
Ещё пару солюшенов. И ок понятно.
——————
Дошли до 1ой единицы. Потенциальный инкремент счётчика перестановок.
000000 1 0 1
|
potentional_swap
Если бы было так:
000000 1
Надо выходить. Или же неикрементнуть результат.
Если бы было так:
000000 1 1
Надо неикрементнуть результат.
У нас так:
000000 1 0
|
Поскольку это ноль, надо отобразить это в результате.
res += cnt
Ок, значит будет:
000000 0 1 (но физически менять не обязательно!)
т.е. res = 1;
Далее. На самом деле у нас в изначальном примере в конце другая единица:
000000 0 1 1
|
Опять единица? Инкрементнули счётчик(сейчас равен 2). Но пока не добавляем ничего в результат.
Ок. Закончили. res = 1; count = 2, выходим. Но...
...если бы был еще 0:
000000 0 1 1 0
Что теперь надо?
Мы же хотим текущие единицы сдвинуть ещё:
000000 0 1 1 0 -> 000000 0 0 1 1
000000 0 1 1 0
|
Встретили ноль. Добавляем в результат текущее значение счётчика res +=2, т.е. к одному в результате прибавили 2, получилось 3.
Чуть магией попахивает. Но работает.
Благодаря этому постоянному инкременту количеству swap'ов как бы сохраняем состояние. Счётчик как память. Плюс, когда встречаемcя с 1цей пока что инкременим на всякий случай, но в результат не добавляем.
Случается этот самый случай - встретили 0. И что тогда? Все предыдущие единицы надо снова сдвигать! Т.е. тогда когда-то почему-то подвинули(встретили 0). И вот опять. Ну что ж. Такова жизнь. se la vi.
Кажется, что пока объяснял немного больше понял.
Тот момент, когда уже сколько-то решаешь, но вот очередная задача оказывается эдакой.
#Т-Банк
BY Укусанный литкодом
Share with your friend now:
tgoop.com/leetcode_bytes_you/4