С каждым случалось?)
Telegram: @DevComics
Telegram: @DevComics
Эта часть является продолжением цикла лекций про деревья. В этой части мы снова воспользуемся рекурсией чтобы инвертировать дерево. Задача довольно популярна и по сложности является довольно простой.
Допустим у нас есть дерево ниже:
Целью является инвертировать дерево. Те для каждого узла нужно поменять местами его левый и правый наследники. Логику надо также применять к наследникам наследников.
Проитерироватсья по всем узлам рекурсией те нам понадобится функция которая будет вызывать саму себя.
Нижние пустые null узлы нужно будет проигнорировать
Для всех остальных узлов нужно выполнить смену ссылок для правого и левого наследников
Думаю вам тоже задача показалось довольно простой но при этом она является одной из самых частых во время собеседований. В следующей статье мы рассмотрим более сложные случаи. Всем кому интересно - добро пожаловать в мою группу.
В прошлой части мы рассмотрели разные подходы рекурсивного обхода дерева. Давайте воспользуемся некоторыми из них для решения довольно известных задач.
Одна из самых популярных и простых задач на деревья - поиск узла находящегося на максимально удаленом расстоянии. Рассмотрим дерево ниже:
Высота данного дерева - пять
Довольно очевидно что самый длинный узел в данном дереве - M и он является пятым по счету если головной является первым.
Если сильно упрощать то нам нужно сделать 2 действия:
Обойти все узлы
Каким то образом "сохранять" состояния каждый раз когда мы обходим узлы
Но как же сохранять состояния о той глубине на которой мы побывали? Тут есть как минимум два варианта:
Использовать возвращемое значение самой рекурсивной функции и "возвращать" её на уровень выше.
Иметь какой то объект в котором мы будем сохранять состояния находясь внутри рекурсии
Рекурсивная функция должна передавать значение сама себе "наверх"
Определить какое именно значение должно перебрасываться.
Логика передаваемого "наверх" значения.
Самые нижние уровни (те что указывают на null) должны возвращать 0 тк они не включены в расчет глубины данного подграфа
Нижний уровень который с листьями имеет лишь null предков должен вернуть 1 тк он является первым уровнем
Узел выше чем 1й (те не лист) должен выбирать максимальный уровень из двух его наследников и добавлять 1 тк находится на уровень выше из наибольшего из них.
После данных рассуждений у нас вырисовывается вот такая картина:
null уровни 0, листья 1 и все остальные узлы - выбирает наибольшее из наследников и добавляют 1.
Все эти рассуждения намекают что в нашей итеративной функциии будет 3 разных сценария и функция которая выбирает наибольшее из двух. Именно подобные размышления чаще всего помогают перевести абстрактные размышления в код.
Версия рабочая но слишком многословная - хотя для собеседования вполне подойдет.
Самый важная часть кода - итеративный вызов левого и правого поддерева и последующий расчет максимального значения среди них. И конечно же добавление 1 наибольшему из них чтобы учесть и текущую высоту.
Этот код можно было бы улучшить удалив случай когда мы находимся в самом низу - дело в том что если условие истино то возвращаемое значение maxDepth + 1 будет также равно 1.
Спасибо за внимание, всем кому интересна промышленная разработка приглашаю в мой канал.
В этом выпуске подкаста ведущие Думфэйс и Шахерезада обсуждают революционные заявления Илона Маска о разработке полностью автономного вождения (FSD) и искусственного общего интеллекта (AGI) уже к следующему году. Гости задаются вопросом, изменит ли это мир программирования и какая роль останется для программистов в эпоху, когда AI, такой как Девин, способен самостоятельно разрабатывать программное обеспечение, потенциально ставя под угрозу их профессию.
https://t.me/d00m4ace_blog – D00M4ACE подкаст на нейронках 🤖 про искусственный интеллект, геймдев и все остальное.
источник https://t.me/itmozg/9693
Справились? Тогда попробуйте пройти нашу новую игру на внимательность. Приз — награда в профиль на Пикабу: https://pikabu.ru/link/-oD8sjtmAi
1️⃣ Софт скиллы КАПЕЦ как важны. В большой компании нужно постоянно что-то у кого-то спрашивать (и переспрашивать), не всегда получается найти инфу самому. Плюс адаптация это дикий стресс и чем быстрее вы научитесь просить помощи и немного себя зарекомендуете, тем лучше.
2️⃣ Коллектив очень важен. Как новичок, в начале вы будете лажать и тупить, но если тимлид и команда это понимают, адаптация пройдет намного проще.
3️⃣ Не стоит учить мелкие особенности Фреймворков, важна база. Рабочий проект вообще не похож на пет, потому что промышленные проекты очень большие, их писали давно и в них используется много внутренних библиотек. Вот поэтому не стоит учить мелкие нюансы работы фреймворка - вы вряд ли встретитесь с этим в компании. Сфокусируйтесь на БАЗЕ - паттернах, протоколах, языке, базовом принципе работы фреймворка и его основных компонентов.
👨💻 Джуниор