PHP | LeetCode
رفتن به کانال در Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
نمایش بیشتر
شبکه:1 356
مشترکین
+124 ساعت
-57 روز
-830 روز
آرشیو پست ها
1 356
Задача: 1029. Two City Scheduling
Сложность: medium
Компания планирует провести интервью с 2n людьми. Учитывая массив costs, где costs[i] = [aCosti, bCosti], стоимость перелета i-го человека в город a равна aCosti, а стоимость перелета i-го человека в город b равна bCosti. Выведите минимальную стоимость перелета каждого человека в город, чтобы в каждый город прибыло ровно n человек.
Пример:
Input: traversal = "1-2--3--4-5--6--7" Output: [1,2,5,3,4,6,7]👨💻 Алгоритм: 1⃣Вычислить разницу стоимости: Для каждого человека вычислите разницу в стоимости между перелетом в город A и город B. 2⃣Сортировать по разнице: Отсортируйте людей по разнице в стоимости перелета в город A и B. Это поможет минимизировать общую стоимость, так как мы сначала будем отправлять тех, для кого разница минимальна. 3⃣Назначить города: Первые n человек из отсортированного списка отправьте в город A. Оставшихся n человек отправьте в город B. 😎 Решение:
class Solution {
function twoCitySchedCost($costs) {
usort($costs, function($a, $b) {
return ($a[0] - $a[1]) - ($b[0] - $b[1]);
});
$totalCost = 0;
$n = count($costs) / 2;
for ($i = 0; $i < $n; $i++) {
$totalCost += $costs[$i][0];
$totalCost += $costs[$i + $n][1];
}
return $totalCost;
}
}1 356
Задача: 943. Find the Shortest Superstring
Сложность: hard
Учитывая массив строк words, верните наименьшую строку, которая содержит каждую строку в words в качестве подстроки. Если существует несколько допустимых строк наименьшей длины, верните любую из них. Вы можете предположить, что ни одна строка в words не является подстрокой другой строки в words.
Пример:
Input: words = ["alex","loves","leetcode"] Output: "alexlovesleetcode"👨💻 Алгоритм: 1⃣Реализовать функцию overlap для вычисления максимального перекрытия двух строк, где одна строка заканчивается, а другая начинается. 2⃣Реализовать функцию merge для объединения двух строк с максимальным перекрытием. Использовать жадный алгоритм для нахождения двух строк с максимальным перекрытием и объединить их, повторяя до тех пор, пока не останется одна строка. 3⃣Вернуть результат. 😎 Решение:
function shortestSuperstring($words) {
while (count($words) > 1) {
$maxOverlap = -1;
$l = 0;
$r = 0;
$merged = '';
for ($i = 0; $i < count($words); $i++) {
for ($j = 0; $j < count($words); $j++) {
if ($i != $j) {
$ovlp = overlap($words[$i], $words[$j]);
if ($ovlp > $maxOverlap) {
$maxOverlap = $ovlp;
$l = $i;
$r = $j;
$merged = merge($words[$i], $words[$j], $ovlp);
}
}
}
}
$words[$l] = $merged;
array_splice($words, $r, 1);
}
return $words[0];
}
function overlap($a, $b) {
$maxOverlap = 0;
for ($i = 1; $i <= min(strlen($a), strlen($b)); $i++) {
if (substr($a, -$i) === substr($b, 0, $i)) {
$maxOverlap = $i;
}
}
return $maxOverlap;
}
function merge($a, $b, $overlapLen) {
return $a . substr($b, $overlapLen);
}1 356
Задача: 285. Inorder Successor in BST
Сложность: medium
Дан корень бинарного дерева поиска и узел p в нем. Верните преемника этого узла в порядке возрастания в бинарном дереве поиска (BST). Если у данного узла нет преемника в порядке возрастания в дереве, верните null.
Преемник узла p — это узел с наименьшим ключом, который больше p.val.
Пример:
Input: root = [2,1,3], p = 1 Output: 2 Explanation: 1's in-order successor node is 2. Note that both p and the return value is of TreeNode type.👨💻 Алгоритм: 1⃣Определение переменных класса: Определите две переменные класса: previous и inorderSuccessorNode. Переменная previous будет использоваться при обработке второго случая, а inorderSuccessorNode будет содержать результат, который нужно вернуть. 2⃣Обработка двух случаев: В функции inorderSuccessor сначала проверьте, какой из двух случаев нужно обработать, проверяя наличие правого дочернего элемента. Правый дочерний элемент существует: - присвойте правый дочерний элемент узлу leftmost и итерируйтесь, пока не достигнете узла (leftmost), у которого нет левого дочернего элемента. Итерируйте, присваивая leftmost = leftmost.left, пока не получите левый узел в поддереве. Правый дочерний элемент не существует: - определите функцию inorderCase2 и передайте ей узел и узел p. - выполните простой обход в порядке возрастания: сначала рекурсируйте на левый дочерний элемент узла. - когда рекурсия вернется, проверьте, равна ли переменная класса previous узлу p. Если это так, значит p является предшественником узла, или, другими словами, узел является преемником узла p. Назначьте inorderSuccessorNode узлу и вернитесь из функции. - наконец, верните inorderSuccessorNode как результат. 3⃣Итерация и обновление: В функции inorderCase2 обновляйте previous текущим узлом и продолжайте рекурсировать на правый дочерний элемент. 😎 Решение:
class TreeNode {
public $val;
public $left;
public $right;
public function __construct($val = 0, $left = null, $right = null) {
$this->val = $val;
$this->left = $left;
$this->right = $right;
}
}
class Solution {
private $previous = null;
private $inorderSuccessorNode = null;
public function inorderSuccessor($root, $p) {
if ($p->right !== null) {
$leftmost = $p->right;
while ($leftmost->left !== null) {
$leftmost = $leftmost->left;
}
$this->inorderSuccessorNode = $leftmost;
} else {
$this->inorderCase2($root, $p);
}
return $this->inorderSuccessorNode;
}
private function inorderCase2($node, $p) {
if ($node === null) {
return;
}
$this->inorderCase2($node->left, $p);
if ($this->previous === $p && $this->inorderSuccessorNode === null) {
$this->inorderSuccessorNode = $node;
return;
}
$this->previous = $node;
$this->inorderCase2($node->right, $p);
}
}1 356
Задача: 305. Number of Islands II
Сложность: hard
Дан пустой двумерный бинарный массив
grid размером m x n. Этот массив представляет собой карту, где 0 означает воду, а 1 — сушу. Изначально все ячейки массива — водные (т.е. все ячейки содержат 0).
Вы можете выполнить операцию "добавить землю", которая превращает воду в указанной позиции в сушу. Вам дан массив positions, где positions[i] = [ri, ci] — позиция (ri, ci), в которой следует выполнить i-ю операцию.
Верните массив целых чисел answer, где answer[i] — количество островов после превращения ячейки (ri, ci) в сушу.
Остров окружен водой и образуется путем соединения соседних земель по горизонтали или вертикали. Вы можете считать, что все четыре края сетки окружены водой.
Пример:
Input: m = 1, n = 1, positions = [[0,0]]
Output: [1]class UnionFind {
private $parent, $rank, $count;
public function __construct($size) { $this->parent = array_fill(0, $size, -1); $this->rank = array_fill(0, $size, 0); $this->count = 0; }
public function addLand($x) { if ($this->parent[$x] < 0) { $this->parent[$x] = $x; $this->count++; } }
public function isLand($x) { return $this->parent[$x] >= 0; }
public function find($x) { if ($this->parent[$x] != $x) $this->parent[$x] = $this->find($this->parent[$x]); return $this->parent[$x]; }
public function unionSet($x, $y) { $xset = $this->find($x); $yset = $this->find($y);
if ($xset != $yset) { if ($this->rank[$xset] < $this->rank[$yset]) $this->parent[$xset] = $yset
else { $this->parent[$yset] = $xset; if ($this->rank[$xset] == $this->rank[$yset]) $this->rank[$xset]++; }; $this->count--; } }
}
class Solution {
public function numIslands2($m, $n, $positions) {
$dsu = new UnionFind($m * $n); $x = [-1, 1, 0, 0]; $y = [0, 0, -1, 1]; $answer = [];
foreach ($positions as $pos) { $land = $pos[0] * $n + $pos[1]; $dsu->addLand($land);
for ($i = 0; $i < 4; $i++) { $nx = $pos[0] + $x[$i]; $ny = $pos[1] + $y[$i]; $neighbor = $nx * $n + $ny;
if ($nx >= 0 && $nx < $m && $ny >= 0 && $ny < $n && $dsu->isLand($neighbor)) $dsu->unionSet($land, $neighbor); }
$answer[] = $dsu->count; }
return $answer;
}
}1 356
Задача: 132. Palindrome Partitioning II
Сложность: Hard
Дана строка s. Разделите строку так, чтобы каждая подстрока разделения была палиндромом.
Верните минимальное количество разрезов, необходимых для разделения строки s на палиндромы.
Пример:
Input: s = "aab" Output: 1 Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.👨💻 Алгоритм: 1⃣Определение задачи и начальные условия: Алгоритм обратного отслеживания реализуется путём рекурсивного изучения кандидатов-подстрок. Мы определяем рекурсивный метод findMinimumCut, который находит минимальное количество разрезов для подстроки, начинающейся с индекса start и заканчивающейся на индексе end. Чтобы найти минимальное количество разрезов, мы также должны знать минимальное количество разрезов, которые были найдены ранее для других разделений на палиндромы. Эта информация отслеживается в переменной minimumCut. Начальное значение minimumCut будет равно максимально возможному количеству разрезов в строке, что равно длине строки минус один (т.е. разрез между каждым символом). 2⃣Генерация подстрок и рекурсивный поиск: Теперь, когда мы знаем начальные и конечные индексы, мы должны сгенерировать все возможные подстроки, начиная с индекса start. Для этого мы будем держать начальный индекс постоянным. currentEndIndex обозначает конец текущей подстроки. 3⃣Условие палиндрома и рекурсивное разделение: Если текущая подстрока является палиндромом, мы сделаем разрез после currentEndIndex и рекурсивно найдем минимальный разрез для оставшейся строки 😎 Решение:
class Solution {
public function minCut($s) {
return $this->findMinimumCut($s, 0, strlen($s) - 1, strlen($s) - 1);
}
private function findMinimumCut($s, $start, $end, $minimumCut) {
if ($start === $end || $this->isPalindrome($s, $start, $end)) {
return 0;
}
for ($currentEndIndex = $start; $currentEndIndex <= $end; $currentEndIndex++) {
if ($this->isPalindrome($s, $start, $currentEndIndex)) {
$minimumCut = min(
$minimumCut,
1 + $this->findMinimumCut($s, $currentEndIndex + 1, $end, $minimumCut)
);
}
}
return $minimumCut;
}
private function isPalindrome($s, $start, $end) {
while ($start < $end) {
if ($s[$start++] !== $s[$end--]) {
return false;
}
}
return true;
}
}1 356
Задача: 841. Keys and Rooms
Сложность: medium
Есть n комнат, пронумерованных от 0 до n - 1, и все комнаты закрыты, кроме комнаты 0. Ваша цель — посетить все комнаты. Однако вы не можете войти в закрытую комнату, не имея ключа от нее.
Когда вы посещаете комнату, вы можете найти в ней набор различных ключей. Каждый ключ имеет номер, указывающий, какую комнату он открывает, и вы можете взять их все с собой, чтобы открыть другие комнаты.
Дан массив rooms, где rooms[i] — это набор ключей, которые вы можете получить, если посетите комнату i. Верните true, если вы можете посетить все комнаты, или false в противном случае.
Пример:
Input: rooms = [[1],[2],[3],[]] Output: true Explanation: We visit room 0 and pick up key 1. We then visit room 1 and pick up key 2. We then visit room 2 and pick up key 3. We then visit room 3. Since we were able to visit every room, we return true.👨💻 Алгоритм: 1⃣Создайте массив seen для отслеживания посещенных комнат и стек stack для ключей, которые нужно использовать. 2⃣Поместите ключ от комнаты 0 в стек и отметьте комнату 0 как посещенную. 3⃣Пока стек не пуст, извлекайте ключи из стека и используйте их для открытия новых комнат, добавляя найденные ключи в стек. Если все комнаты посещены, верните true, иначе false. 😎 Решение:
class Solution {
/**
* @param Integer[][] $rooms
* @return Boolean
*/
function canVisitAllRooms($rooms) {
$seen = array_fill(0, count($rooms), false);
$seen[0] = true;
$stack = [0];
while (!empty($stack)) {
$node = array_pop($stack);
foreach ($rooms[$node] as $nei) {
if (!$seen[$nei]) {
$seen[$nei] = true;
array_push($stack, $nei);
}
}
}
return !in_array(false, $seen);
}
}1 356
Задача: 1491. Average Salary Excluding the Minimum and Maximum Salary
Сложность: easy
Вам дан массив уникальных целых чисел
salary, где salary[i] — это зарплата i-го сотрудника.
Верните среднюю зарплату сотрудников, исключая минимальную и максимальную зарплату. Ответы, отличающиеся не более чем на 10^-5 от фактического ответа, будут приняты.
Пример:
Input: salary = [4000,3000,1000,2000]
Output: 2500.00000
Explanation: Minimum salary and maximum salary are 1000 and 4000 respectively.
Average salary excluding minimum and maximum salary is (2000+3000) / 2 = 2500class Solution {
function average($salary) {
$minSalary = PHP_INT_MAX;
$maxSalary = PHP_INT_MIN;
$sum = 0;
foreach ($salary as $sal) {
$sum += $sal;
$minSalary = min($minSalary, $sal);
$maxSalary = max($maxSalary, $sal);
}
return ($sum - $minSalary - $maxSalary) / (count($salary) - 2);
}
}1 356
Задача: 225. Implement Stack using Queues
Сложность: easy
Реализуйте стек (последним пришел - первым вышел, LIFO) с использованием только двух очередей. Реализованный стек должен поддерживать все функции обычного стека (push, top, pop и empty).
Реализуйте класс MyStack:
void push(int x): Добавляет элемент x на вершину стека.
int pop(): Удаляет элемент с вершины стека и возвращает его.
int top(): Возвращает элемент на вершине стека.
boolean empty(): Возвращает true, если стек пуст, иначе false.
Примечания:
Вы должны использовать только стандартные операции очереди, что означает, что допустимы только операции добавления в конец, просмотр/удаление из начала, определение размера и проверка на пустоту.
Пример:
Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]
Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return Falseclass MyStack {
private $q1;
private $q2;
private $topElement;
public function __construct() {
$this->q1 = [];
$this->q2 = [];
}
public function push($x) {
array_push($this->q2, $x);
$this->topElement = $x;
while (!empty($this->q1)) {
array_push($this->q2, array_shift($this->q1));
}
$temp = $this->q1;
$this->q1 = $this->q2;
$this->q2 = $temp;
}
public function pop() {
$result = array_shift($this->q1);
if (!empty($this->q1)) {
$this->topElement = $this->q1[0];
}
return $result;
}
public function top() {
return $this->topElement;
}
public function empty() {
return empty($this->q1);
}
}1 356
Задача: 939. Minimum Area Rectangle
Сложность: medium
Дан массив точек в плоскости X-Y points, где points[i] = [xi, yi]. Верните минимальную площадь прямоугольника, образованного из этих точек, со сторонами, параллельными осям X и Y. Если такого прямоугольника не существует, верните 0.
Пример:
Input: points = [[1,1],[1,3],[3,1],[3,3],[2,2]] Output: 4👨💻 Алгоритм: 1⃣Создать множество для хранения всех точек. Инициализировать переменную для хранения минимальной площади прямоугольника с бесконечным значением. 2⃣Пройти через все пары точек: Если две точки могут образовать диагональ прямоугольника, то проверить, существуют ли оставшиеся две точки для замкнутого прямоугольника. Если да, вычислить площадь прямоугольника и обновить минимальную площадь. 3⃣Если минимальная площадь остается бесконечной, вернуть 0. Иначе вернуть минимальную площадь. 😎 Решение:
function minAreaRect($points) {
$pointSet = [];
foreach ($points as $point) {
$pointSet["{$point[0]},{$point[1]}"] = true;
}
$minArea = PHP_INT_MAX;
$len = count($points);
for ($i = 0; $i < $len; $i++) {
for ($j = $i + 1; $j < $len; $j++) {
$x1 = $points[$i][0];
$y1 = $points[$i][1];
$x2 = $points[$j][0];
$y2 = $points[$j][1];
if ($x1 != $x2 && $y1 != $y2 && isset($pointSet["$x1,$y2"]) && isset($pointSet["$x2,$y1"])) {
$minArea = min($minArea, abs($x2 - $x1) * abs($y2 - $y1));
}
}
}
return $minArea == PHP_INT_MAX ? 0 : $minArea;
}1 356
Задача: 131. Palindrome Partitioning
Сложность: Medium
Дана строка s. Разделите строку таким образом, чтобы каждая подстрока разделения была палиндромом. Верните все возможные варианты разделения строки s на палиндромы.
Пример:
Input: s = "aab" Output: [["a","a","b"],["aa","b"]]👨💻 Алгоритм: 1⃣Инициация рекурсивного обхода: В алгоритме обратного отслеживания (backtracking) мы рекурсивно пробегаем по строке, используя метод поиска в глубину (depth-first search). Для каждого рекурсивного вызова задаётся начальный индекс строки start. Итеративно генерируем все возможные подстроки, начиная с индекса start. Индекс end увеличивается от start до конца строки. 2⃣Проверка на палиндром и продолжение поиска: Для каждой сгенерированной подстроки проверяем, является ли она палиндромом. Если подстрока оказывается палиндромом, она становится потенциальным кандидатом. Добавляем подстроку в currentList и выполняем поиск в глубину для оставшейся части строки. Если текущая подстрока заканчивается на индексе end, то end+1 становится начальным индексом для следующего рекурсивного вызова. 3⃣Возврат (Backtracking) и сохранение результатов: Возвращаемся, если начальный индекс start больше или равен длине строки, и добавляем currentList в результат. 😎 Решение:
class Solution {
public function partition($s) {
$res = [];
$this->dfs($s, [], $res);
return $res;
}
private function dfs($s, $path, &$res) {
if ($s === '') {
$res[] = $path;
return;
}
for ($i = 0; $i < strlen($s); $i++) {
$cur = substr($s, 0, $i + 1);
if ($this->isPalindrome($cur)) {
$newPath = $path;
array_push($newPath, $cur);
$this->dfs(substr($s, $i + 1), $newPath, $res);
}
}
}
private function isPalindrome($s) {
$lo = 0;
$hi = strlen($s) - 1;
while ($lo < $hi) {
if ($s[$lo++] != $s[$hi--]) {
return false;
}
}
return true;
}
}1 356
Задача: CodeTestcaseTest ResultTest Result1523. Count Odd Numbers in an Interval Range
Сложность: easy
### Условие задачи
Даны два неотрицательных целых числа low и high. Верните количество нечётных чисел между low и high (включительно).
Пример:
Input: low = 3, high = 7
Output: 3
Explanation: The odd numbers between 3 and 7 are [3,5,7].class Solution {
function countOdds($low, $high) {
if (($low & 1) == 0) {
$low++;
}
return $low > $high ? 0 : intdiv($high - $low, 2) + 1;
}
}1 356
Задача: 1254. Number of Closed Islands
Сложность: medium
Дана двумерная сетка, состоящая из 0 (земля) и 1 (вода).Остров - это максимальная 4-направленно связная группа из 0s, а закрытый остров - это остров, полностью (слева, сверху, справа, снизу) окруженный 1s. Верните количество закрытых островов.
Пример:
Input: grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]] Output: 2👨💻 Алгоритм: 1⃣Пройдите по границам сетки и с помощью поиска в глубину (DFS) или поиска в ширину (BFS) замените все связанные земли (0) на воду (1). 2⃣Пройдите по всей сетке, используя DFS или BFS для поиска всех оставшихся островов (групп 0) 3⃣Подсчитайте количество таких островов. 😎 Решение:
class Solution {
function closedIsland($grid) {
$m = count($grid);
$n = count($grid[0]);
for ($i = 0; $i < $m; $i++) {
for ($j = 0; $j < $n; $j++) {
if (($i == 0 || $i == $m - 1 || $j == 0 || $j == $n - 1) && $grid[$i][$j] == 0) {
$this->dfs($grid, $i, $j);
}
}
}
$count = 0;
for ($i = 1; $i < $m - 1; $i++) {
for ($j = 1; $j < $n - 1; $j++) {
if ($grid[$i][$j] == 0) {
$this->dfs($grid, $i, $j);
$count++;
}
}
}
return $count;
}
private function dfs(&$grid, $x, $y) {
if ($x < 0 || $y < 0 || $x >= count($grid) || $y >= count($grid[0]) || $grid[$x][$y] == 1) {
return;
}
$grid[$x][$y] = 1;
$this->dfs($grid, $x + 1, $y);
$this->dfs($grid, $x - 1, $y);
$this->dfs($grid, $x, $y + 1);
$this->dfs($grid, $x, $y - 1);
}
}1 356
Задача: 1019. Next Greater Node In Linked List
Сложность: medium
Вам дана голова связного списка с n узлами. Для каждого узла в списке найдите значение следующего большего узла. То есть для каждого узла найдите значение первого узла, который находится рядом с ним и имеет строго большее значение, чем он. Верните целочисленный массив answer, где answer[i] - это значение следующего большего узла ith-узла (с индексацией по 1). Если у узла ith нет следующего большего узла, установите answer[i] = 0.
Пример:
Input: head = [2,1,5] Output: [5,5,0]👨💻 Алгоритм: 1⃣Инициализация переменных: Пройдитесь по всему списку и сохраните значения узлов в массив. Инициализируйте стек для хранения индексов узлов, которые нужно обработать. 2⃣Поиск следующего большего элемента: Итерируйте по массиву значений узлов. Для каждого элемента, пока стек не пуст и текущий элемент больше, чем элемент на вершине стека, обновите массив ответов значением текущего элемента и удалите элемент из стека. Добавьте текущий индекс в стек. 3⃣Заполнение оставшихся значений: Для всех индексов, оставшихся в стеке, установите значение ответа равным 0, так как для них не найдено большего элемента. 😎 Решение:
class ListNode {
public $val = 0;
public $next = null;
function __construct($val = 0, $next = null) {
$this->val = $val;
$this->next = $next;
}
}
class Solution {
function nextLargerNodes($head) {
$values = [];
while ($head != null) {
$values[] = $head->val;
$head = $head->next;
}
$answer = array_fill(0, count($values), 0);
$stack = [];
for ($i = 0; $i < count($values); $i++) {
while (!empty($stack) && $values[end($stack)] < $values[$i]) {
$answer[array_pop($stack)] = $values[$i];
}
$stack[] = $i;
}
return $answer;
}
}1 356
Задача: 904. Fruit Into Baskets
Сложность: medium
Вы посещаете ферму, где в один ряд слева направо расположены фруктовые деревья. Деревья представлены целочисленным массивом fruits, где fruits[i] - это тип фрукта, который производит i-е дерево. Вы хотите собрать как можно больше фруктов. Однако у владельца есть строгие правила, которым вы должны следовать: у вас есть только две корзины, и каждая корзина может содержать только один тип фруктов. Количество фруктов в каждой корзине не ограничено. Начиная с любого дерева по вашему выбору, вы должны собрать ровно один фрукт с каждого дерева (включая начальное), двигаясь при этом вправо. Собранные фрукты должны поместиться в одну из ваших корзин. Как только вы достигнете дерева с фруктами, которые не могут поместиться в ваши корзины, вы должны остановиться. Учитывая целочисленный массив fruits, верните максимальное количество фруктов, которое вы можете собрать.
Пример:
Input: fruits = [1,2,1] Output: 3👨💻 Алгоритм: 1⃣Использовать метод скользящего окна для поддержания текущего подмассива, содержащего не более двух типов фруктов. 2⃣Перемещать правый указатель, расширяя окно, и обновлять количество каждого типа фрукта в окне. Если количество типов фруктов в окне превышает два, перемещать левый указатель, уменьшая окно, пока в окне снова не будет не более двух типов фруктов. 3⃣Подсчитывать максимальное количество фруктов, собранных на каждом шаге. 😎 Решение:
function totalFruit($fruits) {
$basket = [];
$left = 0;
$maxFruits = 0;
for ($right = 0; $right < count($fruits); $right++) {
if (!isset($basket[$fruits[$right]])) {
$basket[$fruits[$right]] = 0;
}
$basket[$fruits[$right]]++;
while (count($basket) > 2) {
$basket[$fruits[$left]]--;
if ($basket[$fruits[$left]] == 0) {
unset($basket[$fruits[$left]]);
}
$left++;
}
$maxFruits = max($maxFruits, $right - $left + 1);
}
return $maxFruits;
}1 356
Задача: 314. Binary Tree Vertical Order Traversal
Сложность: medium
Дан корень бинарного дерева, верните вертикальный порядок обхода значений его узлов (т.е. сверху вниз, столбец за столбцом).
Если два узла находятся в одной строке и столбце, порядок должен быть слева направо.
Пример:
Input: root = [3,9,20,null,null,15,7] Output: [[9],[3,15],[20],[7]]👨💻 Алгоритм: 1⃣Создайте хэш-таблицу с именем columnTable для отслеживания результатов. 2⃣Инициализируйте очередь, поместив в нее корневой узел вместе с его индексом столбца (0). Выполните обход в ширину (BFS), извлекая элементы из очереди. На каждой итерации извлекайте элемент, состоящий из узла и соответствующего индекса столбца. Если узел не пуст, добавьте его значение в columnTable. Затем поместите дочерние узлы с их индексами столбцов (т.е. column-1 и column+1) в очередь. 3⃣После завершения BFS обхода получите хэш-таблицу, содержащую значения узлов, сгруппированные по индексам столбцов. Для каждой группы значений отсортируйте их по индексам строк. Отсортируйте хэш-таблицу по ключам (индексам столбцов) в порядке возрастания и верните результаты по столбцам. 😎 Решение:
class TreeNode {
public $val;
public $left;
public $right;
public function __construct($val = 0, $left = null, $right = null) {
$this->val = $val;
$this->left = $left;
$this->right = $right;
}
}
class Solution {
function verticalOrder($root) {
$output = [];
if ($root === null) {
return $output;
}
$columnTable = [];
$queue = [[$root, 0]];
while (!empty($queue)) {
list($node, $col) = array_shift($queue);
if ($node !== null) {
if (!isset($columnTable[$col])) {
$columnTable[$col] = [];
}
$columnTable[$col][] = $node->val;
$queue[] = [$node->left, $col - 1];
$queue[] = [$node->right, $col + 1];
}
}
ksort($columnTable);
foreach ($columnTable as $col => $vals) {
$output[] = $vals;
}
return $output;
}
}1 356
Задача: 1042. Flower Planting With No Adjacent
Сложность: medium
У вас есть n садов, помеченных от 1 до n, и массив paths, где paths[i] = [xi, yi] описывает двунаправленный путь между садом xi и садом yi. В каждом саду вы хотите посадить один из 4 типов цветов. Все сады имеют не более 3 путей, входящих и выходящих из него. Ваша задача - выбрать тип цветка для каждого сада так, чтобы для любых двух садов, соединенных путем, они имели разные типы цветов. Верните любой такой выбор в виде массива answer, где answer[i] - тип цветка, посаженного в (i+1)-м саду. Типы цветов обозначаются 1, 2, 3 или 4. Ответ гарантированно существует.
Пример:
Input: n = 3, paths = [[1,2],[2,3],[3,1]] Output: [1,2,3]👨💻 Алгоритм: 1⃣Создайте граф из садов и путей между ними. 2⃣Присваивание цветов: Для каждого сада выберите тип цветка, который не используется соседними садами. 3⃣Мы будем проходить по каждому саду и выбирать тип цветка, который не совпадает с типами цветов в соседних садах. Поскольку у каждого сада не более трех соседей, всегда будет возможность выбрать тип цветка из 4 возможных типов. 😎 Решение:
function gardenNoAdj($n, $paths) {
$graph = array_fill(0, $n, []);
foreach ($paths as $path) {
$graph[$path[0] - 1][] = $path[1] - 1;
$graph[$path[1] - 1][] = $path[0] - 1;
}
$answer = array_fill(0, $n, 0);
for ($garden = 0; $garden < $n; $garden++) {
$used = [];
foreach ($graph[$garden] as $neighbor) {
$used[$answer[$neighbor]] = true;
}
for ($flower = 1; $flower <= 4; $flower++) {
if (!isset($used[$flower])) {
$answer[$garden] = $flower;
break;
}
}
}
return $answer;
}1 356
Задача: 1119. Remove Vowels from a String
Сложность: easy
Дана строка s, удалите из нее гласные 'a', 'e', 'i', 'o' и 'u' и верните новую строку.
Пример:
Input: s = "leetcodeisacommunityforcoders" Output: "ltcdscmmntyfrcdrs"👨💻 Алгоритм: 1⃣Создайте метод isVowel(), который возвращает true, если переданный символ является одной из гласных [a, e, i, o, u], и false в противном случае. 2⃣Инициализируйте пустую строку ans. 3⃣Пройдитесь по каждому символу в строке s, и для каждого символа c проверьте, является ли он гласной, используя isVowel(c). Если нет, добавьте символ в строку ans. В конце верните строку ans. 😎 Решение:
class Solution {
function removeVowels($s) {
$ans = '';
for ($i = 0; $i < strlen($s); $i++) {
if (!$this->isVowel($s[$i])) {
$ans .= $s[$i];
}
}
return $ans;
}
private function isVowel($c) {
return $c == 'a' || $c == 'e' || $c == 'i' || $c == 'o' || $c == 'u';
}
}1 356
Задача: 1232. Check If It Is a Straight Line
Сложность: easy
Вам дан массив координат, coordinates[i] = [x, y], где [x, y] - координаты точки. Проверьте, образуют ли эти точки прямую линию в плоскости XY.
Пример:
Input: coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]] Output: true👨💻 Алгоритм: 1⃣Определение наклона: Вычисляем наклон между первыми двумя точками и используем его как эталон. 2⃣Проверка других точек: Для всех остальных точек проверяем, совпадает ли наклон, образуемый этими точками с первой точкой, с эталонным наклоном. 3⃣Если все наклоны совпадают, то все точки лежат на одной прямой. 😎 Решение:
function checkStraightLine($coordinates) {
list($x0, $y0) = $coordinates[0];
list($x1, $y1) = $coordinates[1];
foreach ($coordinates as $coord) {
list($x, $y) = $coord;
if (($x1 - $x0) * ($y - $y0) !== ($y1 - $y0) * ($x - $x0)) {
return false;
}
}
return true;
}1 356
Задача: 270. Closest Binary Search Tree Value
Сложность: easy
Дано корень бинарного дерева поиска и целевое значение. Верните значение в дереве, которое ближе всего к целевому. Если существует несколько ответов, выведите наименьшее.
Пример:
Input: root = [4,2,5,1,3], target = 3.714286 Output: 4👨💻 Алгоритм: 1⃣Построить массив с помощью inorder обхода: Выполнить inorder обход дерева и собрать элементы в отсортированный массив. 2⃣Найти ближайший элемент: Пройти по массиву и определить элемент, наиболее близкий к целевому значению. 3⃣Выбрать наименьший из ближайших элементов: Если несколько элементов одинаково близки к целевому значению, выбрать наименьший из них. 😎 Решение:
class Solution {
function closestValue($root, $target) {
$closest = $root->val;
while ($root) {
if (abs($root->val - $target) < abs($closest - $target)) {
$closest = $root->val;
} else if (abs($root->val - $target) == abs($closest - $target)) {
$closest = min($root->val, $closest);
}
$root = $target < $root->val ? $root->left : $root->right;
}
return $closest;
}
}
Ставь 👍 и забирай 📚 Базу знаний1 356
Repost from easyoffer
Я поставил целью сбора скромные 300 тыс. рублей, но ребята, вы накидали больше млн. всего за 1 день. Это просто невероятно!
Благодаря вашей поддержке, я смогу привлечь еще больше людей для разработки сайта и обработки собеседований. Ваш вклад сделает проект качественнее и ускорит его выход! Огромное вам спасибо!
Краудфандинг будет продолжаться еще 31 день и все кто поддержать проект сейчас, до его выхода, смогут получить:
🚀 PRO-тариф на 1 год, по цене месячной подписки на релизе.
➕ Доступ к закрытому бета-тесту easyoffer 2.0 (середина–конец мая)
Поддержать проект можно здесь:
https://planeta.ru/campaigns/easyoffer
Огромное спасибо за вашу поддержку! 🤝
