Всем привет!
Сегодня испытал настоящее интеллектуальное удовольствие, когда решил эту задачу. Она немного на логику, немного на понимание алгоритмов, и конечно же перекладывание шариков по ящикам навивает воспоминания о задачах из детства.
В задаче было дано распределение шаров по ящикам (задано строкой состоящей из нулей и единиц). То есть изначально, в каждом ящике не более одного шара. Шары можно перекладывать только в соседние ящики, причем не важно сколько их там уже (то есть можно больше одного).
Нужно посчитать, сколько шагов нужно сделать, чтобы переместить все шары в один ящик. Причем для каждого ящика. Соответствующий результат вывести в форме списка.
Поехали…
Для начала я решил задачу грубой силой. Из условия следует, что итоговое количество шагов складывается из шагов, которые нужно сделать каждому шарику, чтобы попасть в заданный ящик. При этом, шарики никак не взаимодействуют друг с другом. То есть нужно просто посчитать, разницу между номером ящика с шариком и заданным ящиком, и сложить все эти разницы. И так для каждого ящика.
Соответственно получается два вложенных цикла. В верхнем цикле ищем все ящики, в которых есть шарик. Если шарик найден, считаем сколько шагов нужно, чтобы переместить его в остальные ящики, это значение добавляем в нужные места в списке-ответе.
Понятно, что это решение не эффективно. Так как оно построено на двух вложенных циклах. И временная сложность пропорциональна квадрату рассматриваемых элементов O(n^2).
Но решение работает. Я даже засунул туда пару фишечек, которые выучил недавно: моржёвый оператор ( := ) и функцию enumerate()
Если понятна проблема, нужно искать ее решение. Но как избавиться от вложенного цикла?
Тут следует внимательно посмотреть на данные примеры. Так при распределении шаров "001011" ответом будет [11,8,5,4,3,4]. То есть, чтобы поместить все шары в самый левый ящик, нужно сделать 11 «Шагов». Для следующего ящика 8 «Шагов», или на 3 меньше, чем для самого левого. А число 3 совпадает с количеством шаров справа от этого ящика. Оно и логично, нам не нужно перекладывать эти шары из одного ящика в другой, соответственно и значение меньше на количество шаров.
Эта логика не меняется, даже когда шары изначально находятся слева от ящика. Просто к известному значению предыдущего ящика мы прибавляем, а не отнимаем, соответствующее количество шаров.
В данном подходе я сначала посчитал количество шагов для самого левого ящика (по схеме из первого решения, заодно посчитал количество шаров справа), а затем по предложенному алгоритму из этого значения вычитал или прибавлял шары слева и справа.
В итоге получилось очень эффективное решение. Несмотря на то, что тут тоже два цикла, они не зависимы друг от друга и временная сложность составляет O(2n), что практически значит O(n).
Вот так, все на сегодня