PHP | LeetCode
رفتن به کانال در Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
نمایش بیشتر
شبکه:1 355
مشترکین
-124 ساعت
-67 روز
-1030 روز
آرشیو پست ها
1 355
Задача: 347. Top K Frequent Elements
Сложность: medium
Дан массив целых чисел nums и целое число k. Верните k самых частых элементов. Вы можете вернуть ответ в любом порядке.
Пример:
Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2]👨💻 Алгоритм: 1⃣Подсчет частоты: Используйте хеш-таблицу или словарь для подсчета количества вхождений каждого элемента в массиве nums. 2⃣Создание кучи: Создайте кучу, чтобы отсортировать элементы по их частоте и выбрать k самых частых элементов. 3⃣Возврат результата: Верните k самых частых элементов. 😎 Решение:
class Solution {
function topKFrequent($nums, $k) {
$count = array_count_values($nums);
arsort($count);
return array_slice(array_keys($count), 0, $k);
}
}1 355
Задача: 918. Maximum Sum Circular Subarray
Сложность: medium
Если задан круговой целочисленный массив nums длины n, верните максимально возможную сумму непустого подмассива nums. Круговой массив означает, что конец массива соединяется с его началом. Формально, следующий элемент nums[i] равен nums[(i + 1) % n], а предыдущий элемент nums[i] равен nums[(i - 1 + n) % n]. Подмассив может включать каждый элемент фиксированного буфера nums не более одного раза. Формально, для подмассива nums[i], nums[i + 1], ..., nums[j] не существует i <= k1, k2 <= j, при этом k1 % n == k2 % n.
Пример:
Input: nums = [1,-2,3,-2] Output: 3👨💻 Алгоритм: 1⃣Найти стандартную максимальную сумму подмассива с помощью алгоритма Кадане. 2⃣Найти минимальную сумму подмассива с помощью алгоритма Кадане и вычесть ее из общей суммы массива. 3⃣Вернуть максимум между стандартной максимальной суммой подмассива и общей суммой массива минус минимальную сумму подмассива, если результат не равен 0 (чтобы учесть случай, когда все числа отрицательные). 😎 Решение:
function maxSubarraySumCircular($nums) {
function kadane($arr) {
$currentSum = $arr[0];
$maxSum = $arr[0];
for ($i = 1; $i < count($arr); $i++) {
$currentSum = max($arr[$i], $currentSum + $arr[$i]);
$maxSum = max($maxSum, $currentSum);
}
return $maxSum;
}
$maxKadane = kadane($nums);
$totalSum = array_sum($nums);
$nums = array_map(function($num) { return -$num; }, $nums);
$minKadane = kadane($nums);
return max($maxKadane, $totalSum + $minKadane == 0 ? $maxKadane : $totalSum + $minKadane);
}1 355
Зарплата 207.000р у Middle-разработчика в Яндекс
«В день уходит несколько часов на созвоны, в остальное время закрываю задачки из спринта, редко перерабатываю. У компании топовый офис, но с коллективом как-то не заладилось. Радуюсь классному ДМС и стабильной зарплате» - middle разработчик из Яндекса.
Бигтех по-русски - канал с реальными зарплатами и историями IT-специалистов российского БигТеха. Там уже опубликованы рассказы программистов Альфа-банка, Сбера и Тинькофф 🤯
Читайте: @bigtech_russia
1 355
Задача: 565. Array Nesting
Сложность: medium
Дан массив целых чисел nums длиной n, где nums является перестановкой чисел в диапазоне [0, n - 1].
Вы должны построить множество s[k] = {nums[k], nums[nums[k]], nums[nums[nums[k]]], ...} при соблюдении следующего правила:
Первый элемент в s[k] начинается с выбора элемента nums[k] с индексом k.
Следующий элемент в s[k] должен быть nums[nums[k]], затем nums[nums[nums[k]]], и так далее.
Мы прекращаем добавлять элементы непосредственно перед тем, как в s[k] появится дубликат.
Верните длину самого длинного множества s[k].
Пример:
Input: nums = [5,4,0,3,1,6,2]
Output: 4
Explanation:
nums[0] = 5, nums[1] = 4, nums[2] = 0, nums[3] = 3, nums[4] = 1, nums[5] = 6, nums[6] = 2.
One of the longest sets s[k]:
s[0] = {nums[0], nums[5], nums[6], nums[2]} = {5, 6, 2, 0}
👨💻 Алгоритм:
1⃣Создайте массив для отслеживания посещенных элементов.
2⃣Для каждого элемента в nums, если он не посещен, начните формирование множества s[k], последовательно переходя по элементам, пока не встретится уже посещенный элемент.
3⃣Обновите максимальную длину найденного множества.
😎 Решение:
class Solution {
function arrayNesting($nums) {
$visited = array_fill(0, count($nums), false);
$maxLength = 0;
for ($i = 0; $i < count($nums); $i++) {
if (!$visited[$i]) {
$start = $i;
$count = 0;
while (!$visited[$start]) {
$visited[$start] = true;
$start = $nums[$start];
$count++;
}
$maxLength = max($maxLength, $count);
}
}
return $maxLength;
}
}1 355
Задача: 946. Validate Stack Sequences
Сложность: medium
Учитывая, что два целочисленных массива pushed и popped имеют разные значения, верните true, если это могло быть результатом последовательности операций push и pop на изначально пустом стеке, или false в противном случае.
Пример:
Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1] Output: true👨💻 Алгоритм: 1⃣Инициализировать пустой стек. Использовать указатель j для отслеживания текущей позиции в массиве popped. 2⃣Пройти по каждому элементу в массиве pushed: Добавить элемент в стек. Проверить верхний элемент стека: Если он совпадает с текущим элементом в popped, удалить элемент из стека и увеличить указатель j. 3⃣В конце вернуть true, если указатель j достиг конца массива popped, иначе вернуть false. 😎 Решение:
function validateStackSequences($pushed, $popped) {
$stack = [];
$j = 0;
foreach ($pushed as $x) {
$stack[] = $x;
while (!empty($stack) && $j < count($popped) && end($stack) == $popped[$j]) {
array_pop($stack);
$j++;
}
}
return $j == count($popped);
}1 355
Telegram опубликовал список 8 самых быстрорастущих каналов для программистов:
Only Python — Подборки приёмов и фич, о которых не рассказывают в курсах.
Only Tech — Главные тренды и инсайды из мира технологий, маркетинга и интернет-культуры.
Only Hack — Реальные кейсы кибератак, инструменты и методы защиты, которые используют хакеры.
Only GitHub — Репозитории, которые решают реальные задачи.
Скрипты, фреймворки и готовые решения
Only IT — Без мнений и слухов — только факты и важные IT-события.
Only Apple — Новые апдейты, утечки и фишки, которые Apple ещё не показала.
Only GPT — Промпты, хаки и свежие инструменты, о которых молчат даже AI-каналы.
Only Memes — Если ты когда-нибудь деплоил в пятницу вечером — ты поймешь
Подписывайтесь и прокачивайте свои скиллы.
1 355
📺 База 1000+ реальных собеседований
На программиста, тестировщика, аналитика, проджекта и другие IT профы.
Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д.
🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!
1 355
Задача: 416. Partition Equal Subset Sum
Сложность: medium
Если задан целочисленный массив nums, верните третье максимальное число в этом массиве. Если третьего максимального числа не существует, верните максимальное число.
Пример:
Input: nums = [1,5,11,5] Output: true👨💻 Алгоритм: 1⃣Проверьте, является ли сумма всех элементов массива четной. Если нет, верните false. 2⃣Используйте динамическое программирование для определения, можно ли найти подмножество с суммой, равной половине от общей суммы элементов. 3⃣Инициализируйте массив для хранения возможных сумм и обновляйте его, проверяя каждое число в массиве. 😎 Решение:
function canPartition($nums) {
$sum = array_sum($nums);
if ($sum % 2 != 0) return false;
$target = $sum / 2;
$dp = array_fill(0, $target + 1, false);
$dp[0] = true;
foreach ($nums as $num) {
for ($j = $target; $j >= $num; $j--) {
$dp[$j] = $dp[$j] || $dp[$j - $num];
}
}
return $dp[$target];
}1 355
Задача: 250. Count Univalue Subtrees
Сложность: medium
Дан корень бинарного дерева, верните количество поддеревьев с одинаковыми значениями.
Поддерево с одинаковыми значениями означает, что все узлы поддерева имеют одно и то же значение.
Пример:
Input: root = [5,1,5,5,5,null,5] Output: 4👨💻 Алгоритм: 1⃣Создайте целочисленную переменную count для подсчета количества поддеревьев с одинаковыми значениями. Инициализируйте её значением 0. 2⃣Выполните обход в глубину (DFS) для данного бинарного дерева. Выполните dfs(root), где dfs — это рекурсивный метод, который принимает узел TreeNode в качестве параметра, от которого начинается обход. Метод возвращает логическое значение, указывающее, является ли поддерево, укоренённое в этом узле, поддеревом с одинаковыми значениями. Выполните следующие действия в этом методе: Если узел равен null, верните true. Рекурсивно проверьте, образует ли левый потомок поддерево с одинаковыми значениями. Выполните isLeftUniValue = dfs(node.left). Рекурсивно проверьте, образует ли правый потомок поддерево с одинаковыми значениями. Выполните isRightUniValue = dfs(node.right). Если оба потомка образуют поддеревья с одинаковыми значениями, т.е. isLeftUniValue && isRightUniValue равно true, сравните значения потомков узла со значением самого узла. Если левый потомок существует и node.left.val != node.val, верните false, так как значения не совпадают и мы не имеем поддерева с одинаковыми значениями. Аналогично, если правый потомок существует и node.right.val != node.val, верните false. В противном случае, увеличьте count на 1 и верните true. В противном случае, одно или оба поддерева потомков не образуют поддеревья с одинаковыми значениями, поэтому дерево, укоренённое в node, также не может быть таким поддеревом. Верните false. 3⃣Верните count. 😎 Решение:
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 $count = 0;
private function dfs($node) {
if ($node === null) {
return true;
}
$isLeftUniValue = $this->dfs($node->left);
$isRightUniValue = $this->dfs($node->right);
if ($isLeftUniValue && $isRightUniValue) {
if ($node->left !== null && $node->left->val !== $node->val) {
return false;
}
if ($node->right !== null && $node->right->val !== $node->val) {
return false;
}
$this->count++;
return true;
}
return false;
}
public function countUnivalSubtrees($root) {
$this->dfs($root);
return $this->count;
}
}1 355
Задача: 673. Number of Longest Increasing Subsequence
Сложность: medium
Дан массив целых чисел nums, верните количество самых длинных строго возрастающих подпоследовательностей.
Пример:
Input: n = 1, presses = 1
Output: 2
Explanation: Status can be:
- [off] by pressing button 1
- [on] by pressing button 2class Solution {
function findNumberOfLIS($nums) {
$n = count($nums);
$length = array_fill(0, $n, 1);
$count = array_fill(0, $n, 1);
for ($i = 0; $i < $n; $i++) {
for ($j = 0; $j < $i; $j++) {
if ($nums[$j] < $nums[$i]) {
if ($length[$j] + 1 > $length[$i]) {
$length[$i] = $length[$j] + 1;
$count[$i] = 0;
}
if ($length[$j] + 1 == $length[$i]) {
$count[$i] += $count[$j];
}
}
}
}
$maxLength = max($length);
$result = 0;
for ($i = 0; $i < $n; $i++) {
if ($length[$i] == $maxLength) {
$result += $count[$i];
}
}
return $result;
}
}1 355
Задача: 899. Orderly Queue
Сложность: hard
Вам дана строка s и целое число k. Вы можете выбрать одну из первых k букв s и добавить ее в конец строки. Верните лексикографически наименьшую строку, которая может получиться после применения указанного шага за любое количество ходов.
Пример:
Input: s = "cba", k = 1 Output: "acb"👨💻 Алгоритм: 1⃣Если k равно 1, найти лексикографически наименьшую строку путем вращения строки и поиска минимального варианта. 2⃣Если k больше 1, отсортировать строку, так как любое количество перемещений позволит упорядочить все символы в строке. 3⃣Вернуть результат. 😎 Решение:
function orderlyQueue($s, $k) {
if ($k == 1) {
$minString = $s;
for ($i = 1; $i < strlen($s); $i++) {
$rotated = substr($s, $i) . substr($s, 0, $i);
if ($rotated < $minString) {
$minString = $rotated;
}
}
return $minString;
} else {
$sArray = str_split($s);
sort($sArray);
return implode('', $sArray);
}
}1 355
Задача: 664. Strange Printer
Сложность: hard
Существует странный принтер с двумя особыми свойствами:
Принтер может печатать последовательность одного и того же символа за раз.
На каждом шагу принтер может печатать новые символы, начиная и заканчивая в любом месте, при этом покрывая уже существующие символы.
Дана строка s. Верните минимальное количество ходов, необходимых для её печати.
Пример:
Input: s = "aaabbb" Output: 2 Explanation: Print "aaa" first and then print "bbb".👨💻 Алгоритм: 1⃣Инициализация и подсчет: Создайте двумерный массив dp, где dp[i][j] представляет минимальное количество ходов для печати подстроки s[i:j+1]. 2⃣Динамическое программирование: Если s[i] == s[j], тогда dp[i][j] = dp[i][j-1], так как последний символ совпадает с предыдущим. В противном случае, dp[i][j] = min(dp[i][k] + dp[k+1][j]) для всех i <= k < j, чтобы найти минимальное количество ходов. 3⃣Возврат результата: Возвратите dp[0][n-1], где n - длина строки s, что представляет минимальное количество ходов для печати всей строки. 😎 Решение:
class Solution {
function strangePrinter($s) {
$n = strlen($s);
$dp = array_fill(0, $n, array_fill(0, $n, 0));
for ($length = 1; $length <= $n; $length++) {
for ($i = 0; $i <= $n - $length; $i++) {
$j = $i + $length - 1;
$dp[$i][$j] = ($i === $j) ? 1 : $dp[$i][$j - 1] + 1;
for ($k = $i; $k < $j; $k++) {
if ($s[$k] === $s[$j]) {
$dp[$i][$j] = min($dp[$i][$j], $dp[$i][$k] + ($k + 1 <= $j - 1 ? $dp[$k + 1][$j - 1] : 0));
}
}
}
}
return $dp[0][$n - 1];
}
}1 355
Задача: 911. Online Election
Сложность: medium
Вам даны два целочисленных массива persons и times. На выборах i-й голос был отдан за person[i] в момент времени times[i]. Для каждого запроса в момент времени t найдите человека, который лидировал на выборах в момент времени t. Голоса, отданные в момент времени t, будут учитываться в нашем запросе. В случае равенства голосов побеждает тот, кто проголосовал последним (среди равных кандидатов). Реализация класса TopVotedCandidate: TopVotedCandidate(int[] persons, int[] times) Инициализирует объект с массивами persons и times. int q(int t) Возвращает номер человека, который лидировал на выборах в момент времени t в соответствии с указанными правилами.
Пример:
Input ["TopVotedCandidate", "q", "q", "q", "q", "q", "q"] [[[0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]], [3], [12], [25], [15], [24], [8]] Output [null, 0, 1, 1, 0, 0, 1]👨💻 Алгоритм: 1⃣Использовать два массива для хранения лиц и времени голосования. 2⃣Поддерживать текущий счет для каждого кандидата и текущего лидера на момент времени. 3⃣На каждый запрос времени t, найти наибольший индекс времени, который не превышает t, и вернуть лидера на этот момент времени. 😎 Решение:
class TopVotedCandidate {
private $times;
private $leaders;
function __construct($persons, $times) {
$this->times = $times;
$this->leaders = [];
$counts = [];
$leader = -1;
foreach ($persons as $person) {
if (!isset($counts[$person])) {
$counts[$person] = 0;
}
$counts[$person]++;
if (!isset($counts[$leader]) || $counts[$person] >= $counts[$leader]) {
$leader = $person;
}
$this->leaders[] = $leader;
}
}
function q($t) {
$left = 0;
$right = count($this->times) - 1;
while ($left < $right) {
$mid = intdiv($left + $right + 1, 2);
if ($this->times[$mid] <= $t) {
$left = $mid;
} else {
$right = $mid - 1;
}
}
return $this->leaders[$left];
}
}1 355
"Ты че, дурак?" – базовая реакция сеньора на тех, кто покупает IT курсы
Дело в том, что онлайн школы создают инкубаторных айтишников, которые в реальных условиях попросту зависнут.
Трушные ребята учатся на жизненных каналах для айтишников. Вот топ-5 от тимлида из Сбера:
⚙️ Технолоджия – для тех, кто хочет быть в курсе новостей в айти
🧠 Ai-чница – способы превратить нейросети в заработок $$$
💻 ИИ тебя заменит! – тенденции айти рынка в связке с нейросетями
4️⃣ Войти в IT – тонны бесплатного обучения для прогеров
😄 IT индус – сборник айти мемов
1 355
Задача: 1209. Remove All Adjacent Duplicates in String II
Сложность: medium
Вам дана строка s и целое число k. Удаление k дубликатов состоит в выборе k соседних и одинаковых букв из s и их удалении, что приводит к соединению левой и правой части удаленной подстроки вместе.
Мы повторяем удаление k дубликатов в s до тех пор, пока не сможем больше этого сделать.
Верните итоговую строку после всех таких удалений дубликатов. Гарантируется, что ответ уникален.
Пример:
Input: s = "deeedbbcccbdaa", k = 3 Output: "aa" Explanation: First delete "eee" and "ccc", get "ddbbbdaa" Then delete "bbb", get "dddaa" Finally delete "ddd", get "aa"👨💻 Алгоритм: 1⃣ Инициализировать медленный указатель j значением 0 и стек counts для хранения количества одинаковых символов. 2⃣Перемещать быстрый указатель i по строке s: Копировать s[i] в s[j]. Если s[j] совпадает с s[j - 1], увеличить значение на вершине стека. Иначе добавить 1 в стек. Если количество символов равно k, уменьшить j на k и извлечь из стека. 3⃣Вернуть первые j символов строки. 😎 Решение:
class Solution {
function removeDuplicates($s, $k) {
$counts = [];
$sa = str_split($s);
$j = 0;
for ($i = 0; $i < count($sa); ++$i, ++$j) {
$sa[$j] = $sa[$i];
if ($j == 0 || $sa[$j] != $sa[$j - 1]) {
array_push($counts, 1);
} else {
$incremented = array_pop($counts) + 1;
if ($incremented == $k) {
$j -= $k;
} else {
array_push($counts, $incremented);
}
}
}
return implode('', array_slice($sa, 0, $j));
}
}1 355
Айтишники, это вам — в телеграм есть комьюнити по каждому направлению в IT
Там есть буквально всё: чаты для общения, тонны материала(книги, курсы, ресурсы и гайды), свежие новости и конечно же мемы
Выбирайте своё направление:
💩 Frontend 🐍 Python
🐧 Linux 👩💻 С/С++
👩💻 C# 🤔 Хакинг & ИБ
📱 GitHub 🖥 SQL
👩💻 Сисадмин 🤟 DevOps
⚙️ Backend 🖥 Data Science
🧑💻 Java 🐞 Тестирование
🖥 PM / PdM 👩💻 GameDev
🧑💻 Golang 🤵♂️ IT-Митапы
🧑💻 PHP 💻 WebDev
🖥 Моб. Dev 🖥Анали.(SA&BA)
👩💻 Дизайн 🖥 Нейросети
💛 1C 🤓 Книги IT
➡️ Сохраняйте в закладки
1 355
Задача: 1030. Matrix Cells in Distance Order
Сложность: easy
Вам даны четыре целых числа row, cols, rCenter и cCenter. Имеется матрица rows x cols, и вы находитесь на ячейке с координатами (rCenter, cCenter). Верните координаты всех ячеек в матрице, отсортированные по их расстоянию от (rCenter, cCenter) от наименьшего расстояния до наибольшего. Вы можете вернуть ответ в любом порядке, удовлетворяющем этому условию. Расстояние между двумя ячейками (r1, c1) и (r2, c2) равно |r1 - r2| + |c1 - c2|.
Пример:
Input: rows = 1, cols = 2, rCenter = 0, cCenter = 0
Output: [[0,0],[0,1]]function allCellsDistOrder($rows, $cols, $rCenter, $cCenter) {
$cells = [];
for ($r = 0; $r < $rows; $r++) {
for ($c = 0; $c < $cols; $c++) {
$distance = abs($r - $rCenter) + abs($c - $cCenter);
$cells[] = [$distance, $r, $c];
}
}
usort($cells, function($a, $b) {
return $a[0] <=> $b[0];
});
return array_map(function($cell) {
return [$cell[1], $cell[2]];
}, $cells);
}1 355
Задача: 1329. Sort the Matrix Diagonally
Сложность: medium
Диагональ матрицы — это диагональная линия ячеек, начинающаяся с какой-либо ячейки в самой верхней строке или в самом левом столбце и идущая в направлении вниз-вправо до конца матрицы. Например, диагональ матрицы, начинающаяся с mat[2][0], где mat — это матрица размером 6 x 3, включает ячейки mat[2][0], mat[3][1] и mat[4][2].
Дана матрица mat размером m x n, состоящая из целых чисел. Отсортируйте каждую диагональ матрицы по возрастанию и верните полученную матрицу.
Пример:
Input: mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]
Output: [[1,1,1,1],[1,2,2,2],[1,2,3,3]]class Solution {
function diagonalSort($mat) {
$m = count($mat);
$n = count($mat[0]);
$diagonals = [];
for ($row = 0; $row < $m; $row++) {
for ($col = 0; $col < $n; $col++) {
$key = $row - $col;
if (!isset($diagonals[$key])) {
$diagonals[$key] = [];
}
$diagonals[$key][] = $mat[$row][$col];
}
}
foreach ($diagonals as &$diagonal) {
sort($diagonal);
}
for ($row = 0; $row < $m; $row++) {
for ($col = 0; $col < $n; $col++) {
$key = $row - $col;
$mat[$row][$col] = array_shift($diagonals[$key]);
}
}
return $mat;
}
}1 355
Задача: 1140. Stone Game II
Сложность: medium
Алиса и Боб продолжают свои игры с кучами камней. Есть несколько куч, расположенных в ряд, и в каждой куче положительное количество камней piles[i]. Цель игры - закончить с наибольшим количеством камней.
Алиса и Боб ходят по очереди, начиная с Алисы. Изначально M = 1.
В свой ход каждый игрок может взять все камни из первых X оставшихся куч, где 1 <= X <= 2M. Затем, мы устанавливаем M = max(M, X).
Игра продолжается до тех пор, пока все камни не будут взяты.
Предполагая, что Алиса и Боб играют оптимально, верните максимальное количество камней, которые может получить Алиса.
Пример:
Input: piles = [2,7,9,4,4] Output: 10 Explanation: If Alice takes one pile at the beginning, Bob takes two piles, then Alice takes 2 piles again. Alice can get 2 + 4 + 4 = 10 piles in total. If Alice takes two piles at the beginning, then Bob can take all three piles left. In this case, Alice get 2 + 7 = 9 piles in total. So we return 10 since it's larger.👨💻 Алгоритм: 1⃣Создать рекурсивную функцию f, которая принимает три параметра: p (игрок), i (индекс текущей кучи), и m (максимальное количество куч, которые можно взять за ход). Если i равен длине массива кучи, вернуть 0 (базовый случай рекурсии). Если значение уже вычислено ранее (dp[p][i][m] != -1), вернуть его. 2⃣ Инициализировать переменную s как количество камней, взятых текущим игроком за ход, и переменную res для хранения результата текущего состояния. Если ход Боба, инициализировать res большим числом, так как Боб хочет минимизировать результат. Если ход Алисы, инициализировать res маленьким числом, так как Алиса хочет максимизировать результат. 3⃣Итеративно обновлять значение res в зависимости от того, чей ход, и обновлять значения в dp[p][i][m]. В конце вернуть res. 😎 Решение:
class Solution {
function stoneGameII($piles) {
$n = count($piles);
$dp = array_fill(0, 2, array_fill(0, $n + 1, array_fill(0, $n + 1, -1)));
function f($p, $i, $m, &$dp, &$piles) {
if ($i == count($piles)) return 0;
if ($dp[$p][$i][$m] != -1) return $dp[$p][$i][$m];
$res = $p == 1 ? 1000000 : -1;
$s = 0;
for ($x = 1; $x <= min(2 * $m, count($piles) - $i); $x++) {
$s += $piles[$i + $x - 1];
if ($p == 0) {
$res = max($res, $s + f(1, $i + $x, max($m, $x), $dp, $piles));
} else {
$res = min($res, f(0, $i + $x, max($m, $x), $dp, $piles));
}
}
return $dp[$p][$i][$m] = $res;
}
return f(0, 0, 1, $dp, $piles);
}
}1 355
Задача: 1470. Shuffle the Array
Сложность: easy
Дан массив nums, состоящий из 2n элементов в форме [x1, x2, ..., xn, y1, y2, ..., yn].
Верните массив в форме [x1, y1, x2, y2, ..., xn, yn].
Пример:
Input: nums = [2,5,1,3,4,7], n = 3
Output: [2,3,5,4,1,7]
Explanation: Since x1=2, x2=5, x3=1, y1=3, y2=4, y3=7 then the answer is [2,3,5,4,1,7].class Solution {
/**
* @param Integer[] $nums
* @param Integer $n
* @return Integer[]
*/
function shuffle($nums, $n) {
$result = array_fill(0, 2 * $n, 0);
for ($i = 0; $i < $n; ++$i) {
$result[2 * $i] = $nums[$i];
$result[2 * $i + 1] = $nums[$n + $i];
}
return $result;
}
}