Холиварофорум

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

Задача на вращение бинарного дерева!
Лёгкий уровень, поиск в глубину, бинарные деревья, примерно 18 минут.

▼Дано бинарное дерево, перевернуть его (поменять местами левые и правые ноды и листья) и вернуть ссылку на корень⬍

Если нет ноды, вернуть None.
Если у ноды есть левый или правый потомок, поменять их местами (если нет потомка, считается, что это нода None).
Под конец вернуть ноду.

# Definition for a binary tree node.
# class TreeNode:
#     def init(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right


def rotate_binary_tree(node):
    if not node:
        return None
    if node.left or node.right:
        node.left, node.right = node.right, node.left
        rotate_binary_tree(node.left)
        rotate_binary_tree(node.right)
    return node 

Помимо ЛитКода продолжаю заниматься Реактом. Разобрал state variables, state setter functions и useState hook. Научился работать с callback функциями, lifting state up из одного компонента в другой (хз как лаконично и грамотно перевести). Научился рекурсивно создавать инстанс компонента, когда надо было отобразить вложенную структуру. Прочитал про классы компонентов (пора, наверное, попробовать перейти к таким от компонентов-функций в моём проекте).

Работодатель даёт доступ к платформе для ментального здоровья, я решил как-то понизить свою тревожность, потому что я тот ещё тревожный сырочек, и мысли "а что, если" порой мешают мне. Ну и просто ощущение смутной тревоги, иногда беспричинно, иногда из-за каких-то банальных вещей.
Зарегался на платформе, выбрал цель, прошёл опрос, приложение по итогам дало оценку общему состоянию. 47 из 100. Ок, это было в начале февраля, к марту улучшилось до 55  . Выбрал специалиста из тех, что посоветовало приложение по результатам опроса, очень приятная женщина. Первую сессию говорили о моём состоянии в общем, целях, что меня тревожит.
Первое, о чём она спросила и что посоветовала наладить в первую очередь - сон, еда и упражнения. К первой сессии у меня с ними всё было в порядке, а сейчас вот нарушил свой график, часто ложусь спать после 12 и сплю меньше 8 часов, мог бы чаще выходить на прогулку. Далее она посоветовала вести журнал тревожности. И когда приходят тревожные мысли, то записывать их - о чём, почему и давать оценку: это реальный повод тревожиться или нет. Вообще мне нравится, посмотрим, что из этого выйдет.

анон-левел-апер

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

Когда-то я писал, что побывал на двух побережьях и выложил фото с одного - дикий лес, пора бы выложить и со второго - старый город!
Итак, Бостон! 

Подгадал приехать туда в октябре, в золотую осень, и не разочаровался. Больше, теперь я влюблён!
Он не очень большой, но живой, яркий и со своим очарованием.

Что мне очень нравится в нём, пожалуй, главная вещь - это его история и то, как плотно она переплетается с современностью. Конечно, город развивается всё время, и из моего любимого 18 века в самом Бостоне осталось не так чтобы много зданий, но почему-то этот дух ощущается очень живо, совсем рядом. Не покидает ощущение, что вот-вот увидишь в толпе треуголку, старинный чепчик или красный мундир 

▼Слайды⬍

Old State House, здание, с балкона которого зачитали Декларацию о независимости. Льва и единорога сбросили в своё время, но в конце 20 века водрузили обратно, чтобы здание выглядело более исторично.

Памятник Полу Риверу, одному из героев Американской революции. Он знаменит тем, что ночью накануне наступления британских войск предупредил повстанцев ("British are coming!"), это произошло незадолго перед сражениями у Лексингтона и Конкорда, первыми в ходе революции.
Кстати, после Войны за независимость он основал медный завод, который работает и по сей день.

Музей-типография, там реконструкторы покажут и объяснят, как работает печатный станок 18 века и как патриоты на нём печатали памфлеты и листовки.

Сказать ещё можно очень много всего, например, про метро с милыми олдовыми трамвайчиками на одной из линий, кажется, самой старой. Про музей искусств, где выставлены предметы быта и части домов самых первых поселенцев (какими же могучими были деревья, из которых строили!), где за многими портретами скрываются увлекательнейшие биографии... Кстати, теперь у меня есть ещё один любимый художник - Джон Синглтон Копли, и его именем названа одна из станций метро. Интересно, что он был лоялистом и после революции вернулся в Лондон.

▼Конечно же, старинные кладбища⬍

Кладбища с захоронениями 17-18 веков, небольшие, но атмосферные, можно найти прямо в центре города. Очень любопытно рассматривать надгробия и читать эпитафии. Кто-то просил похоронить его поглубже, чтобы эти красные мундиры своими ядрами и пулями не доставали его на том свете, у кого-то на памятнике нарисованы Отец Время и Смерть, что гасит свечу, словом, я бы мог проводить там очень много времени. 

Также съездили погулять в лес. Оказалось, что 10 дней совсем мало для Бостона, не говоря уже о многочисленных старинных городках Новой Англии и природе восточного побережья.

▼Осенний лес в Массачусетсе⬍

Помимо Бостона были и в Салеме (том самом) и месте, что заслуживает отдельного упоминания - на фрегате 18 века USS Constitution, что до сих пор продолжает ходить под парусами 

анон-левел-апер-путешественник

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

