现已上线！2025 年 Telegram 研究 — 年度关键洞察 
PHP | LeetCode
前往频道在 Telegram
Cайт easyoffer.ru Реклама @easyoffer_adv ВП @easyoffer_vp Тесты t.me/+pSDoLEZBQRZlNmFi Вопросы собесов t.me/+RJaDhjYaQDo2Njcy Вакансии t.me/+J-DKRUtjUgMxZGNi
显示更多1 387
订阅者
+224 小时
+47 天
-930 天
帖子存档
1 386
Задача: 657. Robot Return to Origin
Сложность: easy
На плоскости с координатами (0, 0) находится робот. Дана последовательность его движений, определите, возвращается ли робот в исходную точку (0, 0) после завершения всех своих движений.
Вам дана строка moves, представляющая последовательность движений робота, где moves[i] представляет его i-ое движение. Допустимые движения: 'R' (вправо), 'L' (влево), 'U' (вверх) и 'D' (вниз).
Верните true, если робот возвращается в исходную точку после завершения всех своих движений, или false в противном случае.
Примечание: направление, в котором "смотрит" робот, не имеет значения. 'R' всегда будет перемещать робота на один шаг вправо, 'L' всегда будет перемещать его на один шаг влево и т.д. Также предполагается, что величина перемещения робота одинакова для каждого хода.
Пример:
Input: moves = "UD" Output: true👨💻 Алгоритм: 1⃣Инициализация координат: Начните с координат (0, 0). 2⃣Обработка движений: Пройдите по строке moves и обновляйте координаты в зависимости от движения: 'R' увеличивает координату x на 1. 'L' уменьшает координату x на 1. 'U' увеличивает координату y на 1. 'D' уменьшает координату y на 1. 3⃣Проверка конечных координат: Если после всех движений координаты снова равны (0, 0), верните true. В противном случае, верните false. 😎 Решение:
class Solution {
function judgeCircle($moves) {
$x = 0;
$y = 0;
for ($i = 0; $i < strlen($moves); $i++) {
switch ($moves[$i]) {
case 'R': $x++; break;
case 'L': $x--; break;
case 'U': $y++; break;
case 'D': $y--; break;
}
}
return $x == 0 && $y == 0;
}
}1 386
Задача: 1437. Check If All 1's Are at Least Length K Places Away
Сложность: easy
Дан бинарный массив nums и целое число k. Вернуть true, если все единицы находятся на расстоянии не менее k позиций друг от друга, в противном случае вернуть false.
Пример:
Input: nums = [1,0,0,0,1,0,0,1], k = 2 Output: true Explanation: Each of the 1s are at least 2 places away from each other.👨💻 Алгоритм: 1⃣Инициализировать счетчик нулей значением k для учета первого появления единицы. 2⃣Итерировать по массиву nums, проверяя, если текущий элемент равен 1. Если число нулей между единицами меньше k, вернуть false; иначе сбросить счетчик нулей на 0. 3⃣Если текущий элемент равен 0, увеличить счетчик нулей. В конце итерации вернуть true. 😎 Решение:
class Solution {
function kLengthApart($nums, $k) {
$count = $k;
foreach ($nums as $num) {
if ($num == 1) {
if ($count < $k) {
return false;
}
$count = 0;
} else {
$count++;
}
}
return true;
}
}1 386
📺 База 1000+ реальных собеседований
На программиста, тестировщика, аналитика, проджекта и другие IT профы.
Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д.
🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!
1 386
Задача: 82. Remove Duplicates from Sorted List II
Сложность: medium
Дана голова отсортированного связного списка. Удалите все узлы, содержащие повторяющиеся числа, оставив только уникальные числа из исходного списка. Верните отсортированный связный список.
Пример:
Input: head = [1,2,3,3,4,4,5] Output: [1,2,5]👨💻 Алгоритм: 1⃣Инициализация "стража" и предшественника: Создается фиктивный начальный узел sentinel, который указывает на начало связного списка. Это делается для удобства управления указателем на начало списка, особенно если первые несколько узлов могут быть удалены. Устанавливаем предшественника pred, который будет последним узлом перед потенциально дублирующимися узлами. Изначально предшественником назначается страж. 2⃣Проход по списку с проверкой на дубликаты: Итерируемся по списку начиная с головы head. На каждом шаге проверяем, есть ли дублирующиеся узлы, сравнивая текущий узел head.val с следующим head.next.val. Если узлы дублируются, то пропускаем все последующие дубликаты, перемещая указатель head до последнего дублированного узла. После этого предшественник pred соединяется с первым узлом после всех дубликатов pred.next = head.next, тем самым пропуская весь блок дублированных узлов. 3⃣Переход к следующему узлу и возврат результата: Если текущий узел не имел дубликатов, просто переводим предшественника pred на следующий узел. Двигаем указатель head на следующий узел в списке. После завершения цикла возвращаем список, начиная с узла, на который указывает sentinel.next, что позволяет исключить все дублирующиеся узлы и вернуть начало нового списка без дубликатов. 😎 Решение:
class ListNode {
public $val = 0;
public $next = null;
public function __construct($val = 0, $next = null) {
$this->val = $val;
$this->next = $next;
}
}
function deleteDuplicates($head) {
$sentinel = new ListNode(0, $head);
$pred = $sentinel;
while ($head !== null) {
if ($head->next !== null && $head->val === $head->next->val) {
while ($head->next !== null && $head->val === $head->next->val) {
$head = $head->next;
}
$pred->next = $head->next;
} else {
$pred = $pred->next;
}
$head = $head->next;
}
return $sentinel->next;
}
?>1 386
Задача: 988. Smallest String Starting From Leaf
Сложность: medium
Дан корень бинарного дерева, где каждый узел имеет значение в диапазоне [0, 25], представляющее буквы от 'a' до 'z'.
Верните лексикографически наименьшую строку, которая начинается с листа этого дерева и заканчивается у корня.
Напоминаем, что любая более короткая префиксная строка является лексикографически меньшей.
Например, "ab" лексикографически меньше, чем "aba".
Лист узла - это узел, у которого нет потомков.
Пример:
Input: root = [0,1,2,3,4,3,4] Output: "dba"👨💻 Алгоритм: 1⃣Инициализация и подготовка: Создайте переменную ans и установите ее значение как максимальное возможное (например, "~" для строк). Определите вспомогательную функцию dfs, которая будет выполнять обход дерева в глубину (DFS), принимая текущий узел и путь как аргументы. 2⃣Обход дерева: Если текущий узел пуст (null), просто вернитесь из функции. Добавьте текущий символ (соответствующий значению узла) в начало строки пути. Если текущий узел является листом (не имеет потомков), сравните текущий путь с ans и обновите ans, если текущий путь лексикографически меньше. Рекурсивно вызовите dfs для левого и правого потомков текущего узла. 3⃣Возврат результата: Вызовите функцию dfs с корневым узлом и пустым путем. Верните значение переменной ans, содержащее лексикографически наименьший путь от листа до корня. 😎 Решение:
class Solution {
private $ans = "~";
function smallestFromLeaf($root) {
$this->dfs($root, "");
return $this->ans;
}
private function dfs($node, $path) {
if ($node === null) return;
$path = chr($node->val + ord('a')) . $path;
if ($node->left === null && $node->right === null) {
if (strcmp($path, $this->ans) < 0) {
$this->ans = $path;
}
}
$this->dfs($node->left, $path);
$this->dfs($node->right, $path);
}
}1 386
Задача: 1669. Merge In Between Linked Lists
Сложность: medium
Вам даны два связанных списка: list1 и list2 размером n и m соответственно.
Удалите узлы list1 с ath узла по bth узел и вставьте на их место list2.
Синие ребра и узлы на рисунке в вверху поста указывают на результат:
Пример:
Input: list1 = [10,1,13,6,9,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
Output: [10,1,13,1000000,1000001,1000002,5]
Explanation: We remove the nodes 3 and 4 and put the entire list2 in their place. The blue edges and nodes in the above figure indicate the result.class Solution {
function mergeInBetween($list1, $a, $b, $list2) {
$mergeArray = [];
$index = 0;
$current1 = $list1;
while ($index < $a) {
$mergeArray[] = $current1->val;
$current1 = $current1->next;
$index++;
}
$current2 = $list2;
while ($current2 !== null) {
$mergeArray[] = $current2->val;
$current2 = $current2->next;
}
while ($index < $b + 1) {
$current1 = $current1->next;
$index++;
}
while ($current1 !== null) {
$mergeArray[] = $current1->val;
$current1 = $current1->next;
}
$resultList = null;
for ($i = count($mergeArray) - 1; $i >= 0; $i--) {
$resultList = new ListNode($mergeArray[$i], $resultList);
}
return $resultList;
}
}1 386
Задача: 437. Path Sum III
Сложность: medium
Дан корень бинарного дерева и целое число targetSum, вернуть количество путей, где сумма значений вдоль пути равна targetSum.
Путь не обязательно должен начинаться или заканчиваться в корне или на листе, но он должен идти вниз (т.е. перемещаться только от родительских узлов к дочерним).
Пример:
Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8 Output: 3 Explanation: The paths that sum to 8 are shown.👨💻 Алгоритм: 1⃣Инициализируем счетчик путей в дереве count = 0 и хеш-таблицу h, где ключ - это префиксная сумма, а значение - сколько раз она встречалась. Выполним рекурсивный обход дерева в порядке preorder: узел -> левый -> правый. Функция preorder(node: TreeNode, curr_sum: int) принимает два аргумента: узел дерева и префиксную сумму перед этим узлом. Чтобы запустить рекурсию, вызовем preorder(root, 0). 2⃣Сначала обновим текущую префиксную сумму, добавив значение текущего узла: curr_sum += node.val. Теперь можно обновить счетчик. Рассмотрим две ситуации. В первой ситуации путь в дереве с целевой суммой начинается с корня. Это означает, что текущая префиксная сумма равна целевой сумме curr_sum == k, поэтому увеличиваем счетчик на 1: count += 1. Во второй ситуации путь с целевой суммой начинается где-то ниже. Это означает, что нужно добавить к счетчику количество раз, когда мы видели префиксную сумму curr_sum - target: count += h[curr_sum - target]. 3⃣Логика проста: текущая префиксная сумма - это curr_sum, а несколько элементов назад префиксная сумма была curr_sum - target. Все элементы между ними суммируются до curr_sum - (curr_sum - target) = target. Теперь обновим хеш-таблицу: h[curr_sum] += 1. Проанализируем левое и правое поддеревья: preorder(node.left, curr_sum), preorder(node.right, curr_sum). После обработки текущего поддерева удалим текущую префиксную сумму из хеш-таблицы, чтобы не смешивать параллельные поддеревья: h[curr_sum] -= 1. Когда обход в порядке preorder завершен, счетчик обновлен. Вернем его. 😎 Решение:
class Solution {
function pathSum($root, $sum) {
$count = 0;
$k = $sum;
$h = [];
$preorder = function($node, $curr_sum) use (&$preorder, &$count, &$h, $k) {
if (!$node) return;
$curr_sum += $node->val;
if ($curr_sum == $k) {
$count++;
}
$count += $h[$curr_sum - $k] ?? 0;
$h[$curr_sum] = ($h[$curr_sum] ?? 0) + 1;
$preorder($node->left, $curr_sum);
$preorder($node->right, $curr_sum);
$h[$curr_sum]--;
};
$preorder($root, 0);
return $count;
}
}1 386
Задача: 258. Add Digits
Сложность: easy
Дано целое число num. Повторно складывайте все его цифры, пока результат не станет однозначным, и верните его.
Пример:
Input: num = 38 Output: 2 Explanation: The process is 38 --> 3 + 8 --> 11 11 --> 1 + 1 --> 2 Since 2 has only one digit, return it.👨💻 Алгоритм: 1⃣Инициализируйте переменную digital_root значением 0. 2⃣В цикле, пока num больше 0: Добавьте к digital_root последнюю цифру num. Уменьшите num, удалив последнюю цифру. Если num равно 0 и digital_root больше 9, присвойте num значение digital_root и сбросьте digital_root в 0. 3⃣Верните значение digital_root. 😎 Решение:
class Solution {
function addDigits($num) {
$digital_root = 0
while ($num > 0) {
$digital_root += $num % 10
$num = intdiv($num, 10)
if ($num == 0 && $digital_root > 9) {
$num = $digital_root
$digital_root = 0
}
}
return $digital_root
}
}1 386
Задача: 419. Battleships in a Board
Сложность: medium
Если задана матричная доска размером m x n, где каждая клетка - линкор 'X' или пустая '.', верните количество линкоров на доске. Линкоры могут располагаться на доске только горизонтально или вертикально. Другими словами, они могут быть выполнены только в форме 1 x k (1 строка, k столбцов) или k x 1 (k строк, 1 столбец), где k может быть любого размера. Между двумя линкорами есть хотя бы одна горизонтальная или вертикальная клетка (т. е. нет соседних линкоров).
Пример:
Input: board = [["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]] Output: 2👨💻 Алгоритм: 1⃣Пройдите по каждой клетке матрицы. 2⃣Если текущая клетка содержит 'X' и она не является продолжением линкора (т.е. не имеет 'X' сверху или слева), увеличьте счетчик линкоров. 3⃣Верните итоговый счетчик. 😎 Решение:
function countBattleships($board) {
$m = count($board);
$n = count($board[0]);
$count = 0;
for ($i = 0; $i < $m; $i++) {
for ($j = 0; $j < $n; $j++) {
if ($board[$i][$j] == 'X') {
if (($i == 0 || $board[$i-1][$j] != 'X') && ($j == 0 || $board[$i][$j-1] != 'X')) {
$count++;
}
}
}
}
return $count;
}1 386
Задача: 986. Interval List Intersections
Сложность: medium
Вам даны два списка закрытых интервалов, firstList и secondList, где firstList[i] = [starti, endi] и secondList[j] = [startj, endj]. Каждый список интервалов является попарно непересекающимся и отсортированным.
Верните пересечение этих двух списков интервалов.
Закрытый интервал [a, b] (где a <= b) обозначает множество действительных чисел x с a <= x <= b.
Пересечение двух закрытых интервалов - это множество действительных чисел, которые либо пусты, либо представлены как закрытый интервал. Например, пересечение [1, 3] и [2, 4] равно [2, 3].
Пример:
Input: firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]] Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]👨💻 Алгоритм: 1⃣Инициализация указателей: Завести два указателя i и j, указывающие на начало firstList и secondList соответственно. 2⃣Поиск пересечений: Пока оба указателя находятся в пределах своих списков, выполнить следующие действия: Найти максимальное начало и минимальный конец текущих интервалов. Если начало меньше или равно концу, добавить пересечение в результат. Сдвинуть указатель списка, у которого текущий интервал заканчивается раньше. 3⃣Возврат результата: Вернуть список пересечений. 😎 Решение:
class Solution {
function intervalIntersection($firstList, $secondList) {
$i = 0;
$j = 0;
$result = [];
while ($i < count($firstList) && $j < count($secondList)) {
$start = max($firstList[$i][0], $secondList[$j][0]);
$end = min($firstList[$i][1], $secondList[$j][1]);
if ($start <= $end) {
$result[] = [$start, $end];
}
if ($firstList[$i][1] < $secondList[$j][1]) {
$i++;
} else {
$j++;
}
}
return $result;
}
}1 386
Задача: 406. Queue Reconstruction by Height
Сложность: medium
Вам дан массив людей, people, которые являются атрибутами некоторых людей в очереди (не обязательно по порядку). Каждый people[i] = [hi, ki] представляет собой человека ростом hi, перед которым стоят ровно ki других людей, чей рост больше или равен hi. Реконструируйте и верните очередь, представленную входным массивом people. Возвращаемая очередь должна быть отформатирована как массив queue, где queue[j] = [hj, kj] - это атрибуты j-го человека в очереди (queue[0] - человек, находящийся в начале очереди).
Пример:
Input: people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]] Output: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]👨💻 Алгоритм: 1⃣Отсортируйте массив people по убыванию роста hi. Если два человека имеют одинаковый рост, отсортируйте их по возрастанию значения ki. 2⃣Создайте пустой список для результата. Вставляйте каждого человека из отсортированного массива в список на позицию, соответствующую значению ki. 3⃣Верните список результата. 😎 Решение:
function reconstructQueue($people) {
usort($people, function($a, $b) {
return $a[0] === $b[0] ? $a[1] <=> $b[1] : $b[0] <=> $a[0];
});
$result = [];
foreach ($people as $person) {
array_splice($result, $person[1], 0, [$person]);
}
return $result;
}1 386
Задача: 1533. Find the Index of the Large Integer
Сложность: medium
У нас есть целочисленный массив arr, в котором все элементы равны, кроме одного элемента, который больше остальных. Вам не будет предоставлен прямой доступ к массиву, вместо этого у вас будет API ArrayReader, который имеет следующие функции:
int compareSub(int l, int r, int x, int y): где 0 <= l, r, x, y < ArrayReader.length(), l <= r и x <= y. Функция сравнивает сумму подмассива arr[l..r] с суммой подмассива arr[x..y] и возвращает:
1, если arr[l] + arr[l+1] + ... + arr[r] > arr[x] + arr[x+1] + ... + arr[y].
0, если arr[l] + arr[l+1] + ... + arr[r] == arr[x] + arr[x+1] + ... + arr[y].
-1, если arr[l] + arr[l+1] + ... + arr[r] < arr[x] + arr[x+1] + ... + arr[y].
int length(): Возвращает размер массива.
Вам разрешено вызывать compareSub() не более 20 раз. Вы можете предположить, что обе функции работают за O(1) время.
Верните индекс массива arr, который содержит наибольший элемент.
Пример:
Input: arr = [7,7,7,7,10,7,7,7]
Output: 4
Explanation: The following calls to the API
reader.compareSub(0, 0, 1, 1) // returns 0 this is a query comparing the sub-array (0, 0) with the sub array (1, 1), (i.e. compares arr[0] with arr[1]).
Thus we know that arr[0] and arr[1] doesn't contain the largest element.
reader.compareSub(2, 2, 3, 3) // returns 0, we can exclude arr[2] and arr[3].
reader.compareSub(4, 4, 5, 5) // returns 1, thus for sure arr[4] is the largest element in the array.
Notice that we made only 3 calls, so the answer is valid.class Solution {
function getIndex($reader) {
$left = 0;
$length = $reader->length();
while ($length > 1) {
$length = intdiv($length, 2);
$cmp = $reader->compareSub($left, $left + $length - 1, $left + $length, $left + 2 * $length - 1);
if ($cmp == 0) {
return $left + 2 * $length;
}
if ($cmp < 0) {
$left += $length;
}
}
return $left;
}
}1 386
Задача: 106. Construct Binary Tree from Inorder and Postorder Traversal
Сложность: medium
Даны два массива целых чисел: inorder и postorder, где inorder — это массив обхода в глубину бинарного дерева слева направо, а postorder — это массив обхода в глубину после обработки всех потомков узла. Постройте и верните соответствующее бинарное дерево.
Пример:
Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3] Output: [3,9,20,null,null,15,7]👨💻 Алгоритм: 1⃣Создайте хэш-таблицу (hashmap) для хранения соответствия значений и их индексов в массиве обхода inorder. 2⃣Определите вспомогательную функцию
helper, которая принимает границы левой и правой части текущего поддерева в массиве inorder. Эти границы используются для проверки, пусто ли поддерево. Если левая граница больше правой (in_left > in_right), то поддерево пустое и функция возвращает None.
3⃣Выберите последний элемент в массиве обхода postorder в качестве корня. Значение корня имеет индекс index в обходе inorder. Элементы от in_left до index - 1 принадлежат левому поддереву, а элементы от index + 1 до in_right — правому поддереву. Согласно логике обхода postorder, сначала рекурсивно строится правое поддерево helper(index + 1, in_right), а затем левое поддерево helper(in_left, index - 1). Возвращается корень.
😎 Решение:
function buildTree($inorder, $postorder) {
$idx_map = [];
$post_idx = count($postorder) - 1;
$helper = function($in_left, $in_right) use (&$helper, &$postorder, &$idx_map, &$post_idx) {
if ($in_left > $in_right) return null;
$root_val = $postorder[$post_idx];
$root = new TreeNode($root_val);
$index = $idx_map[$root_val];
$post_idx--;
$root->right = $helper($index + 1, $in_right);
$root->left = $helper($in_left, $index - 1);
return $root;
};
foreach ($inorder as $i => $val) {
$idx_map[$val] = $i;
}
return $helper(0, count($inorder) - 1);
}1 386
Repost from easyoffer
⏳ Осталось 20 мест
Акция со скидкой 50% для первых 500 пользователей easyoffer подходит к концу
🔥 Узнай вопросы и задачи с собеседований в конкретных компаниях
🔥 Получи лучшие ответы и видео-примеры от middle/senior специалистов
🔥 Обходи фильтры ATS, добавив топ30 ключевых слов в свое резюме
🔥 Экономь время с помощью автоматических откликов
🔥 Подготовься идеально к интервью с тренажёрами и симуляторами
Успей забрать место по акции: 👉 https://easyoffer.ru/pro
1 386
Задача: 849. Maximize Distance to Closest Person
Сложность: medium
Вам дан массив, представляющий ряд сидений, где seats[i] = 1 означает, что на i-м месте сидит человек, а seats[i] = 0 означает, что i-е место пусто (индексация с нуля).
Есть по крайней мере одно пустое место и по крайней мере один человек, сидящий на месте.
Алекс хочет сесть на такое место, чтобы расстояние между ним и ближайшим к нему человеком было максимальным.
Верните это максимальное расстояние до ближайшего человека.
Пример:
Input: seats = [1,0,0,0,1,0,1] Output: 2 Explanation: If Alex sits in the second open seat (i.e. seats[2]), then the closest person has distance 2. If Alex sits in any other open seat, the closest person has distance 1. Thus, the maximum distance to the closest person is 2.👨💻 Алгоритм: 1⃣Следите за prev, занятым местом слева или на текущей позиции i, и future, занятым местом справа или на текущей позиции i. 2⃣Для каждого пустого места i определите ближайшее занятие места как min(i - prev, future - i), с учетом, что i - prev считается бесконечностью, если слева нет занятого места, и future - i считается бесконечностью, если справа нет занятого места. 3⃣Найдите и верните максимальное расстояние до ближайшего занятого места. 😎 Решение:
class Solution {
/**
* @param Integer[] $seats
* @return Integer
*/
function maxDistToClosest($seats) {
$n = count($seats);
$prev = -1;
$future = 0;
$ans = 0;
for ($i = 0; $i < $n; ++$i) {
if ($seats[$i] == 1) {
$prev = $i;
} else {
while ($future < $n && ($seats[$future] == 0 || $future < $i)) {
$future++;
}
$left = $prev == -1 ? $n : $i - $prev;
$right = $future == $n ? $n : $future - $i;
$ans = max($ans, min($left, $right));
}
}
return $ans;
}
}1 386
Задача: 367. Valid Perfect Square
Сложность: easy
Дано положительное целое число num, вернуть true, если num является идеальным квадратом, или false в противном случае.
Идеальный квадрат — это целое число, являющееся квадратом целого числа. Другими словами, это произведение некоторого целого числа на само себя.
Вы не должны использовать какие-либо встроенные библиотечные функции, такие как sqrt.
Пример:
Input: num = 16 Output: true Explanation: We return true because 4 * 4 = 16 and 4 is an integer.👨💻 Алгоритм: 1⃣Если num < 2, вернуть True. Установить левую границу в 2, а правую границу в num / 2. 2⃣Пока left <= right, взять x = (left + right) / 2, вычислить guess_squared = x * x и сравнить его с num: Если guess_squared == num, вернуть True. Если guess_squared > num, сдвинуть правую границу right = x - 1. В противном случае сдвинуть левую границу left = x + 1. 3⃣Если вышли из цикла, вернуть False. 😎 Решение:
class Solution {
public function isPerfectSquare(int $num): bool {
if ($num < 2) {
return true;
}
$x = intdiv($num, 2);
while ($x * $x > $num) {
$x = intdiv($x + intdiv($num, $x), 2);
}
return $x * $x == $num;
}
}1 386
Задача: 472. Concatenated Words
Сложность: hard
Дан массив строк words (без дубликатов). Верните все составные слова из данного списка слов.
Составное слово определяется как строка, которая полностью состоит как минимум из двух более коротких слов (не обязательно различных) из данного массива.
Пример:
Input: words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"] Output: ["catsdogcats","dogcatsdog","ratcatdogcat"] Explanation: "catsdogcats" can be concatenated by "cats", "dog" and "cats"; "dogcatsdog" can be concatenated by "dog", "cats" and "dog"; "ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat".👨💻 Алгоритм: 1⃣Для каждого слова в списке: Построить неявный граф, в котором узлы представляют индексы символов в слове, а ребра представляют возможность перехода от одного индекса к другому, если подстрока между ними является словом из списка. 2⃣Использовать поиск в глубину (DFS) для проверки, можно ли достигнуть узел с индексом word.length от узла с индексом 0 в графе. 3⃣Если узел word.length достижим от узла 0, добавить слово в ответ. 😎 Решение:
class Solution {
private function dfs($word, $length, &$visited, $dictionary) {
if ($length == strlen($word)) {
return true;
}
if ($visited[$length]) {
return false;
}
$visited[$length] = true;
for ($i = strlen($word) - ($length == 0 ? 1 : 0); $i > $length; $i--) {
if (isset($dictionary[substr($word, $length, $i - $length)]) &&
$this->dfs($word, $i, $visited, $dictionary)) {
return true;
}
}
return false;
}
function findAllConcatenatedWordsInADict($words) {
$dictionary = array_flip($words);
$answer = [];
foreach ($words as $word) {
$visited = array_fill(0, strlen($word), false);
if ($this->dfs($word, 0, $visited, $dictionary)) {
$answer[] = $word;
}
}
return $answer;
}
}
// Example usage
$solution = new Solution();
$words = ["cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"];
print_r($solution->findAllConcatenatedWordsInADict($words));1 386
Задача: 733. Flood Fill
Сложность: easy
Изображение представлено в виде целочисленной сетки m x n, где image[i][j] - значение пикселя изображения. Вам также даны три целых числа sr, sc и color. Вы должны выполнить заливку изображения, начиная с пикселя image[sr][sc]. Чтобы выполнить заливку, рассмотрите начальный пиксель, плюс все пиксели, соединенные по 4-м направлениям с начальным пикселем, того же цвета, что и начальный пиксель, плюс все пиксели, соединенные по 4-м направлениям с этими пикселями (также того же цвета), и так далее. Замените цвет всех вышеупомянутых пикселей на цвет. Верните измененное изображение после выполнения заливки.
Пример:
Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2 Output: [[2,2,2],[2,2,0],[2,0,1]]👨💻 Алгоритм: 1⃣Получите цвет начального пикселя. 2⃣Используйте обход в глубину (DFS) или обход в ширину (BFS) для замены цвета всех пикселей, которые соединены с начальным пикселем и имеют тот же цвет. 3⃣Обновите изображение и верните его. 😎 Решение:
function floodFill($image, $sr, $sc, $color) {
$originalColor = $image[$sr][$sc];
if ($originalColor == $color) {
return $image;
}
$dfs = function($x, $y) use (&$image, &$dfs, $originalColor, $color) {
if ($x < 0 || $x >= count($image) || $y < 0 || $y >= count($image[0]) || $image[$x][$y] != $originalColor) {
return;
}
$image[$x][$y] = $color;
$dfs($x + 1, $y);
$dfs($x - 1, $y);
$dfs($x, $y + 1);
$dfs($x, $y - 1);
};
$dfs($sr, $sc);
return $image;
}1 386
🖼️ PHP вакансии всех грейдов: удалёнка, реклок, щедрый оффер!
Вакансии, только с прямыми контактами в Telegram! Ноль автоотказов — живой диалог и быстрые объективные решения.
🖼️ PHP 👩💻 Python
👩💻 Java 👣 Go
🤖 ML & DS 👩💻 C#
🔎 QA 👩💻 Frontend
👩💻 Node.js 🖥 SQL
👩💻 UX/UI 👩💻 DevOps
👩💻 Mobile 📋 Analyst
💼 1C 👨✈️ CyberSec
👩💻 IT HR
Подпишись чтобы не упустить свой шанс получить лучший оффер!
1 386
Repost from easyoffer
⏳ 90 акционных мест
Акция со скидкой 50% для первых 500 пользователей easyoffer подходит к концу
🔥 Узнай вопросы и задачи с собеседований в конкретных компаниях
🔥 Получи лучшие ответы и видео-примеры от middle/senior специалистов
🔥 Обходи фильтры ATS, добавив топ30 ключевых слов в свое резюме
🔥 Экономь время с помощью автоматических откликов
🔥 Подготовься идеально к интервью с тренажёрами и симуляторами
Успей забрать место по акции: 👉 https://easyoffer.ru/pro
