Сообщения

Обход бинарного дерева по уровням

Изображение
Источник задачи: https://leetcode.com/problems/binary-tree-level-order-traversal/ Дан корень root бинарного дерева. Вернуть обход дерева по уровням, то есть слева направа, уровень за уровнем. Пример 1:   Дано: root = [3,9,20,null,null,15,7] Результат: [[3],[9,20],[15,7]] Пример 2: Дано: root = [1] Результат: [[1]] Пример 3: Дано: root = [] Результат: [] Ограничения: Число вершин дерева находятся в диапазоне [0, 2000] . -1000 <= Node.val <= 1000     Теория. Как можно обходить деревья Есть 2 основные стратегии обхода дерева: Depth First Search (DFS) - обход в глубину В этой стратегии мы принимаем глубину в качестве приоритета, чтобы можно было начинать с корня и доходить до определенного листа, а затем обратно к корню, чтобы достичь другой ветви. Стратегия DFS дополнительно может быть разделена на предварительный порядок ( preorder ), порядок следования ( inorder ) и последующий порядок ( postorder ) в зависимости от относительного порядка между корневым узло...

Номер колонки в таблице Excel

Источник задачи: https://leetcode.com/problems/excel-sheet-column-number/ Дана строка columnTitle она представляет собой название колонки в таблице Excel. Рассчитать номер этой колонки. Например: A -> 1 B -> 2 C -> 3 ... Z -> 26 AA -> 27 AB -> 28 ... Пример 1: Дано: columnTitle = "A" Результат: 1 Пример 2: Дано: columnTitle = "AB" Результат: 28 Пример 3: Дано: columnTitle = "ZY" Результат: 701 Пример 4: Дано: columnTitle = "FXSHRXW" Результат: 2147483647 Ограничения: 1 <= columnTitle.length <= 7 columnTitle состоит только из заглавных букв английсокго алфавита. columnTitle находится в диапазоне ["A", "FXSHRXW"] . Имплементация class Solution {    public int titleToNumber(String A) {          int base = 26; // 26 заглавных букв в алфавите         int result = 0; // просматриваем каждый символ строки         for (int i = 0; i < A.length...

Самый короткий палиндром

Источник: https://leetcode.com/problems/shortest-palindrome/   в гугл таблицах от 23.01.2020 Дана строка s. Вы можете конвертировать s в палиндром, если добавите необходимые символы в начало строки. Вернуть самый короткий палиндром, который можно построить при помощи описанной трансформации. Пример 1: Дано: s = "aacecaaa" Результат: " a aacecaaa" Пояснение : добавили символ а в начале строки. Пример 2: Input: s = "abcd" Output: " dcb abcd" Пояснение : добавили символы dcb в начале строки. Ограничения: 0 <= s.length <= 5 * 10 4 s состоит из маленьких латинских букв английского алфавита . Идея решения Если представить, что строка s=AB, где А - это палиндром, то тогда нам нужно добавить развернуют строку B в начало s, чтобы получить результат. То есть результат = B'AB, где B' - это развернутая строка. Как найти А? Надо склеить строку с её частями по-другому: построим q=A'B'BA. Но поскольку А - палиндром, то есть А=А', ...

Наидлиннейшая арифметическая подпоследовательность с заданной разностью

Источник: https://leetcode.com/problems/longest-arithmetic-subsequence-of-given-difference/ 1218.   Longest Arithmetic Subsequence of Given Difference Дан массив целых чисел и целое число, представляющее собой искомую разность. Вернуть наидленнейшую подпоследовательность в массиве такую, что разница между соседними элементами подпоследовательности равна искомой разности. Подпоследовательность - это последовательность, которая может быть получена из исходного массива путем удаления из него нескольких (или 0) элементов, без изменения порядка в оставшихся элементах.   Пример 1: Дано: arr = [1,2,3,4], difference = 1 Результат: 4 Пояснение: Наидлиннейшая подпоследовательность = [1,2,3,4]. В ней каждая пара соседних элементов отличается на значение difference. Пример 2: Дано: arr = [1,3,5,7], difference = 1 Результат: 1 Пояснение: Любой элемент массива является подпоследовательностью длины 1. Пример 3: Дано: arr = [1,5,7,8,5,3,4,2,1], difference = -2 Результат: 4 Пояснение: ...

Валидные скобки

Источник: https://leetcode.com/problems/valid-parentheses/ Дана строка s , состояшая из символов '(' ,   ')' ,   '{' ,   '}' ,   '[' и ']' . Определеить валидна ли последовательность скобок. Последовательность сокбок валидна: Открытые скобки закрываются тем же типом скобок. Открытые скобки закрываются в корректной последовательности.   Пример 1: Дано: s = "()" Результат: true Пример 2: Дано: s = "()[]{}" Результат : true Пример 3: Дано : s = "(]" Результат : false Пример 4: Дано : s = "([)]" Результат : false Example 5: Дано : s = "{[]}" Результат : true   Ограничения: 1 <= s.length <= 10 4 s состоит только из '()[]{}' . Идея решения Для проверки валидности выражений в скобках удобно использовать стеки. Каждую открывающую скобку бросаем в стек. Как только встречаем закрывающую скобку, смотрим, что у нас в верхушке стека. Там бует открывающая скобка, но нам нужн...

Игра в камни 3

Источник: https://leetcode.com/problems/stone-game-iii/ Alice и Bob играют с камнями. Несколько камней выложены в рядок. У каждого камня есть своя стоимость stoneValue положительная или отрицательная. Alice и Bob играют по очереди, при этом Alice начинает первая . каждый ход позволяет взять игроку 1, 2 или 3 подряд лежащих камня , с первого доступного в ряду. Счёт каждого игрока - это сумма камней, которые он взял. Начальный счёт = 0. Цель игры: завершить игру (когда не осталось доступных камней) со счётом, превосходящим счёт противника. Если у обоих игроков равный счёт, то получается ничья (tie). Игра продолжается, пока камней не останется. Можно считать, что Alice и Bob играют оптимально . Вернуть "Alice" , если победит Alice; "Bob" , если победит Bob; или "Tie", если ничья . Пример 1: Дано: values = [1,2,3,7] Результат: "Bob" Пояснение : Alice проиграет в любом случае. Её лучший ход, дающий максимальный счёт - это первые три камня: 1...

Флот машин

 Источник: https://leetcode.com/problems/car-fleet/ N машин собираются достичб одной и той же точки назначения на одном и том же маршруте. Точка назначения находится на отметке target миль. Каждая машина i имеет константную скорость speed[i]  (миль/час), и начальную позицию position[i] миль относительно некоторой нулевой точки маршрута к пункту назначения. Машина не может обойти другую машину, но может присоединиться к ней, продолжая движение бампер за бампером с той же скоростью. В этом случае мы считаем расстояние между машинами равно нулю, и эти машины находятся в одной точке. Флот машин - это не пустое множество машин, которые движутся вместе (в одних и тех же точках) с одной и той же скоростью. Одна машина - это тоже флот. Если машина достигает точку назначения одновременно с каким-то флотом, то мы считаем, что она тоже принадлежит этому флоту. Нужно посчитать, сколько отдельных машинных флотов прибудут в точку назначения. Пример: Дано: target = 12 , position = [...