Поучаствовал в субботнем контесте на ЛитКоде, это когда за полтора часа надо решить 4 задачи на алгоритмы и структуры данных, награда не за первые места символическая, но шанс потренироваться на время в новой задаче.

К началу контеста ЛитКод прилёг, и минут 40 не мог прийти в себя, но всё же потом ожил.
Пока каждый раз у меня одно и тот же: я быстро решаю первую задачу лёгкого уровня, оставшееся время мучаю следующую и ломаюсь на очередном граничном условии. В этот раз я не мог понять, почему из массива [998, 2] можно сделать массив, отсортированный по возрастанию, если из первого элемента вычесть целое число, которое строго меньше (вычитаем 997 и получаем массив [1, 2]), а из массива [17, 2] - нельзя 

Утром ездил на фехтование. Нас было четверо, включая тренера, разбирали интересные вещи для так называемого half-swording. Это когда одной рукой держишь меч за рукоять как обычно, а второй берёшь его за лезвие и используешь сначала для защиты от удара, а потом, если противник не отступил, переходишь на рукопашную - ударить противника рукояткой в лицо, заблокировать своим мечом его меч/руки, после этого можно перейти к бросанию на землю и так далее.
Импровизировали, и я очень доволен, что уже получается в разных вариантах без размышлений применять то, чему научился, используя меч, который держу обеими руками, как рычаг, тренер меня похвалил 
На фехтование ещё ходит англичанин в годах, который знаком с многими боевыми искусствами и видами оружия и всегда рад объяснить и показать какую-то нетривиальную идею. Сегодня в поединке он хотел ударить меня в грудь клинком снизу вверх, держа его обеими руками, я заблокировал это, выставив свой клинок перпендикулярно его, но он тут же перенаправил свой меч сверху вниз, и это вышло очень натурально и быстро, мне понравилась идея, я о таком раньше и не думал, хотя казалось бы

анон-левел-апер

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

В этот раз я не мог понять, почему из массива [998, 2] можно сделать массив, отсортированный по возрастанию, если из первого элемента вычесть целое число, которое строго меньше (вычитаем 997 и получаем массив [1, 2]), а из массива [17, 2] - нельзя 

А почему нельзя?  Вычитаем 16 и получаем [1,2] по аналогии?

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

Я пока и сам не понял, почему так. Сначала моё решение свалилось на кейсе [998, 2], я добавил обработку в код, и решение свалилось на кейсе [17, 2], так и не увидел разницы. Надо будет разобрать решение и пройти дебаггером.

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

А почему нельзя?  Вычитаем 16 и получаем [1,2] по аналогии?

Похоже, я знаю, в чём проблема с массивом [17, 2].

В дискуссии кто-то задал такой же вопрос, и там ответили, что:

• вычитать из элементов массива можно только простые числа, строго меньше самого элемента массива (сейчас я понял, что упустил это, когда читал условие)

• элементы массива должны быть больше единицы

Но по второму пункту не совсем очевидно. В условии сказано, что исходный массив состоит из элементов величиной от 1 до 100. Но не сказано прямо, что элементы результирующего массива должны также удовлетворять этому ограничению 

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

А вот в случае [998, 2] ближайшее к первому элементу простое число, которое строго меньше - это 997.
998 - 997 = 1 => [1, 2].
Вот в чём разница 

Я всё ещё пока не совсем представляю, как решить эту задачу, оставлю на попозже. А заодно потренирую скилл более внимательного чтения условия.

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

Лёгкий уровень, массивы и битовая манипуляция, 30 минут.

▼Дан непустой массив чисел, все числа, кроме одного, повторяются в массиве ровно один раз. Вернуть единственное неповоторяющееся число. Решение должно занимать линейное время и постоянную память. ⬍

Пример: исходный массив [4,1,2,1,2], ответ 4.

Я смог надумать сам только решение с почти линейной памятью - записывать каждое число в хэш-таблицу, проходя по массиву. Если очередной элемент массива уже есть в хэш-таблице - его можно выбросить оттуда, потому что он повторяется, а значит, нам не нужен. После прохода по массиву вернуть оставшееся число, что встретилось ровно один раз.
Но этот вариант не подходит под ограничение постоянной памяти.

Пошёл смотреть разборы задачи.
Для решения можно использовать логический оператор XOR (исключающее ИЛИ).
Если применить XOR для ненулевого числа и нуля, вернётся число. Если применить для чисел, равных друг другу, вернётся ноль. Также XOR обладает такими свойствами, как коммутативность (a + b = b + a) b ассоциативность (a + b) + c = a + (b + c).
4 ^ 1 ^ 2 ^ 1 ^ 2 = 4 ^ 1 ^ 1 ^ 2 ^ 2 = 4 ^ (1 ^ 1) ^ (2 ^ 2) = 4 ^ 0 ^ 0 = 4 ^ 0 = 4
Таким образом, все числа массива, которые равны друг другу, должны в совокупности дать 0 после применения XOR. А 0 и число, которое не повторяется, после XOR вернёт это самое число.

def singleNumber(nums: List[int]) -> int:
    len_n = len(nums)
    for i in range(1, len_n):
        nums[0] ^= nums[i]
    return nums[0]

Линейное время: максимум один проход по массиву и постоянная память.
Я практически не применял такое для решения задач, но мне нравится идея.

