Задача: 435. Non-overlapping Intervals
Сложность: medium

Дан массив интервалов intervals, где intervals[i] = [starti, endi]. Верните минимальное количество интервалов, которые нужно удалить, чтобы остальные интервалы не пересекались.

Пример:

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.

👨‍💻 Алгоритм:

1⃣Отсортируйте интервалы по времени окончания.

2⃣Инициализируйте переменную ответа ans = 0 и целое число k для представления самого последнего времени окончания. k следует инициализировать небольшим значением, например, INT_MIN.

3⃣Итеративно пройдитесь по интервалам. Для каждого интервала: Если время начала больше или равно k, обновите k до времени окончания текущего интервала. В противном случае увеличьте ans. Верните ans.

😎 Решение:

class Solution {
    function eraseOverlapIntervals($intervals) {
        usort($intervals, function($a, $b) {
            return $a[1] - $b[1];
        });
        $ans = 0;
        $k = -INF;
        
        foreach ($intervals as $interval) {
            list($x, $y) = $interval;
            if ($x >= $k) {
                $k = $y;
            } else {
                $ans++;
            }
        }
        
        return $ans;
    }
}

Ставь 👍👍 и забирай 📚 📚 Базу знанийБазу знаний

Задача: 393. UTF-8 Validation
Сложность: medium

Дан целочисленный массив data, представляющий данные, верните, является ли это допустимой UTF-8 кодировкой (т.е. переводится в последовательность допустимых UTF-8 закодированных символов).
Символ в UTF-8 может быть от 1 до 4 байтов в длину, при этом соблюдаются следующие правила:
Для 1-байтового символа первый бит — 0, за которым следует его Unicode код.
Для n-байтового символа первые n битов — все единицы, (n + 1)-й бит — 0, за которыми следуют n - 1 байт с наиболее значимыми 2 битами, равными 10.
Это работает следующим образом:

     Количество байтов  |        UTF-8 Октетная последовательность
                       |              (бинарная)
   --------------------+-----------------------------------------
            1          |   0xxxxxxx
            2          |   110xxxxx 10xxxxxx
            3          |   1110xxxx 10xxxxxx 10xxxxxx
            4          |   11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

x обозначает бит в бинарной форме байта, который может быть как 0, так и 1.

Примечание: Вход представляет собой массив целых чисел. Используются только 8 младших значимых битов каждого целого числа. Это означает, что каждое целое число представляет только 1 байт данных.

Пример:

Input: data = [197,130,1]
Output: true
Explanation: data represents the octet sequence: 11000101 10000010 00000001.
It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character.

👨‍💻 Алгоритм:

1⃣Начните обработку целых чисел в данном массиве одно за другим. Для каждого целого числа получите его двоичное представление в виде строки. Поскольку целые числа могут быть очень большими, следует учитывать только 8 младших значимых битов данных и отбросить остальные, как указано в условии задачи. После этого шага у вас должно быть 8-битное или 1-байтовое строковое представление целого числа. Назовем эту строку bin_rep.

2⃣Далее нужно рассмотреть два сценария. Первый — мы находимся в процессе обработки некоторого UTF-8 закодированного символа. В этом случае нужно просто проверить первые два бита строки и посмотреть, равны ли они "10", т.е. наиболее значимые два бита целого числа равны 1 и 0. bin_rep[:2] == "10". Второй сценарий — мы уже обработали несколько допустимых UTF-8 символов и должны начать обработку нового UTF-8 символа. В этом случае нужно посмотреть на префикс строкового представления и посчитать количество единиц, которые мы встречаем до первой нули. Это скажет нам, каков размер следующего UTF-8 символа.

3⃣Продолжайте обрабатывать целые числа массива таким образом, пока не обработаете их все или не обнаружите недопустимый сценарий.

Теперь давайте перейдем к реализации этого алгоритма.

😎 Решение:

class Solution {
    function validUtf8($data) {
        $nBytes = 0;
        foreach ($data as $num) {
            $binRep = substr(sprintf('%08b', $num), -8);
            if ($nBytes == 0) {
                foreach (str_split($binRep) as $bit) {
                    if ($bit == '0') break;
                    $nBytes++;
                }
                if ($nBytes == 0) continue;
                if ($nBytes == 1 || $nBytes > 4) return false;
            } else {
                if (!(substr($binRep, 0, 2) == '10')) return false;
            }
            $nBytes--;
        }
        return $nBytes == 0;
    }
}

Ставь 👍👍 и забирай 📚 📚 Базу знанийБазу знаний

Задача: 141. Linked List Cycle
Сложность: easy

