Сообщения

Проверить идентичность деревьев

Даны два бинарных дерева, написать функцию, которая проверяет, идентичны ли они. Два бинарных дерева идентичны, если у них одинаковая структура и на узлах в идентичных позициях храняться одинаковые значения. Пример 1: Дано: 1 1 / \ / \ 2 3 2 3 [1,2,3], [1,2,3] Результат: true Пример 2: Дано : 1 1 / \ 2 2 [1,2], [1,null,2] Результат : false Пример 3: Дано : 1 1 / \ / \ 2 1 1 2 [1,2,1], [1,1,2] Результат : false Идея решения Дерево А идентично дереву Б, если значения в корнях совпадают, а также идентичны левые и правые поддревья, для которых мы можем опять проверить корни и левые/правые поддеревья и так далее. Очевидно, для решения нам понадобится рекурси. Имплементация     public boolean isSameTree(TreeNode p, TreeNode q) {         if (...

Сложить два числа, которые представлены списком

Даны 2 непустых списка, в которых закодированы, соответственно, два неотрицательных чила. Цифры каждого числа хранятся в обратном порядке. В каждоя ячейке списка находится одна цифра. Сложить эти два числа и вернуть их в виде списка. Можно предположить, что заданные числа не начинаются с нуля, за исключением если они и есть 0. Пример: Дано: (2 -> 4 -> 3) + (5 -> 6 -> 4) Резальтат: 7 -> 0 -> 8 Пояснение: 342 + 465 = 807. Идея решения. В начале каждого списка установим указатель, они будут смещаться одновременно складывая числа ячеек: a+b по правилам сложения в столбик. Имплементация. public ListNode addTwoNumbers(ListNode l1, ListNode l2) {     ListNode dummyHead = new ListNode(0); // запоминаем начало результирующего списка     ListNode p = l1, q = l2, curr = dummyHead;     int carry = 0;     while (p != null || q != null) {         int x = (p != null) ? p.v...

Волшебный словарь

Нужно создать структуру "волшебный" словарь с методами buildDict и search . Для метода buildDict будет дан список неповторящихся слов, которые будут использованы для создания словаря. Для метода search будет дано одно слово, оно может совпадать с каким-то словом из словаря или отличаться от слова в словаре на одну букву . Пример: Input: buildDict(["hello", "leetcode"]), Output: Null Input: search("hello"), Output: False Input: search("hhllo"), Output: True Input: search("hell"), Output: False Input: search("leetcoded"), Output: False Примечания: Мы предполагаем, что все слова в словаре написаны маленькими буквами английского алфавита a-z . Словарь может быть очень большим. Идея решения В процессе инициализации словаря мы можем рассортировать слова по "ведрам" (buckets), где каждое ведро содержит слова определенной длины. Когда поступает слово на поиск, мы берем список слов той же...

Перемешать элементы в списке

Дан однонаправленный связный список L :  L 0 → L 1 →…→ L n -1 → L n , Надо перемешать его элменты в следующем порядке:  L 0 → L n → L 1 → L n -1 → L 2 → L n -2 →… То есть первый, последний, второй, предпоследний и т.д. Нельзя модифицировать значения val в ячейке, можно только менять указатели. Пример 1: Дан список 1->2->3->4, перемешиваем его так: 1->4->2->3. Example 2: Дан список 1->2->3->4->5, перемешиваем его так: 1->5->2->4->3. Идея решения Нам нужно сделать три шага: разбить исходный список на две равные части; вторую часть развернуть, см. Развернуть связный список сформировать новый список, добавляя в результат попеременно то элемент из первого списка, то из второго. Компилируемое решение class Solution { public void reorderList(ListNode head) { if (head == null || head. next == null ) return ; // step 1. находим середину списка и его конец // prev - это хвост первой половины списк...

Развернуть связный список

Развернуть в обратном порядке элементы в связном списке с позиции m до n . Сделать это за один проход. Примечание:  1 ≤  m  ≤  n  ≤ длина списка. Пример: Дано: 1->2->3->4->5->NULL, m = 2, n = 4 Результат: 1->4->3->2->5->NULL Идея решения  Нам нужно помнить элемент curr (текущий) и pre (предыдущий). prev.next=curr curr.next=temp prev>curr>temp  Тогда, если мы хотим получить конфигурацию prev<curr<temp , то curr.next = prev; temp.next=curr. Компилируемое решение /**  * Definition for singly-linked list.  * public class ListNode {  *     int val;  *     ListNode next;  *     ListNode(int x) { val = x; }  * }  */ class Solution {     public ListNode reverseBetween(ListNode head, int m, int n) { // фейковый элемент списка         ListNode dummy =...

Сумма квадратов

Доно неотрицательное целое число c , нужно определить, существуюь ли два целых числа a и b , что a 2  + b 2  = c. Пример 1: Дано: 5 Ответ: True Пояснение: 1 * 1 + 2 * 2 = 5 Пример 2: Дано: 3 Ответ: False Компилируемое решение public class Solution {     public boolean judgeSquareSum(int c) {         for (long a = 0; a * a <= c; a++) {             double b = Math.sqrt(c - a * a);             if (b == (int) b)                 return true;         }         return false;     } } Анализ сложности Сложность по времени :   O\big(\sqrt{c}\log c\big) O ( c ​ lo g c ) . Мы ищем среди \sqrt{c} c ​ значений, чтобы определить a a . Для каж...

Бронирование мест в самолете

Вы обрабатываете бронирование мест в самолете. Есть N рядов, в кажом ряду 10 мест от A до K, при этом I пропущено, как на схеме: +---+---+---+ +---+---+---+---+ +---+---+---+ | A | B | C | | D | E | F | G | | H | J | K | +---+---+---+ +---+---+---+---+ +---+---+---+ 1 | | | | | | | | | | | | | +---+---+---+ +---+---+---+---+ +---+---+---+ 2 | | | | | | | | | | | | | +---+---+---+ +---+---+---+---+ +---+---+---+ 3 | | | | | | | | | | | | | +---+---+---+ +---+---+---+---+ +---+---+---+ ... ... ... ... ... ... ... ... ... ... +---+---+---+ +---+---+---+---+ +---+---+---+ N | | | | | | | | | | | | | +---+---+---+ +---+---+---+---+ +---+---+---+ Некоторые из мест уже забронированы. Список забронированных мест даётся в виде строки, например: "1A 3C 2B 40G 5A" . Ваша задача забронировать места для семьи из 4 человек так, чтобы они были рядом. Мес...