Ещё интересный вариант, но тоже не попадающий под условие постоянной памяти: создать из массива сет, суммировать все его значения, умножить полученную сумму на два и вычесть оттуда сумму всех значений исходного массива, ответом будет искомое число.
2 * (sum(4, 1, 2)) - sum([4,1,2,1,2]) = 14 - 10 = 4

Недавно подался на позицию питон-разработчика, описание и требования подходят под мои скиллы и опыт.
Пишут из компании: мы хотим поговорить с вами! Насчёт вакансии Senior QA Automation engineer! Выберите время!
Я отвечал, что мол, простите, я подавался на питон-разработчика, но указал свободное время для звонка.
На письмо нет ответа.
На следующий день звонят: здравствуйте, мы по поводу позиции Senior QA Automation engineer!

Я: здравствуйте, а я подавался на питон-девелопера, я на ваше письмо ответил, что хочу на позицию питон-девелопер.
Рекрутёр: но наш хайринг-менеджер считает, что вы лучше подходите на другую позицию!
Я: я бы хотел свичнуться в разработчики (Так-то у меня и в резюме сказано, что хочу свичнуться).
Рекрутёр: жаль, очень жаль, мы свяжемся с вами, если будет открыта такая позиция! Хорошего дня!

Как же бесит, а.

анон-левел-апер

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

Снова начались классы по классическому фехтованию на шпаге И я понял, что то ли отвык, пока занимался только двуручным мечом, то ли всё ещё чересчур медленный   

Но на классе исторического фехтования, где я оказался единственным пришедшим студентом в тот вечер - почему и была шпага, а не двуручник -  дела всё же пошли получше, и я уверился, что не безнадёжен. А может, раскачался наконец. 

На прошлый же класс по историчке пришёл новый чувак. Вообще он ходил раньше, давно, до меня, а теперь пришёл после перерыва. А перерыв  - потому что у него было сотрясение мозга. Полученное на фехтовании. И у милого пожилого англичанина недавний перерыв тоже был из-за сотрясения мозга. Тоже полученного на фехтовании. Они не сказали, как именно это случилось, но подозреваю, что на турнире.

Тренер философски сказал, что все рано или поздно что-то себе ломают, и научил, что когда противник атакует мечом твою голову, не надо отворачиваться, а надо наоборот, чтобы меч попал по передней части маски с металлом, а не по затылку. Потому что даже защита затылка на HEMA-шлеме может быть недостаточна для защиты от сотрясения при сильном ударе

Тренировка прошла очень хорошо, я научился новому, и меня во время дуэльных поединков не валяли по земле, как на прошлой неделе. Я смог выкрутить руку одному из соперников, после того, как защитился от его атаки, и приставить меч к его горлу, а там и время поединка вышло.

анон-левел-апер

Отредактировано (2023-04-02 09:15:41)

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

Лёгкий уровень, связанные списки, хэш-таблицы и техника двух указателей, 40 минут.

▼Даны головные ноды двух связанных списков (однонаправленных), вернуть ноду, в которой оба листа пересекаются, если не пересекаются, то вернуть None⬍

Пример 1:
list_1 = [4,1,8,4,5], list_2 = [5,6,1,8,4,5], пересекаются в ноде со значением '8'.
   4 - 1
            \
             8 - 4 -5
            /
5 - 6 - 1

Пример 2:
list_1 = [2,6,4], list_2 = [1,5], не пересекаются.
2 - 6 - 4
1 - 5
На самом деле, значение ноды не так важно, как сам объект ноды.

Первая идея: использовать хэш-таблицу для хранения нод, которые уже посетили, пройтись по обоим листам, проверяя, нет ли нынешней ноды в хэш-таблице, если есть, то вернуть её. Иначе вернуть None.
Линейное время (m + n, где m и n - длина списков, если быть точнее), линейная память.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        seen = set()
        while headA:
            seen.add(headA)
            headA = headA.next
        while headB:
            if headB in seen:
                return headB
            headB = headB.next

        return None

В задаче потом был вопрос, можно ли решить за постоянную память, не создавая дополнительной структуры.
Вторая идея: создать две переменных-указателя, стартовать с начала каждого листа.
Пока указатели не равны друг другу: если один из указателей достиг последней ноды своего листа, приравнять его к голове другого листа и продолжить обход. Оба указателя пройдутся по обоим листам и рано или поздно встретятся в точке пересечения, если такая есть. Если нет, оба станут None (делать каждый шаг a = a.next). Возвращаем один из двух.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        a, b = headA, headB
        while a!= b:
            a = a.next if a else headB
            b = b.next if b else headA
        return a

анон-левел-апер

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

То ли я разучился управлять временем, то ли надо делать это лучше. Некоторые дела стали пожирать всё время, которое не занято чем-то необходимым.

Наверное, это потому, что я делаю до победного конца, а потом ещё читаю/пробую что-то похожее, потому что интересно или чтобы ещё лучше разобраться. Порой спонтанность вовсе не помогает.

Попробую вернуться к расписанию дел и не вылезать за временные рамки для каждого дела, иначе это будет только ЛитКод и попытки просто отдохнуть от него вместо ЛитКода, дизайна систем и Линукса (и перерывов на отдых). А, ну и вместо чтения книг и других хобби.

И вместе с принятием решения о лучшей самоорганизации я записался на кружок по фото класс 
Всего три занятия, впрочем.

анон-левел-апер

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