Дана переменная head, которая является началом связного списка. Определите, содержит ли связный список цикл.
Цикл в связном списке существует, если существует узел в списке, до которого можно добраться снова, последовательно следуя по указателю next. Внутренне переменная pos используется для обозначения индекса узла, к которому подключен указатель next последнего узла. Обратите внимание, что pos не передается в качестве параметра.
Верните true, если в связном списке есть цикл. В противном случае верните false.

Пример:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

👨‍💻 Алгоритм:

1⃣Инициализация структуры данных:
Создайте хеш-таблицу (или множество) для хранения ссылок на узлы, чтобы отслеживать уже посещённые узлы.

2⃣Обход списка:
Перемещайтесь по связному списку, начиная с головы (head), и проверяйте каждый узел по очереди.

3⃣Проверка на цикл:
Если текущий узел равен null, это означает, что вы достигли конца списка, и список не имеет циклов. В этом случае верните false.
Если текущий узел уже содержится в хеш-таблице, это означает, что вы вернулись к ранее посещённому узлу, и, следовательно, в списке присутствует цикл. Верните true.
Если ни одно из этих условий не выполнено, добавьте текущий узел в хеш-таблицу и продолжите обход списка.

😎 Решение:

class ListNode {
    public $val;
    public $next;

    public function __construct($val = 0, $next = null) {
        $this->val = $val;
        $this->next = $next;
    }
}

function hasCycle($head) {
    $nodesSeen = [];
    $current = $head;

    while ($current !== null) {
        $nodeId = spl_object_id($current); 
        if (isset($nodesSeen[$nodeId])) {
            return true;
        }
        $nodesSeen[$nodeId] = true;
        $current = $current->next;
    }
    return false;
}

Ставь 👍👍 и забирай 📚 📚 Базу знанийБазу знаний

Задача: 438. Find All Anagrams in a String
Сложность: medium

Даны две строки s и p, вернуть массив всех начальных индексов анаграмм строки p в строке s. Ответ можно вернуть в любом порядке.
Анаграмма - это слово или фраза, образованные перестановкой букв другого слова или фразы, обычно с использованием всех исходных букв ровно один раз.

Пример:

Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

👨‍💻 Алгоритм:

1⃣Построить эталонный счетчик pCount для строки p.

2⃣Передвигать скользящее окно по строке s: Пересчитывать счетчик скользящего окна sCount на каждом шаге, добавляя одну букву справа и удаляя одну букву слева.

3⃣Если sCount == pCount, обновить выходной список. Вернуть выходной список.

😎 Решение:

function findAnagrams($s, $p) {
    $ns = strlen($s);
    $np = strlen($p);
    if ($ns < $np) {
        return [];
    }

    $pCount = array_fill_keys(range('a', 'z'), 0);
    $sCount = array_fill_keys(range('a', 'z'), 0);

    for ($i = 0; $i < $np; $i++) {
        $pCount[$p[$i]]++;
    }

    $output = [];

    for ($i = 0; $i < $ns; $i++) {
        $sCount[$s[$i]]++;

        if ($i >= $np) {
            $leftChar = $s[$i - $np];
            if ($sCount[$leftChar] == 1) {
                unset($sCount[$leftChar]);
            } else {
                $sCount[$leftChar]--;
            }
        }

        if ($pCount == $sCount) {
            $output[] = $i - $np + 1;
        }
    }

    return $output;
}

Ставь 👍👍 и забирай 📚 📚 Базу знанийБазу знаний

Задача: 1063. Number of Valid Subarrays
Сложность: hard

Дан целочисленный массив nums. Вернуть количество непустых подмассивов, в которых левый элемент не больше других элементов подмассива.

Подмассив — это непрерывная часть массива.

Пример:

Input: nums = [1,4,2,5,3]
Output: 11
Explanation: There are 11 valid subarrays: [1],[4],[2],[5],[3],[1,4],[2,5],[1,4,2],[2,5,3],[1,4,2,5],[1,4,2,5,3].

👨‍💻 Алгоритм:

1⃣нициализируйте переменную ans значением 0. Инициализируйте пустой стек st, который будет хранить индексы элементов в стеке.

2⃣Итерируйте по элементам массива nums для каждого индекса i: продолжайте извлекать элементы из стека st, пока стек не станет пустым или элемент nums[i] не станет больше элемента на вершине стека. Для каждого извлеченного элемента добавляйте количество подмассивов как i - st.top(). Поместите текущий индекс i в стек.

3⃣Извлеките все оставшиеся элементы из стека и для каждого рассмотрите размер nums как индекс следующего меньшего элемента. Соответственно, добавьте nums.size() - st.top() к переменной ans. Верните ans.

😎 Решение:

