PHP | LeetCode
Kanalga Telegram’da o‘tish
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @sendme_ads
Ko'proq ko'rsatish1 311
Obunachilar
-124 soatlar
-37 kun
-1930 kun
Postlar arxiv
1 311
Задача: 1043. Partition Array for Maximum Sum
Сложность: medium
Если задан целочисленный массив arr, разбейте его на (смежные) подмассивы длины не более k. После разбиения значения каждого подмассива меняются так, чтобы стать максимальным значением этого подмассива. Верните наибольшую сумму заданного массива после разбиения. Тестовые примеры генерируются таким образом, чтобы ответ умещался в 32-битное целое число.
Пример:
Input: arr = [1,15,7,9,2,5,10], k = 3 Output: 84👨💻 Алгоритм: 1⃣Инициализация: Создаем массив dp, где dp[i] будет хранить наибольшую сумму подмассива, заканчивающегося в позиции i. 2⃣Заполнение массива dp: Проходим по массиву arr и для каждой позиции i пытаемся разбить подмассив длины до k и обновить dp[i] с максимальной возможной суммой. 3⃣Поддержание максимального значения в подмассиве: Для каждого подмассива длины 1 до k, вычисляем максимальное значение в этом подмассиве и обновляем dp[i]. 😎 Решение:
function maxSumAfterPartitioning($arr, $k) {
$n = count($arr);
$dp = array_fill(0, $n, 0);
for ($i = 0; $i < $n; $i++) {
$maxVal = 0;
for ($j = 1; $j <= $k; $j++) {
if ($i - $j + 1 >= 0) {
$maxVal = max($maxVal, $arr[$i - $j + 1]);
if ($i - $j >= 0) {
$dp[$i] = max($dp[$i], $dp[$i - $j] + $maxVal * $j);
} else {
$dp[$i] = max($dp[$i], $maxVal * $j);
}
}
}
}
return $dp[$n - 1];
}
Ставь 👍 и забирай 📚 Базу знаний1 311
Задача: 1146. Snapshot Array
Сложность: medium
Реализуйте SnapshotArray, который поддерживает следующий интерфейс:
SnapshotArray(int length) инициализирует структуру данных, похожую на массив, с заданной длиной. Изначально каждый элемент равен 0.
void set(index, val) устанавливает элемент с заданным индексом равным val.
int snap() делает снимок массива и возвращает snap_id: общее количество вызовов snap() минус 1.
int get(index, snap_id) возвращает значение на заданном индексе в момент, когда мы сделали снимок с указанным snap_id.
Пример:
Input: ["SnapshotArray","set","snap","set","get"]
[[3],[0,5],[],[0,6],[0,0]]
Output: [null,null,0,null,5]
Explanation:
SnapshotArray snapshotArr = new SnapshotArray(3); // set the length to be 3
snapshotArr.set(0,5); // Set array[0] = 5
snapshotArr.snap(); // Take a snapshot, return snap_id = 0
snapshotArr.set(0,6);
snapshotArr.get(0,0); // Get the value of array[0] with snap_id = 0, return 5
👨💻 Алгоритм:
1⃣Инициализация: Для каждого элемента nums[i] в массиве создайте пустой список для хранения его исторических значений в формате [snap_id, value]. Инициализируйте каждый список, добавив первую запись [0, 0].
2⃣Метод set: Добавьте историческую запись [snap_id, value] в список записей historyRecords[index].
3⃣Методы snap и get:
Метод snap возвращает snap_id и увеличивает его на 1.
Метод get использует бинарный поиск, чтобы найти индекс последней вставки snap_id в данный снимок (целевой индекс будет snap_index - 1). Возвращает historyRecords[index][snap_index - 1][1].
😎 Решение:
class SnapshotArray {
private $snapId;
private $historyRecords;
function __construct($length) {
$this->snapId = 0;
$this->historyRecords = array_fill(0, $length, [0 => 0]);
}
function set($index, $val) {
$this->historyRecords[$index][$this->snapId] = $val;
}
function snap() {
$this->snapId++;
return $this->snapId - 1;
}
function get($index, $snapId) {
while ($snapId >= 0) {
if (isset($this->historyRecords[$index][$snapId])) {
return $this->historyRecords[$index][$snapId];
}
$snapId--;
}
return 0;
}
}
Ставь 👍 и забирай 📚 Базу знаний1 311
Задача: 1466. Reorder Routes to Make All Paths Lead to the City Zero
Сложность: medium
Дано n городов, пронумерованных от 0 до n - 1, и n - 1 дорог, таких, что существует только один путь между двумя различными городами (эта сеть образует дерево). В прошлом году Министерство транспорта решило направить дороги в одном направлении, потому что они слишком узкие.
Дороги представлены массивом connections, где connections[i] = [ai, bi] представляет дорогу от города ai до города bi.
В этом году в столице (город 0) будет большое событие, и многие люди хотят приехать в этот город.
Ваша задача состоит в том, чтобы переориентировать некоторые дороги так, чтобы каждый город мог посетить город 0. Верните минимальное количество изменённых дорог.
Гарантируется, что каждый город может добраться до города 0 после перенаправления.
Пример:
Input: n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
Output: 3
Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).
👨💻 Алгоритм:
1⃣Создайте переменную count для подсчета количества рёбер, которые необходимо изменить. Инициализируйте её нулём. Создайте список смежности adj, который содержит список пар целых чисел так, чтобы adj[node] содержал всех соседей node в форме (neighbor, sign), где neighbor - соседний узел, а sign обозначает направление ребра (оригинальное или искусственное).
2⃣Начните обход в глубину (DFS). Используйте функцию dfs для выполнения обхода. В каждом вызове передавайте параметры node, parent и adj. Начните с узла 0 и parent равным -1.
3⃣Перебирайте всех соседей узла с помощью adj[node]. Для каждого neighbor, sign в adj[node], проверьте, равен ли neighbor родителю. Если равен, не посещайте его снова. Если neighbor не равен parent, выполните count += sign и рекурсивно вызовите dfs с node = neighbor и parent = node. По завершении обхода DFS, в count будет содержаться количество рёбер, которые необходимо изменить. Верните count.
😎 Решение:
class Solution {
private $count = 0;
function dfs($node, $parent, $adj) {
if (!isset($adj[$node])) return;
foreach ($adj[$node] as $nei) {
list($neighbor, $sign) = $nei;
if ($neighbor != $parent) {
$this->count += $sign;
$this->dfs($neighbor, $node, $adj);
}
}
}
function minReorder($n, $connections) {
$adj = [];
foreach ($connections as $connection) {
$adj[$connection[0]][] = [$connection[1], 1];
$adj[$connection[1]][] = [$connection[0], 0];
}
$this->dfs(0, -1, $adj);
return $this->count;
}
}
Ставь 👍 и забирай 📚 Базу знаний1 311
Задача: 1535. Find the Winner of an Array Game
Сложность: medium
Дан целочисленный массив
arr из различных целых чисел и целое число k.
Игра будет проводиться между первыми двумя элементами массива (т.е. arr[0] и arr[1]). В каждом раунде игры мы сравниваем arr[0] с arr[1], большее число побеждает и остается на позиции 0, а меньшее число перемещается в конец массива. Игра заканчивается, когда одно число выигрывает k подряд раундов.
Верните число, которое выиграет игру.
Гарантируется, что у игры будет победитель.
Пример:
Input: arr = [2,1,3,5,4,6,7], k = 2
Output: 5
Explanation: Let's see the rounds of the game:
Round | arr | winner | win_count
1 | [2,1,3,5,4,6,7] | 2 | 1
2 | [2,3,5,4,6,7,1] | 3 | 1
3 | [3,5,4,6,7,1,2] | 5 | 1
4 | [5,4,6,7,1,2,3] | 5 | 2
So we can see that 4 rounds will be played and 5 is the winner because it wins 2 consecutive games.
👨💻 Алгоритм:
1⃣Инициализируйте maxElement как максимальный элемент в arr, queue как очередь с элементами массива, кроме первого, curr = arr[0] и winstreak = 0.
2⃣Пока очередь не пуста (или используйте бесконечный цикл), извлеките opponent из начала очереди. Если curr > opponent, добавьте opponent в конец очереди и увеличьте winstreak на 1. В противном случае добавьте curr в конец очереди, установите curr = opponent и winstreak = 1.
3⃣Если winstreak = k или curr = maxElement, верните curr. Код никогда не должен достигать этой точки, так как гарантированно есть победитель. Верните любое значение.
😎 Решение:
class Solution {
function getWinner($arr, $k) {
$maxElement = $arr[0];
$queue = array_slice($arr, 1);
for ($i = 1; $i < count($arr); $i++) {
$maxElement = max($maxElement, $arr[$i]);
}
$curr = $arr[0];
$winstreak = 0;
while (!empty($queue)) {
$opponent = array_shift($queue);
if ($curr > $opponent) {
array_push($queue, $opponent);
$winstreak++;
} else {
array_push($queue, $curr);
$curr = $opponent;
$winstreak = 1;
}
if ($winstreak == $k || $curr == $maxElement) {
return $curr;
}
}
return -1;
}
}
Ставь 👍 и забирай 📚 Базу знаний1 311
Задача: 1276. Number of Burgers with No Waste of Ingredients
Сложность: medium
Даны два целых числа tomatoSlices и cheeseSlices. Ингредиенты разных бургеров таковы: Jumbo Burger: 4 ломтика помидора и 1 ломтик сыра. Small Burger: 2 ломтика помидора и 1 ломтик сыра. Верните [total_jumbo, total_small] так, чтобы количество оставшихся tomatoSlices было равно 0, а количество оставшихся cheeseSlices было равно 0. Если невозможно сделать так, чтобы оставшиеся tomatoSlices и cheeseSlices были равны 0, верните [].
Пример:
Input: tomatoSlices = 16, cheeseSlices = 7 Output: [1,6]👨💻 Алгоритм: 1⃣Проверьте, возможно ли решить задачу, убедившись, что tomatoSlices четно и находится в допустимых пределах. 2⃣Решите систему уравнений: 4J + 2S = tomatoSlices J + S = cheeseSlices 3⃣Если решение существует, верните его, иначе верните пустой список. 😎 Решение:
function numOfBurgers($tomatoSlices, $cheeseSlices) {
if ($tomatoSlices % 2 != 0 || $tomatoSlices < 2 * $cheeseSlices || $tomatoSlices > 4 * $cheeseSlices) {
return [];
}
$total_jumbo = ($tomatoSlices - 2 * $cheeseSlices) / 2;
$total_small = $cheeseSlices - $total_jumbo;
return [$total_jumbo, $total_small];
}
Ставь 👍 и забирай 📚 Базу знаний1 311
Задача: 928. Minimize Malware Spread II
Сложность: hard
Вам дана сеть из n узлов, представленная в виде графа с матрицей смежности n x n, где i-й узел непосредственно связан с j-м узлом, если graph[i][j] == 1. Некоторые узлы изначально заражены вредоносным ПО. Если два узла соединены напрямую и хотя бы один из них заражен вредоносным ПО, то оба узла будут заражены вредоносным ПО. Такое распространение вредоносного ПО будет продолжаться до тех пор, пока больше не останется ни одного узла, зараженного таким образом. Предположим, что M(initial) - это конечное число узлов, зараженных вредоносным ПО, во всей сети после прекращения распространения вредоносного ПО. Мы удалим ровно один узел из initial, полностью удалив его и все связи от этого узла к любому другому узлу. Верните узел, который, если его удалить, минимизирует M(initial). Если для минимизации M(initial) можно удалить несколько узлов, верните такой узел с наименьшим индексом.
Пример:
Input: graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1] Output: 0👨💻 Алгоритм: 1⃣Определить компоненты связности в графе. Для каждой компоненты связности определить количество зараженных узлов и общее количество узлов. 2⃣Для каждого узла в initial удалить его и пересчитать количество зараженных узлов. 3⃣Найти узел, удаление которого минимизирует количество зараженных узлов. Если несколько узлов минимизируют количество зараженных узлов одинаково, выбрать узел с наименьшим индексом. 😎 Решение:
function minMalwareSpread($graph, $initial) {
$n = count($graph);
$components = [];
$visited = [];
function dfs($graph, $node, &$component, &$visited) {
$stack = [$node];
while (!empty($stack)) {
$u = array_pop($stack);
if (!isset($visited[$u])) {
$visited[$u] = true;
$component[] = $u;
foreach ($graph[$u] as $v => $connected) {
if ($connected == 1 && !isset($visited[$v])) {
$stack[] = $v;
}
}
}
}
}
for ($i = 0; $i < $n; $i++) {
if (!isset($visited[$i])) {
$component = [];
dfs($graph, $i, $component, $visited);
$components[] = $component;
}
}
$infectedInComponent = array_fill(0, count($components), 0);
$nodeToComponent = array_fill(0, $n, -1);
foreach ($components as $idx => $component) {
foreach ($component as $node) {
$nodeToComponent[$node] = $idx;
if (in_array($node, $initial)) {
$infectedInComponent[$idx]++;
}
}
}
$minInfected = PHP_INT_MAX;
$resultNode = min($initial);
foreach ($initial as $node) {
$componentIdx = $nodeToComponent[$node];
if ($infectedInComponent[$componentIdx] == 1) {
$componentSize = count($components[$componentIdx]);
if ($componentSize < $minInfected || ($componentSize == $minInfected && $node < $resultNode)) {
$minInfected = $componentSize;
$resultNode = $node;
}
}
}
return $resultNode;
}
Ставь 👍 и забирай 📚 Базу знаний1 311
Задача: 1240. Tiling a Rectangle with the Fewest Squares
Сложность: hard
Если задан прямоугольник размером n x m, верните минимальное количество квадратов с целочисленными сторонами, которые покрывают этот прямоугольник.
Пример:
Input: n = 2, m = 3 Output: 3👨💻 Алгоритм: 1⃣Инициализация рекурсивной функции: Функция принимает размеры прямоугольника n x m. 2⃣Базовый случай: Если n = 0 или m = 0, возвращаем 0, так как не осталось пространства для покрытия. 3⃣Рекурсивный случай: Находим наибольший возможный квадрат, который может быть размещен в текущем прямоугольнике. Это квадрат со стороной min(n, m). Размещаем этот квадрат в левом верхнем углу и рекурсивно покрываем оставшиеся три части: Прямоугольник слева от квадрата. Прямоугольник сверху от квадрата. Прямоугольник справа и снизу от квадрата. 😎 Решение:
function tilingRectangle($n, $m) {
$dp = array_fill(0, $n + 1, array_fill(0, $m + 1, PHP_INT_MAX));
for ($i = 1; $i <= min($n, $m); $i++) {
$dp[$i][$i] = 1;
}
for ($h = 1; $h <= $n; $h++) {
for ($w = 1; $w <= $m; $w++) {
if ($h == $w) continue;
for ($i = 1; $i <= intdiv($h, 2); $i++) {
$dp[$h][$w] = min($dp[$h][$w], $dp[$i][$w] + $dp[$h - $i][$w]);
}
for ($j = 1; $j <= intdiv($w, 2); $j++) {
$dp[$h][$w] = min($dp[$h][$w], $dp[$h][$j] + $dp[$h][$w - $j]);
}
}
}
return $dp[$n][$m];
}
Ставь 👍 и забирай 📚 Базу знаний1 311
Задача: 942. DI String Match
Сложность: easy
Перестановка perm из n + 1 целых чисел всех целых чисел в диапазоне [0, n] может быть представлена в виде строки s длины n, где: s[i] == 'I', если perm[i] < perm[i + 1], и s[i] == 'D', если perm[i] > perm[i + 1]. Получив строку s, восстановите перестановку perm и верните ее. Если существует несколько допустимых перестановок perm, верните любую из них.
Пример:
Input: s = "IDID" Output: [0,4,1,3,2]👨💻 Алгоритм: 1⃣Инициализировать два указателя low и high для отслеживания минимального и максимального числа, которые можно использовать в перестановке. 2⃣Создать массив perm длиной n + 1. Пройти по строке s: Если текущий символ равен 'I', добавить low в текущую позицию perm и увеличить low. Если текущий символ равен 'D', добавить high в текущую позицию perm и уменьшить high. Добавить оставшееся значение (low или high, так как они будут равны) в последнюю позицию perm. 3⃣Вернуть массив perm. 😎 Решение:
function diStringMatch($s) {
$n = strlen($s);
$low = 0;
$high = $n;
$perm = array_fill(0, $n + 1, 0);
for ($i = 0; $i < $n; $i++) {
if ($s[$i] == 'I') {
$perm[$i] = $low++;
} else {
$perm[$i] = $high--;
}
}
$perm[$n] = $low;
return $perm;
}
Ставь 👍 и забирай 📚 Базу знаний1 311
Задача: 260. Single Number III
Сложность: medium
Дан целочисленный массив nums, в котором ровно два элемента встречаются только один раз, а все остальные элементы встречаются ровно дважды. Найдите два элемента, которые встречаются только один раз. Вы можете вернуть ответ в любом порядке.
Вы должны написать алгоритм, который работает за линейное время и использует только постоянное дополнительное пространство..
Пример:
Input: nums = [1,2,1,3,2,5] Output: [3,5] Explanation: [5, 3] is also a valid answer.👨💻 Алгоритм: 1⃣Выполните XOR для всех элементов массива nums. Это даст результат, который является XOR двух уникальных чисел. 2⃣Найдите бит, который отличается в этих двух числах, чтобы разделить все числа в массиве на две группы. 3⃣Выполните XOR для каждой группы, чтобы найти два уникальных числа. 😎 Решение:
class Solution {
public function singleNumber($nums) {
$xor = 0;
foreach ($nums as $num) {
$xor ^= $num;
}
$diff = $xor & -$xor;
$res = [0, 0];
foreach ($nums as $num) {
if (($num & $diff) == 0) {
$res[0] ^= $num;
} else {
$res[1] ^= $num;
}
}
return $res;
}
}
Ставь 👍 и забирай 📚 Базу знаний1 311
Задача: 434. Number of Segments in a String
Сложность: easy
Дана строка s, верните количество сегментов в строке.
Сегмент определяется как непрерывная последовательность символов, отличных от пробелов.
Пример:
Input: s = "Hello, my name is John" Output: 5 Explanation: The five segments are ["Hello,", "my", "name", "is", "John"]👨💻 Алгоритм: 1⃣Инициализируйте счетчик сегментов segment_count равным 0. 2⃣Итеративно пройдитесь по строке s. Для каждого индекса i проверьте, начинается ли на этом индексе сегмент: Если символ s[i] не является пробелом, и (либо это первый символ строки, либо предыдущий символ s[i-1] является пробелом), увеличьте segment_count. 3⃣Верните segment_count. 😎 Решение:
class Solution {
function countSegments($s) {
$segmentCount = 0;
for ($i = 0; $i < strlen($s); $i++) {
if (($i == 0 || $s[$i - 1] == ' ') && $s[$i] != ' ') {
$segmentCount++;
}
}
return $segmentCount;
}
}
Ставь 👍 и забирай 📚 Базу знаний1 311
Задача: 662. Maximum Width of Binary Tree
Сложность: medium
Дан корень бинарного дерева, верните максимальную ширину данного дерева.
Максимальная ширина дерева - это максимальная ширина среди всех уровней.
Ширина одного уровня определяется как расстояние между конечными узлами (самыми левыми и самыми правыми ненулевыми узлами), где нулевые узлы между конечными узлами, которые присутствовали бы в полном бинарном дереве, продолжающемся до этого уровня, также учитываются при вычислении длины.
Гарантируется, что ответ будет в диапазоне 32-битного знакового целого числа.
Пример:
Input: root = [1,3,2,5,3,null,9] Output: 4 Explanation: The maximum width exists in the third level with length 4 (5,3,null,9).👨💻 Алгоритм: 1⃣Инициализация: Создайте очередь для хранения узлов и их позиций на уровне. Начните с корневого узла и его позиции 0. 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 {
function widthOfBinaryTree($root) {
if ($root === null) return 0;
$maxWidth = 0;
$queue = [[$root, 0]];
while (!empty($queue)) {
$levelSize = count($queue);
$firstPos = $queue[0][1];
for ($i = 0; $i < $levelSize; $i++) {
list($node, $pos) = array_shift($queue);
if ($node->left !== null) $queue[] = [$node->left, 2 * $pos];
if ($node->right !== null) $queue[] = [$node->right, 2 * $pos + 1];
}
$lastPos = !empty($queue) ? end($queue)[1] : $firstPos;
$maxWidth = max($maxWidth, $lastPos - $firstPos + 1);
}
return $maxWidth;
}
}
Ставь 👍 и забирай 📚 Базу знаний1 311
Задача: 345. Reverse Vowels of a String
Сложность: easy
Дана строка s, переверните только все гласные в строке и верните её.
Гласные: 'a', 'e', 'i', 'o', 'u', а также их верхние регистры.
Пример:
Input: s = "hello" Output: "holle"👨💻 Алгоритм: 1⃣Инициализация указателей и гласных: Создайте набор гласных для быстрой проверки. Установите два указателя: один на начало строки (left), другой на конец строки (right). 2⃣Перестановка гласных: Пока левый указатель меньше правого, перемещайте указатели к центру, пока не найдёте гласные. Обменивайте найденные гласные и продолжайте сдвигать указатели. 3⃣Завершение работы: Когда указатели пересекутся, остановите процесс и верните строку. 😎 Решение:
class Solution {
function reverseVowels($s) {
$vowels = ['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'];
$s = str_split($s);
$left = 0;
$right = count($s) - 1;
while ($left < $right) {
if (!in_array($s[$left], $vowels)) {
$left++;
} else if (!in_array($s[$right], $vowels)) {
$right--;
} else {
$temp = $s[$left];
$s[$left] = $s[$right];
$s[$right] = $temp;
$left++;
$right--;
}
}
return implode('', $s);
}
}
Ставь 👍 и забирай 📚 Базу знаний1 311
🔴 Собес на PHP-разработчика с экс-лидом из Bumble в субботу в 15:00
7 ноября (в эту субботу!) в 15:00 мск приходи онлайн на открытое собеседование. Посмотришь, как проходит настоящее интервью на Middle PHP-разработчика
Как это будет:
📂 Глеб Виноградов, Staff Software Engineer в Ad Tyres International, ex-Lead в Bumble, проведёт собес. У Глеба больше 11 лет в разработке. В Bumble он 4 года писал бэкенд для приложений Bumble и Badoo 📂 Глеб задаст реальные вопросы с технических секций и прокомментирует ответы 📂 В конце можно будет задать ему любой вопросУчастие бесплатное. Эфир проходит в рамках менторской программы ШОРТКАТ для разработчиков, которые хотят сменить работу, повысить грейд и зарплату или прокачать навыки Переходи в нашего бота, чтобы получить ссылку на эфир → @shortcut_php_bot Реклама. О рекламодателе.
1 311
Задача: 169. Majority Element
Сложность: easy
Дан массив nums размера n, верните элемент большинства.
Элемент большинства — это элемент, который встречается более чем ⌊n / 2⌋ раз. Можно предположить, что элемент большинства всегда существует в массиве.
Пример:
Input: nums = [3,2,3] Output: 3👨💻 Алгоритм: 1⃣Использование HashMap для подсчета: Создайте HashMap для отслеживания количества каждого элемента в массиве. 2⃣Подсчет вхождений элементов: Пройдите по массиву nums, увеличивая счетчик в HashMap для каждого элемента. 3⃣Поиск элемента большинства: Определите элемент большинства, просмотрев HashMap и найдя ключ с максимальным значением, которое должно быть больше ⌊n / 2⌋ 😎 Решение:
function majorityElement($nums) {
$counts = [];
foreach ($nums as $num) {
if (!isset($counts[$num])) {
$counts[$num] = 1;
} else {
$counts[$num]++;
}
}
foreach ($counts as $num => $count) {
if ($count > count($nums) / 2) {
return $num;
}
}
return 0;
}
Ставь 👍 и забирай 📚 Базу знаний1 311
🔥 Скрытые вакансии с удаленной работой для PHP разработчика, которые нигде больше не публикуются. Напрямую от компаний, с контактами рекрутеров.
🔹 PHP Jobs | Вакансии
🔸 Все каналы с вакансиями
1 311
Задача: 1125. Smallest Sufficient Team
Сложность: hard
В проекте у вас есть список необходимых навыков req_skills и список людей. i-й человек people[i] содержит список навыков, которыми обладает этот человек.
Рассмотрим достаточную команду: набор людей, такой что для каждого необходимого навыка из req_skills, есть по крайней мере один человек в команде, который обладает этим навыком. Мы можем представить эти команды индексами каждого человека.
Например, команда = [0, 1, 3] представляет людей с навыками people[0], people[1] и people[3].
Верните любую достаточную команду наименьшего возможного размера, представленную индексами каждого человека. Вы можете вернуть ответ в любом порядке.
Гарантируется, что ответ существует.
Пример:
Input: req_skills = ["algorithms","math","java","reactjs","csharp","aws"], people = [["algorithms","math","java"],["algorithms","math","reactjs"], ["java","csharp","aws"],["reactjs","csharp"],["csharp","math"],["aws","java"]] Output: [1,2]👨💻 Алгоритм: 1⃣Инициализация и создание масок навыков: Определите количество людей n и количество необходимых навыков m. Создайте хэш-таблицу skillId, чтобы сопоставить каждому навыку уникальный индекс. Создайте массив skillsMaskOfPerson, который будет содержать битовые маски навыков для каждого человека. 2⃣Динамическое программирование (DP): Создайте массив dp размера 2^m и заполните его значениями (1 << n) - 1. Установите dp[0] в 0 (базовый случай). Для каждого skillsMask от 1 до 2^m - 1: - для каждого человека i: - вычислите smallerSkillsMask как skillsMask & ~skillsMaskOfPerson[i]. - если smallerSkillsMask отличается от skillsMask, обновите dp[skillsMask], если новая команда лучше (имеет меньше установленных битов). 3⃣Формирование ответа: Извлеките ответ из dp и верните массив индексов людей, составляющих минимальную достаточную команду. 😎 Решение:
class Solution {
function smallestSufficientTeam($req_skills, $people) {
$n = count($people);
$m = count($req_skills);
$skillId = array_flip($req_skills);
$skillsMaskOfPerson = array_fill(0, $n, 0);
foreach ($people as $i => $person) {
foreach ($person as $skill) {
if (isset($skillId[$skill])) {
$skillsMaskOfPerson[$i] |= 1 << $skillId[$skill];
}
}
}
$dp = array_fill(0, 1 << $m, (1 << $n) - 1);
$dp[0] = 0;
for ($skillsMask = 1; $skillsMask < (1 << $m); $skillsMask++) {
foreach ($skillsMaskOfPerson as $i => $mask) {
$smallerSkillsMask = $skillsMask & ~$mask;
if ($smallerSkillsMask != $skillsMask) {
$peopleMask = $dp[$smallerSkillsMask] | (1 << $i);
if (substr_count(decbin($peopleMask), '1') < substr_count(decbin($dp[$skillsMask]), '1')) {
$dp[$skillsMask] = $peopleMask;
}
}
}
}
$answerMask = $dp[(1 << $m) - 1];
$result = [];
for ($i = 0; $i < $n; $i++) {
if (($answerMask >> $i) & 1) {
$result[] = $i;
}
}
return $result;
}
}
Ставь 👍 и забирай 📚 Базу знаний1 311
Задача: 1319. Number of Operations to Make Network Connected
Сложность: medium
Дано n компьютеров, пронумерованных от 0 до n - 1, соединённых Ethernet-кабелями connections, образующими сеть, где connections[i] = [ai, bi] представляет собой соединение между компьютерами ai и bi. Любой компьютер может достичь любого другого компьютера напрямую или косвенно через сеть.
Вам даны начальные соединения сети. Вы можете извлекать определённые кабели между двумя напрямую соединёнными компьютерами и размещать их между любыми парами несоединённых компьютеров, чтобы сделать их напрямую соединёнными.
Верните минимальное количество раз, которое необходимо сделать это, чтобы соединить все компьютеры. Если это невозможно, верните -1.
Пример:
Input: n = 4, connections = [[0,1],[0,2],[1,2]]
Output: 1
Explanation: Remove cable between computer 1 and 2 and place between computers 1 and 3.
👨💻 Алгоритм:
1⃣Проверьте размер connections. Если он меньше n - 1, у нас недостаточно ребер, чтобы соединить весь граф. В этом случае возвращаем -1.
2⃣Создайте список смежности с помощью connections, где adj[x] содержит всех соседей узла x. Создайте целое число numberOfConnectedComponents, которое хранит количество компонент связности в графе. Инициализируйте его значением 0.
3⃣Создайте массив visit длиной n для отслеживания посещенных узлов. Пройдите по всем узлам, и для каждого узла i проверьте, был ли он посещен. Если узел i не был посещен, увеличьте numberOfConnectedComponents на 1 и начните обход DFS:
Используйте функцию dfs для выполнения обхода. Для каждого вызова передавайте узел, ребра и visit в качестве параметров, начиная с узла i.
Отметьте узел как посещенный.
Пройдитесь по всем соседям узла. Если какой-либо сосед еще не был посещен, рекурсивно вызовите dfs с этим соседом в качестве узла.
Верните numberOfConnectedComponents - 1.
😎 Решение:
class Solution {
private function dfs($node, $adj, &$visit) {
$visit[$node] = true;
if (!isset($adj[$node])) {
return;
}
foreach ($adj[$node] as $neighbor) {
if (!$visit[$neighbor]) {
$visit[$neighbor] = true;
$this->dfs($neighbor, $adj, $visit);
}
}
}
function makeConnected($n, $connections) {
if (count($connections) < $n - 1) {
return -1;
}
$adj = [];
foreach ($connections as $connection) {
$adj[$connection[0]][] = $connection[1];
$adj[$connection[1]][] = $connection[0];
}
$numberOfConnectedComponents = 0;
$visit = array_fill(0, $n, false);
for ($i = 0; $i < $n; $i++) {
if (!$visit[$i]) {
$numberOfConnectedComponents++;
$this->dfs($i, $adj, $visit);
}
}
return $numberOfConnectedComponents - 1;
}
}
Ставь 👍 и забирай 📚 Базу знаний1 311
Задача: 354. Russian Doll Envelopes
Сложность: hard
Вам дан двумерный массив целых чисел envelopes, где envelopes[i] = [wi, hi] представляет ширину и высоту конверта.
Один конверт может поместиться в другой, если и только если ширина и высота одного конверта больше ширины и высоты другого конверта.
Верните максимальное количество конвертов, которые вы можете вложить друг в друга (т.е. поместить один в другой).
Примечание: Вы не можете поворачивать конверт.
Пример:
Input: envelopes = [[5,4],[6,4],[6,7],[2,3]] Output: 3 Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).👨💻 Алгоритм: 1⃣Отсортируйте массив конвертов по возрастанию по первой размерности (ширине) и по убыванию по второй размерности (высоте). 2⃣Извлеките вторую размерность (высоты) отсортированного массива. 3⃣Найдите длину наибольшей возрастающей подпоследовательности в массиве высот. 😎 Решение:
class Solution {
function lengthOfLIS($nums) {
$dp = [];
foreach ($nums as $num) {
$i = $this->binarySearch($dp, $num);
if ($i < 0) $i = -($i + 1);
$dp[$i] = $num;
}
return count($dp);
}
function binarySearch($arr, $target) {
$left = 0;
$right = count($arr);
while ($left < $right) {
$mid = intdiv($left + $right, 2);
if ($arr[$mid] < $target) {
$left = $mid + 1;
} else {
$right = $mid;
}
}
return ($left < count($arr) && $arr[$left] == $target) ? $left : -($left + 1);
}
function maxEnvelopes($envelopes) {
usort($envelopes, function($a, $b) {
return $a[0] == $b[0] ? $b[1] - $a[1] : $a[0] - $b[0];
});
$secondDim = array_map(function($envelope) {
return $envelope[1];
}, $envelopes);
return $this->lengthOfLIS($secondDim);
}
}
Ставь 👍 и забирай 📚 Базу знаний1 311
Задача: 553. Optimal Division
Сложность: medium
Дано целочисленный массив nums. Соседние целые числа в nums будут выполнять деление с плавающей запятой.
Например, для nums = [2,3,4] мы будем вычислять выражение "2/3/4".
Однако, вы можете добавить любое количество скобок в любое место, чтобы изменить приоритет операций. Вы хотите добавить эти скобки так, чтобы значение выражения после вычисления было максимальным.
Верните соответствующее выражение, которое имеет максимальное значение в строковом формате.
Пример:
Input: nums = [1000,100,10,2] Output: "1000/(100/10/2)" Explanation: 1000/(100/10/2) = 1000/((100/10)/2) = 200 However, the bold parenthesis in "1000/((100/10)/2)" are redundant since they do not influence the operation priority. So you should return "1000/(100/10/2)". Other cases: 1000/(100/10)/2 = 50 1000/(100/(10/2)) = 50 1000/100/10/2 = 0.5 1000/100/(10/2) = 2👨💻 Алгоритм: 1⃣Разверните оба числа. Инициализируйте массив ans с (N+M) нулями. Для каждой цифры во втором числе: держите переменную переноса, изначально равную 0. Инициализируйте массив (currentResult), начинающийся с некоторых нулей в зависимости от места цифры во втором числе. 2⃣Для каждой цифры первого числа: умножьте цифру второго числа на цифру первого числа и добавьте предыдущий перенос к результату умножения. Возьмите остаток от деления на 10, чтобы получить последнюю цифру. Добавьте последнюю цифру к массиву currentResult. Разделите результат умножения на 10, чтобы получить новое значение переноса. 3⃣После итерации по каждой цифре в первом числе, если перенос не равен нулю, добавьте перенос к массиву currentResult. Добавьте currentResult к массиву ans. Если последняя цифра в ans равна нулю, перед разворотом ans удалите этот ноль, чтобы избежать ведущего нуля в окончательном ответе. Разверните ans и верните его. 😎 Решение:
class Solution {
private function addStrings($num1, $num2) {
$ans = [];
$carry = 0;
$n1 = count($num1);
$n2 = count($num2);
for ($i = 0; $i < max($n1, $n2) || $carry; $i++) {
$digit1 = $i < $n1 ? $num1[$i] : 0;
$digit2 = $i < $n2 ? $num2[$i] : 0;
$sum = $digit1 + $digit2 + $carry;
$carry = intdiv($sum, 10);
$ans[] = $sum % 10;
}
return $ans;
}
private function multiplyOneDigit($firstNumber, $secondNumberDigit, $numZeros) {
$currentResult = array_fill(0, $numZeros, 0);
$carry = 0;
for ($i = 0; $i < strlen($firstNumber); $i++) {
$multiplication = (intval($secondNumberDigit) * intval($firstNumber[$i])) + $carry;
$carry = intdiv($multiplication, 10);
$currentResult[] = $multiplication % 10;
}
if ($carry != 0) {
$currentResult[] = $carry;
}
return $currentResult;
}
public function multiply($firstNumber, $secondNumber) {
if ($firstNumber === "0" || $secondNumber === "0") {
return "0";
}
$firstNumber = strrev($firstNumber);
$secondNumber = strrev($secondNumber);
$ans = array_fill(0, strlen($firstNumber) + strlen($secondNumber), 0);
for ($i = 0; $i < strlen($secondNumber); $i++) {
$ans = $this->addStrings($this->multiplyOneDigit($firstNumber, $secondNumber[$i], $i), $ans);
}
while (end($ans) === 0) {
array_pop($ans);
}
return implode('', array_reverse($ans));
}
}
Ставь 👍 и забирай 📚 Базу знаний1 311
Задача: 1396. Design Underground System
Сложность: medium
Подземная железнодорожная система отслеживает время поездок между станциями для вычисления среднего времени поездки от одной станции до другой.
Реализуйте класс UndergroundSystem:
- void checkIn(int id, string stationName, int t)
Пассажир с карточкой, идентификатор которой равен id, регистрируется на станции stationName в момент времени t.
Пассажир может быть зарегистрирован только в одном месте в одно и то же время.
- void checkOut(int id, string stationName, int t)
Пассажир с карточкой, идентификатор которой равен id, покидает станцию stationName в момент времени t.
- double getAverageTime(string startStation, string endStation)
Возвращает среднее время, необходимое для поездки от startStation до endStation.
Среднее время рассчитывается на основе всех предыдущих поездок от startStation до endStation, где пассажиры зарегистрировались на startStation и вышли на endStation. Время поездки от startStation до endStation может отличаться от времени поездки от endStation до startStation. Перед вызовом getAverageTime как минимум один пассажир уже совершил поездку от startStation до endStation. Предполагается, что все вызовы методов checkIn и checkOut последовательны и происходят в хронологическом порядке.
Пример:
Input
["UndergroundSystem","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime"]
[[],[10,"Leyton",3],[10,"Paradise",8],["Leyton","Paradise"],[5,"Leyton",10],[5,"Paradise",16],["Leyton","Paradise"],[2,"Leyton",21],[2,"Paradise",30],["Leyton","Paradise"]]
Output
[null,null,null,5.00000,null,null,5.50000]
Explanation
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(10, "Leyton", 3);
undergroundSystem.checkOut(10, "Paradise", 8); // Customer 10 "Leyton" -> "Paradise" in 8-3 = 5
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.00000, (5) / 1 = 5
undergroundSystem.checkIn(5, "Leyton", 10);
undergroundSystem.checkOut(5, "Paradise", 16); // Customer 5 "Leyton" -> "Paradise" in 16-10 = 6
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.50000, (5 + 6) / 2 = 5.5
👨💻 Алгоритм:
1⃣При регистрации на входе сохраняем информацию о начале пути (станция и время) в словаре checkInData.
2⃣При регистрации на выходе извлекаем информацию о начале пути из checkInData, вычисляем время поездки и обновляем статистику для маршрута в journeyData.
3⃣Для получения среднего времени поездки по заданному маршруту извлекаем статистику из journeyData и вычисляем среднее значение.
😎 Решение:
class UndergroundSystem {
private $journeyData;
private $checkInData;
function __construct() {
$this->journeyData = [];
$this->checkInData = [];
}
function checkIn($id, $stationName, $t) {
$this->checkInData[$id] = [$stationName, $t];
}
function checkOut($id, $stationName, $t) {
list($startStation, $startTime) = $this->checkInData[$id];
unset($this->checkInData[$id]);
$routeKey = "{$startStation}->{$stationName}";
$tripTime = $t - $startTime;
if (!isset($this->journeyData[$routeKey])) {
$this->journeyData[$routeKey] = [0, 0];
}
list($totalTime, $trips) = $this->journeyData[$routeKey];
$this->journeyData[$routeKey] = [$totalTime + $tripTime, $trips + 1];
}
function getAverageTime($startStation, $endStation) {
list($totalTime, $trips) = $this->journeyData["{$startStation}->{$endStation}"];
return $totalTime / $trips;
}
}
Ставь 👍 и забирай 📚 Базу знаний