Сегодня решил отдохнуть от литкода, к тому же там задача на битовые манипуляции, с которыми я не очень знаком так-то.
Зато разобрал задачу по системному дизайну (дизайн чата, хех) и наконец понял, как в реакте делать поле ввода и кнопку одной строкой (бутстрап). Правда, теперь у меня поле ввода скукожилось вполовину, так что буду разбираться, как сделать его снова нормальной ширины.

Переставил швейный манекен из одной комнаты в другую, надел на него полуготовое платье. Теперь то и дело мне внезапно мерещится, что кто-то стоит рядом! Смотрит! Ну да, это стоит манекен 

В прошлый раз такие нескучные ощущения были, когда я надел на манекен длинный и широкий чёрный плащ с капюшоном и оставил в комнате с выключенным светом, в которую тем не менее заходил то и дело. Капюшон при этом ещё и склонился вниз из-за тяжести ткани.
Я было привык уже к этой угрюмой фигуре, а теперь свежие ощущения 

анон-левел-апер

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

Лёгкий уровень, битовые манипуляции, 1 час 11 минут, пришлось неслабо поскрипеть мозгами.

▼Дано 32-битное беззнаковое целое число, переставить биты в нём в обратном порядке⬍

Пример:

Число 00000010100101000001111010011100, ответ 964176192 (00111001011110000010100101000000)
Двоичное число 00000010100101000001111010011100 представляет десятичное число 43261596, таким образом, ответом будет 964176192, что в двоичном представлении будет 00111001011110000010100101000000.
Но вообще ответ принимается, если так и вернуть его в двоичной форме.

Первая идея - буквально перевернуть число и вернуть результат. Проще всего это сделать, превратив число в строку, пройдя её с конца и превратив полученную строку обратно в число. Просто, быстро, но задача всё же на битовые манипуляции, а решение занимает линейные время и память. Зато знаю, как форматить строку в 32-битный int и указывать систему счисления при переводе строки в целое число!

class Solution:
    def reverseBits(self, n: int) -> int:
        s = f"{n:032b}"
        s = s[::-1]
        return int(s, 2)

Я довольно быстро понял, что не знаю, как можно решить эту задачу другим способом, так что полез вспоминать про битовые манипуляции. Это было сложно, мозг скрипел, но я справился. Потом я полез смотреть объяснения других литкодеров и пробовать их понять. Это было сложнее. Я долгое время не мог разобраться, зачем тут нужны эти ваши битовые сдвиги. Спасибо одному очень классному человеку, он объяснил на примере, и после часа ломания головы я наконец понял идею. Если интересно, вот его объяснение с разбором примера https://leetcode.com/problems/reverse-b … planation/  :heart

Идея проста: создать переменную для результата, в цикле 0-31(потому что 32-битное число) сдвигать её биты влево и записывать в неё с конца последнюю цифру исходного числа.
Последняя цифра исходного числа получается результатом применения к нему логического И.
После этого исходное число сдвигается вправо на 1 бит (1 цифру), потому что нам нужна следующая цифра этого числа.
Результат сдвигается влево, чтобы полученные из исходного числа цифры "ползли" вперёд.
Грубо говоря, берём цифры с конца исходного числа и добавляем их в переменную с конца, каждую итерацию подвигая их к началу.

class Solution:
    def reverseBits(self, n: int) -> int:
        if n == 0:
            return 0
        result = 0
        for i in range(32):
            result = result << 1
            result += n & 1
            n = n >> 1
        return result 

Это решение занимает постоянные время и память, потому что не создаёт дополнительных структур данных и каждый раз проходит по 32-битному числу.

Вообще сложилось впечатление, что к задачам на битовые манипуляции труднее найти подход с помощью интуиции, но, возможно, это из-за того, что я мало их решал. На собеседованиях они ни разу не попадались, насколько помню. Посмотрел, где такое обычно применяется, и в принципе железо, шифрование и сжатие данных далековаты от сферы моих интересов

анон-левел-апер

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

Кстати, получил внезапный привет из любимого 18 века, когда читал про битовые манипуляции.

Есть два (ок, третий - переключаемый) порядка записи байтов в памяти: с начала (слева направо, от старшего, наиболее значимого байта, к младшему) и с конца (наоборот). Они называются big-endian и little-endian соответственно.

Их названия отсылают к "Путешествиям Гулливера" англо-ирландского писателя Дж. Свифта, где описан конфликт между теми, кто разбивает яйца с острого конца (Little-Endians, Остроконечники) и теми, кто с тупого (Big-Endians, Тупоконечники).
Не могу сказать, что мне нравится эта книга, во "взрослом" переводе - так особенно, но всё же эта отсылка кажется милой.

анон-левел-апер

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

И чтобы ненадолго отвлечься от литкода и прочего левел-апа, вернусь мыслями на восточное побережье и покажу Салем (тот самый) 

▼Солнечная осень в Новой Англии⬍

Он недалеко от Бостона, несколько остановок на пригородном поезде. Мы приехали погулять в рабочий день, так что народа на улицах  было мало. 

▼Одни из самые старых сохранившихся дома, 17 век⬍

Салем украл моё сердечко практически сразу Тихие улицы со старыми домами, на многих из которых таблички с датой постройки пару-тройку веков назад  и именем тогдашнего хозяина, высокие раскидистые деревья, старинные маленькие кладбища.

▼Скрытый текст⬍