class Solution {
    function validSubarrays($nums) {
        $ans = 0;
        $st = [];
        
        for ($i = 0; $i < count($nums); $i++) {
            while (!empty($st) && $nums[$i] < $nums[end($st)]) {
                $ans += ($i - array_pop($st));
            }
            $st[] = $i;
        }
        
        while (!empty($st)) {
            $ans += (count($nums) - array_pop($st));
        }
        
        return $ans;
    }
}

Ставь 👍👍 и забирай 📚 📚 Базу знанийБазу знаний

Задача: 247. Strobogrammatic Number II
Сложность: medium

Дано целое число n, верните все стробограмматические числа длины n. Ответ можно возвращать в любом порядке.
Стробограмматическое число — это число, которое выглядит одинаково при повороте на 180 градусов (если посмотреть вверх ногами).

Пример:

Input: n = 2
Output: ["11","69","88","96"]

👨‍💻 Алгоритм:

1⃣Инициализируйте структуру данных reversiblePairs, которая содержит все пары обратимых цифр. Вызовите и верните результат рекурсивной функции generateStroboNumbers(n, finalLength), где первый аргумент указывает, что текущий вызов создаст все стробограмматические числа длиной n, а второй аргумент указывает длину конечных стробограмматических чисел, которые мы будем генерировать, и будет использоваться для проверки возможности добавления '0' в начало и конец числа.

2⃣Создайте функцию generateStroboNumbers(n, finalLength), которая вернет все стробограмматические числа длиной n:
Проверьте базовые случаи: если n == 0, верните массив с пустой строкой [""]; если n == 1, верните ["0", "1", "8"].
Вызовите generateStroboNumbers(n - 2, finalLength), чтобы получить все стробограмматические числа длиной (n-2), и сохраните их в subAns.
Инициализируйте пустой массив currStroboNums для хранения стробограмматических чисел длиной n.

3⃣Для каждого числа в subAns добавьте все reversiblePairs в начало и конец, за исключением случая, когда текущая пара '00' и n == finalLength (потому что нельзя добавить '0' в начало числа), и добавьте это новое число в currStroboNums. В конце функции верните все стробограмматические числа, т.е. currStroboNums.

😎 Решение:

class Solution {
    private $reversiblePairs = [
        ['0', '0'], ['1', '1'],
        ['6', '9'], ['8', '8'], ['9', '6']
    ];

    private function generateStroboNumbers($n, $finalLength) {
        if ($n == 0) {
            return [""];
        }

        if ($n == 1) {
            return ["0", "1", "8"];
        }

        $prevStroboNums = $this->generateStroboNumbers($n - 2, $finalLength);
        $currStroboNums = [];

        foreach ($prevStroboNums as $prevStroboNum) {
            foreach ($this->reversiblePairs as $pair) {
                if ($pair[0] != '0' || $n != $finalLength) {
                    $currStroboNums[] = $pair[0] . $prevStroboNum . $pair[1];
                }
            }
        }

        return $currStroboNums;
    }

    public function findStrobogrammatic($n) {
        return $this->generateStroboNumbers($n, $n);
    }
}

Ставь 👍👍 и забирай 📚 📚 Базу знанийБазу знаний

Задача: 1023. Camelcase Matching
Сложность: medium

Учитывая массив строк queries и строку pattern, верните булевский массив answer, где answer[i] - true, если queries[i] соответствует pattern, и false в противном случае. Слово запроса queries[i] соответствует pattern, если вы можете вставить строчные английские буквы pattern так, чтобы они были равны запросу. Вы можете вставить каждый символ в любую позицию и не можете вставить ни одного символа.

Пример:

Input: queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FB"
Output: [true,false,true,true,false]

👨‍💻 Алгоритм:

1⃣Инициализация переменных:
Создайте массив answer для хранения результатов соответствия каждого запроса шаблону.

2⃣Проверка каждого запроса:
Для каждого запроса из queries, проверьте, можно ли вставить строчные буквы в pattern, чтобы они соответствовали запросу.
Используйте два указателя, один для query и один для pattern. Перемещайте оба указателя, пока они не достигнут конца строк. Если текущие символы совпадают, переместите оба указателя. Если символы не совпадают и текущий символ в запросе является строчной буквой, переместите только указатель запроса.

3⃣Возврат результата:
Если указатель шаблона достиг конца строки, добавьте true в answer, иначе добавьте false.
Верните массив answer.

😎 Решение:

class Solution {
    function camelMatch($queries, $pattern) {
        function matches($query, $pattern) {
            $i = 0;
            $j = 0;
            
            while ($i < strlen($query)) {
                if ($j < strlen($pattern) && $query[$i] == $pattern[$j]) {
                    $j++;
                } else if (ctype_upper($query[$i])) {
                    return false;
                }
                $i++;
            }
            
            return $j == strlen($pattern);
        }
        
        $answer = [];
        foreach ($queries as $query) {
            $answer[] = matches($query, $pattern);
        }
        
        return $answer;
    }
}

