Ноябрьское испытание LeetCode — день 1

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

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

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

Надеюсь, вы найдете их полезными.

Проблема 1:

Учитывая односвязный список, где значение каждого узла равно 0 или 1, найдите десятичное значение двоичного числа, записанного в списке.

Поскольку это только первый день, я думаю, что небольшое объяснение связанных списков не повредит. Односвязный список — это структура данных, которую можно представить следующим образом:

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

Главный вопрос, который у вас должен возникнуть сейчас, заключается в том, как мы храним структуру такого типа внутри компьютера?

Связанные списки создаются рекурсивно. Другими словами, мы определяем полный список на основе меньшей части списка. Рассмотрим пример. Определите один узел нашего списка, присвоив значение 1 переменной, которую мы назовем NODE_1. Мы также будем говорить, что после этого узла нет других узлов (узел Следующий имеет значение Null, что пишется NONE в Python ).

Теперь, когда мы создали наш первый узел, мы можем довольно легко создать второй:

Итак, мы можем определить полный список, как в нашем примере, создав конечный узел с Val = 1 и Next = NODE_2.

Если мы создадим общий объект NODE(Val, Next), который принимает значение и другой объект NODE в качестве входных данных, мы можем сформулировать наш список на выбранном нами языке программирования:

Теперь, когда мы понимаем, как создаются односвязные списки, мы можем вернуться к проблеме преобразования двоичного числа, записанного в списке, в десятичное число. В приведенном выше примере списка у нас было бы двоичное число 101 (читается слева направо), поэтому мы хотели бы вернуть число 5, поскольку:

1*2² + 0*2¹ + 1*2⁰ = 5

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

В приведенном выше решении нам необходимо преобразовать наши цифры в строки, чтобы соединить их вместе, а затем преобразовать обратно в целое число, а также изменить основание 2 на основание 10. Но мы можем добиться большего!

Рассмотрим снова наш пример выше. Начиная слева от связанного списка, мы видим цифру 1. Давайте запишем это:

1

Следующая цифра в нашем списке — 0. Давайте умножим все, что мы записали (пока только 1), на 2, а затем добавим 0:

1*2 + 0

Последняя цифра в нашем списке — еще одна 1. Давайте снова умножим все, что мы записали, на 2, а затем добавим 1:

(1*2 + 0) * 2 +1 = 1*2² + 0*2¹ + 1 = 5

Обратите внимание, что это именно тот результат, к которому мы стремились! И вообще, если мы будем следовать этой процедуре умножения всего на 2 и прибавления к следующей цифре, мы преобразуем наше полное число в основание 10.

Последний прием, который мы можем добавить к этому решению, — это использование побитовых операций.

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

Для целей этого вопроса полезно знать, что битовый сдвиг (где вы сдвигаете все цифры влево и добавляете дополнительный ноль справа) эквивалентен умножению на 2 , а также то, что оператор ИЛИ с одной единицей гарантирует, что последняя цифра также равна 1 (добавление 1, если наше число четное). Например:

1011 (основание 2) = 1*2³+ 0*2² + 1*2¹ + 1*2⁰ = 11

Битовый сдвиг 1 влево:

10110 (основание 2) = 1*2⁴+ 0*2³ + 1 *2² + 1*2¹ + 0*2⁰= 22

И затем ИЛИ с 1:

10110 ИЛИ 1 (по основанию 2) = 10111 (по основанию 2)

= 1*2⁴ + 0*2³ + 1*2² + 1*2¹ + 1*2¹= 23

Следовательно, мы можем заменить части нашего предыдущего кода побитовыми операциями, добавив эффективности и стиля 😎