PHP | LeetCode
Відкрити в Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
Показати більше
Сітка:1 348
Підписники
-224 години
-47 днів
-1130 днів
Архів дописів
1 348
Задача: 999. Available Captures for Rook
Сложность: easy
Вам дана матрица 8 x 8, изображающая шахматную доску. На ней есть ровно одна белая ладья, представленная символом "R", некоторое количество белых слонов "B" и некоторое количество черных пешек "p". Пустые клетки обозначаются символом '.'. Ладья может перемещаться на любое количество клеток по горизонтали или вертикали (вверх, вниз, влево, вправо), пока не достигнет другой фигуры или края доски. Ладья атакует пешку, если она может переместиться на ее клетку за один ход. Примечание: Ладья не может перемещаться через другие фигуры, такие как слоны или пешки. Это означает, что ладья не может атаковать пешку, если путь ей преграждает другая фигура. Верните количество пешек, которые атакует белая ладья.
Пример:
Input: board = [[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","R",".",".",".","p"],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]] Output: 3👨💻 Алгоритм: 1⃣Поиск ладьи: Найдите координаты белой ладьи "R" на шахматной доске. 2⃣Проверка направлений атаки: Проверьте все четыре направления (влево, вправо, вверх, вниз) от позиции ладьи. Перемещайтесь по каждому направлению до тех пор, пока не встретите другую фигуру или край доски. 3⃣Подсчет атакованных пешек: Если встреченная фигура - черная пешка "p", увеличьте счетчик атакованных пешек. Если встреченная фигура - белый слон "B" или край доски, остановитесь в этом направлении. 😎 Решение:
class Solution {
function numRookCaptures($board) {
$countPawns = function($x, $y, $dx, $dy) use ($board) {
while ($x >= 0 && $x < 8 && $y >= 0 && $y < 8) {
if ($board[$x][$y] == 'B') break;
if ($board[$x][$y] == 'p') return 1;
$x += $dx;
$y += $dy;
}
return 0;
};
for ($i = 0; $i < 8; $i++) {
for ($j = 0; $j < 8; $j++) {
if ($board[$i][$j] == 'R') {
return $countPawns($i, $j, -1, 0) + $countPawns($i, $j, 1, 0) +
$countPawns($i, $j, 0, -1) + $countPawns($i, $j, 0, 1);
}
}
}
return 0;
}
}1 348
Задача: 921. Minimum Add to Make Parentheses Valid4
Сложность: medium
Строка со скобками допустима тогда и только тогда, когда: это пустая строка, ее можно записать как AB (A, совмещенное с B), где A и B - допустимые строки, или ее можно записать как (A), где A - допустимая строка. Вам дана строка s со скобками. За один ход вы можете вставить скобку в любую позицию строки. Например, если s = "()))", вы можете вставить открывающую скобку в виде "(()))" или закрывающую скобку в виде "())))". Верните минимальное количество ходов, необходимое для того, чтобы сделать s допустимой.
Пример:
Input: n = 3, goal = 3, k = 1 Output: 6👨💻 Алгоритм: 1⃣Инициализировать два счетчика open_needed и close_needed. 2⃣Пройти по строке s символ за символом: Если текущий символ - открывающая скобка (, увеличьте open_needed. Если текущий символ - закрывающая скобка ), проверьте: Если open_needed больше 0, уменьшите open_needed. Иначе увеличьте close_needed. 3⃣Суммируйте значения open_needed и close_needed, чтобы получить минимальное количество вставок. 😎 Решение:
function minAddToMakeValid($s) {
$openNeeded = 0;
$closeNeeded = 0;
for ($i = 0; $i < strlen($s); $i++) {
if ($s[$i] == '(') {
$openNeeded++;
} elseif ($s[$i] == ')') {
if ($openNeeded > 0) {
$openNeeded--;
} else {
$closeNeeded++;
}
}
}
return $openNeeded + $closeNeeded;
}1 348
Задача: 845. Longest Mountain in Array
Сложность: medium
Вы можете вспомнить, что массив arr является горным массивом тогда и только тогда, когда:
длина массива arr >= 3
Существует индекс i (счёт начинается с 0) такой, что:
arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
Дан целочисленный массив arr, верните длину самой длинной подпоследовательности, которая является горной. Верните 0, если такой подпоследовательности нет.
Пример:
Input: arr = [2,1,4,7,3,2,5] Output: 5 Explanation: The largest mountain is [1,4,7,3,2] which has length 5.👨💻 Алгоритм: 1⃣Инициализируйте переменные для отслеживания текущего основания и максимальной длины горного массива. 2⃣Для каждого индекса, который может быть началом горного массива, определите пиковый элемент и найдите правую границу горного массива. 3⃣Если найден горный массив, обновите максимальную длину и переместите основание на конец текущего горного массива. 😎 Решение:
class Solution {
/**
* @param Integer[] $arr
* @return Integer
*/
function longestMountain($arr) {
$n = count($arr);
$ans = 0;
$base = 0;
while ($base < $n) {
$end = $base;
if ($end + 1 < $n && $arr[$end] < $arr[$end + 1]) {
while ($end + 1 < $n && $arr[$end] < $arr[$end + 1]) {
$end++;
}
if ($end + 1 < $n && $arr[$end] > $arr[$end + 1]) {
while ($end + 1 < $n && $arr[$end] > $arr[$end + 1]) {
$end++;
}
$ans = max($ans, $end - $base + 1);
}
}
$base = max($end, $base + 1);
}
return $ans;
}
}1 348
Задача: 1672. Richest Customer Wealth
Сложность: easy
Вам дан целочисленный массив размером m x n под названием accounts, где accounts[i][j] — это сумма денег, которую i-й клиент имеет в j-м банке. Верните богатство самого богатого клиента.
Богатство клиента — это сумма денег, которую он имеет во всех своих банковских счетах. Самый богатый клиент — это клиент, который имеет максимальное богатство.
Пример:
Input: accounts = [[1,2,3],[3,2,1]]
Output: 6
Explanation:
1st customer has wealth = 1 + 2 + 3 = 6
2nd customer has wealth = 3 + 2 + 1 = 6
Both customers are considered the richest with a wealth of 6 each, so return 6.class Solution {
/**
* @param Integer[][] $accounts
* @return Integer
*/
function maximumWealth($accounts) {
$maxWealthSoFar = 0;
foreach ($accounts as $account) {
$currCustomerWealth = array_sum($account);
if ($currCustomerWealth > $maxWealthSoFar) {
$maxWealthSoFar = $currCustomerWealth;
}
}
return $maxWealthSoFar;
}
}1 348
Задача: 1496. Path Crossing
Сложность: easy
Дана строка path, где path[i] = 'N', 'S', 'E' или 'W', каждая из которых представляет движение на одну единицу на север, юг, восток или запад соответственно. Вы начинаете с точки (0, 0) на 2D плоскости и идете по пути, указанному в path.
Верните true, если путь пересекает сам себя в какой-либо точке, то есть если вы в какой-то момент окажетесь в месте, которое уже посещали ранее. В противном случае верните false.
Пример:
Input: path = "NESWW"
Output: true
Explanation: Notice that the path visits the origin twice.class Solution {
function isPathCrossing($path) {
$moves = [
'N' => [0, 1], 'S' => [0, -1],
'E' => [1, 0], 'W' => [-1, 0]
];
$visited = [[0, 0]];
$x = 0;
$y = 0;
foreach (str_split($path) as $c) {
list($dx, $dy) = $moves[$c];
$x += $dx;
$y += $dy;
$point = [$x, $y];
if (in_array($point, $visited)) {
return true;
}
$visited[] = $point;
}
return false;
}
}1 348
Задача: 1474. Delete N Nodes After M Nodes of a Linked List
Сложность: easy
Вам дано начало связанного списка и два целых числа m и n.
Пройдите по связанному списку и удалите некоторые узлы следующим образом:
Начните с головы как текущего узла.
Сохраните первые m узлов, начиная с текущего узла.
Удалите следующие n узлов.
Продолжайте повторять шаги 2 и 3, пока не достигнете конца списка.
Верните голову изменённого списка после удаления указанных узлов.
Пример:
Input: head = [1,2,3,4,5,6,7,8,9,10,11,12,13], m = 2, n = 3
Output: [1,2,6,7,11,12]
Explanation: Keep the first (m = 2) nodes starting from the head of the linked List (1 ->2) show in black nodes.
Delete the next (n = 3) nodes (3 -> 4 -> 5) show in read nodes.
Continue with the same procedure until reaching the tail of the Linked List.
Head of the linked list after removing nodes is returned.class ListNode {
public $val = 0;
public $next = null;
function __construct($val = 0, $next = null) {
$this->val = $val;
$this->next = $next;
}
}
class Solution {
function deleteNodes($head, $m, $n) {
$currentNode = $head;
$lastMNode = $head;
while ($currentNode !== null) {
$mCount = $m;
$nCount = $n;
while ($currentNode !== null && $mCount > 0) {
$lastMNode = $currentNode;
$currentNode = $currentNode->next;
$mCount--;
}
while ($currentNode !== null && $nCount > 0) {
$currentNode = $currentNode->next;
$nCount--;
}
$lastMNode->next = $currentNode;
}
return $head;
}
}1 348
Задача: 1305. All Elements in Two Binary Search Trees
Сложность: medium
Даны два бинарных дерева поиска root1 и root2. Вернуть список, содержащий все целые числа из обоих деревьев, отсортированные в порядке возрастания.
Пример:
Input: root1 = [2,1,4], root2 = [1,0,3] Output: [0,1,1,2,3,4]👨💻 Алгоритм: 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 {
function getAllElements($root1, $root2) {
$stack1 = new SplStack();
$stack2 = new SplStack();
$output = [];
while ($root1 !== null || $root2 !== null || !$stack1->isEmpty() || !$stack2->isEmpty()) {
while ($root1 !== null) {
$stack1->push($root1);
$root1 = $root1->left;
}
while ($root2 !== null) {
$stack2->push($root2);
$root2 = $root2->left;
}
if ($stack2->isEmpty() || (!$stack1->isEmpty() && $stack1->top()->val <= $stack2->top()->val)) {
$root1 = $stack1->pop();
$output[] = $root1->val;
$root1 = $root1->right;
} else {
$root2 = $stack2->pop();
$output[] = $root2->val;
$root2 = $root2->right;
}
}
return $output;
}
}1 348
Задача: 487. Max Consecutive Ones II
Сложность: medium
Дан бинарный массив nums, верните максимальное количество последовательных единиц в массиве, если можно перевернуть не более одного нуля.
Пример:
Input: nums = [1,0,1,1,0] Output: 4 Explanation: - If we flip the first zero, nums becomes [1,1,1,1,0] and we have 4 consecutive ones. - If we flip the second zero, nums becomes [1,0,1,1,1] and we have 3 consecutive ones. The max number of consecutive ones is 4.👨💻 Алгоритм: 1⃣Для каждого возможного начала последовательности в массиве nums начните считать количество нулей. 2⃣Для каждой последовательности проверяйте, сколько нулей содержится в ней. Если количество нулей не превышает одного, обновите максимальную длину последовательности единиц. 3⃣Продолжайте проверять все возможные последовательности в массиве, и верните максимальную длину последовательности единиц, удовлетворяющую условию. 😎 Решение:
class Solution {
function findMaxConsecutiveOnes($nums) {
$longestSequence = 0;
for ($left = 0; $left < count($nums); $left++) {
$numZeroes = 0;
for ($right = $left; $right < count($nums); $right++) {
if ($nums[$right] == 0) {
$numZeroes++;
}
if ($numZeroes <= 1) {
$longestSequence = max($longestSequence, $right - $left + 1);
}
}
}
return $longestSequence;
}
}1 348
Задача: 1038. Binary Search Tree to Greater Sum Tree
Сложность: medium
Получив корень двоичного дерева поиска (BST), преобразуйте его в большее дерево таким образом, чтобы каждый ключ исходного BST был заменен на исходный ключ плюс сумма всех ключей, превышающих исходный ключ в BST. Напомним, что двоичное дерево поиска - это дерево, удовлетворяющее следующим ограничениям: левое поддерево узла содержит только узлы с ключами меньше, чем ключ узла. Правое поддерево узла содержит только узлы с ключами больше, чем ключ узла. И левое, и правое поддеревья должны быть двоичными деревьями поиска.
Пример:
Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8] Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]👨💻 Алгоритм: 1⃣Обратный обход in-order: Пройдите по дереву в порядке "правый, корень, левый" (обратный in-order обход). Это обеспечит посещение узлов в порядке убывания их значений. 2⃣Накопление суммы: Во время обхода поддерживайте переменную для хранения накопленной суммы. На каждом узле добавляйте значение узла к накопленной сумме и обновляйте значение узла этой накопленной суммой. 3⃣Преобразование узлов: Преобразуйте значение каждого узла в накопленную сумму. 😎 Решение:
class TreeNode {
public $val = null;
public $left = null;
public $right = null;
function __construct($val = 0, $left = null, $right = null) {
$this->val = $val;
$this->left = $left;
$this->right = $right;
}
}
class Solution {
private $sum = 0;
function bstToGst($root) {
$this->reverseInorder($root);
return $root;
}
function reverseInorder($node) {
if ($node === null) return;
$this->reverseInorder($node->right);
$this->sum += $node->val;
$node->val = $this->sum;
$this->reverseInorder($node->left);
}
}1 348
Задача: 856. Score of Parentheses
Сложность: medium
Дана строка s, состоящая из сбалансированных скобок, верните счёт строки.
Счёт сбалансированной строки скобок основывается на следующих правилах:
"()" имеет счёт 1.
AB имеет счёт A + B, где A и B — сбалансированные строки скобок.
(A) имеет счёт 2 * A, где A — сбалансированная строка скобок.
Пример:
Input: s = "()"
Output: 1class Solution {
function scoreOfParentheses($S) {
return $this->F($S, 0, strlen($S));
}
function F($S, $i, $j) {
$ans = 0;
$bal = 0;
for ($k = $i; $k < $j; $k++) {
$bal += $S[$k] === '(' ? 1 : -1;
if ($bal === 0) {
if ($k - $i === 1) {
$ans++;
} else {
$ans += 2 * $this->F($S, $i + 1, $k);
}
$i = $k + 1;
}
}
return $ans;
}
}1 348
🚨60 минут
Пожизненный PRO-доступ на easyoffer (подготовка к IT-собесам + поиск оффера) по цене одного года закрывается прямо сейчас. Один платёж — доступ навсегда.
Последнее напоминание 👇
👉 https://easyoffer.ru/pro
1 348
⚠️ 3 часа до конца акции.
Последний шанс забрать пожизненный PRO на easyoffer по цене одного года. Это полный доступ к подготовке к собесам и инструментам поиска работы (вопросы с реальных интервью, ответы сеньоров, автоотклики, тренажёры) — один раз и навсегда, вместо ежегодной оплаты.
В полночь цена возвращается к обычной.
👉 https://easyoffer.ru/pro
1 348
⏳ Ребята, сегодня заканчивается акция, о которой стоит знать, если вы в поиске работы или планируете сменить её в ближайший год.
easyoffer — это платформа для подготовки к IT-собесам и поиска оффера. Внутри:
– база реальных вопросов и live-coding задач с собесов (с частотой их встречаемости)
– эталонные ответы от Senior-разработчиков
– 1100+ записей настоящих интервью (Сбер, Яндекс, Авито, WB, OZON, МТС)
– автоотклики на hh, генератор резюме под вакансию, тренажёры собеседований
Сегодня пожизненный PRO-доступ продаётся по цене одного года — платишь один раз и пользуешься всем этим всю жизнь, включая будущие фичи. С завтрашнего дня — только обычная годовая подписка.
👉 https://easyoffer.ru/pro
1 348
Пожизненный 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.ru — пока вы спите, резюме уходит рекрутерам автоматически. Экономия сотен часов ручного кликанья.
7. Аналитика ТОП-требований из вакансий. Парсим рынок и показываем, какие скиллы сейчас в цене. Апгрейдите резюме точечно и проходите ATS-фильтры (они отсеивают до 75% резюме ещё до рекрутера).
8. Генератор резюме и CV под каждую вакансию. Забудьте про «универсальное» резюме — нейросеть адаптирует ваш опыт под конкретную позицию за минуту и повышает шансы на приглашение в разы.
9. Тренажёры подготовки к собеседованию:
«Реальное собеседование» — сценарий вопросов из настоящих интервью. «Проработка вопросов» — флеш-карточки по методике интервальных повторений (как Anki)
10. 🔥 Самое важное: все будущие фичи
Вы платите один раз, а продукт растёт всю жизнь. Каждое обновление, каждый новый инструмент, каждая фича, которая появится за все годы проекта, автоматически падает вам в подписку без доплат. Вы фиксируете цену года, а получаете продукт, который через пару лет будет стоить в разы дороже
⭐️ Это уникальная акция пока сайт в режиме Beta.
Успей ей воспользоваться⏳ Завтра последний день.
👉 https://easyoffer.ru/pro
1 348
🔥 Осталось 3 дня!
Пожизненный easyoffer PRO по цене одного года. Покупаешь один раз – пользуешься всю жизнь.
Что входит в PRO:
– Вопросы и задачи с реальных собеседований в конкретных компаниях
– Лучшие ответы и видео-примеры от middle/senior специалистов
– Записи реальных собеседований
– Обход фильтров ATS с топ-30 ключевых слов в резюме
– Автоотклики на hh
– Тренажёры и симуляторы для идеальной подготовки к интервью
⏳ Акция действует только до 2 сентября 23:59 по МСК
👉 Забрать PRO со скидкой 70%: https://easyoffer.ru/pro
1 348
Задача: 986. Interval List Intersections
Сложность: medium
Вам даны два списка закрытых интервалов, firstList и secondList, где firstList[i] = [starti, endi] и secondList[j] = [startj, endj]. Каждый список интервалов является попарно непересекающимся и отсортированным.
Верните пересечение этих двух списков интервалов.
Закрытый интервал [a, b] (где a <= b) обозначает множество действительных чисел x с a <= x <= b.
Пересечение двух закрытых интервалов - это множество действительных чисел, которые либо пусты, либо представлены как закрытый интервал. Например, пересечение [1, 3] и [2, 4] равно [2, 3].
Пример:
Input: firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]] Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]👨💻 Алгоритм: 1⃣Инициализация указателей: Завести два указателя i и j, указывающие на начало firstList и secondList соответственно. 2⃣Поиск пересечений: Пока оба указателя находятся в пределах своих списков, выполнить следующие действия: Найти максимальное начало и минимальный конец текущих интервалов. Если начало меньше или равно концу, добавить пересечение в результат. Сдвинуть указатель списка, у которого текущий интервал заканчивается раньше. 3⃣Возврат результата: Вернуть список пересечений. 😎 Решение:
class Solution {
function intervalIntersection($firstList, $secondList) {
$i = 0;
$j = 0;
$result = [];
while ($i < count($firstList) && $j < count($secondList)) {
$start = max($firstList[$i][0], $secondList[$j][0]);
$end = min($firstList[$i][1], $secondList[$j][1]);
if ($start <= $end) {
$result[] = [$start, $end];
}
if ($firstList[$i][1] < $secondList[$j][1]) {
$i++;
} else {
$j++;
}
}
return $result;
}
}1 348
Задача: 846. Hand of Straights
Сложность: medium
У Алисы есть некоторое количество карт, и она хочет переставить карты в группы так, чтобы каждая группа была размером groupSize и состояла из groupSize последовательных карт.
Дан целочисленный массив hand, где hand[i] — это значение, написанное на i-й карте, и целое число groupSize. Верните true, если она может переставить карты, или false в противном случае.
Пример:
Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3 Output: true Explanation: Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8]👨💻 Алгоритм: 1⃣Проверьте, делится ли длина массива hand на groupSize. Если нет, верните false. 2⃣Создайте карту cardCount для хранения количества каждой карты в массиве hand. 3⃣Итерируйте по массиву hand и обновляйте карту cardCount. Затем итерируйте снова для создания групп: Найдите начальную карту startCard для потенциальной последовательности, уменьшая startCard, пока не найдёте карту, которая отсутствует в карте cardCount. Попробуйте сформировать последовательность из groupSize карт, начиная с startCard. Если какая-либо карта в потенциальной последовательности отсутствует в карте cardCount, верните false. Если последовательность можно сформировать, уменьшите количество каждой карты в последовательности в карте cardCount. 😎 Решение:
class Solution {
/**
* @param Integer[] $hand
* @param Integer $groupSize
* @return Boolean
*/
function isNStraightHand($hand, $groupSize) {
if (count($hand) % $groupSize != 0) {
return false;
}
$cardCount = [];
foreach ($hand as $card) {
if (!isset($cardCount[$card])) {
$cardCount[$card] = 0;
}
$cardCount[$card]++;
}
sort($hand);
foreach ($hand as $card) {
if ($cardCount[$card] == 0) {
continue;
}
for ($nextCard = $card; $nextCard < $card + $groupSize; $nextCard++) {
if (!isset($cardCount[$nextCard]) || $cardCount[$nextCard] == 0) {
return false;
}
$cardCount[$nextCard]--;
}
}
return true;
}
}1 348
Задача: 820. Short Encoding of Words
Сложность: medium
Допустимым кодированием массива слов является любая опорная строка s и массив индексов indices, такие что:
words.length == indices.length
Опорная строка s заканчивается символом '#'.
Для каждого индекса indices[i], подстрока строки s, начинающаяся с indices[i] и заканчивающаяся (но не включительно) следующим символом '#', равна words[i].
Дан массив слов, верните длину самой короткой возможной опорной строки s для любого допустимого кодирования слов.
Пример:
Input: words = ["time", "me", "bell"] Output: 10 Explanation: A valid encoding would be s = "time#bell#" and indices = [0, 2, 5]. words[0] = "time", the substring of s starting from indices[0] = 0 to the next '#' is underlined in "time#bell#" words[1] = "me", the substring of s starting from indices[1] = 2 to the next '#' is underlined in "time#bell#" words[2] = "bell", the substring of s starting from indices[2] = 5 to the next '#' is underlined in "time#bell#"👨💻 Алгоритм: 1⃣Поскольку слово имеет не более 6 собственных суффиксов (так как words[i].length <= 7), давайте итерироваться по всем из них. Для каждого собственного суффикса мы попытаемся удалить его из нашего списка слов. Для эффективности сделаем words множеством. 2⃣Затем создадим список оставшихся слов и сформируем опорную строку, объединяя каждое слово с символом '#'. 3⃣В конце вернем длину полученной опорной строки. 😎 Решение:
class Solution {
function minimumLengthEncoding($words) {
$good = array_flip($words);
foreach ($words as $word) {
for ($k = 1; $k < strlen($word); $k++) {
unset($good[substr($word, $k)]);
}
}
$length = 0;
foreach ($good as $word => $_) {
$length += strlen($word) + 1;
}
return $length;
}
}1 348
Задача: 1473. Paint House III
Сложность: hard
Есть ряд из m домов в маленьком городе, каждый дом должен быть покрашен одним из n цветов (обозначены от 1 до n), некоторые дома, которые были покрашены прошлым летом, не должны быть перекрашены.
Соседство — это максимальная группа непрерывных домов, которые покрашены в один и тот же цвет.
Например: дома = [1,2,2,3,3,2,1,1] содержат 5 соседств [{1}, {2,2}, {3,3}, {2}, {1,1}].
Дан массив домов, матрица m x n стоимости и целое число target, где:
houses[i]: цвет дома i, и 0, если дом ещё не покрашен.
cost[i][j]: стоимость покраски дома i в цвет j + 1.
Верните минимальную стоимость покраски всех оставшихся домов таким образом, чтобы было ровно target соседств. Если это невозможно, верните -1.
Пример:
Input: houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
Output: 9
Explanation: Paint houses of this way [1,2,2,1,1]
This array contains target = 3 neighborhoods, [{1}, {2,2}, {1,1}].
Cost of paint all houses (1 + 1 + 1 + 1 + 5) = 9.class Solution {
private $MAX_COST = 1000001;
private $memo = [];
private function findMinCost($houses, $cost, $targetCount, $currIndex, $neighborhoodCount, $prevHouseColor) {
if ($currIndex == count($houses)) {
return $neighborhoodCount == $targetCount ? 0 : $this->MAX_COST;
}
if ($neighborhoodCount > $targetCount) {
return $this->MAX_COST;
}
$key = "$currIndex,$neighborhoodCount,$prevHouseColor";
if (isset($this->memo[$key])) {
return $this->memo[$key];
}
$minCost = $this->MAX_COST;
if ($houses[$currIndex] != 0) {
$newNeighborhoodCount = $neighborhoodCount + ($houses[$currIndex] != $prevHouseColor ? 1 : 0);
$minCost = $this->findMinCost($houses, $cost, $targetCount, $currIndex + 1, $newNeighborhoodCount, $houses[$currIndex]);
} else {
for ($color = 1; $color <= count($cost[0]); $color++) {
$newNeighborhoodCount = $neighborhoodCount + ($color != $prevHouseColor ? 1 : 0);
$currCost = $cost[$currIndex][$color - 1] + $this->findMinCost($houses, $cost, $targetCount, $currIndex + 1, $newNeighborhoodCount, $color);
$minCost = min($minCost, $currCost);
}
}
$this->memo[$key] = $minCost;
return $minCost;
}
public function minCost($houses, $cost, $m, $n, $target) {
$answer = $this->findMinCost($houses, $cost, $target, 0, 0, 0);
return $answer == $this->MAX_COST ? -1 : $answer;
}
}1 348
Пожизненный PRO доступ на easyoffer — по цене одного года!
До 2 сентября вы можете купить PRO навсегда.
Покупаешь один раз — пользуешься всю жизнь.
– База вопросов и задач из собеседований
– Примеры видео-ответов на вопросы
– Записи реальных собеседований
– Тренажеры "Проработка вопросов" и "Реальное собеседование"
– Аналитика требований из вакансий
– Автоотклики на вакансии
– Агрегатор вакансий (скоро)
👉 Купить PRO со скидкой 70%: https://easyoffer.ru/pro