Ставь 👍👍 и забирай 📚 📚 Базу знанийБазу знаний

Задача: 287. Find the Duplicate Number
Сложность: medium

Дан массив целых чисел nums, содержащий n + 1 целых чисел, где каждое число находится в диапазоне [1, n] включительно.
В массиве есть только одно повторяющееся число, верните это повторяющееся число.
Вы должны решить задачу, не изменяя массив nums и используя только постоянное дополнительное пространство.

Пример:

Input: nums = [1,3,4,2,2]
Output: 2

👨‍💻 Алгоритм:

1⃣Определение дубликата:
Итерируйте по массиву, оценивая каждый элемент (назовем его cur). Используйте абсолютное значение текущего элемента, чтобы получить индекс.
Если элемент по индексу cur отрицательный, значит, мы уже встречали этот элемент ранее, и cur является дубликатом. Сохраните cur как дубликат и выйдите из цикла.
Если элемент по индексу cur положительный, инвертируйте знак этого элемента, чтобы пометить его как встреченный, и перейдите к следующему элементу.

2⃣Восстановление массива:
Пройдите по массиву и измените все отрицательные элементы обратно на положительные, чтобы восстановить исходное состояние массива.

3⃣Возврат результата:
Верните найденный дубликат.

😎 Решение:

class Solution {
    function findDuplicate($nums) {
        $duplicate = -1;
        for ($i = 0; $i < count($nums); $i++) {
            $cur = abs($nums[$i]);
            if ($nums[$cur] < 0) {
                $duplicate = $cur;
                break;
            }
            $nums[$cur] *= -1;
        }
        for ($i = 0; $i < count($nums); $i++) {
            $nums[$i] = abs($nums[$i]);
        }
        return $duplicate;
    }
}

Ставь 👍👍 и забирай 📚 📚 Базу знанийБазу знаний

Задача: 234. Palindrome Linked List
Сложность: easy

Дан головной элемент односвязного списка. Верните true, если список является палиндромом, и false в противном случае.

Пример:

Input: head = [1,2,2,1]
Output: true

👨‍💻 Алгоритм:

1⃣Копирование односвязного списка в массив: Итеративно пройдите по односвязному списку, добавляя каждое значение в массив. Для этого используйте переменную currentNode, указывающую на текущий узел. На каждой итерации добавляйте currentNode.val в массив и обновляйте currentNode, чтобы он указывал на currentNode.next. Остановите цикл, когда currentNode укажет на null.

2⃣Проверка массива на палиндром: Используйте метод с двумя указателями для проверки массива на палиндром. Разместите один указатель в начале массива, а другой в конце. На каждом шаге проверяйте, равны ли значения, на которые указывают указатели, и перемещайте указатели к центру, пока они не встретятся.

3⃣Сравнение значений: Помните, что необходимо сравнивать значения узлов, а не сами узлы. Используйте node_1.val == node_2.val для сравнения значений узлов. Сравнение узлов как объектов node_1 == node_2 не даст ожидаемого результата.

😎 Решение:

class Solution {
    function isPalindrome($head) {
        $vals = [];
        $currentNode = $head;

        while ($currentNode !== null) {
            $vals[] = $currentNode->val;
            $currentNode = $currentNode->next;
        }

        $front = 0;
        $back = count($vals) - 1;
        while ($front < $back) {
            if ($vals[$front] != $vals[$back]) {
                return false;
            }
            $front++;
            $back--;
        }
        return true;
    }
}

Ставь 👍👍 и забирай 📚 📚 Базу знанийБазу знаний

Задача: 1436. Destination City
Сложность: easy

Дан массив paths, где paths[i] = [cityAi, cityBi] означает, что существует прямой путь из cityAi в cityBi. Вернуть конечный город, то есть город, из которого нет пути в другой город.

Гарантируется, что граф путей образует линию без циклов, поэтому будет ровно один конечный город.

Пример:

Input: paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
Output: "Sao Paulo" 
Explanation: Starting at "London" city you will reach "Sao Paulo" city which is the destination city. Your trip consist of: "London" -> "New York" -> "Lima" -> "Sao Paulo".

👨‍💻 Алгоритм:

1⃣Для каждого города cityBi в paths проверьте, является ли он кандидатом на конечный город.

2⃣Для каждого кандидата проверьте, нет ли пути, ведущего из него (cityAi == candidate).

3⃣Верните город, который не имеет исходящих путей.

😎 Решение:

class Solution {
    function destCity($paths) {
        foreach ($paths as $path) {
            $candidate = $path[1];
            $good = true;
            foreach ($paths as $p) {
                if ($p[0] === $candidate) {
                    $good = false;
                    break;
                }
            }
            if ($good) {
                return $candidate;
            }
        }
        return "";
    }
}

Ставь 👍👍 и забирай 📚 📚 Базу знанийБазу знаний

Задача: 498. Diagonal Traverse
Сложность: medium

Дан массив m x n матрицы mat, верните массив всех элементов матрицы в диагональном порядке.

Пример:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,4,7,5,3,6,8,9]

👨‍💻 Алгоритм:

1⃣Инициализация и подготовка
Проверьте, пуста ли матрица. Инициализируйте переменные для хранения размеров матрицы. Создайте массив result для хранения окончательных результатов и временный список intermediate для промежуточных значений диагоналей.

2⃣Итерация по диагоналям
Внешний цикл для прохождения по всем диагоналям. Головы диагоналей находятся в первой строке и последнем столбце. Внутренний цикл для итерации по элементам каждой диагонали. Индексы элементов диагонали изменяются до выхода за пределы матрицы.

3⃣Обработка диагоналей
Для каждой диагонали сохраните её элементы в списке intermediate. Переверните элементы диагонали, если её номер чётный. Добавьте элементы диагонали в массив result.

😎 Решение:

class Solution {
    function findDiagonalOrder($mat) {
        if (empty($mat) || empty($mat[0])) return [];
        $N = count($mat);
        $M = count($mat[0]);
        $result = [];
        
        for ($d = 0; $d < $N + $M - 1; $d++) {
            $intermediate = [];
            $r = $d < $M ? 0 : $d - $M + 1;
            $c = $d < $M ? $d : $M - 1;
            
            while ($r < $N && $c >= 0) {
                $intermediate[] = $mat[$r][$c];
                $r++;
                $c--;
            }
            
            if ($d % 2 == 0) {
                $intermediate = array_reverse($intermediate);
            }
            $result = array_merge($result, $intermediate);
        }
        
        return $result;
    }
}

Ставь 👍👍 и забирай 📚 📚 Базу знанийБазу знаний

Задача: 154. Find Minimum in Rotated Sorted Array II
Сложность: Hard

Предположим, что массив длиной n, отсортированный в порядке возрастания, повернут от 1 до n раз. Например, массив nums = [0,1,4,4,5,6,7] может стать:
[4,5,6,7,0,1,4], если он был повернут 4 раза.
[0,1,4,4,5,6,7], если он был повернут 7 раз.
Обратите внимание, что поворот массива [a[0], a[1], a[2], ..., a[n-1]] 1 раз приводит к массиву [a[n-1], a[0], a[1], a[2], ..., a[n-2]].
Для данного отсортированного и повернутого массива nums, который может содержать дубликаты, верните минимальный элемент этого массива.
Необходимо максимально уменьшить количество операций.

Пример:

Input: nums = [1,3,5]
Output: 1

👨‍💻 Алгоритм:

1⃣Сравнение с правой границей:
В классическом бинарном поиске мы бы сравнивали элемент в середине (nums[mid]) с искомым значением. В нашем случае мы сравниваем его с элементом, на который указывает правый указатель (nums[high]).

2⃣Обновление указателей:
Если элемент в середине находится в той же половине массива, что и элемент на правой границе (nums[mid] > nums[high]), минимальный элемент должен находиться в левой половине от mid. Следовательно, сдвигаем правый указатель на позицию mid.
Если nums[mid] < nums[high], это указывает, что минимальный элемент находится в правой половине или равен mid. Сдвигаем правый указатель на mid.
Если nums[mid] == nums[high], мы не можем быть уверены, в какой половине находится минимальный элемент из-за наличия дубликатов. В этом случае безопасно сдвинуть правый указатель на один шаг влево (high = high - 1), чтобы сузить область поиска без пропуска возможного минимального элемента.

3⃣Итерация до сужения диапазона поиска:
Продолжаем процесс, пока левый указатель не встретится с правым. В конечном итоге правый указатель укажет на минимальный элемент массива после всех поворотов.

😎 Решение:

class Solution {
    function findMin($nums) {
        $low = 0;
        $high = count($nums) - 1;
        
        while ($low < $high) {
            $pivot = $low + intdiv($high - $low, 2);
            if ($nums[$pivot] < $nums[$high]) {
                $high = $pivot;
            } else if ($nums[$pivot] > $nums[$high]) {
                $low = $pivot + 1;
            } else {
                $high -= 1;
            }
        }
        return $nums[$low];
    }
}

Ставь 👍👍 и забирай 📚 📚 Базу знанийБазу знаний

Задача: 968. Binary Tree Cameras
Сложность: hard

