Сообщения

Показаны сообщения с ярлыком "Списки"

Итератор по двоичному поисковому дереву II

Изображение
Источник: https://leetcode.com/problems/binary-search-tree-iterator-ii/ Заимплементировать класс BSTIterator который представляет собой in-order обход (левое поддерево - текущий узел - правое поддерево) бинарного поискового дерева (BST): BSTIterator(TreeNode root) конструктор. Корень root является входным значением для конструктора. boolean hasNext() возвращает true если можно перейти вправо, иначе false . int next() перемещает указатель вправо и возвращает значение вершины. boolean hasPrev() возвращает true если можно перейти влево, иначе false . int prev() перемещает указатель влево и возвращает значение вершины. После инициализации курсор указывает на несуществующее значение, то есть можно сделать next() и получить наименьший элемент в дереве. Можем считать, что next() и prev() всегда валидны. То есть когда мы их вызваем, то всегда возвращаем какое-то значение. Пример: Дано ["BSTIterator", "next", "next", "prev", "n...

Объединить k отсортированных списков в один отсортированный список

 Источник: https://leetcode.com/problems/merge-k-sorted-lists Дан массив из k связных списокв lists , элементы в каждом идут в возрастающем порядке. Объединить все связные списки в один список,в к отором элементы идут в возрастающем порядке, и вернуть его. Пример 1: Дано: lists = [[1,4,5],[1,3,4],[2,6]] Результат: [1,1,2,3,4,4,5,6] Пояснение: Исходные списки такие: [ 1->4->5, 1->3->4, 2->6 ] если их объединить, то мы получим такой список: 1->1->2->3->4->4->5->6 Пример 2: Дано : lists = [] Результат : [] Пример 3: Дано : lists = [[]] Результат : [] Ограничения: k == lists.length 0 <= k <= 10^4 0 <= lists[i].length <= 500 -10^4 <= lists[i][j] <= 10^4 lists[i] содержит элементы отсортированные в возрастающем порядке Скммарная длиннавсех списков не превышает 10^4 . Идея решения Мы можем объединить два списка в один отсортированный за линейное время. Для этого мы сканируем оба списка и заносим в результат наименьший...

Взвешенная сумма вложенного списка

Источник: https://leetcode.com/problems/nested-list-weight-sum-ii/ Дан вложенный список целых чисел. Подсчитать сумму всех его элементов, взвешенных их глубиной. Каждый элемент вложенного списка может быть целым числом или вложенным списком - тоже состоящий из целых чисел и вложенных списков. Вес увеличивается снизу вверх, то есть "листьевые" целые элементы имеют вес 1. А корень имеет наибольший вес. Как изменится алгоритм, если вес увеличивается от корня к листьям? Пример 1: Дано: [[1,1],2,[1,1]] Результат: 8 Пояснение: Четыре единицы находятся на глубине 1, а 2 - на глубине 2 . Поэтому сумма считается: 1*1 + 1*1 + 2*2 + 1*1 + 1*1 = 8. Пример 2: Дано: [1,[4,[6]]] Результат: 17 Поясненеи: Число 1 находится на глубине 3, 4 - на глубине 2, 6 - на глубине 1. Поэтому сумма считается: 1*3 + 4*2 + 6*1 = 17. Есть некоторый класс NestedInteger, со следующим интерфейсом: /**  * // Интерфейс для вложенного списка, не нужно его имплементировать  *  * public interface NestedIn...

LRU-кэш

Источник: https://leetcode.com/problems/lru-cache/ Создайте структуру данных для  Least Recently Used (LRU) cache . Эта структура поддерживает две операции: get и put . get(key)   - извлекает значение (всегда положительное) по ключу key, если ключ присутствует в кэше, а в противном случае возвращает -1. put(key, value)   - помещает или изменяет значение по ключу.  Когда кэш достигает своей вместимости, наименее используемые элемент можно удалить и поместить новый элемент. Кэш инициализируется положительной вместимостью. Сделайте так, чтобы обе операции выполнялись за время со сложностью O(1) , то есть за константу. Пример 1: Входные данные ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] Результат [null, null, null, 1, null, -1, null, -1, 3, 4] Пояснение LRUCache lRUCache = new LRUCache(2);...

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

Даны 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...

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

Дан однонаправленный связный список 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 =...

Удалить элемент в списке

Изображение
Написать функцию, которая удаляет звено (за исключением последнего) в односвязном списке, на вход поступает только звено, которое необходимо удалить. Например, список = [4,5,1,9] выглядит так: Example 1: Input: head = [4,5,1,9], node = 5 Output: [4,1,9] Example 2: Input: head = [4,5,1,9], node = 1 Output: [4,5,9] Компилируемое решение:  /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public void deleteNode(ListNode node ) { ListNode temp = node . next ; if (temp!=null) { node . val = temp.val; node . next = temp.next; temp = null; } } }