Сообщения

Поисковое дерево с возрастающими значениям

Задача. Дано бинарное поисковое дерево. Реорганизовать его в порядке in_order таким образом, чтобы самый левый (наименьший, поскольку это бинарное поисковое дерево) ребенок стал корнем, чтобы у любой вершины не было левого ребенка, но был только правый ребенок. Пример: Дано: [5,3,6,2,4,null,8,1,null,null,null,7,9] 5 / \ 3 6 / \ \ 2 4 8  / / \ 1 7 9 Результат: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9] 1   \   2   \   3   \   4   \   5   \   6   \   7   \   8   \ 9 Примечания: У каждого вдерева вершин 1 до 100. У каждой вершины значения варьируются от 0 до 1000. /**  * Definition for a binary tree node.  * public class TreeNode {  *     int val;  *  ...

Первая плохая версия

Источник: https://leetcode.com/problems/first-bad-version/ Задача. Вы разрабатываете продукт. И в какой-то момент одна из версий не проходит тесты - bad version. Все версии после нее тоже не проходят тесты и считаются bad version. Допустим, у вас n версий продукта: [1, 2, ..., n] и вы хотите найти первую bad, которая все последующие окрасила в bad. У вас есть функция API  bool isBadVersion(version) которая возвращает значения истинно/ложно, если version является bad.  Надо написать функцию, которая находит первую bad version. Следует мимнимизировать число вызовов API. Пример: Дано n = 5, and version = 4 это первая bad version (но мы об этом не знаем, нам нужно, чтобы наш алгоритм это выявил). call isBadVersion(3) -> false call isBadVersion(5) -> true call isBadVersion(4) -> true Значит 4 - это первая bad version. Идея решения: все версии идут в растущем порядке по понятным причинам. Значит, методом дихотомии (binary search, двоичный поиск...

Благородное число (Noble integer)

Задача. Дан целочисленный массив. Найти целое число p, если оно существует, такое, что количество элементов массива, которые больше, чем p, равно (количество таких элементов) p Если число существует, вернуть 1, иначе вернуть -1. Идея решения. Поскольку речь идёт об отношениях больше-меньше между всеми элементами, то имеет смысл отсортировать исходный массив. Затем нужно просматривать каждый эелемент массива (пропуская его дубликаты) и сравнивать, сколько элементов (больше его) ещё остались до конца массива. если число оставшихся элементов равно самому (в настоящий момент рассматриваемому) элементу, то мы нашли благородное число. public class Solution { public int solve ( ArrayList < Integer > A ) { // Total runtime: O(n log n) due to sort Collections . sort ( A ); for ( int i = 0 ; i < A . size (); i ++) { // Пропускаем все дубликаты if ( i < A . size () - 1 && A . get ...

Дневные температуры

Дан список (массив) дневных температур T , вернуть такой массив, в котором в каждому дню будет соответствовать число, сколько дней ждать повышения температуры. Если повышения не предвидится для какого-то дня, то ему поставить 0 . Например, массив температур: T = [73, 74, 75, 71, 69, 72, 76, 73] , результат будет [1, 1, 4, 2, 1, 1, 0, 0] . Примечание: Длинна массива temperatures находится в интервале [1, 30000] . Каждая температура - это целое число в интервале [30, 100] . Идея решения: здесь удобно начать с конца массива . Для финального элемента повышения не будет, поэтому сразу запишем последний элемент в массиве результата 0. Смотрим предпоследний элемент. Два случая: Если он больше последнего, то ставим опять 0 (повышения не произошло до конца массива).  Если он меньше последнего, то повышение температуры происходит на следующий день и мы ставим 1. Смотрим третий с конца элемент. Тут четыре ситуации. Пусть X, Y, Z - это три последних элемента массива. Индексы...

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

Изображение
Написать функцию, которая удаляет звено (за исключением последнего) в односвязном списке, на вход поступает только звено, которое необходимо удалить. Например, список = [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; } } }

Число единичек в двоичном представлении числа

Дано целочисленное число N без знака. Нужно подсчитать количество единичек в его двоичном представлении. Например, число 11 в двоичном представлении выглядит 1011. Значит ответ будет 3. Идея решения: если самый правый бит равен 1, то увеличить счётчик единичек. И в любом случае (0 или 1 справа) сдвинуть битовое представление на 1 позицию вправо, заменяя свободные биты слева нулями. Повторять до тех пор, пока результат сдвига не станет равен нулю. Компилируемый код идеи решения:      int sum=0;         while(N!=0) {             if ((N&1)==1) sum++;             N = N >>> 1;         } Проблема в том, что для больших чисел такой подсчёт может быть непозволительно длинным. Ускорим алгоритм, находя сразу позицию p самого правого ненулевго бита и сдвигая число N на чис...