Вам дан корень бинарного дерева. Мы устанавливаем камеры на узлы дерева, где каждая камера на узле может наблюдать за своим родителем, собой и своими непосредственными детьми.

Верните минимальное количество камер, необходимых для наблюдения за всеми узлами дерева.

Пример:

Input: root = [0,0,null,0,null,0,null,null,0]
Output: 2
Explanation: At least two cameras are needed to monitor all nodes of the tree. The above image shows one of the valid configurations of camera placement.

👨‍💻 Алгоритм:

1⃣Рекурсивное решение (solve):
Для каждого узла определите три состояния:
- [State 0] Строгое поддерево: все узлы ниже этого узла покрыты, но не сам узел.
- [State 1] Нормальное поддерево: все узлы ниже и включая этот узел покрыты, но на этом узле нет камеры.
- [State 2] Установленная камера: все узлы ниже и включая этот узел покрыты, и на этом узле установлена камера.
Рассчитайте эти состояния для левого и правого поддеревьев.

2⃣Рассчёт состояний:
Чтобы покрыть строгое поддерево, дети этого узла должны находиться в состоянии 1.
Чтобы покрыть нормальное поддерево без установки камеры на этом узле, дети этого узла должны находиться в состояниях 1 или 2, и по крайней мере один из этих детей должен быть в состоянии 2.
Чтобы покрыть поддерево при установке камеры на этом узле, дети могут находиться в любом состоянии.

3⃣Минимальное количество камер:
Запустите функцию solve на корневом узле и верните минимальное значение между состояниями 1 и 2.

😎 Решение:

class Solution {
    function minCameraCover($root) {
        $ans = $this->solve($root);
        return min($ans[1], $ans[2]);
    }

    private function solve($node) {
        if ($node == null) {
            return [0, 0, 99999];
        }

        $L = $this->solve($node->left);
        $R = $this->solve($node->right);
        $mL12 = min($L[1], $L[2]);
        $mR12 = min($R[1], $R[2]);

        $d0 = $L[1] + $R[1];
        $d1 = min($L[2] + $mR12, $R[2] + $mL12);
        $d2 = 1 + min($L[0], $mL12) + min($R[0], $mR12);
        return [$d0, $d1, $d2];
    }
}

Ставь 👍👍 и забирай 📚 📚 Базу знанийБазу знаний

Задача: 103. Binary Tree Zigzag Level Order Traversal
Сложность: medium

Дан корень бинарного дерева. Верните обход узлов дерева по уровням в виде зигзага (то есть слева направо, затем справа налево для следующего уровня и чередуйте далее).

Пример:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]

👨‍💻 Алгоритм:

1⃣Мы также можем реализовать поиск в ширину (BFS) с использованием одного цикла. Трюк заключается в том, что мы добавляем узлы для посещения в очередь, а узлы разных уровней разделяем с помощью какого-то разделителя (например, пустого узла). Разделитель отмечает конец уровня, а также начало нового уровня.

2⃣Здесь мы принимаем второй подход, описанный выше. Можно начать с обычного алгоритма BFS, к которому мы добавляем элемент порядка зигзага с помощью deque (двусторонней очереди).

3⃣Для каждого уровня мы начинаем с пустого контейнера deque, который будет содержать все значения данного уровня. В зависимости от порядка каждого уровня, т.е. либо слева направо, либо справа налево, мы решаем, с какого конца deque добавлять новый элемент.

😎 Решение:

class TreeNode {
    public $val;
    public $left;
    public $right;

