Кстати, до меня наконец-то дошло, что продерура процедуре рознь. Если процедура не модифицирует входную коллекцию, а изменяет только выходную, то её всегда можно “обернуть” функцией. В итоге процедура делает своё дело, а за пределами “обёртки” не видна. Следовательно, собственно “обёртка” побочных эффектов не имеет.
Это типичная задача на использование пары указателей/итераторов:
В Java не получится использовать один итератор для чтения, а второй для записи. В тексте статьи рассказывается об этом.
Зачем здесь рекурсия, непонятно, разве чтобы посильнее запутать.
Наверное, под рекурсией имелось ввиду, что выходную коллекцию нужно обрабатывать повторно до тех пор, пока одинаковых подряд идущих элементов вообще не останется.
О повторной обработке получившейся коллекции я не подумал. Я решил, что рекурсия требуется лишь для замены цикла, а не глобально.
Что касается подряд идущих элементов… Мне кажется наиболее простым обход коллекции слева направо с “загребанием” как можно большего количества одинаковых (вроде бы это называется жадный алгоритм). Так что ["dog", "cat", "cat", "dog"] превратится в ["dog", null, "dog"], а ["dog", "dog", null, "cat"] станет [null, "cat"].
Но если обработку ["dog", "cat", "cat", "dog"] начать с середины и объединить одинаковые значения слева и справа, то получится [null"]. Тут всё упирается в итераторы Java: они не дают разгуляться.
Мне тоже не нравится. Даже с циклом как-то неэлегантно получилось. Не говоря уже про рекурсию. Я всё думал, думал и думал, как бы улучшить…
Пришёл к выводу, что ни сократить код, ни разбить его на функции поменьше не получается. Все эти итераторы, значения прошлые и текущие, счётчик настолько связаны, что если их разнести по маленьким функциям, кода получится даже больше. И не очень понятного.
Наверное, всё же O(n). Ведь там всего один цикл, а не два вложенных. Счётчик инкрементируется заодно с итерацией по входной коллекции. В рекурсии то же самое, только вместо цикла “хвост” коллекции передаётся в точно такую же функцию.
Кстати, входная коллекция не меняется и при передаче на очередной уровень вложенности не копируется. А вот с результатом наоборот: каждый рекурсивный вызов создаёт новый список, все элементы которого добавляются к списку, созданному предыдущим вызовом. Так что память разбазаривается. А что тут такого? Функциональный подход.
Потребление памяти можно было бы и сократить. Но это совсем другая история. Зарядка должна оставаться зарядкой, а не тренировкой на изнеможение :)
получается что половина статьи посвящена неправильному условию? :)
Так и есть, к сожалению. Собственно решение отошло на второй план.
в качестве статьи про “алгоритмы” выглядит несколько преждевременно, не серчайте пожалуйста :)
Согласен с Вами, оставил только “Java” и “Программирование”. Просто мне показалось, что эти два хаба слишком общие. Плюс мой стереотип о том, что если что-то делается на Java без сторонних библиотек и фреймворков, то это сто процентов алгоритм. Интересно, у других тоже так?
P.S. самое безобразное что “подряд идущие” элементы - это понятие примениемое далеко не к любой коллекции
Над этим я думал и всё бился, как бы это толково расписать, не раздувая, скажем так, теоретическую часть. Но не осилил. Только упомянул, что для множества вообще решать нечего, так как там изначально не может быть двух одинаковых элементов ни рядом, и порознь.
Мне кажется, для состоятельных людей ничего не поменялось с середины прошлого века, когда телефон перестал быть диковинкой. Рядом есть секретарь, который может не то что организовать разговор, но и встречу. Если нет секретаря, то рядом водитель. Если нет водителя, то охранник. У биллов гейтсов просто нет нужды в гаджетах, за исключением простого сотового телефона с парочкой номеров.
И ещё я думаю, что “цифровой детокс” - это такой же трюк, как и бытие онлайн. Только раньше впаривали айфоны, а теперь настала очередь тех же оффлайн-клубов, активного отдыха и одноразовых mp3-плееров по цене баяна. Очередная крайность. Гораздо более перспективным выглядит движение downgrade (хотя скорее это кружок по интересам).
Допилил, теперь
nullобрабатывается наравне с другими значениями.Всё норм. Действительно, процедура лучше.
Кстати, до меня наконец-то дошло, что продерура процедуре рознь. Если процедура не модифицирует входную коллекцию, а изменяет только выходную, то её всегда можно “обернуть” функцией. В итоге процедура делает своё дело, а за пределами “обёртки” не видна. Следовательно, собственно “обёртка” побочных эффектов не имеет.
Спасибо!
Я так упёрся в отсутствие побочных эффектов, что не заметил O(n^2).
В Java не получится использовать один итератор для чтения, а второй для записи. В тексте статьи рассказывается об этом.
Наверное, под рекурсией имелось ввиду, что выходную коллекцию нужно обрабатывать повторно до тех пор, пока одинаковых подряд идущих элементов вообще не останется.
О повторной обработке получившейся коллекции я не подумал. Я решил, что рекурсия требуется лишь для замены цикла, а не глобально.
Что касается подряд идущих элементов… Мне кажется наиболее простым обход коллекции слева направо с “загребанием” как можно большего количества одинаковых (вроде бы это называется жадный алгоритм). Так что
["dog", "cat", "cat", "dog"]превратится в["dog", null, "dog"], а["dog", "dog", null, "cat"]станет[null, "cat"].Но если обработку
["dog", "cat", "cat", "dog"]начать с середины и объединить одинаковые значения слева и справа, то получится[null"]. Тут всё упирается в итераторы Java: они не дают разгуляться.Мне тоже не нравится. Даже с циклом как-то неэлегантно получилось. Не говоря уже про рекурсию. Я всё думал, думал и думал, как бы улучшить…
Пришёл к выводу, что ни сократить код, ни разбить его на функции поменьше не получается. Все эти итераторы, значения прошлые и текущие, счётчик настолько связаны, что если их разнести по маленьким функциям, кода получится даже больше. И не очень понятного.
Наверное, всё же O(n). Ведь там всего один цикл, а не два вложенных. Счётчик инкрементируется заодно с итерацией по входной коллекции. В рекурсии то же самое, только вместо цикла “хвост” коллекции передаётся в точно такую же функцию.
Кстати, входная коллекция не меняется и при передаче на очередной уровень вложенности не копируется. А вот с результатом наоборот: каждый рекурсивный вызов создаёт новый список, все элементы которого добавляются к списку, созданному предыдущим вызовом. Так что память разбазаривается. А что тут такого? Функциональный подход.
Потребление памяти можно было бы и сократить. Но это совсем другая история. Зарядка должна оставаться зарядкой, а не тренировкой на изнеможение :)
Так и есть, к сожалению. Собственно решение отошло на второй план.
Согласен с Вами, оставил только “Java” и “Программирование”. Просто мне показалось, что эти два хаба слишком общие. Плюс мой стереотип о том, что если что-то делается на Java без сторонних библиотек и фреймворков, то это сто процентов алгоритм. Интересно, у других тоже так?
Над этим я думал и всё бился, как бы это толково расписать, не раздувая, скажем так, теоретическую часть. Но не осилил. Только упомянул, что для множества вообще решать нечего, так как там изначально не может быть двух одинаковых элементов ни рядом, и порознь.
Мне кажется, для состоятельных людей ничего не поменялось с середины прошлого века, когда телефон перестал быть диковинкой. Рядом есть секретарь, который может не то что организовать разговор, но и встречу. Если нет секретаря, то рядом водитель. Если нет водителя, то охранник. У биллов гейтсов просто нет нужды в гаджетах, за исключением простого сотового телефона с парочкой номеров.
И ещё я думаю, что “цифровой детокс” - это такой же трюк, как и бытие онлайн. Только раньше впаривали айфоны, а теперь настала очередь тех же оффлайн-клубов, активного отдыха и одноразовых mp3-плееров по цене баяна. Очередная крайность. Гораздо более перспективным выглядит движение downgrade (хотя скорее это кружок по интересам).