PHP | LeetCode
الذهاب إلى القناة على Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @sendme_ads
إظهار المزيد
الشبكة:1 325
المشتركون
لا توجد بيانات24 ساعات
لا توجد بيانات7 أيام
-1830 أيام
أرشيف المشاركات
1 326
Задача: 362. Design Hit Counter
Сложность: medium
Дана матрица размером m x n, где каждая ячейка является либо стеной 'W', либо врагом 'E', либо пустой '0'. Верните максимальное количество врагов, которых можно уничтожить, используя одну бомбу. Вы можете разместить бомбу только в пустой ячейке.
Бомба уничтожает всех врагов в той же строке и столбце от точки установки до тех пор, пока не встретит стену, так как она слишком сильна, чтобы быть разрушенной.
Пример:
Input
["HitCounter", "hit", "hit", "hit", "getHits", "hit", "getHits", "getHits"]
[[], [1], [2], [3], [4], [300], [300], [301]]
Output
[null, null, null, null, 3, null, 4, 3]
Explanation
HitCounter hitCounter = new HitCounter();
hitCounter.hit(1); // hit at timestamp 1.
hitCounter.hit(2); // hit at timestamp 2.
hitCounter.hit(3); // hit at timestamp 3.
hitCounter.getHits(4); // get hits at timestamp 4, return 3.
hitCounter.hit(300); // hit at timestamp 300.
hitCounter.getHits(300); // get hits at timestamp 300, return 4.
hitCounter.getHits(301); // get hits at timestamp 301, return 3.class HitCounter {
private $hits;
public function __construct() {
$this->hits = [];
}
public function hit($timestamp) {
array_push($this->hits, $timestamp);
}
public function getHits($timestamp) {
while (!empty($this->hits) && $timestamp - $this->hits[0] >= 300) {
array_shift($this->hits);
}
return count($this->hits);
}
}1 326
Задача: 60. Permutation Sequence
Сложность: hard
Множество [1, 2, 3, ..., n] содержит в общей сложности n! уникальных перестановок.
Списком и маркировкой всех перестановок по порядку, мы получаем следующую последовательность для n = 3:
"123"
"132"
"213"
"231"
"312"
"321"
Дано n и k, верните k-ю перестановку последовательности.
Пример:
Input: n = 3, k = 3 Output: "213"👨💻 Алгоритм: 1⃣Сгенерируйте входной массив nums чисел от 1 до N. 2⃣Вычислите все факториальные основы от 0 до (N−1)!. 3⃣Уменьшите k на 1, чтобы значение попало в интервал (0, N!−1). Используйте коэффициенты факториалов для построения перестановки. Верните строку перестановки. 😎 Решение:
class Solution {
public function getPermutation($n, $k) {
$factorials = array_fill(0, $n, 1);
$nums = [];
for ($i = 1; $i < $n; $i++) {
$factorials[$i] = $factorials[$i - 1] * $i;
$nums[] = strval($i + 1);
}
$k--;
$result = "";
for ($i = $n - 1; $i >= 0; $i--) {
$idx = intdiv($k, $factorials[$i]);
$k -= $idx * $factorials[$i];
$result .= $nums[$idx];
array_splice($nums, $idx, 1);
}
return $result;
}
}1 326
Задача: 59. Spiral Matrix II
Сложность: medium
Дано положительное целое число n. Сгенерируйте матрицу n на n, заполненную элементами от 1 до n^2 в спиральном порядке.
Пример:
Input: n = 3 Output: [[1,2,3],[8,9,4],[7,6,5]]👨💻 Алгоритм: 1⃣Определение направлений движения: Для обхода матрицы используются четыре направления, формирующие слои. Создается массив dir, который хранит изменения координат x и y для каждого направления. Например, при движении слева направо (направление №1) координата x остается неизменной, а y увеличивается (x=0, y=1). При движении справа налево (направление №3) x остается неизменным, а y уменьшается (x=0, y=-1). 2⃣Перемещение по матрице: Переменные row и col представляют текущие координаты x и y соответственно. Они обновляются в зависимости от направления движения. Применяется предварительно определенный массив dir с изменениями координат x и y для каждого из четырех направлений. 3⃣Изменение направления: Направление изменяется, когда следующая строка или столбец в определенном направлении имеют ненулевое значение, что указывает на то, что они уже были пройдены. Переменная d представляет текущий индекс направления. Переход к следующему направлению в массиве dir осуществляется с использованием формулы (d+1)%4. Это позволяет вернуться к направлению 1 после завершения одного полного круга от направления 1 до направления 4. 😎 Решение:
class Solution {
// Helper function to handle negative indices in modulo operations
private function floorMod($x, $y) {
return (($x % $y) + $y) % $y;
}
// Function to generate an n x n matrix in spiral order
public function generateMatrix($n) {
$result = array_fill(0, $n, array_fill(0, $n, 0));
$cnt = 1;
$dir = [[0, 1], [1, 0], [0, -1], [-1, 0]];
$d = 0;
$row = 0;
$col = 0;
while ($cnt <= $n * $n) {
$result[$row][$col] = $cnt;
$cnt++;
$r = $this->floorMod($row + $dir[$d][0], $n);
$c = $this->floorMod($col + $dir[$d][1], $n);
if ($result[$r][$c] != 0) {
$d = ($d + 1) % 4;
}
$row += $dir[$d][0];
$col += $dir[$d][1];
}
return $result;
}
}1 326
Задача: 45. Jump Game II
Сложность: medium
Вам дан массив целых чисел nums с индексацией с нуля и длиной n. Изначально вы находитесь в позиции nums[0].
Каждый элемент nums[i] представляет максимальную длину прыжка вперед с индекса i. Другими словами, если вы находитесь в nums[i], вы можете прыгнуть на любой nums[i + j], где:
0 <= j <= nums[i] и
i + j < n
Верните минимальное количество прыжков, чтобы достичь nums[n - 1]. Тестовые случаи сгенерированы таким образом, что вы можете достичь nums[n - 1].
Пример:
Input: nums = [2,3,0,1,4] Output: 2👨💻 Алгоритм: 1⃣Инициализируйте curEnd = 0, curFar = 0 и количество прыжков как answer = 0. 2⃣Итерируйтесь по массиву nums. Для каждого индекса i наибольший индекс, до которого мы можем добраться из i, равен i + nums[i]. Обновите curFar = max(curFar, i + nums[i]). 3⃣Если i = curEnd, это означает, что текущий прыжок завершен, и следует перейти к следующему прыжку. Увеличьте answer и установите curEnd = curFar как наибольшее расстояние, которое мы можем преодолеть следующим прыжком. Повторите с шага 2. 😎 Решение:
function jump($nums) {
$answer = 0;
$n = count($nums);
$curEnd = 0;
$curFar = 0;
for ($i = 0; $i < $n - 1; ++$i) {
$curFar = max($curFar, $i + $nums[$i]);
if ($i === $curEnd) {
++$answer;
$curEnd = $curFar;
}
}
return $answer;
}1 326
Задача: 1237. Find Positive Integer Solution for a Given Equation
Сложность: medium
Если дана вызываемая функция f(x, y) со скрытой формулой и значением z, выполните обратную разработку формулы и верните все пары целых положительных чисел x и y, в которых f(x,y) == z. Пары можно возвращать в любом порядке. Хотя точная формула скрыта, функция является монотонно возрастающей, т.е.Например: f(x, y) < f(x + 1, y) f(x, y) < f(x, y + 1) Интерфейс функции определяется следующим образом: interface CustomFunction { public: // Возвращает некоторое положительное целое число f(x, y) для двух положительных целых чисел x и y на основе формулы.
int f(int x, int y); }; Мы будем оценивать ваше решение следующим образом: у судьи есть список из 9 скрытых реализаций CustomFunction, а также способ сгенерировать ключ ответа из всех допустимых пар для определенного z. Судья получит два входа: function_id (чтобы определить, с какой реализацией тестировать ваш код) и целевое z. Судья вызовет ваш findSolution и сравнит ваши результаты с ключом ответа. Если ваши результаты совпадут с ключом ответа, ваше решение будет принято.
Пример:
Input: function_id = 1, z = 5 Output: [[1,4],[2,3],[3,2],[4,1]]👨💻 Алгоритм: 1⃣Начнем с =1 x=1 и 𝑦=1000 y=1000 (предполагаем максимальное значение y). 2⃣Перемещение указателей: Если 𝑓(𝑥,𝑦)=𝑧 f(x,y)=z, добавляем пару (𝑥,𝑦)(x,y) в результат и увеличиваем x. 3⃣Повторяем шаги до тех пор, пока 𝑥≤1000 x≤1000 и 𝑦≥1y≥1. 😎 Решение:
class CustomFunction {
public function f($x, $y) {}
}
function findSolution($customfunction, $z) {
$result = [];
$x = 1;
$y = 1000;
while ($x <= 1000 && $y >= 1) {
$value = $customfunction->f($x, $y);
if ($value == $z) {
$result[] = [$x, $y];
$x++;
} else if ($value < $z) {
$x++;
} else {
$y--;
}
}
return $result;
}1 326
🖼️ Стажировки и вакансии для PHP разработчиков.
- Вакансии которых нет на джоб-агрегаторах
- Только прямые контакты HR в Telegram
👉 @jobs_php
🤖 ML & DS 👩💻 DevOps
👨✈️ ИБ & OSINT 👣 Go
👩💻 Mobile 👩💻 C#
👩💻 Node.js 👩💻 Python
🔎 QA 👩💻 Java
👩💻 UX/UI 👩💻 Frontend
🖼️ PHP 📋 Analyst
💼 1C 🖥 SQL
👩💻 IT HR
Пока другие листают джоб-сайты — ты уже пишешь HR в Telegram.
1 326
Задача: 88. Merge Sorted Array
Сложность: easy
Вам даны два массива целых чисел nums1 и nums2, отсортированных в порядке неубывания, а также два целых числа m и n, представляющих количество элементов в nums1 и nums2 соответственно.
Слейте nums1 и nums2 в один массив, отсортированный в порядке неубывания.
Итоговый отсортированный массив не должен возвращаться функцией, а должен храниться внутри массива nums1. Чтобы это обеспечить, длина nums1 составляет m + n, где первые m элементов обозначают элементы, которые должны быть объединены, а последние n элементов установлены в 0 и должны быть проигнорированы. Длина nums2 составляет n.
Пример:
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 Output: [1,2,2,3,5,6] Explanation: The arrays we are merging are [1,2,3] and [2,5,6]. The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.👨💻 Алгоритм: 1⃣Самая простая реализация заключалась бы в создании копии значений в nums1, называемой nums1Copy, а затем использовании двух указателей для чтения и одного указателя для записи для чтения значений из nums1Copy и nums2 и записи их в nums1. 2⃣Инициализируйте nums1Copy новым массивом, содержащим первые m значений nums1. Инициализируйте указатель для чтения p1 в начале nums1Copy. Инициализируйте указатель для чтения p2 в начале nums2. 3⃣Инициализируйте указатель для записи p в начале nums1. Пока p все еще находится внутри nums1: Если nums1Copy[p1] существует и меньше или равно nums2[p2]: Запишите nums1Copy[p1] в nums1[p], и увеличьте p1 на 1. Иначе Запишите nums2[p2] в nums1[p], и увеличьте p2 на 1. Увеличьте p на 1. 😎 Решение:
class Solution {
public function merge(&$nums1, $m, $nums2, $n) {
$nums1Copy = array_slice($nums1, 0, $m);
$p1 = 0;
$p2 = 0;
for ($p = 0; $p < $n + $m; $p++) {
if ($p2 >= $n || ($p1 < $m && $nums1Copy[$p1] <= $nums2[$p2])) {
$nums1[$p] = $nums1Copy[$p1];
$p1++;
} else {
$nums1[$p] = $nums2[$p2];
$p2++;
}
}
}
}1 326
Задача: 913. Cat and Mouse4
Сложность: hard
В игру на неориентированном графе играют два игрока, Мышь и Кот, которые чередуются по очереди. Граф задан следующим образом: graph[a] - это список всех вершин b, таких, что ab является ребром графа. Мышь начинает в вершине 1 и идет первой, Кот начинает в вершине 2 и идет второй, а в вершине 0 находится дыра. Во время хода каждого игрока он должен пройти по одному ребру графа, которое встречает его местоположение.Например, если Мышь находится в узле 1, она должна добраться до любого узла графа[1]. Кроме того, Кошке запрещено добираться до Дыры (узел 0). Затем игра может закончиться тремя способами: если Кошка занимает тот же узел, что и Мышь, Кошка побеждает. Если Мышь достигает Дыры, Мышь побеждает. Если позиция повторяется (т.е, игроки находятся в той же позиции, что и в предыдущий ход, и сейчас очередь того же игрока двигаться), то игра считается ничейной. Учитывая граф и предполагая, что оба игрока играют оптимально, верните 1, если в игре победила мышь, 2, если в игре победила кошка, или 0, если в игре ничья.
Пример:
Input: graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]] Output: 0👨💻 Алгоритм: 1⃣Использовать динамическое программирование с мемоизацией для хранения результатов игры для каждой комбинации позиций мыши, кота и текущего игрока. 2⃣Проверить три условия окончания игры: Мышь достигает дырки (победа мыши). Кот достигает мыши (победа кота). Позиция повторяется (ничья). 3⃣Использовать BFS (поиск в ширину) для определения результатов игры, начиная с конечных состояний и работая назад. 😎 Решение:
function catMouseGame($graph) {
$n = count($graph);
$DRAW = 0; $MOUSE = 1; $CAT = 2;
$dp = array_fill(0, $n, array_fill(0, $n, array_fill(0, 2, $DRAW)));
$queue = [];
for ($i = 1; $i < $n; $i++) {
$dp[0][$i][0] = $MOUSE;
$dp[0][$i][1] = $MOUSE;
$dp[$i][$i][0] = $CAT;
$dp[$i][$i][1] = $CAT;
$queue[] = [0, $i, 0, $MOUSE];
$queue[] = [0, $i, 1, $MOUSE];
$queue[] = [$i, $i, 0, $CAT];
$queue[] = [$i, $i, 1, $CAT];
}
function parents($graph, $mouse, $cat, $turn) {
$res = [];
if ($turn == 1) {
foreach ($graph[$mouse] as $m) {
$res[] = [$m, $cat, 0];
}
} else {
foreach ($graph[$cat] as $c) {
if ($c > 0) $res[] = [$mouse, $c, 1];
}
}
return $res;
}
while (!empty($queue)) {
list($mouse, $cat, $turn, $winner) = array_shift($queue);
foreach (parents($graph, $mouse, $cat, $turn) as list($m, $c, $t)) {
if ($dp[$m][$c][$t] == $DRAW) {
if (($t == 0 && $winner == $MOUSE) || ($t == 1 && $winner == $CAT)) {
$dp[$m][$c][$t] = $winner;
$queue[] = [$m, $c, $t, $winner];
} else {
$degrees = 0;
foreach (parents($graph, $m, $c, $t) as $_) $degrees++;
if ($degrees == 0) {
$dp[$m][$c][$t] = $winner;
$queue[] = [$m, $c, $t, $winner];
}
}
}
}
}
return $dp[1][2][0];
}1 326
Задача: 990. Satisfiability of Equality Equations
Сложность: medium
Дан массив строк equations, представляющий отношения между переменными, где каждая строка equations[i] имеет длину 4 и принимает одну из двух форм: "xi==yi" или "xi!=yi". Здесь xi и yi - это строчные буквы (не обязательно разные), представляющие имена переменных из одной буквы.
Верните true, если возможно назначить целые числа именам переменных таким образом, чтобы удовлетворить всем заданным уравнениям, или false в противном случае.
Пример:
Input: equations = ["b==a","a==b"] Output: true Explanation: We could assign a = 1 and b = 1 to satisfy both equations.👨💻 Алгоритм: 1⃣Создание графа для уравнений "==": Создайте структуру данных для объединения (Union-Find) для обработки уравнений равенства. Пройдите через массив equations и для каждого уравнения типа "xi==yi" объедините соответствующие переменные. 2⃣Проверка уравнений "!=": Пройдите через массив equations и для каждого уравнения типа "xi!=yi" проверьте, принадлежат ли переменные к одной и той же группе в структуре объединения. Если принадлежат, верните false. 3⃣Возврат результата: Если после проверки всех уравнений "xi!=yi" не было обнаружено противоречий, верните true. 😎 Решение:
class UnionFind {
private $parent;
public function __construct($size) {
$this->parent = range(0, $size - 1);
}
public function find($x) {
if ($this->parent[$x] != $x) {
$this->parent[$x] = $this->find($this->parent[$x]);
}
return $this->parent[$x];
}
public function union($x, $y) {
$rootX = $this->find($x);
$rootY = $this->find($y);
if ($rootX != $rootY) {
$this->parent[$rootX] = $rootY;
}
}
public function connected($x, $y) {
return $this->find($x) == $this->find($y);
}
}
class Solution {
function equationsPossible($equations) {
$uf = new UnionFind(26);
foreach ($equations as $eq) {
if ($eq[1] == '=') {
$x = ord($eq[0]) - ord('a');
$y = ord($eq[3]) - ord('a');
$uf->union($x, $y);
}
}
foreach ($equations as $eq) {
if ($eq[1] == '!') {
$x = ord($eq[0]) - ord('a');
$y = ord($eq[3]) - ord('a');
if ($uf->connected($x, $y)) {
return false;
}
}
}
return true;
}
}1 326
Задача: 783. Minimum Distance Between BST Nodes
Сложность: easy
Дан корень дерева поиска (BST). Верните минимальную разницу между значениями любых двух различных узлов в дереве.
Пример:
Input: root = [4,2,6,1,3] Output: 1👨💻 Алгоритм: 1⃣Инициализируйте minDistance значением MAX_VALUE; это переменная для хранения минимальной разницы. 2⃣Выполните обход дерева поиска в порядке возрастания (in-order traversal) и сохраните узлы в списке inorderNodes. 3⃣Итеративно проходите по списку inorderNodes, начиная с индекса 1. Для каждого элемента на позиции i найдите разницу с элементом на индексе i - 1 и соответствующим образом обновите переменную minDistance. Верните minDistance. 😎 Решение:
class Solution {
private $inorderNodes = [];
private function inorderTraversal($root) {
if ($root === null) {
return;
}
$this->inorderTraversal($root->left);
$this->inorderNodes[] = $root->val;
$this->inorderTraversal($root->right);
}
public function minDiffInBST($root) {
$this->inorderTraversal($root);
$minDistance = PHP_INT_MAX;
for ($i = 1; $i < count($this->inorderNodes); $i++) {
$minDistance = min($minDistance, $this->inorderNodes[$i] - $this->inorderNodes[$i - 1]);
}
return $minDistance;
}
}1 326
Задача: 563. Binary Tree Tilt
Сложность: easy
Дано корневое значение бинарного дерева. Вернуть сумму значений наклонов всех узлов дерева.
Наклон узла дерева - это абсолютная разница между суммой всех значений узлов левого поддерева и всех значений узлов правого поддерева. Если у узла нет левого потомка, то сумма значений узлов левого поддерева считается равной 0. То же правило применяется, если у узла нет правого потомка.
Пример:
Input: root = [1,2,3] Output: 1 Explanation: Tilt of node 2 : |0-0| = 0 (no children) Tilt of node 3 : |0-0| = 0 (no children) Tilt of node 1 : |2-3| = 1 (left subtree is just left child, so sum is 2; right subtree is just right child, so sum is 3) Sum of every tilt : 0 + 0 + 1 = 1👨💻 Алгоритм: 1⃣Определите рекурсивную функцию, которая вычисляет сумму значений узлов поддерева и наклон текущего узла. 2⃣Для каждого узла вычислите сумму значений левого и правого поддерева, а также их наклон, добавляя наклон к общей сумме. 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;
}
}
class Solution {
private $totalTilt = 0;
function findTilt($root) {
$this->sumAndTilt($root);
return $this->totalTilt;
}
private function sumAndTilt($node) {
if ($node === null) {
return 0;
}
$leftSum = $this->sumAndTilt($node->left);
$rightSum = $this->sumAndTilt($node->right);
$nodeTilt = abs($leftSum - $rightSum);
$this->totalTilt += $nodeTilt;
return $node->val + $leftSum + $rightSum;
}
}1 326
Задача: 244. Shortest Word Distance II
Сложность: medium
Создайте структуру данных, которая будет инициализироваться массивом строк, а затем должна отвечать на запросы о наименьшем расстоянии между двумя разными строками из массива.
Реализуйте класс WordDistance:
WordDistance(String[] wordsDict) инициализирует объект с массивом строк wordsDict.
int shortest(String word1, String word2) возвращает наименьшее расстояние между word1 и word2 в массиве wordsDict.
Пример:
Input
["WordDistance", "shortest", "shortest"]
[[["practice", "makes", "perfect", "coding", "makes"]], ["coding", "practice"], ["makes", "coding"]]
Output
[null, 3, 1]
Explanation
WordDistance wordDistance = new WordDistance(["practice", "makes", "perfect", "coding", "makes"]);
wordDistance.shortest("coding", "practice"); // return 3
wordDistance.shortest("makes", "coding"); // return 1// PHP
class WordDistance {
private $locations;
function __construct($words) {
$this->locations = [];
foreach ($words as $i => $word) {
if (!isset($this->locations[$word])) {
$this->locations[$word] = [];
}
$this->locations[$word][] = $i;
}
}
function shortest($word1, $word2) {
$loc1 = $this->locations[$word1];
$loc2 = $this->locations[$word2];
$l1 = 0;
$l2 = 0;
$minDiff = PHP_INT_MAX;
while ($l1 < count($loc1) && $l2 < count($loc2)) {
$minDiff = min($minDiff, abs($loc1[$l1] - $loc2[$l2]));
if ($loc1[$l1] < $loc2[$l2]) {
$l1++;
} else {
$l2++;
}
}
return $minDiff;1 326
Задача: 666. Path Sum IV
Сложность: medium
Если глубина дерева меньше 5, то это дерево можно представить в виде массива трехзначных чисел. Для каждого числа в этом массиве:
Сотни представляют глубину d этого узла, где 1 <= d <= 4.
Десятки представляют позицию p этого узла на уровне, которому он принадлежит, где 1 <= p <= 8. Позиция соответствует позиции в полном бинарном дереве.
Единицы представляют значение v этого узла, где 0 <= v <= 9.
Дан массив возрастающих трехзначных чисел nums, представляющих бинарное дерево с глубиной меньше 5. Верните сумму всех путей от корня к листьям.
Гарантируется, что данный массив представляет собой валидное связанное бинарное дерево.
Пример:
Input: nums = [113,215,221] Output: 12 Explanation: The tree that the list represents is shown. The path sum is (3 + 5) + (3 + 1) = 12.👨💻 Алгоритм: 1⃣Создание структуры дерева: Пройдите по массиву nums и для каждого элемента создайте узел дерева. Сохраните узлы в словаре для удобного доступа по их позиции. 2⃣Связывание узлов: Пройдите по массиву и свяжите узлы друг с другом, исходя из их позиции и глубины. Найдите левого и правого ребенка для каждого узла и установите соответствующие связи. 3⃣Подсчет суммы путей: Выполните обход дерева (например, используя DFS) и подсчитайте сумму всех путей от корня к листьям. 😎 Решение:
class Solution {
function pathSum($nums) {
$tree = [];
foreach ($nums as $num) {
$depth = intdiv($num, 100);
$pos = intdiv($num, 10) % 10;
$val = $num % 10;
$tree[$depth * 10 + $pos] = $val;
}
return $this->dfs($tree, 1, 1, 0);
}
private function dfs($tree, $depth, $pos, $currentSum) {
$key = $depth * 10 + $pos;
if (!isset($tree[$key])) {
return 0;
}
$currentSum += $tree[$key];
$leftChild = ($depth + 1) * 10 + 2 * $pos - 1;
$rightChild = ($depth + 1) * 10 + 2 * $pos;
if (!isset($tree[$leftChild]) && !isset($tree[$rightChild])) {
return $currentSum;
}
return $this->dfs($tree, $depth + 1, 2 * $pos - 1, $currentSum) + $this->dfs($tree, $depth + 1, 2 * $pos, $currentSum);
}
}1 326
Задача: 1037. Valid Boomerang
Сложность: easy
Если задан массив points, где points[i] = [xi, yi] представляет точку на плоскости X-Y, верните true, если эти точки являются бумерангом. Бумеранг - это набор из трех точек, которые отличаются друг от друга и не являются прямой линией.
Пример:
Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2] Output: false👨💻 Алгоритм: 1⃣Проверка уникальности точек: Убедитесь, что все три точки уникальны. Если любые две точки совпадают, то это не бумеранг. 2⃣Проверка на коллинеарность: Используйте определитель (или площадь параллелограмма) для проверки, находятся ли три точки на одной прямой. Если площадь параллелограмма, образованного тремя точками, равна нулю, то точки коллинеарны. 3⃣Результат: Если точки уникальны и не коллинеарны, верните true. В противном случае, верните false. 😎 Решение:
function isBoomerang($points) {
list($x1, $y1) = $points[0];
list($x2, $y2) = $points[1];
list($x3, $y3) = $points[2];
return ($x1 != $x2 || $y1 != $y2) &&
($x1 != $x3 || $y1 != $y3) &&
($x2 != $x3 || $y2 != $y3) &&
($x1 * ($y2 - $y3) + $x2 * ($y3 - $y1) + $x3 * ($y1 - $y2)) != 0;
}1 326
Задача: 1065. Index Pairs of a String
Сложность: easy
Дана строка text и массив строк words, верните массив всех пар индексов [i, j], таких что подстрока text[i...j] находится в words.
Верните пары [i, j] в отсортированном порядке (то есть отсортируйте их по первой координате, а в случае совпадения сортируйте их по второй координате).
Пример:
Input: text = "thestoryofleetcodeandme", words = ["story","fleet","leetcode"]
Output: [[3,7],[9,13],[10,17]]class Solution {
function indexPairs($text, $words) {
$wordsSet = array_flip($words);
$ans = [];
for ($i = 0; $i < strlen($text); $i++) {
for ($j = $i; $j < strlen($text); $j++) {
if (isset($wordsSet[substr($text, $i, $j - $i + 1)])) {
$ans[] = [$i, $j];
}
}
}
return $ans;
}
}1 326
Задача: 606. Construct String from Binary Tree
Сложность: medium
Дано бинарное дерево, необходимо вернуть его строковое представление, используя прямой обход (preorder traversal) и правила со скобками:
Скобки для детей обязательны, если есть правый ребёнок
Пропускать пустые скобки, кроме случая, когда отсутствует левый, но есть правый ребёнок
Пример:
Input: root = [1,2,3,4]
Output: "1(2(4))(3)"
Explanation: Originally, it needs to be "1(2(4)())(3()())", but you need to omit all the empty parenthesis pairs. And it will be "1(2(4))(3)".class Solution {
function tree2str($t) {
$res = "";
$this->dfs($t, $res);
return $res;
}
function dfs($t, &$res) {
if ($t == null)
return;
$res .= $t->val;
if ($t->left == null && $t->right == null)
return;
$res .= '(';
$this->dfs($t->left, $res);
$res .= ')';
if ($t->right != null) {
$res .= '(';
$this->dfs($t->right, $res);
$res .= ')';
}
}
}1 326
Задача: 1048. Longest String Chain
Сложность: easy
Вам дан массив слов, каждое из которых состоит из строчных английских букв. СловоА является предшественником словаВ тогда и только тогда, когда мы можем вставить ровно одну букву в любое место словаА, не меняя порядка остальных символов, чтобы оно стало равно словуВ.
Например, "abc" является предшественником "abac", а "cba" не является предшественником "bcad". Цепочка слов - это последовательность слов [word1, word2, ..., wordk] с k >= 1, где word1 является предшественником word2, word2 является предшественником word3 и так далее. Одиночное слово тривиально является цепочкой слов с k == 1. Верните длину самой длинной возможной цепочки слов со словами, выбранными из заданного списка слов.
Пример:
Input: words = ["a","b","ba","bca","bda","bdca"] Output: 4👨💻 Алгоритм: 1⃣Отсортируй список слов по длине. 2⃣Используй динамическое программирование для вычисления длины самой длинной цепочки для каждого слова. 3⃣Верни максимальную длину среди всех цепочек. 😎 Решение:
function longestStrChain($words) {
usort($words, function($a, $b) {
return strlen($a) - strlen($b);
});
$dp = [];
$longestChain = 1;
foreach ($words as $word) {
$dp[$word] = 1;
for ($i = 0; $i < strlen($word); $i++) {
$predecessor = substr($word, 0, $i) . substr($word, $i + 1);
if (isset($dp[$predecessor])) {
$dp[$word] = max($dp[$word], $dp[$predecessor] + 1);
}
}
$longestChain = max($longestChain, $dp[$word]);
}
return $longestChain;
}1 326
Задача: 745. Prefix and Suffix Search
Сложность: hard
Создайте специальный словарь, в котором поиск слов осуществляется по префиксу и суффиксу. Реализуйте класс WordFilter: WordFilter(string[] words) Инициализирует объект со словами в словаре. f(string pref, string suff) Возвращает индекс слова в словаре, которое имеет префикс pref и суффикс suff. Если существует более одного допустимого индекса, возвращается наибольший из них. Если в словаре нет такого слова, возвращается -1.
Пример:
Input: letters = ["c","f","j"], target = "a" Output: "c"👨💻 Алгоритм: 1⃣Сохраните слова и их индексы в словаре. 2⃣Создайте объединенные ключи, состоящие из префиксов и суффиксов для всех возможных комбинаций. 3⃣Реализуйте функцию поиска, которая ищет наибольший индекс слова по префиксу и суффиксу. 😎 Решение:
class WordFilter {
private $prefixSuffixMap = [];
function __construct($words) {
foreach ($words as $index => $word) {
$length = strlen($word);
for ($prefixLength = 1; $prefixLength <= $length; $prefixLength++) {
for ($suffixLength = 1; $suffixLength <= $length; $suffixLength++) {
$prefix = substr($word, 0, $prefixLength);
$suffix = substr($word, $length - $suffixLength);
$key = $prefix . '#' . $suffix;
$this->prefixSuffixMap[$key] = $index;
}
}
}
}
function f($pref, $suff) {
$key = $pref . '#' . $suff;
return array_key_exists($key, $this->prefixSuffixMap) ? $this->prefixSuffixMap[$key] : -1;
}
}1 326
Задача: 1245. Tree Diameter
Сложность: medium
Диаметр дерева - это количество ребер в самом длинном пути в этом дереве. Имеется неориентированное дерево из n узлов, помеченных от 0 до n - 1. Вам дан двумерный массив edges, где edges.length == n - 1 и edges[i] = [ai, bi] означает, что между узлами ai и bi в дереве есть неориентированное ребро. Верните диаметр дерева.
Пример:
Input: edges = [[0,1],[0,2]] Output: 2👨💻 Алгоритм: 1⃣Построение графа: Используем представление графа в виде списка смежности. 2⃣Поиск самой удаленной вершины (DFS1): Запускаем DFS от произвольной вершины (например, 0) для нахождения самой удаленной вершины от нее. 3⃣Поиск диаметра (DFS2): Запускаем DFS от найденной на предыдущем шаге самой удаленной вершины и находим самую удаленную вершину от нее. Это расстояние и будет диаметром дерева.reset(playerId): Устанавливаем счет игрока в 0. 😎 Решение:
function treeDiameter($edges) {
if (count($edges) === 0) return 0;
$graph = [];
foreach ($edges as $edge) {
if (!isset($graph[$edge[0]])) $graph[$edge[0]] = [];
if (!isset($graph[$edge[1]])) $graph[$edge[1]] = [];
$graph[$edge[0]][] = $edge[1];
$graph[$edge[1]][] = $edge[0];
}
$farthestNode = 0;
function dfs($node, $parent, &$graph, &$farthestNode) {
$maxDepth = 0;
foreach ($graph[$node] as $neighbor) {
if ($neighbor !== $parent) {
$depth = dfs($neighbor, $node, $graph, $farthestNode);
if ($depth + 1 > $maxDepth) {
$maxDepth = $depth + 1;
$farthestNode = $neighbor;
}
}
}
return $maxDepth;
}
dfs(0, -1, $graph, $farthestNode);
$startNode = $farthestNode;
dfs($startNode, -1, $graph, $farthestNode);
return dfs($farthestNode, -1, $graph, $farthestNode);
}1 326
Задача: 589. N-ary Tree Preorder Traversal
Сложность: easy
Дан корень N-арного дерева, верните значения его узлов в порядке предварительного (preorder) обхода.
Сериализация ввода N-арного дерева представлена в их обходе уровнями. Каждая группа детей разделена значением null (См. примеры).
Пример:
Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] Output: [1,2,3,6,7,11,14,4,8,12,5,9,13,10]👨💻 Алгоритм: 1⃣Инициализация Создайте два списка: stack для хранения узлов и output для хранения значений узлов в порядке обхода. Добавьте корневой узел в stack. 2⃣Итеративный обход Пока stack не пуст, извлекайте узел из stack и добавляйте его значение в output. Разверните список дочерних узлов текущего узла и добавьте их в stack. 3⃣Возврат результата Верните список output как результат. 😎 Решение:
class Node {
public $val;
public $children;
function __construct($val = 0, $children = []) {
$this->val = $val;
$this->children = $children;
}
}
class Solution {
function preorder($root) {
if ($root === null) return [];
$stack = [$root];
$output = [];
while (!empty($stack)) {
$node = array_pop($stack);
$output[] = $node->val;
$children = array_reverse($node->children);
foreach ($children as $child) {
$stack[] = $child;
}
}
return $output;
}
}