Coding interview scrapbook

Дан однонаправленный связный список 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 человек так, чтобы они были рядом. Мес...

Дана коллекция интервалов на горизонтальной линии. Нужно объединить пересекающиеся и вернуть коллекцию непересекающихся интервалов. Пример 1: Дано: [[1,3],[2,6],[8,10],[15,18]] Решение: [[1,6],[8,10],[15,18]] Объяснение: Поскольку интервалы [1,3] и [2,6] пересекатся, мы их объединяем в один [1,6]. Пример 2: Дано: [[1,4],[4,5]] Решение: [[1,5]] Объяснение: Интервалы [1,4] и [4,5] пересекаются в точке 4. Идея решения Отсортируем наши интервалы по их стартовой точке. И добавим первый интервал в список merged , который выдадим, как результат. Далее смотрим на следующий интервал. Если его начальная точка больше, чем конечная точка последнего интервала в нашем списке, то это непересекающиеся интрвалы, и мы опять добавляем текущий интервал в список, и будем его сравнивать со следущим. Если же начальная точка следующего интрвала МЕНЬШЕ финальной точки последнего интервала из списка merged , то они пересекаются, мы обновляем последний интервал в списке, ничего нового не добав...

Даны фишки, пронумерованные от 0 до n. Они находятся в позициях, от 1 до m. Массив chips показывает, что фишка chips[i] находится в позиции i. Фишки можно переставлять влево или вправо на 1 или 2 шага любое количество раз. Каждая перестановка фишки имеет стоимость: Переместить i -ю фишку влево или вправо на две позиции стоит 0 . Переместить i -ю фишку влево или вправо на одну позицию стоит 1 . Изначально на одной позиции могут находиться несколько фишек. Вернуть минимальную стоимость того, что мы можем переместить все фишки в одну позицию. Пример 1: Дано: chips = [1,2,3] - три фишки расставлены на разных местах 1, 2, 3 Результат: 1 Пояснение: Если мы хотим сместить всё в 1-ю позицию, то из позиции 3 мы переходим за нулевую стоимость, а из позиции 2 - за стоимость 1. Аналогично, если мы хотим сместить всё в позицию 3. Если мы хотим сместить всё в позицию 2, то стоимость перемещения из позиции 1 и 3 будет стоить нам по 1, то есть суммарно 2, а это не минимальная сто...

Даны две строки, которые представляют собой комплексное число . Нужно вернуть строку, которая представляет собой результат умножения двух комплексных чисел. Примечание:  i 2   = -1 - свойство комплесных чисел. Пример 1: Дано: "1+1i", "1+1i" Результат: "0+2i" Пояснение: (1 + i) * (1 + i) = 1 + i 2 + 2 * i = 2i, и финальный результат: 0+2i. Пример 2: Дано: "1+-1i", "1+-1i" Результат: "0+-2i" Пояснение: (1 - i) * (1 - i) = 1 + i 2 - 2 * i = -2i, и финальный результат: 0+-2i. Примечание: Во входных строках нет лишних пробелов. Входны строки даны в форме a+bi , где целые a и b из интервала [-100, 100]. И результат должен быть отформатирован также. Идея решения: Просто умножим с раскрытием скобок и применением свойства квадрата мнимой части, полдучится: (a+bi)   * (c+di) = a*c + a*di + c*bi - b*d = (a*c - b*d) + (a*d + c*b)i Поскольку вход  дон в виде сток, то нужно в строках выделить подстроки, пр...