PHP | LeetCode
前往频道在 Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @sendme_ads
显示更多
网络:1 322
订阅者
-124 小时
-57 天
-2130 天
帖子存档
1 320
🎃 3 часа до полуночи...
Ровно в 00:00 предложение исчезнет, как призрак на рассвете 👻 Последний шанс забрать PRO навсегда по цене одного года. Без продлений и без воскрешений.
Если откладывал — не дай этой возможности стать твоим ночным кошмаром 🦇
👉 https://easyoffer.ru/pro
1 320
Задача: 256. Paint House
Сложность: medium
Есть ряд из n домов, где каждый дом можно покрасить в один из трёх цветов: красный, синий или зелёный. Стоимость покраски каждого дома в определённый цвет разная. Необходимо покрасить все дома так, чтобы никакие два соседних дома не были окрашены в один и тот же цвет.
Стоимость покраски каждого дома в определённый цвет представлена в виде матрицы стоимости n x 3.
Например, costs[0][0] — это стоимость покраски дома 0 в красный цвет; costs[1][2] — это стоимость покраски дома 1 в зелёный цвет и так далее...
Верните минимальную стоимость покраски всех домов.
Пример:
Input: costs = [[17,2,17],[16,16,5],[14,3,19]] Output: 10 Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue. Minimum cost: 2 + 5 + 3 = 10.👨💻 Алгоритм: 1⃣Инициализируйте массив dp размера n x 3 для хранения минимальных затрат на покраску домов. Установите начальные значения для первого дома: dp[0][0] = costs[0][0], dp[0][1] = costs[0][1], dp[0][2] = costs[0][2]. 2⃣Для каждого дома i от 1 до n-1 обновите значения массива dp: dp[i][0] = costs[i][0] + min(dp[i-1][1], dp[i-1][2]) dp[i][1] = costs[i][1] + min(dp[i-1][0], dp[i-1][2]) dp[i][2] = costs[i][2] + min(dp[i-1][0], dp[i-1][1]) 3⃣Верните минимальное значение из последней строки массива dp: min(dp[n-1][0], dp[n-1][1], dp[n-1][2]). 😎 Решение:
class Solution {
function minCost($costs) {
$n = count($costs);
$dp = array_fill(0, $n, array_fill(0, 3, 0));
$dp[0] = $costs[0];
for ($i = 1; $i < $n; $i++) {
$dp[$i][0] = $costs[$i][0] + min($dp[$i-1][1], $dp[$i-1][2]);
$dp[$i][1] = $costs[$i][1] + min($dp[$i-1][0], $dp[$i-1][2]);
$dp[$i][2] = $costs[$i][2] + min($dp[$i-1][0], $dp[$i-1][1]);
}
return min($dp[$n-1][0], $dp[$n-1][1], $dp[$n-1][2]);
}
}1 320
🕯 Страшилка на ночь
Год спустя. Финальный этап собеседования. В комнате становится холодно. Интервьюер медленно наклоняется и шепчет: «Почему вы ушли с прошлого места работы?» Ты открываешь easyoffer, а там… «Ваша подписка истекла» 💀
Чтобы эта история не стала твоей, забери пожизненный PRO по цене одного года. База собесов, эталонные ответы, автоотклики, тренажёры и всё, что появится дальше, остаются с тобой навсегда.
⏳ Осталось 7 часов. В полночь предложение исчезнет.
👉 https://easyoffer.ru/pro
1 320
Задача: 1431. Kids With the Greatest Number of Candies
Сложность: easy
Дано n детей с конфетами. Вам дан целочисленный массив candies, где каждый candies[i] представляет количество конфет у i-го ребенка, и целое число extraCandies, обозначающее количество дополнительных конфет, которые у вас есть.
Вернуть булев массив result длиной n, где result[i] равно true, если, дав i-му ребенку все дополнительные конфеты, он будет иметь наибольшее количество конфет среди всех детей, или false в противном случае.
Обратите внимание, что несколько детей могут иметь наибольшее количество конфет.
Пример:
Input: candies = [2,3,5,1,3], extraCandies = 3 Output: [true,true,true,false,true] Explanation: If you give all extraCandies to: - Kid 1, they will have 2 + 3 = 5 candies, which is the greatest among the kids. - Kid 2, they will have 3 + 3 = 6 candies, which is the greatest among the kids. - Kid 3, they will have 5 + 3 = 8 candies, which is the greatest among the kids. - Kid 4, they will have 1 + 3 = 4 candies, which is not the greatest among the kids. - Kid 5, they will have 3 + 3 = 6 candies, which is the greatest among the kids.👨💻 Алгоритм: 1⃣Найдите максимальное количество конфет в массиве candies, сохраняя его в переменной maxCandies. 2⃣Создайте булев список answer и пройдитесь по массиву candies, добавляя в answer значение true, если текущий ребенок с добавленными extraCandies имеет количество конфет больше или равное maxCandies, иначе добавляйте false. 3⃣Верните список answer. 😎 Решение:
class Solution {
public function kidsWithCandies($candies, $extraCandies) {
$maxCandies = max($candies);
$result = [];
foreach ($candies as $candy) {
$result[] = $candy + $extraCandies >= $maxCandies;
}
return $result;
}
}1 320
⏳ Сегодня последний день
Платишь один раз и забираешь весь easyoffer навсегда, вместе со всеми будущими фичами проекта. Никаких ежегодных продлений, только ты, твой оффер и мешок конфет 🍭
🎃 Завтра цена вернётся к обычной, и такого угощения уже не будет.
👉 https://easyoffer.ru/pro
1 320
Задача: 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 320
Пожизненный PRO — по цене одного года.
Покупаешь один раз — пользуешься всю жизнь:
👉 https://easyoffer.ru/pro
🚀 PRO-доступ закроет 99% проблем на пути к офферу:
1. 1100+ записей реальных собеседований (включая топы: Сбер, Авито, Яндекс, WB, OZON, МТС). Видите всё изнутри: как спрашивают, как отвечают сильные кандидаты и на каких ошибках проваливаются 80%.
2. База live-coding задач и вопросов с реальных собесов — с уникальной системой вероятности их встречи. Готовитесь не вслепую, а точечно по темам, которые спрашивают чаще всего.
3. Эталонные ответы от Senior-разработчиков. Никакой воды и догадок — только чёткие структурированные решения, за которые дают «зелёный свет» к офферу.
4. Полный доступ ко всем грейдам и профессиям. Junior вы или Senior, тестировщик, разработчик или проджект — вы получаете ВСЕ материалы easyoffer без ограничений. Безлимитно, Все, Навсегда.
5. База 400+ тестовых заданий. Прокачивайте навыки на реальных задачах — тех самых, что дают перед собесом.
6. Автоотклики на hh — пока вы спите, резюме уходит рекрутерам автоматически. Экономия сотен часов ручного кликанья.
7. Аналитика ТОП-требований из вакансий. Парсим рынок и показываем, какие скиллы сейчас в цене. Апгрейдите резюме точечно и проходите ATS-фильтры (они отсеивают до 75% резюме ещё до рекрутера).
8. Генератор резюме и CV под каждую вакансию. Забудьте про «универсальное» резюме — нейросеть адаптирует ваш опыт под конкретную позицию за минуту и повышает шансы на приглашение в разы.
9. Тренажёры подготовки к собеседованию:
«Реальное собеседование» — сценарий вопросов из настоящих интервью. «Проработка вопросов» — флеш-карточки по методике интервальных повторений (как Anki)
10. 🔥 Самое важное: все будущие фичи
Вы платите один раз, а продукт растёт всю жизнь. Каждое обновление, каждый новый инструмент, каждая фича, которая появится за все годы проекта, автоматически падает вам в подписку без доплат. Вы фиксируете цену года, а получаете продукт, который через пару лет будет стоить в разы дороже
⭐️ Это уникальная акция пока сайт в режиме Beta.
Успей ей воспользоваться ⏳ Завтра последний день.
👉 https://easyoffer.ru/pro
1 320
Задача: 446. Arithmetic Slices II - Subsequence
Сложность: hard
Дан целочисленный массив nums, вернуть количество всех арифметических подпоследовательностей nums.
Последовательность чисел называется арифметической, если она состоит как минимум из трех элементов и если разница между любыми двумя последовательными элементами одинаковая.
Например, [1, 3, 5, 7, 9], [7, 7, 7, 7] и [3, -1, -5, -9] являются арифметическими последовательностями.
Например, [1, 1, 2, 5, 7] не является арифметической последовательностью.
Подпоследовательность массива - это последовательность, которая может быть образована путем удаления некоторых элементов (возможно, ни одного) из массива.
Например, [2, 5, 10] является подпоследовательностью [1, 2, 1, 2, 4, 1, 5, 10].
Тестовые случаи сгенерированы таким образом, что ответ помещается в 32-битное целое число.
Пример:
Input: nums = [2,4,6,8,10] Output: 7 Explanation: All arithmetic subsequence slices are: [2,4,6] [4,6,8] [6,8,10] [2,4,6,8] [4,6,8,10] [2,4,6,8,10] [2,6,10]👨💻 Алгоритм: 1⃣Мы можем использовать поиск в глубину (DFS) для генерации всех подпоследовательностей. 2⃣Мы можем проверить, является ли подпоследовательность арифметической, согласно ее определению. 3⃣Возвращаем количество всех арифметических подпоследовательностей. 😎 Решение:
class Solution {
private $n;
private $ans;
private function dfs($dep, $A, $cur) {
if ($dep == $this->n) {
if (count($cur) < 3) return;
for ($i = 1; $i < count($cur); $i++) {
if ($cur[$i] - $cur[$i - 1] != $cur[1] - $cur[0]) return;
}
$this->ans++;
return;
}
$this->dfs($dep + 1, $A, $cur);
array_push($cur, $A[$dep]);
$this->dfs($dep + 1, $A, $cur);
}
public function numberOfArithmeticSlices($A) {
$this->n = count($A);
$this->ans = 0;
$this->dfs(0, $A, []);
return $this->ans;
}
}1 320
Задача: 782. Transform to Chessboard
Сложность: hard
Дана бинарная сетка размером n x n. В каждом ходе можно поменять местами любые две строки или любые два столбца.
Верните минимальное количество ходов, чтобы преобразовать сетку в шахматную доску. Если задача невыполнима, верните -1.
Шахматная доска — это доска, на которой ни один 0 и ни одна 1 не соприкасаются друг с другом по вертикали и горизонтали.
Пример:
Input: board = [[0,1,1,0],[0,1,1,0],[1,0,0,1],[1,0,0,1]] Output: 2 Explanation: One potential sequence of moves is shown. The first move swaps the first and second column. The second move swaps the second and third row.👨💻 Алгоритм: 1⃣Для каждого набора строк (и столбцов соответственно) убедитесь, что существует только 2 вида линий в правильных количествах, которые являются противоположностями друг друга. 2⃣Затем для каждой возможной идеальной трансформации этой линии найдите минимальное количество перестановок, чтобы преобразовать эту линию в её идеальную и добавьте это к ответу. Например, [0, 1, 1, 1, 0, 0] имеет два идеала [0, 1, 0, 1, 0, 1] или [1, 0, 1, 0, 1, 0]; но [0, 1, 1, 1, 0] имеет только один идеал [1, 0, 1, 0, 1]. 3⃣В Java мы используем целые числа для представления строк как двоичных чисел. Мы проверяем количество различий с [1, 0, 1, 0, 1, 0, ...] с помощью побитового исключающего ИЛИ с 0b010101010101.....01 = 0x55555555. Чтобы убедиться, что мы не добавляем излишне большие элементы. 😎 Решение:
class Solution {
function movesToChessboard($board) {
$N = count($board);
$ans = 0;
foreach ([$this->getCount($board), $this->getCount($this->transpose($board))] as $count) {
$values = array_values($count);
sort($values);
if (count($values) !== 2 || $values[0] !== intdiv($N, 2) || $values[1] !== intdiv($N + 1, 2)) {
return -1;
}
$keys = array_keys($count);
$line1 = $keys[0];
$line2 = $keys[1];
if (!$this->allOpposite($line1, $line2)) {
return -1;
}
$starts = $N % 2 === 0 ? [0, 1] : [substr_count($line1, '1') * 2 > $N ? 1 : 0];
$minSwaps = PHP_INT_MAX;
foreach ($starts as $start) {
$swaps = 0;
for ($i = 0; $i < $N; $i++) {
if ((int)$line1[$i] !== ($i % 2 === $start ? 1 : 0)) {
$swaps++;
}
}
$minSwaps = min($minSwaps, intdiv($swaps, 2));
}
$ans += $minSwaps;
}
return $ans;
}
private function getCount($board) {
$count = [];
foreach ($board as $row) {
$key = implode('', $row);
if (!isset($count[$key])) {
$count[$key] = 0;
}
$count[$key]++;
}
return $count;
}
private function transpose($board) {
$N = count($board);
$transposed = array_fill(0, $N, array_fill(0, $N, 0));
for ($i = 0; $i < $N; $i++) {
for ($j = 0; $j < $N; $j++) {
$transposed[$j][$i] = $board[$i][$j];
}
}
return $transposed;
}
private function allOpposite($line1, $line2) {
for ($i = 0; $i < strlen($line1); $i++) {
if ((int)$line1[$i] ^ (int)$line2[$i] === 0) {
return false;
}
}
return true;
}
}1 320
🧿 Осталось 3 дня, чтобы забрать оберег!
Пожизненный easyoffer PRO по цене одного года. Надеваешь один раз и защищён всю жизнь 🎃
От чего защищает оберег:
1. Вопросы и задачи с реальных собеседований в конкретных компаниях — от сюрпризов на собесе
2. Лучшие ответы и видео-примеры от middle/senior специалистов — от ответов уровня джуна
3. Записи реальных собеседований — от страха неизвестности
4. Обход фильтров ATS с топ-30 ключевых слов в резюме — от автоотказов, пришедших из темноты в 3 часа ночи
5. Автоотклики на hh — от бесконечных часов ручных откликов
6. Тренажёры и симуляторы — от дрожи в голосе перед интервьюером 👻
⏳ Акция действует только до 31 октября 23:59 по МСК
👉 Забрать оберег со скидкой 70%: https://easyoffer.ru/pro
1 320
Задача: 925. Long Pressed Name
Сложность: easy
Ваш друг набирает на клавиатуре свое имя. Иногда, при наборе символа c, клавиша может быть долго нажата, и символ будет набран 1 или более раз. Вы исследуете набранные символы клавиатуры. Верните True, если возможно, что это было имя вашего друга, при этом некоторые символы (возможно, ни один) не были долго нажаты.
Пример:
Input: name = "alex", typed = "aaleex" Output: true👨💻 Алгоритм: 1⃣Инициализировать два указателя i и j для строки имени и набранной строки соответственно. 2⃣Пройти по набранной строке: Если символы имени и набранной строки совпадают, сдвинуть оба указателя. Если символы не совпадают, проверить, является ли текущий символ набранной строки повторением предыдущего символа. Если да, сдвинуть указатель набранной строки. Если символ не совпадает и не является повторением предыдущего символа, вернуть False. После завершения цикла проверить, что все символы имени были обработаны. 3⃣Вернуть True, если все символы имени были обработаны, иначе False. 😎 Решение:
function isLongPressedName($name, $typed) {
$i = 0;
$j = 0;
while ($j < strlen($typed)) {
if ($i < strlen($name) && $name[$i] == $typed[$j]) {
$i++;
} elseif ($j == 0 || $typed[$j] != $typed[$j - 1]) {
return false;
}
$j++;
}
return $i == strlen($name);
}1 320
Задача: 1086. High Five
м
Дан список оценок различных студентов, items, где items[i] = [IDi, scorei] представляет собой одну оценку студента с идентификатором IDi. Вычислите среднее значение пяти лучших оценок каждого студента.
Верните ответ в виде массива пар result, где result[j] = [IDj, topFiveAveragej] представляет студента с идентификатором IDj и его среднее значение пяти лучших оценок. Отсортируйте result по IDj в порядке возрастания.
Среднее значение пяти лучших оценок студента вычисляется путем сложения его пяти лучших оценок и деления на 5 с использованием целочисленного деления.
Пример:
Input: items = [[1,100],[7,100],[1,100],[7,100],[1,100],[7,100],[1,100],[7,100],[1,100],[7,100]]
Output: [[1,100],[7,100]]class Solution {
function highFive($items) {
$K = 5;
usort($items, function($a, $b) {
if ($a[0] != $b[0]) return $a[0] - $b[0];
return $b[1] - $a[1];
});
$solution = [];
$i = 0;
$n = count($items);
while ($i < $n) {
$id = $items[$i][0];
$sum = 0;
for ($k = $i; $k < $i + $K; $k++) {
$sum += $items[$k][1];
}
while ($i < $n && $items[$i][0] == $id) {
$i++;
}
$solution[] = [$id, intdiv($sum, $K)];
}
return $solution;
}
}1 320
Задача: 507. Perfect Number
Сложность: easy
Совершенное число — это положительное целое число, которое равно сумме своих положительных делителей, исключая само число. Делитель целого числа x — это целое число, которое может делить x нацело.
Дано целое число n, верните true, если n является совершенным числом, в противном случае верните false.
Пример:
Input: num = 28 Output: true Explanation: 28 = 1 + 2 + 4 + 7 + 14 1, 2, 4, 7, and 14 are all divisors of 28.👨💻 Алгоритм: 1⃣Инициализация Если число num меньше или равно 0, вернуть false. Инициализируйте переменную sum значением 0. 2⃣Поиск делителей и вычисление суммы Переберите числа от 1 до квадратного корня num. Если число является делителем num, добавьте его к sum. Если делитель не равен квадратному корню num, добавьте к sum также результат деления num на делитель. 3⃣Проверка на совершенное число Вычтите num из sum. Если результат равен num, вернуть true, иначе вернуть false. 😎 Решение:
class Solution {
function checkPerfectNumber($num) {
if ($num <= 0) {
return false;
}
$sum = 0;
for ($i = 1; $i * $i <= $num; $i++) {
if ($num % $i == 0) {
$sum += $i;
if ($i * $i != $num) {
$sum += $num / $i;
}
}
}
return $sum - $num == $num;
}
}1 320
🎃 Хеллоуинская акция на easyoffer
В честь Хеллоуина до 31 октября можно забрать PRO навсегда. Покупаешь один раз и пользуешься всю жизнь
🍬Что внутри мешка с угощениями:
– База вопросов и задач из собеседований
– Примеры видео-ответов на вопросы
– Записи реальных собеседований
– Тренажёры «Проработка вопросов» и «Реальное собеседование»
– Аналитика требований из вакансий
– Автоотклики на вакансии
👉 Забрать PRO со скидкой 70%: https://easyoffer.ru/pro
1 320
Задача: 315. Count of Smaller Numbers After Self
Сложность: hard
Дан целочисленный массив nums, верните целочисленный массив counts, где counts[i] - это количество элементов справа от nums[i], которые меньше nums[i].
Пример:
Input: nums = [5,2,6,1] Output: [2,1,1,0] Explanation: To the right of 5 there are 2 smaller elements (2 and 1). To the right of 2 there is only 1 smaller element (1). To the right of 6 there is 1 smaller element (1). To the right of 1 there is 0 smaller element.👨💻 Алгоритм: 1⃣Реализуйте дерево отрезков (segment tree). Поскольку дерево инициализируется нулями, нужно реализовать только операции обновления и запроса. Установите смещение offset = 10^4. 2⃣Итерация по каждому числу в nums в обратном порядке. Для каждого числа выполните следующие действия: Смещайте число на num + offset. Запросите количество элементов в дереве отрезков, которые меньше текущего числа. Обновите счетчик текущего числа в дереве отрезков. 3⃣Верните результат. 😎 Решение:
class Solution {
function countSmaller($nums) {
$offset = 10000;
$size = 2 * 10000 + 1;
$tree = array_fill(0, $size * 2, 0);
$result = [];
for ($i = count($nums) - 1; $i >= 0; $i--) {
$smallerCount = $this->query(0, $nums[$i] + $offset, $tree, $size);
$result[] = $smallerCount;
$this->update($nums[$i] + $offset, 1, $tree, $size);
}
return array_reverse($result);
}
function update($index, $value, &$tree, $size) {
$index += $size;
$tree[$index] += $value;
while ($index > 1) {
$index = intdiv($index, 2);
$tree[$index] = $tree[$index * 2] + $tree[$index * 2 + 1];
}
}
function query($left, $right, &$tree, $size) {
$result = 0;
$left += $size;
$right += $size;
while ($left < $right) {
if ($left % 2 == 1) {
$result += $tree[$left];
$left++;
}
$left = intdiv($left, 2);
if ($right % 2 == 1) {
$right--;
$result += $tree[$right];
}
$right = intdiv($right, 2);
}
return $result;
}
}1 320
Задача: 1166. Design File System
Сложность: medium
Вам нужно разработать файловую систему, которая позволяет создавать новые пути и связывать их с различными значениями.
Формат пути - это одна или несколько конкатенированных строк в форме: /, за которой следует одна или несколько строчных английских букв. Например, "/leetcode" и "/leetcode/problems" - допустимые пути, в то время как пустая строка "" и "/" не допустимы.
Реализуйте класс FileSystem:
-
bool createPath(string path, int value) создает новый путь и связывает с ним значение, если это возможно, и возвращает true. Возвращает false, если путь уже существует или его родительский путь не существует.
- int get(string path) возвращает значение, связанное с путем, или возвращает -1, если путь не существует.
Пример:
Input:
["FileSystem","createPath","get"]
[[],["/a",1],["/a"]]
Output:
[null,true,1]
Explanation:
FileSystem fileSystem = new FileSystem();
fileSystem.createPath("/a", 1); // return true
fileSystem.get("/a"); // return 1class FileSystem {
private $paths;
function __construct() {
$this->paths = array();
}
function createPath($path, $value) {
if (empty($path) || (strlen($path) == 1 && $path == "/") || array_key_exists($path, $this->paths)) {
return false;
}
$delimIndex = strrpos($path, "/");
$parent = substr($path, 0, $delimIndex);
if (strlen($parent) > 1 && !array_key_exists($parent, $this->paths)) {
return false;
}
$this->paths[$path] = $value;
return true;
}
function get($path) {
return array_key_exists($path, $this->paths) ? $this->paths[$path] : -1;
}
}1 320
Задача: 1663. Smallest String With A Given Numeric Value
Сложность: medium
Числовое значение строчной буквы определяется ее позицией (начиная с 1) в алфавите, поэтому числовое значение a равно 1, числовое значение b равно 2, числовое значение c равно 3 и так далее.
Числовое значение строки, состоящей из строчных букв, определяется как сумма числовых значений ее символов. Например, числовое значение строки "abe" равно 1 + 2 + 5 = 8.
Вам даны два целых числа n и k. Верните лексикографически наименьшую строку длиной n с числовым значением, равным k.
Обратите внимание, что строка x лексикографически меньше строки y, если x идет перед y в словарном порядке, то есть либо x является префиксом y, либо, если i - первая позиция, где x[i] != y[i], то x[i] идет перед y[i] в алфавитном порядке.
Пример:
Input: n = 3, k = 27
Output: "aay"
Explanation: The numeric value of the string is 1 + 1 + 25 = 27, and it is the smallest string with such a value and length equal to 3.class Solution {
function getSmallestString($n, $k) {
$result = array_fill(0, $n, 'a');
for ($position = 0; $position < $n; $position++) {
$positionsLeft = ($n - $position - 1);
if ($k > $positionsLeft * 26) {
$add = $k - ($positionsLeft * 26);
$result[$position] = chr(97 + $add - 1);
$k -= $add;
} else {
$k -= 1;
}
}
return implode('', $result);
}
}1 320
Задача: 732. My Calendar III
Сложность: hard
k-бронирование происходит, когда k событий имеют некоторое непустое пересечение (т.е, дано некоторое время, общее для всех k событий). Даны некоторые события [startTime, endTime), после каждого данного события верните целое число k, представляющее максимальное k-бронирование между всеми предыдущими событиями. Реализация класса MyCalendarThree: MyCalendarThree() Инициализирует объект. int book(int startTime, int endTime) Возвращает целое число k, представляющее наибольшее целое число, при котором в календаре существует k-бронирование.
Пример:
Input ["MyCalendarThree", "book", "book", "book", "book", "book", "book"] [[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]] Output [null, 1, 1, 2, 3, 3, 3]👨💻 Алгоритм: 1⃣Создайте два словаря для хранения изменений времени бронирования: один для начала событий, другой для конца событий. 2⃣Для каждого нового события обновите словари начала и конца событий. 3⃣Поддерживайте текущее количество активных бронирований и обновляйте максимальное количество активных бронирований по мере добавления новых событий. 😎 Решение:
class MyCalendarThree {
private $events;
function __construct() {
$this->events = [];
}
function book($startTime, $endTime) {
if (!isset($this->events[$startTime])) {
$this->events[$startTime] = 0;
}
if (!isset($this->events[$endTime])) {
$this->events[$endTime] = 0;
}
$this->events[$startTime]++;
$this->events[$endTime]--;
ksort($this->events);
$active = 0;
$maxActive = 0;
foreach ($this->events as $time => $count) {
$active += $count;
$maxActive = max($maxActive, $active);
}
return $maxActive;
}
}1 320
🔥 Скрытые вакансии с удаленной работой для PHP разработчика, которые нигде больше не публикуются. Напрямую от компаний, с контактами рекрутеров.
🔹 PHP Jobs | Вакансии
🔸 Все каналы с вакансиями
1 320
Задача: 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);
}