PHP | LeetCode
Open in Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
Show more
Network:1 355
Subscribers
No data24 hours
-67 days
-930 days
Posts Archive
1 355
Задача: 1178. Number of Valid Words for Each PuzzleHardTopicsHint
Сложность: hard
Относительно заданной строки-головоломки, слово является допустимым, если выполняются оба следующих условия:
Слово содержит первую букву головоломки.
Каждая буква в слове присутствует в головоломке.
Например, если головоломка "abcdefg", то допустимыми словами являются "faced", "cabbage" и "baggage", а недопустимыми словами являются "beefed" (не включает 'a') и "based" (включает 's', которой нет в головоломке).
Верните массив answer, где answer[i] - это количество слов в данном списке слов words, которые допустимы относительно головоломки puzzles[i].
Пример:
Input: words = ["apple","pleas","please"], puzzles = ["aelwxyz","aelpxyz","aelpsxy","saelpxy","xaelpsy"]
Output: [0,1,3,2,0]class Solution {
private function bitmask($word) {
$mask = 0;
for ($i = 0; $i < strlen($word); $i++) {
$mask |= 1 << (ord($word[$i]) - ord('a'));
}
return $mask;
}
function findNumOfValidWords($words, $puzzles) {
$wordCount = [];
foreach ($words as $word) {
$mask = $this->bitmask($word);
if (!isset($wordCount[$mask])) {
$wordCount[$mask] = 0;
}
$wordCount[$mask]++;
}
$result = [];
foreach ($puzzles as $puzzle) {
$first = 1 << (ord($puzzle[0]) - ord('a'));
$count = isset($wordCount[$first]) ? $wordCount[$first] : 0;
$mask = $this->bitmask(substr($puzzle, 1));
for ($submask = $mask; $submask > 0; $submask = ($submask - 1) & $mask) {
$count += isset($wordCount[$submask | $first]) ? $wordCount[$submask | $first] : 0;
}
$result[] = $count;
}
return $result;
}
}1 355
Задача: 415. Add Strings
Сложность: easy
Если задан целочисленный массив nums, верните третье максимальное число в этом массиве. Если третьего максимального числа не существует, верните максимальное число.
Пример:
Input: num1 = "11", num2 = "123" Output: "134"👨💻 Алгоритм: 1⃣Инициализируйте три переменные для хранения первого, второго и третьего максимальных чисел. 2⃣Пройдите по массиву nums, обновляя переменные первого, второго и третьего максимальных чисел, избегая дубликатов. 3⃣Верните третье максимальное число, если оно существует, иначе верните первое максимальное число. 😎 Решение:
function thirdMax($nums) {
$first = null;
$second = null;
$third = null;
foreach ($nums as $num) {
if ($num === $first || $num === $second || $num === $third) {
continue;
}
if ($first === null || $num > $first) {
$third = $second;
$second = $first;
$first = $num;
} elseif ($second === null || $num > $second) {
$third = $second;
$second = $num;
} elseif ($third === null || $num > $third) {
$third = $num;
}
}
return $third !== null ? $third : $first;
}1 355
Задача: 532. K-diff Pairs in an Array
Сложность: medium
Дан массив целых чисел nums и целое число k. Верните количество уникальных пар с разницей k в массиве.
Пара с разницей k — это пара целых чисел (nums[i], nums[j]), для которой выполняются следующие условия:
0 <= i, j < nums.length
i != j
|nums[i] - nums[j]| == k
Обратите внимание, что |val| обозначает абсолютное значение val.
Пример:
Input: nums = [3,1,4,1,5], k = 2 Output: 2 Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5). Although we have two 1s in the input, we should only return the number of unique pairs.👨💻 Алгоритм: 1⃣Создайте частотный хэш-словарь для подсчета количества каждого уникального числа в массиве nums. 2⃣Для каждого ключа в хэш-словаре проверьте, можно ли найти пару, удовлетворяющую условиям: Если k > 0, проверьте, существует ли ключ, равный x + k. Если k == 0, проверьте, есть ли более одного вхождения x. 3⃣Увеличьте счётчик результатов, если условие выполняется. 😎 Решение:
class Solution {
function findPairs($nums, $k) {
$counter = [];
foreach ($nums as $num) {
if (!isset($counter[$num])) {
$counter[$num] = 0;
}
$counter[$num]++;
}
$result = 0;
foreach ($counter as $x => $val) {
if ($k > 0) {
if (isset($counter[$x + $k])) {
$result++;
}
} else if ($k == 0 && $val > 1) {
$result++;
}
}
return $result;
}
}1 355
Задача: 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;
}
}1 355
Задача: 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;
}
}1 355
Задача: 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;
}1 355
Задача: 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;
}1 355
Задача: 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].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;
}
}1 355
Задача: 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);
}
}1 355
Задача: 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;
}
}1 355
Задача: 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;
}
}1 355
Задача: 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;
}
}1 355
Задача: 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 "";
}
}1 355
Задача: 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;
}
}1 355
Задача: 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];
}
}1 355
Задача: 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];
}
}1 355
Задача: 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;
}
}1 355
Задача: 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: 7class 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);
}
}1 355
📺 Уникальная база IT собеседований
456+ реальных собеседований на программиста, тестировщика, аналитика и прочие IT профы.
Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д.
🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!
1 355
Задача: 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);
}