Салем ещё и порт, так что у старой пристани стоит здание таможни и дом одного из богатешйих жителей того времени, капитана, который сделал состояние на торговле.

▼Старинная таможня и красивый дом (Derby house) в георгианском стиле 1760, лавка товаров из Вест-Индии, булыжная мостовая⬍

К сожалению, лавка была закрыта, а вокруг шёл ремонт - то ли зданий, то ли улицы, то ли всего вместе

В музей процесса над ведьмами не пошли, гугл сказал, что там то ли кукольное представление, то ли записанный фильм, и это не особо интересно. Зато вдоволь погуляли и полюбовались светлой стороной города.

▼Солнечные осеннние улицы и милые дома, ещё больше красного кирпича⬍

Прогуливаясь по этому местечку у бухты, поймала на себя на мысли, что вспоминаю лавкрафтовские рассказы, действие некоторых как раз происходит в этих местах. Старые дома у самой воды, молча хранящие тайны  

▼Скрытый текст⬍

В несколько интересных мест в тот раз уже не было времени дойти, но всё равно я осталась в восторге
И в тот же день мы посетили ещё одно интересное и чудесное место - старейший корабль на плаву: парусный фрегат "Конституция", но о нём в следующий раз.

анон-левел-апер-путешественник

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

Съездил на дополнительное занятие по фехтованию, рубили татами-маты из бамбука острыми мечами.
Сначала было трудно, потом понял, на каком расстоянии стоять, как именно рубить (делали по диагонали) и где должна быть воображаемая цель (слегка за физической целью, свёрнутым в рулон вертикально закреплённым на стенде матом).

Конечно же, одно дело практиковаться с тренировочными мечами, где главное - тренировать защиты, нападения, тайминг и шаги, и совсем другое - целенаправленно рубить что-то острым мечом насквозь, и я очень рад, что попробовал и теперь знаю, как это. Тренер сказал, что по плотности и толщине эти маты примерно как рука (не считая кости).

С двуручным мечом было тяжеловато, один раз клинок застрял весьма глубоко (почти разрубил!) Полностью одним движением срубить часть мата у нас всех получалось меньше, чем в половине случаев, хех.

А ещё я впервые попробовал катану, и это было офигенно! 
Ей рубить оказалось чуть полегче, нежели двуручным мечом, да и вес, конечно, другой.

анон-левел-апер-фехтовальщик

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

Лёгкий уровень, строки, два указателя, 40 минут на два способа + вариации во втором способе

▼Дана строка, определить, является ли она палиндромом (читается одинаково как слева направо, так и справа налево)⬍

Подразумевается, что учитывать надо только цифры и буквы в нижнем регистре, остальные символы можно игнорировать. Пустая строка - палиндром.

Пример 1: строка "A man, a plan, a canal: Panama" палиндром, потому что её цифробуквенные символы в нижнем регистре читаются одинаково с обеих сторон "amanaplanacanalpanama".
Пример 2: строка "race a car" не палиндром, потому что не читается одинаково с обеих сторон - "raceacar".

Первый подход: создать список, пройти в цикле по строке один раз и каждый символ, который цифра или буква, перевести в нижний регистр и добавить в список. После цикла проверить, равно ли первая половина списка перевёрнутой второй - учитывать ситуации, когда символов чётное и нечётное количество (или равен ли перевёрнутый список сам себе).

Список используем потому, что он - изменяемая структура данных и добавление в него элементов в цикле займёт линейное время, а не квадратичное (как в случае с созданием в цикле новой строки, строки - неизменяемая структура, поэтому каждый раз создавалась бы новая строка).

class Solution:
    def isPalindrome(self, s: str) -> bool:
        help_arr = []
        for i in s:
            if i.isalnum():
                help_arr.append(i.lower())
        if help_arr == help_arr[::-1]:
            return True
        return False

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

Второй подход: пока я разминался первым подходом, у меня в голове вдруг кликнуло: да тут же можно использовать технику двух указателей и не создавать дополнительный список! Сказано - сделано.

Создаём два указателя p1 и p2, помещаем их на начало и конец строки, движем в цикле навстречу друг другу до тех пор, пока p1 <= p2.
На каждом шаге проверяем, что каждый из указателей цифра или буква, если нет, то двигаем указатель дальше. Если оба цифра или буква, сравниваем их в нижнем регистре. Если они не равны, возвращаем False. Снаружи цикла возвращаем True.

Сначала сделал немного стрёмненько выглядящее решение с вложенными if

class Solution:
    def isPalindrome(self, s: str) -> bool:
        len_s = len(s)
        p1, p2 = 0, len_s - 1
        while p1 <= p2:
            if s[p1].lower().isalnum():
                if s[p2].lower().isalnum():
                    if s[p1].lower() != s[p2].lower():
                        return False
                    else:
                        p1 += 1
                        p2 -= 1
                else:
                    p2 -= 1
            else:
                p1 += 1
        return True

Но потом переписал на нечто более пристойно выглядящее

class Solution:
    def isPalindrome(self, s: str) -> bool:
        len_s = len(s)
        p1, p2 = 0, len_s - 1
        while p1 <= p2:
            while p1 < p2 and not s[p1].isalnum():
                p1 += 1
            while p1 < p2 and not s[p2].isalnum():
                p2 -= 1
            if s[p1].lower() != s[p2].lower():
                return False
            p1 += 1
            p2 -= 1
        return True