    public function __construct($val, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

class Solution {
    function zigzagLevelOrder($root) {
        $result = [];
        if ($root === null) {
            return $result;
        }

        $nodeQueue = new SplQueue();
        $nodeQueue->enqueue($root);
        $nodeQueue->enqueue(null);
        $isOrderLeft = true;
        $levelList = [];

        while (!$nodeQueue->isEmpty()) {
            $currentNode = $nodeQueue->dequeue();

            if ($currentNode !== null) {
                if ($isOrderLeft) {
                    $levelList[] = $currentNode->val;
                } else {
                    array_unshift($levelList, $currentNode->val);
                }

                if ($currentNode->left !== null) {
                    $nodeQueue->enqueue($currentNode->left);
                }
                if ($currentNode->right !== null) {
                    $nodeQueue->enqueue($currentNode->right);
                }
            } else {
                $result[] = $levelList;
                $levelList = [];
                if (!$nodeQueue->isEmpty()) {
                    $nodeQueue->enqueue(null);
                }
                $isOrderLeft = !$isOrderLeft;
            }
        }

        return $result;
    }
}

Ставь 👍👍 и забирай 📚 📚 Базу знанийБазу знаний

Задача: 1026. Maximum Difference Between Node and Ancestor
Сложность: medium

Учитывая корень бинарного дерева, найдите максимальное значение v, для которого существуют различные вершины a и b, где v = |a.val - b.val| и a является предком b. Вершина a является предком b, если: любой ребенок a равен b или любой ребенок a является предком b.

Пример:

Input: root = [8,3,10,1,6,null,14,null,null,4,7,13]
Output: 7

👨‍💻 Алгоритм:

1⃣Рекурсивный обход дерева:
Используйте рекурсивную функцию для обхода дерева. Передавайте минимальное и максимальное значения, встреченные на пути от корня к текущему узлу.

2⃣Обновление максимальной разницы:
При посещении каждого узла обновляйте минимальное и максимальное значения. Вычисляйте разницу между текущим значением узла и минимальным и максимальным значениями на пути. Обновляйте максимальную разницу, если текущая разница больше.

3⃣Рекурсивный вызов для детей:
Рекурсивно вызывайте функцию для левого и правого поддерева, передавая обновленные минимальное и максимальное значения.

😎 Решение:

class TreeNode {
    public $val = 0;
    public $left = null;
    public $right = null;
    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

class Solution {
    function maxAncestorDiff($root) {
        return $this->dfs($root, $root->val, $root->val);
    }
    
    private function dfs($node, $minVal, $maxVal) {
        if ($node === null) return $maxVal - $minVal;
        $minVal = min($minVal, $node->val);
        $maxVal = max($maxVal, $node->val);
        $left = $this->dfs($node->left, $minVal, $maxVal);
        $right = $this->dfs($node->right, $minVal, $maxVal);
        return max($left, $right);
    }
}

Ставь 👍👍 и забирай 📚 📚 Базу знанийБазу знаний

Задача: 753. Cracking the Safe
Сложность: medium

Имеется сейф, защищенный паролем. Пароль представляет собой последовательность из n цифр, каждая из которых может находиться в диапазоне [0, k - 1]. Сейф имеет особый способ проверки пароля. Например, правильный пароль - "345", а вы вводите "012345": после ввода 0 последние 3 цифры - "0", что неверно. После ввода 1 последние 3 цифры - "01", что неверно. После ввода 2 последние 3 цифры - "012", что неверно.
После ввода 3 последние 3 цифры - "123", что неверно. После ввода 4 последние 3 цифры - "234", что неверно. После ввода 5 последние 3 цифры - "345", что верно, и сейф разблокируется. Верните любую строку минимальной длины, которая разблокирует сейф на определенном этапе ввода.

Пример:

Input: n = 1, k = 2
Output: "10"

👨‍💻 Алгоритм:

1⃣Создайте граф, где каждая вершина представляет собой строку длины n-1, а каждое ребро между двумя вершинами представляет собой добавление одной из цифр из диапазона [0, k-1].

2⃣Используйте алгоритм Эйлерова пути или цикла для нахождения пути, который проходит через каждое ребро ровно один раз.

3⃣Составьте итоговую строку, которая включает начальную вершину и все добавленные цифры.

😎 Решение:

function crackSafe($n, $k) {
    $seen = [];
    $result = [];

    function dfs($node, $k, &$seen, &$result) {
        for ($x = 0; $x < $k; $x++) {
            $neighbor = $node . $x;
            if (!in_array($neighbor, $seen)) {
                $seen[] = $neighbor;
                dfs(substr($neighbor, 1), $k, $seen, $result);
                $result[] = $x;
            }
        }
    }

    $startNode = str_repeat("0", $n - 1);
    dfs($startNode, $k, $seen, $result);

    return $startNode . implode('', $result);
}

Ставь 👍👍 и забирай 📚 📚 Базу знанийБазу знаний

Сложность: medium
Задача: 1428. Leftmost Column with at Least a One

Строково-отсортированная бинарная матрица означает, что все элементы равны 0 или 1, и каждая строка матрицы отсортирована в неубывающем порядке.
Дана строково-отсортированная бинарная матрица binaryMatrix, верните индекс (начиная с 0) самого левого столбца, содержащего 1. Если такого индекса не существует, верните -1.
Вы не можете напрямую обращаться к бинарной матрице. Вы можете получить доступ к матрице только через интерфейс BinaryMatrix:
- BinaryMatrix.get(row, col) возвращает элемент матрицы с индексом (row, col) (начиная с 0).
- BinaryMatrix.dimensions() возвращает размеры матрицы в виде списка из 2 элементов [rows, cols], что означает, что матрица имеет размер rows x cols.

Отправки, делающие более 1000 вызовов к BinaryMatrix.get, будут оценены как неправильный ответ. Кроме того, любые решения, пытающиеся обойти проверку, будут дисквалифицированы.

Для пользовательского тестирования вводом будет вся бинарная матрица mat. Вы не будете иметь прямого доступа к бинарной матрице.

Пример:

Input: mat = [[0,0],[0,1]]
Output: 1

👨‍💻 Алгоритм:

1⃣Инициализируйте указатели на текущую строку и столбец, начиная с верхнего правого угла матрицы.

2⃣Повторяйте поиск до тех пор, пока указатели не выйдут за границы матрицы:
Если текущий элемент равен 0, сдвигайте указатель строки вниз.
Если текущий элемент равен 1, сдвигайте указатель столбца влево.

3⃣Если указатель столбца остается на последнем столбце, значит, все элементы матрицы равны 0, и верните -1. В противном случае верните индекс самого левого столбца с 1.

😎 Решение:

class Solution {
    function leftMostColumnWithOne($binaryMatrix) {
        list($rows, $cols) = $binaryMatrix->dimensions();
        $currentRow = 0;
        $currentCol = $cols - 1;
        
        while ($currentRow < $rows && $currentCol >= 0) {
            if ($binaryMatrix->get($currentRow, $currentCol) == 0) {
                $currentRow++;
            } else {
                $currentCol--;
            }
        }
        
        return ($currentCol == $cols - 1) ? -1 : $currentCol + 1;
    }
}

Ставь 👍👍 и забирай 📚 📚 Базу знанийБазу знаний

Задача: 923. 3Sum With Multiplicity
Сложность: medium

Если задан целочисленный массив arr и целое число target, верните количество кортежей i, j, k, таких, что i < j < k и arr[i] + arr[j] + arr[k] == target. Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7.

Пример:

Input: arr = [1,1,2,2,3,3,4,4,5,5], target = 8
Output: 20

👨‍💻 Алгоритм:

1⃣Отсортировать массив arr.

2⃣Инициализировать счетчик для количества кортежей.
Пройти по массиву тремя указателями i, j, и k:
Для каждого i, установить j на i + 1, и k на конец массива.
Использовать двухуказательный метод для нахождения пар (j, k), таких что arr[i] + arr[j] + arr[k] == target.

3⃣Вернуть результат по модулю 10^9 + 7.

😎 Решение:

function threeSumMulti($arr, $target) {
    sort($arr);
    $MOD = 1_000_000_007;
    $count = 0;
    
    for ($i = 0; $i < count($arr); $i++) {
        $j = $i + 1;
        $k = count($arr) - 1;
        while ($j < $k) {
            $sum = $arr[$i] + $arr[$j] + $arr[$k];
            if ($sum == $target) {
                if ($arr[$j] == $arr[$k]) {
                    $count += ($k - $j + 1) * ($k - $j) / 2;
                    break;
                } else {
                    $left = 1;
                    $right = 1;
                    while ($j + 1 < $k && $arr[$j] == $arr[$j + 1]) {
                        $left++;
                        $j++;
                    }
                    while ($k - 1 > $j && $arr[$k] == $arr[$k - 1]) {
                        $right++;
                        $k--;
                    }
                    $count += $left * $right;
                    $j++;
                    $k--;
                }
            } elseif ($sum < $target) {
                $j++;
            } else {
                $k--;
            }
        }
    }
    
    return $count % $MOD;
}

Ставь 👍👍 и забирай 📚 📚 Базу знанийБазу знаний

Задача: 897. Increasing Order Search Tree
Сложность: easy

Задав корень дерева двоичного поиска, перестройте дерево по порядку так, чтобы самый левый узел дерева теперь был корнем дерева, а каждый узел не имел левого и только одного правого дочернего узла.

Пример:

Input: root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

👨‍💻 Алгоритм:

1⃣Выполнить обход дерева в порядке in-order, чтобы получить список узлов.

2⃣Перестроить дерево, устанавливая каждый узел из списка как правый дочерний элемент предыдущего узла и устанавливая левые дочерние элементы в null.

3⃣Вернуть новый корень дерева (первый элемент списка).

😎 Решение:

class TreeNode {
    public $val;
    public $left;
    public $right;
    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

function increasingBST($root) {
    $nodes = [];
    
    function inorder($node, &$nodes) {
        if ($node === null) return;
        inorder($node->left, $nodes);
        $nodes[] = $node;
        inorder($node->right, $nodes);
    }
    
    inorder($root, $nodes);
    
    for ($i = 0; $i < count($nodes) - 1; $i++) {
        $nodes[$i]->left = null;
        $nodes[$i]->right = $nodes[$i + 1];
    }
    
    $nodes[count($nodes) - 1]->left = null;
    $nodes[count($nodes) - 1]->right = null;
    return $nodes[0];
}

Ставь 👍👍 и забирай 📚 📚 Базу знанийБазу знаний