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

-
Источник: 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, двоичный поиск) мы можем самым быстрым способом выявить первую неправильную версию за O(log(n)), потому что простраство поиска уменьшается вдвое на каждой итерации, всего итераций может быть не более n.

Компилируемое  решение:

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
// устанавливаем границы дихотомии
        int lo = 1; // это хорошая версия
        int hi = n; // это однозначно bad версия
// все плохие версии находятся во второй части массива
        while (lo < hi) {
// выбираем значение по центру границ дихотомии
            int mid = lo + ((hi-lo)>>1);
            if (isBadVersion(mid)) {
// центральное значение даёт bad, значит, переломная точка левее или mid,
// поэтому включаем это значение в следующую итерацию
                hi = mid;
            } else {
// центральное значение даёт хорошую версию, значит, искомая точка однозначно правее
                lo = mid+1;
            }
        }
// нарушено условие lo < hi, значит мы нашли самую первую точку с bad версией,
// и она как раз в том искаженном индексе lo, который обычно содержал хорошие верссии.
        return lo;
    }
}

Результат:
Runtime: 10 ms, faster than 99.88% of Java online submissions for First Bad Version.
Memory Usage: 33.2 MB, less than 100.00% of Java online submissions for First Bad Version.

Комментарии

Отправить комментарий

Популярные сообщения из этого блога

Разбиение числа на сумму с максимальным произведнием слагаемых

-
Источник: https://leetcode.com/problems/integer-break/ Дано целое число n , нужно представить его в виде суммы k положительных целых чисел , где k >= 2 , и произведение этих чисел максимально. Вернуть максимальное произведение. Пример 1: Дано: n = 2 Результат: 1 Пояснение: 2 = 1 + 1, 1 × 1 = 1. Пример 2: Дано: n = 10 Результат: 36 Пояснение: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36. Ограничения: 2 <= n <= 58 Идея решения Допустим мы представили число n в виде суммы, и произведение слагаемых этой суммы обозначим P = p1 * p2 * ...   pk. Рассмотрим некое слагаемое pi uи представим его в виде суммы pi-2 и 2. Если 2 (pi-2) > pi, то у нас получится ещё большее произведение, и это имеет место при pi > 4. Рассмотрим сумму pi-3 и 3, тогда 3*(pi-3) > pi при pi > 4.5. Если pi= 4, то (4-2)*2=4, а (4-3)*3=3. То есть Таким образом, нам нужно разбить исходное число на сумму двоек и троек, чтобы получить максимальное произведение.  В итоге нам нужно представить n = a 3 + ...
Далее...

Число подмассивов, в которых сумма элементов равна k

-
Дан целочисленный массив и целое число k . Найти количество непрерывных подмассивов таких, что сумма их элементов равна k . Пример 1: Дано: nums = [1,1,1], k = 2 Результат: 2 Условия: Длинна массива находится в диапазоне [1, 20,000]. Элементы массива находятся в диапазоне [-1000, 1000], число k - в диапазоне [-1e7, 1e7]. Идея решения Если кумулятивная сумма (пусть s u m [ i ] - это сумма с нулевого до i^{th} i t h индекса ) одинакова для индексов i и j, значит, сумма между этими двумя индексами равна нулю. А если суммы в индексах i i и  j j таковы, что sum[i] - sum[j] = k s u m [ i ] − s u m [ j ] = k , значит, сумма элементов между индексами i i   and   j j равна k k . Создадим хэшмап map m a p , чтобы хранить кумулятивные суммы для всех индексов, вместе с количеством того, сколько раз мы посчитали эту сумму . То есть это пары (sum_i, no. of occurences of sum_i) ( s u m i ​ , n o . o f o c c u r e n c e s o f s u m i ​ ) . Каждый раз, когда мы встречаем ...
Далее...

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

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