Я задумался о производительности. На первый взгляд, линейная: один раз проходимся по строке.
Но что насчёт функции isalnum()? Ок, lower() по идее имеет постоянное время. Гугл выдал, что isalnum() имеет квадартичную производительность для строки в общем случае, но если строка состоит из одного символа, можно предполагать, что время тоже постоянное 

Решил попробовать вместо isalnum() использовать хэш-таблицу, там-то уж точно постоянное время, кек. Создал сет с буквами в нижнем и регистре и цифрами, все представлены как строки. И что же?

{'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'}

И оказалось, что моё решение с сетом раз за разом работает медленнее, чем с isalnum(). Как я понимаю, isalnum() имеет несколько другой алгоритм проверки принадлежности строки из одного символа, нежели хэш-таблица, и хоть у обоих постоянное время работы, у хэш-тиблицы это постоянное время всё же больше. Так что можно было не тратить время и строчки на создание сета.

Но как бы то ни было, это было интересно сравнивать время выполнения (в мс) с разными проверками и пытаться дойти до причины 
Итак, для второго варианта имеем всё так же линейное время, но уже постоянную память.

Вообще я рад, что уже иногда происходит что-то вроде озарения, когда смотришь на задачу и вдруг понимаешь, какое решение или вариант решения можно применить. Раньше, сразу после долгого перерыва, я мог потратить время и так и не сообразить, что же за подход. Или сообразить, но после нескольких неудачных попыток решения.

Практика делает своё дело 

анон-левел-апер

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

Лёгкий уровень, бинарный поиск, математика, 30 минут

▼Найти квадратный корень данного неотрицательного числа, не используя вспомогательные библиотеки языка⬍

Если ответ получится не целым, то вернуть ближайшее целое число, округлить в меньшую сторону.
Пример: x = 8, ответ 2. Квадратный корень из 8 будет 2.82842..., округляем вниз до ближайшего целого числа.

Обрабатываем ситуацию, где число меньше или равно 2, далее используем бинарный поиск.
Начинаем с границ low, high = 2, x // 2.
Пока левая граница меньше или равна правой: вычисляем значение посередине, среднее между значениями границ. Проверяем, если умножить это значение на самого себя, то получится ли поданный на вход x? Если да, то возвращаем это значение, иначе делаем проверку, результат больше или меньше x. Если больше, то сдвигаем правую границу влево, к значению посередине минус 1, иначе сдвигаем левую границу вправо, к значению посередине плюс 1. Добавление/вычитание единицы нужно, чтобы не зациклиться, когда подберёмся близко к ответу (я так пару раз словил Timeout Exception).
Если не вернули значение квадратного корня, точно равное поданному на вход числу x, то возвращаем снаружи цикла правую границу, потому что нам надо округлить значение вниз.

class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0:
            return 0
        if x <= 2:
            return 1
        low, high= 2, x // 2
        while low <= high:
            mid = (low + high) // 2
            if mid * mid == x:
                return mid
            if mid * mid < x:
                low = mid + 1
            if mid * mid > x:
                high = mid - 1
        return high

Время логарифмическое (бинарный поиск), память постоянная.

Лёгкий уровень, бинарные деревья, поиск в глубину, стек, 7 минут на рекурсивную версию + 18 минут на итеративную = 25 минут

▼Дан корень бинарного дерева, обойти дерево прямым порядком (preorder traversal), рекурсивно и итеративно⬍

Прямой порядок - сначала посетить корень, затем левого потомка, затем правого потомка.

Рекурсивный вариант: если есть корень, взять его значение (можно добавить в результирующий список), потом рекурсивно вызвать функцию для левого потомка, потом для правого.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def helper(self, root, node_list):
        if root:
            node_list.append(root.val)
            self.helper(root.left, node_list)
            self.helper(root.right, node_list)

    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        self.helper(root, result)
        return result

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

Итеративный вариант: создать два списка - один для результата, другой - стек для хранения вершин, в стек сразу же положить корень. Пока есть стек: извлечь последний элемент, и если элемент не None, добавить его значение в результирующий список, а потом добавить в стек сначала правый потомок, потом левый. Такой порядок из-за того, что мы нам нужен прямой обход, и из стека мы сначала извлекаем тот элемент, что был добавлен позднее, механизм LIFO - Last in, First Out. В конце вернуть результирующий список со значениями нод в прямом порядке обхода.

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result, stack = [], [root]
        while stack:
            curr = stack.pop()
            if curr:
                result.append(curr.val)
                stack.append(curr.right)
                stack.append(curr.left)
        return result

Время и память линейные.

Разбирал по системному дизайну создание web crawler, поискового робота, анализирующего веб-страницы. Автор упоминает фильтр Блума (структура данных для проверки, что данный элемент не входит в данное множество) для проверки уникальности URL и говорит, что он более эффективен в плане памяти по сравнению с хэш-таблицей, но не объясняет ничего подробнее. На собеседовании могут спросить про это, поэтому надо бы разобраться получше, чтобы не оказалось, что я использую термин, но не могу объяснить в деталях, почему стоит использовать что-то в конкретной ситуации и как это вообще работает. То же и с хэш-таблицами кстати.

анон-левел-апер

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

Итак, на прошлой неделе ЛитКод занял 125 минут (2 часа и 5 минут), решил 3 задачи, в среднем 41 минуту на задачу. Можно было бы и лучше, конечно. 

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

Не выспался, в итоге в понедельник голова еле варила, но всё же я смог вымучить решение для треугольника Паскаля, после чего что-то свалился полумёртвый.

Лёгкий уровень, массивы, динамическое программирование, 38 минут 

▼Дано число строк в треугольнике Паскаля, вернуть его первую строку (основание)⬍

В треугольник Паскаля каждое число - сумма чисел непосредственно над ним. Вершина треугольника - единица, следующая строка - две единицы, потому что над каждой из них только вершина (единица) и воображаемые нули (их не изображают обычно).
Пример: число строк 5, ответом будет массив [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

    1
   1 1
  1 2 1
1 3 3 1
1 4 6 4 1

Если рассматривать каждый элемент как сумму двух эелементов сверху (если сверху в треугольнике нет элемента в явном виде, то он ноль)
    0 1 0
    \/  \/
   0 1 1 0
    \/\/\/
  0 1 2 1 0
   \/\/\/\/
  0 1 3 3 1 0
   \/\/\/\/\/
0 1 4 6 4 1 0

Создать массив массивов для треугольника, начать с вершины [[1]]. В цикле пройтись по уровням треугольника (подмассивам), исключив первый, что уже существует, создать остальные уровни-подмассивы и заполнить их единицами. Далее в первом цикле создать вложенный цикл, в нём пройтись по элементам-единицам каждого уровня-подмассива треугольника, не включая первый и последний элементы (всегда единицы) и вычислить как сумму двух элементов верхнего уровня над данным элементом. 

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        result= [[1]]
        for i in range(1, numRows):
            result.append([1] * (i + 1))
            for j in range(1, i):
                result[i][j] = result[i - 1][j - 1] + result[i - 1][j]
        return result

Время и память квадратичные.

анон-левел-апер

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

Сегодня чувствовал себя таким же упоротым, как и вчера, но дополз до задачи.
Лёгкий уровень, бинарные деревья, рекурсивный подход (итеративный в другой день, сегодня уже не смог), 35 минут -_-

▼На вход дан корень бинарного дерева, определить, является ли оно симметричным⬍

Симметричное бинарное дерево - дерево, левая часть которого - зеркальное отображение правой части.
Пример 1: дерево симметрично
     1
     /\
  2    2
  /\   /\
3  4 4  3

Пример 2: дерево несимметрично
     1
     /\
  2    2
  /    /
3     3

Рекурсивный подход: создать функцию-помощника, как аргументы передавать две ноды. В функции-помощнике проверить, если обе ноды не нулевые и если их значения равны друг другу, то вернуть значение логического И между рекурсивным вызовом функции для правого потомка одной ноды и левого потомка второй и рекурсивным вызовом функции для левого потомка одной ноды и правого потомка другой (сравниваем левого потомка левой ноды и правого потомка правой ноды с правым потомком левой ноды и левым потомком правой ноды, чтобы понять, являются ли они симметричным отображением друг друга). Снаружи этого условия вернуть сравнение, равно ли одна поданная на вход нода другой (это для случая, если обе ноды None).
Потом в основной функции обработать случай, когда корень None и вызвать функцию-помощника для его левого и правого потомков.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def mirror_helper(self, left, right):
        if left and right and left.val == right.val:
            return self.mirror_helper(left.right, right.left) and self.mirror_helper(left.left, right.right)
        return left == right
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        return self.mirror_helper(root.left, root.right)

Время линейное - обходим каждую ноду, память линейная, зависит от глубины дерева (стек вызова функции равен количеству уровней в дереве)

анон-левел-апер

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

Сон и отдых творят чудеса, и я снова чувствую себя человеком, который может ясно мыслить 
Та же задача, что и вчера: лёгкий уровень, бинарные деревья, но итеративный подход в двух вариантах, 12 минут + 5 минут.

▼На вход дан корень бинарного дерева, определить, является ли оно симметричным⬍

Как я понял, для итеративного решения задач с бинарными деревьями обычно используют стек/очередь, чтобы хранить там ноды в нужном порядке.
Вариант 1: Итак, проверяем, что корень не None. Создаём стек и добавляем в него правого и левого потомка. В стек мы помещаем и проверяем уровни бинарного дерева, один за другим.
Создаём цикл с условием, пока стек не пуст. Проверяем, равен ли стек со значениями нод (тут ещё один массив) себе перевёрнутому (можно проверить, равна ли первая половина перевёрнутой второй половине), чтобы понять, является ли дерево зеркальным отображением себя на данном уровне.  Если нет - возвращаем False.
Если же не является, то идём дальше и создаём временный массив, чтобы записать туда потомков нод текущего уровня. Если нода текущего уровня не None, записываем во временный массив сначала левого потомка, потом правого. Так по порядку добавятся ноды следующего уровня. Далее приравниваем основной массив с нодами уровня этому временному массиву. Можно заморочиться и обойтись без временного массива, используя генератор.
И снаружи цикла возвращаем True - мы попадём туда, если переберём все ноды на каждом уровне и не окажется, что где-то они не симметричны.

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        level = [root.left, root.right]
        while level:
            l_vals = [l.val if l else None for l in level]
            if l_vals != l_vals[::-1]:
                return False
            tmp = []
            for l in level:
                if l:
                    tmp.append(l.left)
                    tmp.append(l.right)
            level = tmp
            # как вариант, генератор, чтобы не создавать временный массив:
            # level = [child for l in level if l for child in (l.left, l.right)]
        return True

Вариант 2: помещаем в стек кортежи (tuples), в каждом - левый и правый потомок очередной ноды. Начинаем с правого и левого потомка корня.
Пока стек не пуст, вытаскиваем из него кортежи (LIFO) и распаковываем ноды в две переменные. Если обе переменные None, распаковываем следующий кортеж, если он есть. Если только одна из нод None, возвращаем False - нет симметрии. Если значения обеих нод равны, записываем в стек их потомков: (left.left, right.right), (left.right, right.left) - в таком порядке мы их сравниваем, чтобы проверить на симметрию.
Снаружи цикла так же возвращаем True.

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        level = [(root.left, root.right)]
        while level:
            left, right = level.pop()
            if not left and not right:
                continue
            if not left or not right:
                return False
            if left.val != right.val:
                return False
            level.append((left.left, right.right))
            level.append((left.right, right.left))
        return True

Линейное время, память - высота дерева * (среднее количество нод на каждом уровне) - потому что используем дополнительные массивы   

анон-левел-апер

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

Лёгкий уровень, массивы, два указателя, сортировка, 1 час 20 минут (получилось не с первой попытки -_-)

▼Даны два массива, отсортированные в неубывающем порядке, соединить их в один массив (перенести все элементы в первый массив), чтобы он был также отсортирован в неубывающем порядке⬍

Даны два массива, в одном m ненулевых элементов, в другом n. Но в первом массиве помимо m элементов в конце ещё n нулей - для вставки элементов из второго массива. Надо переместить элементы в первый массив, производя сортировку на месте. Желательно сделать за линейное время (m + n).
Задача мне какое-то время не давалась, и я оставил её. Но вот недавно разобрал.
Пример 1: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3, результат = [1,2,2,3,5,6]. Т.о. длина певрого массива со всеми значениями m + n - 1.

Подход таков: начать обход массивов с конца, в случае первого массива - там, где заканчиваются ненулевые значения, то есть с m - 1, в случае второго массива - с n - 1.
Сравниваем два значения, и помещаем большее значение в конец первого массива. Индекс, куда помещаем значения, начинается с последнего элемента-нуля первого массива, в начале это m + n - 1. По мере продвижения уменьшаем его на единицу. Если при сравнении больше элемент первого массива, уменьшаем m на единицу, иначе уменьшаем n. Делаем это в цикле до тех пор, пока n не станет равно 0, то есть пока не переберём весь второй массив.

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        
        Do not return anything, modify nums1 in-place instead.
        
        write_point = m + n - 1
        while n > 0:
            if m > 0 and nums1[m - 1] > nums2[n - 1]:
                nums1[write_point] = nums1[m - 1]
                m -= 1
            else:
                nums1[write_point] = nums2[n - 1]
                n -= 1
            write_point -= 1

Время линейное, память постоянная.

Стоит не выспаться и/или понервничать, ко мне цепляется головная боль и не уходит порой несколько дней, ещё и приводя с собой бессонницу, что только усугубляет проблему. Всё же левел-апаюсь, но вместо ЛитКода, системного дизайна, пет-проекта и Линукса я обычно делаю только что-то одно. Я перенервничал и не выспался во вторник, и только сейчас, кажется, снова пришёл в норму.

анон-левел-апер

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

Хотел побурчать на задачи, как они тяжело дались и какие они вообще упоротые, но съездил на фехтование, проветрился и расслабился. А ещё был чудесный тёплый весенний вечер, и в воздухе так нежно и чудесно пахло глицинией, что настроения бурчать вовсе не осталось

анон-левел-апер

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

Кто попал тренеру шпагой в лицо без маски - тот я 

Вообще мы занимались на шпагах с женщиной-тренером, которая готовится к экзаменам на сертификат, studen teacher, так сказать, а он в тот вечер учил её учить. У меня никак не получалось выполнить одно движение правильно, у неё не получалось мне его объяснить, и тренер сказал мне, мол, давай я сейчас тебе объясню движение, а ты (ей) смотри.
Первый раз прошло нормально. Второй раз прошло нормально, и у меня начало получаться как надо. В третий раз то ли дистанция между нами сократилась, то ли я криворук вот это наиболее вероятно, но вместо того, чтобы уколоть тренера шпагой в верхнюю правую часть груди, я ударила его в лицо.

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

На следующий день на тренировке он даже посмеялся, мол, зацените, как анон-левел-апер вчера разбушевалась и двинула мне по лицу шпагой лол кек. Когда я спросила, как он себя чувствует, он сказал, что всё ок и ничего серьёзного   

Но ещё пару раз напомнил всем про технику безопасности

анон-левел-апер-фехтовальщик

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

Хотел было написать про задачи, что простые идут уже за 5-10 минут, что я начала решать средний уровень, и средний уровень внезапно кажется легче, чем в прошлый раз, но что-то совсем устал и уехал в путешествие в Йеллоустоунский парк.

анон-левел-апер

Отредактировано (2023-06-15 01:56:01)

Анон

Re: Вращаем бинарные деревья[айти][левел-ап][фехтование][дыбр][yes com]

Выбирал-выбирал себе шпагу для HEMA и наконец выбрал, и наконец она приехала!  И ножны хороши

▼моя прелессть⬍

анон-левел-апер-фехтовальщик