PHP | LeetCode
Ir al canal en Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
Mostrar más
Red:1 355
Suscriptores
Sin datos24 horas
-67 días
-930 días
Archivo de publicaciones
1 355
Задача: 938. Range Sum of BST
Сложность: easy
Учитывая корневой узел двоичного дерева поиска и два целых числа low и high, верните сумму значений всех узлов со значением в диапазоне [low, high].
Пример:
Input: root = [10,5,15,3,7,null,18], low = 7, high = 15 Output: 32👨💻 Алгоритм: 1⃣Если дерево пустое, вернуть 0. 2⃣Если значение текущего узла меньше low, рекурсивно искать в правом поддереве. Если значение текущего узла больше high, рекурсивно искать в левом поддереве. 3⃣Если значение текущего узла в диапазоне [low, high], включить значение узла в сумму и рекурсивно искать в обоих поддеревьях. 😎 Решение:
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 rangeSumBST($root, $low, $high) {
if ($root === null) return 0;
if ($root->val < $low) return $this->rangeSumBST($root->right, $low, $high);
if ($root->val > $high) return $this->rangeSumBST($root->left, $low, $high);
return $root->val + $this->rangeSumBST($root->left, $low, $high) + $this->rangeSumBST($root->right, $low, $high);
}
}1 355
Задача: 651. 4 Keys Keyboard
Сложность: medium
Представьте, что у вас есть специальная клавиатура со следующими клавишами: A: Напечатать одну букву "A" на экране. Ctrl-A: Выделить весь экран. Ctrl-C: Скопировать выделение в буфер. Ctrl-V: Печать буфера на экране с добавлением его после того, что уже было напечатано. Учитывая целое число n, верните максимальное количество букв 'A', которые можно напечатать на экране при нажатии не более n клавиш.
Пример:
Input: root = [1,2,3,4,null,2,4,null,null,4] Output: [[2,4],[4]]👨💻 Алгоритм: 1⃣Используйте динамическое программирование для отслеживания максимального количества букв 'A' на экране после каждого числа нажатий клавиш. 2⃣Итерируйтесь от 1 до n, вычисляя максимальное количество 'A' для каждой позиции, учитывая возможность вставки скопированного текста. 3⃣Возвращайте значение из таблицы динамического программирования для n нажатий клавиш. 😎 Решение:
function maxA($n) {
$dp = array_fill(0, $n + 1, 0);
for ($i = 1; $i <= $n; $i++) {
$dp[$i] = $dp[$i - 1] + 1;
for ($j = 2; $j < $i; $j++) {
$dp[$i] = max($dp[$i], $dp[$j - 2] * ($i - $j + 1));
}
}
return $dp[$n];
}1 355
Задача: 680. Valid Palindrome II
Сложность: easy
Дана строка s, вернуть true, если s может быть палиндромом после удаления не более одного символа из нее.
Пример:
Input: s = "aba"
Output: trueclass Solution {
private function checkPalindrome($s, $i, $j) {
while ($i < $j) {
if ($s[$i] != $s[$j]) {
return false;
}
$i++;
$j--;
}
return true;
}
public function validPalindrome($s) {
$i = 0;
$j = strlen($s) - 1;
while ($i < $j) {
if ($s[$i] != $s[$j]) {
return $this->checkPalindrome($s, $i, $j - 1) || $this->checkPalindrome($s, $i + 1, $j);
}
$i++;
$j--;
}
return true;
}
}1 355
Задача: 556. Next Greater Element III
Сложность: medium
Мы можем перемешать строку s, чтобы получить строку t, используя следующий алгоритм:
Дано положительное целое число n. Найдите наименьшее целое число, которое имеет точно такие же цифры, как и число n, и больше самого числа n по значению. Если такого положительного целого числа не существует, верните -1.
Учтите, что возвращенное число должно помещаться в 32-битное целое число. Если существует допустимый ответ, но он не помещается в 32-битное целое число, верните -1.
Пример:
Input: n = 12 Output: 21👨💻 Алгоритм: 1⃣Нахождение и перестановка цифр Преобразуйте число n в массив цифр. Найдите первую цифру, которая нарушает убывающий порядок (с конца массива). Назовем её индексом i. Найдите первую цифру, которая больше digits[i-1] (с конца массива). Назовем её индексом j. Поменяйте местами цифры на позициях i-1 и j. 2⃣Обратный порядок оставшихся цифр Обратный порядок части массива от индекса i до конца, чтобы получить наименьшую перестановку, которая больше исходной. 3⃣Проверка результата и преобразование обратно в число Преобразуйте массив цифр обратно в число. Если число превышает 32-битный предел, верните -1. В противном случае верните полученное число. 😎 Решение:
class Solution {
private function swap($s, $i0, $i1) {
if ($i0 == $i1) return $s;
$chars = str_split($s);
$temp = $chars[$i0];
$chars[$i0] = $chars[$i1];
$chars[$i1] = $temp;
return implode('', $chars);
}
private $list = [];
private function permute($a, $l, $r) {
if ($l == $r) {
$this->list[] = $a;
} else {
for ($i = $l; $i <= $r; $i++) {
$a = $this->swap($a, $l, $i);
$this->permute($a, $l + 1, $r);
$a = $this->swap($a, $l, $i);
}
}
}
public function nextGreaterElement($n) {
$s = strval($n);
$this->permute($s, 0, strlen($s) - 1);
sort($this->list);
$index = array_search($s, $this->list);
if ($index !== false && $index < count($this->list) - 1) {
$result = intval($this->list[$index + 1]);
if ($result <= 2147483647) {
return $result;
}
}
return -1;
}
}1 355
Задача: 740. Delete and Earn
Сложность: medium
Вам дан целочисленный массив nums. Вы хотите максимизировать количество очков, выполнив следующую операцию любое количество раз: Выберите любой элемент nums[i] и удалите его, чтобы заработать nums[i] очков. После этого вы должны удалить каждый элемент, равный nums[i] - 1, и каждый элемент, равный nums[i] + 1. Верните максимальное количество очков, которое вы можете заработать, применив вышеуказанную операцию некоторое количество раз.
Пример:
Input: nums = [3,4,2] Output: 6👨💻 Алгоритм: 1⃣Подсчитайте количество каждого числа в массиве nums. 2⃣Используйте динамическое программирование для расчета максимальных очков, которые можно заработать, используя накопленный результат для чисел, меньших текущего. Добавьте текущий день в стек. 3⃣Для каждого числа num в nums, учитывайте два случая: не брать число или взять число и добавить его очки. 😎 Решение:
function deleteAndEarn($nums) {
$count = array_count_values($nums);
$avoid = $using = 0;
$prev = -1;
ksort($count);
foreach ($count as $num => $freq) {
if ($num - 1 != $prev) {
$newAvoid = max($avoid, $using);
$using = $num * $freq + max($avoid, $using);
$avoid = $newAvoid;
} else {
$newAvoid = max($avoid, $using);
$using = $num * $freq + $avoid;
$avoid = $newAvoid;
}
$prev = $num;
}
return max($avoid, $using);
}1 355
Задача: 541. Reverse String II
Сложность: easy
Дана строка s и целое число k, переверните первые k символов для каждых 2k символов, начиная с начала строки.
Если осталось меньше k символов, переверните все. Если осталось меньше 2k, но больше или равно k символов, переверните первые k символов и оставьте остальные как есть.
Пример:
Input: s = "abcdefg", k = 2 Output: "bacdfeg"👨💻 Алгоритм: 1⃣Разворачиваем каждый блок из 2k символов непосредственно. Каждый блок начинается с кратного 2k: например, 0, 2k, 4k, 6k и так далее. 2⃣Будьте внимательны, если символов недостаточно, блок может не быть перевернут. 3⃣Для разворота блока символов с позиции i до j, меняем местами символы на позициях i++ и j--. 😎 Решение:
class Solution {
function reverseStr($s, $k) {
$a = str_split($s);
for ($start = 0; $start < count($a); $start += 2 * $k) {
$i = $start;
$j = min($start + $k - 1, count($a) - 1);
while ($i < $j) {
$tmp = $a[$i];
$a[$i++] = $a[$j];
$a[$j--] = $tmp;
}
}
return implode('', $a);
}
}1 355
Задача: 896. Monotonic Array
Сложность: easy
Массив является монотонным, если он либо монотонно возрастает, либо монотонно убывает. Массив nums является монотонно возрастающим, если для всех i <= j, nums[i] <= nums[j]. Массив nums является монотонно убывающим, если для всех i <= j, nums[i] >= nums[j]. Если задан целочисленный массив nums, верните true, если данный массив монотонный, или false в противном случае.
Пример:
Input: nums = [1,2,2,3] Output: true👨💻 Алгоритм: 1⃣Определить два флага: increasing и decreasing. 2⃣Пройтись по массиву: Если текущий элемент больше следующего, установить increasing в false. Если текущий элемент меньше следующего, установить decreasing в false. 3⃣Вернуть true, если хотя бы один из флагов true, иначе вернуть false. 😎 Решение:
function isMonotonic($nums) {
$increasing = true;
$decreasing = true;
for ($i = 1; $i < count($nums); $i++) {
if ($nums[$i] > $nums[$i - 1]) {
$decreasing = false;
}
if ($nums[$i] < $nums[$i - 1]) {
$increasing = false;
}
}
return $increasing || $decreasing;
}1 355
Repost from easyoffer
🎉 easyoffer 2.0 — релиз уже в этом месяце!
Вас ждут новые фичи, о которых мы ранее даже не упоминали. Они сделают путь к офферам ещё быстрее и эффективнее. Расскажу о них чуть позже 👀
В честь запуска мы готовим ограниченную акцию:
Первые 500 покупателей получат:
🚀 PRO тариф на 1 год с 50% скидкой
Что нужно сделать:
🔔 Подпишитесь на этот Telegram-канал, чтобы первыми узнать о старте релиза. Сообщение появится в нем раньше, чем где-либо еще — вы успеете попасть в число первых 500 и получить максимальную выгоду. 🎁 А еще только для подписчиков канала ценный бонус в подарок к PRO тарифу.
📅 Официальный запуск — уже совсем скоро.
Следите за новостями и не пропустите старт!
1 355
Задача: 1051. Height Checker
Сложность: easy
Школа пытается сделать ежегодную фотографию всех учеников. Учеников просят встать в одну шеренгу в неубывающем порядке по росту. Пусть этот порядок представлен целочисленным массивом expected, где expected[i] - ожидаемый рост i-го студента в очереди. Вам дан целочисленный массив heights, представляющий текущий порядок, в котором стоят студенты. Каждый heights[i] - это высота i-го студента в очереди (с индексом 0). Верните количество индексов, в которых heights[i] != expected[i].
Пример:
Input: heights = [1,1,4,2,1,3] Output: 3👨💻 Алгоритм: 1⃣Создай отсортированную копию массива heights, чтобы получить ожидаемый порядок высот. 2⃣Пройди по обоим массивам и сравни элементы. 3⃣Подсчитай количество индексов, где элементы двух массивов не равны 😎 Решение:
function heightChecker($heights) {
$expected = $heights;
sort($expected);
$count = 0;
for ($i = 0; $i < count($heights); $i++) {
if ($heights[$i] != $expected[$i]) {
$count++;
}
}
return $count;
}1 355
Задача: 202. Happy Number
Сложность: easy
Напишите алгоритм для определения, является ли число n счастливым
Счастливое число определяется следующим процессом:
Начиная с любого положительного целого числа, замените число суммой квадратов его цифр.
Повторяйте процесс, пока число не станет равным 1 (где оно и останется), или пока оно бесконечно не будет циклически повторяться в цикле, который не включает 1.
Те числа, для которых этот процесс завершается 1, являются счастливыми.
Верните true, если n является счастливым числом, и false, если нет.
Пример:
Input: n = 2 Output: false👨💻 Алгоритм: 1⃣Для заданного числа n определите следующее число в последовательности: используйте операторы деления и взятия остатка для последовательного извлечения цифр из числа, пока не закончатся все цифры. Каждую извлеченную цифру возводите в квадрат и суммируйте полученные значения. Это техника "последовательного извлечения цифр" является полезным инструментом для решения множества задач. 2⃣Отслеживайте цепочку чисел и определяйте, не вошли ли вы в цикл, используя структуру данных HashSet. Каждый раз, генерируя следующее число в цепочке, проверяйте, присутствует ли оно уже в HashSet. 3⃣Если числа нет в HashSet, добавьте его туда. Если число уже есть в HashSet, это означает, что вы находитесь в цикле, и следует вернуть false. HashSet используется вместо Vector, List или Array, потому что проверка присутствия числа в HashSet занимает время O(1), тогда как в других структурах данных это займет время O(n). Правильный выбор структур данных является ключевым элементом решения подобных задач. 😎 Решение:
function getNext($n) {
$totalSum = 0;
while ($n > 0) {
$digit = $n % 10;
$n = floor($n / 10);
$totalSum += $digit * $digit;
}
return $totalSum;
}
function isHappy($n) {
$seen = [];
while ($n != 1 && !in_array($n, $seen)) {
$seen[] = $n;
$n = getNext($n);
}
return $n == 1;
}
echo isHappy(19) ? "true" : "false";1 355
🐍💩👩💻👩💻🧑💻🧑💻🐧👩💻🧑💻👩💻👩💻
В сети начали массово сливать курсы и книги известных онлайн школ по айти
Вот отсортированная база с тонной материала (постепенно пополняется):
(363 видео, 87 книги) — Python
(415 видео, 68 книги) — Frontend
(143 видео, 33 книги) — ИБ/Хакинг
(352 видео, 89 книги) — С/С++/C#
(343 видео, 87 книги) — Java/QA
(176 видео, 32 книги) — Git/Linux
(174 видео, 91 книги) — DevOps
(167 видео, 53 книги) — PHP/1С
(227 видео, 83 книги) — SQL/БД
(114 видео, 77 книги) — Сисадмин
(107 видео, 43 книги) — BA/SA
(181 видео, 32 книги) — Go/Rust
(167 видео, 43 книги) — Kotlin/Swift
(112 видео, 24 книги) — Flutter
(137 видео, 93 книги) — DS/ML
(113 видео, 82 книги) — GameDev
(183 видео, 37 книги) — Дизайн
(136 видео, 33 книги) — PM/HR
Скачивать ничего не нужно — все выложили в Telegram
1 355
Задача: 213. House Robber II
Сложность: medium
Вы профессиональный грабитель, планирующий ограбить дома вдоль улицы. В каждом доме спрятано определенное количество денег. Все дома в этом месте расположены по кругу, что означает, что первый дом является соседом последнего. Между тем, в соседних домах установлена охранная система, которая автоматически свяжется с полицией, если два соседних дома будут взломаны в одну ночь.
Дан массив целых чисел nums, представляющий количество денег в каждом доме, верните максимальную сумму денег, которую вы можете ограбить этой ночью, не вызвав полицию.
Пример:
Input: nums = [1,2,3,1] Output: 4 Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4.👨💻 Алгоритм: 1⃣Обработка базовых случаев: Если массив nums пуст, возвращаем 0. Если в массиве nums только один дом, возвращаем значение этого дома. 2⃣Разделение задачи на две подзадачи: Находим максимальную сумму для подмассива домов от первого до предпоследнего, вызывая функцию rob_simple с параметрами 0 и count($nums) - 2. Находим максимальную сумму для подмассива домов от второго до последнего, вызывая функцию rob_simple с параметрами 1 и count($nums) - 1. 3⃣Сравнение результатов и возврат максимального значения: Вернуть максимальное значение из двух полученных результатов. 😎 Решение:
class Solution {
public function rob($nums) {
if (count($nums) == 0) return 0;
if (count($nums) == 1) return $nums[0];
$max1 = $this->rob_simple($nums, 0, count($nums) - 2);
$max2 = $this->rob_simple($nums, 1, count($nums) - 1);
return max($max1, $max2);
}
private function rob_simple($nums, $start, $end) {
$t1 = 0;
$t2 = 0;
for ($i = $start; $i <= $end; $i++) {
$temp = $t1;
$current = $nums[$i];
$t1 = max($current + $t2, $t1);
$t2 = $temp;
}
return $t1;
}
}1 355
Задача: 739. Daily Temperatures
Сложность: medium
Задав массив целых чисел temperature, представляющих дневные температуры, верните массив answer, такой, что answer[i] - это количество дней, которые нужно подождать после i-го дня, чтобы температура стала теплее. Если в будущем не существует дня, для которого это возможно, сохраните answer[i] == 0.
Пример:
Input: temperatures = [73,74,75,71,69,72,76,73] Output: [1,1,4,2,1,1,0,0]👨💻 Алгоритм: 1⃣Создайте стек для хранения индексов дней с температурами, для которых еще не найден более теплый день. 2⃣Пройдите по массиву температур и для каждого дня: Пока текущая температура больше температуры дня на вершине стека, обновляйте массив ответов и удаляйте вершину стека. Добавьте текущий день в стек. 3⃣Возвращайте массив ответов. 😎 Решение:
function dailyTemperatures($T) {
$n = count($T);
$answer = array_fill(0, $n, 0);
$stack = [];
for ($i = 0; $i < $n; $i++) {
while (!empty($stack) && $T[$i] > $T[end($stack)]) {
$j = array_pop($stack);
$answer[$j] = $i - $j;
}
$stack[] = $i;
}
return $answer;
}1 355
Задача: 774. Minimize Max Distance to Gas Station
Сложность: hard
Вам дан массив целых чисел stations, который представляет позиции автозаправочных станций на оси x. Вам также дано целое число k.
Вы должны добавить k новых автозаправочных станций. Вы можете добавлять станции в любое место на оси x, необязательно в целочисленную позицию.
Определим penalty() как максимальное расстояние между соседними автозаправочными станциями после добавления k новых станций.
Верните наименьшее возможное значение penalty(). Ответы, отличающиеся от фактического ответа не более чем на 10^-6, будут приняты.
Пример:
Input: stations = [1,2,3,4,5,6,7,8,9,10], k = 9
Output: 0.50000class Solution {
function minmaxGasDist($stations, $K) {
$N = count($stations);
$deltas = array_fill(0, $N-1, 0);
for ($i = 0; $i < $N-1; ++$i)
$deltas[$i] = $stations[$i+1] - $stations[$i];
$dp = array_fill(0, $N-1, array_fill(0, $K+1, 0));
for ($i = 0; $i <= $K; ++$i)
$dp[0][$i] = $deltas[0] / ($i+1);
for ($p = 1; $p < $N-1; ++$p)
for ($k = 0; $k <= $K; ++$k) {
$bns = 999999999;
for ($x = 0; $x <= $k; ++$x)
$bns = min($bns, max($deltas[$p] / ($x+1), $dp[$p-1][$k-$x]));
$dp[$p][$k] = $bns;
}
return $dp[$N-2][$K];
}
}1 355
![Задача: 465. Optimal Account Balancing Сложность: medium Дан массив транзакций transactions, где transactions[i] = [fromi, to](data:image/jpeg;base64,/9j/4AAQSkZJRgABAQAAAQABAAD/2wBDACgcHiMeGSgjISMtKygwPGRBPDc3PHtYXUlkkYCZlo+AjIqgtObDoKrarYqMyP/L2u71////m8H////6/+b9//j/2wBDASstLTw1PHZBQXb4pYyl+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj4+Pj/wAARCAAYACgDASIAAhEBAxEB/8QAHwAAAQUBAQEBAQEAAAAAAAAAAAECAwQFBgcICQoL/8QAtRAAAgEDAwIEAwUFBAQAAAF9AQIDAAQRBRIhMUEGE1FhByJxFDKBkaEII0KxwRVS0fAkM2JyggkKFhcYGRolJicoKSo0NTY3ODk6Q0RFRkdISUpTVFVWV1hZWmNkZWZnaGlqc3R1dnd4eXqDhIWGh4iJipKTlJWWl5iZmqKjpKWmp6ipqrKztLW2t7i5usLDxMXGx8jJytLT1NXW19jZ2uHi4+Tl5ufo6erx8vP09fb3+Pn6/8QAHwEAAwEBAQEBAQEBAQAAAAAAAAECAwQFBgcICQoL/8QAtREAAgECBAQDBAcFBAQAAQJ3AAECAxEEBSExBhJBUQdhcRMiMoEIFEKRobHBCSMzUvAVYnLRChYkNOEl8RcYGRomJygpKjU2Nzg5OkNERUZHSElKU1RVVldYWVpjZGVmZ2hpanN0dXZ3eHl6goOEhYaHiImKkpOUlZaXmJmaoqOkpaanqKmqsrO0tba3uLm6wsPExcbHyMnK0tPU1dbX2Nna4uPk5ebn6Onq8vP09fb3+Pn6/9oADAMBAAIRAxEAPwDYYhcZ7nFIrhiaGUN1J65pFUKepoAfmmISd2fWn/rTCVDAYGSaAH0UUUAFNYE9xwfSiigBQCBycmkZA3XP50UUAKBiiiigD//Z)
Задача: 465. Optimal Account Balancing
Сложность: medium
Дан массив транзакций transactions, где transactions[i] = [fromi, toi, amounti] указывает на то, что человек с ID = fromi дал сумму amounti долларов человеку с ID = toi.
Верните минимальное количество транзакций, необходимых для урегулирования долгов.
Пример:
Input: transactions = [[0,1,10],[2,0,5]] Output: 2👨💻 Алгоритм: 1⃣Создать хеш-таблицу для хранения чистого баланса каждого человека. 2⃣Собрать все ненулевые чистые балансы в массив balance_list. 3⃣Определить рекурсивную функцию dfs(cur) для очистки всех балансов в диапазоне balance_list[0 ~ cur]: Игнорировать cur, если баланс уже равен 0. Пока balance_list[cur] = 0, переходить к следующему человеку, увеличивая cur на 1. Если cur = n, вернуть 0. В противном случае установить cost на большое значение, например, inf. Пройтись по индексу nxt от cur + 1, если balance_list[nxt] * balance_list[cur] < 0, Добавить баланс balance_list[cur] к balance_list[nxt]: balance_list[nxt] += balance_list[cur]. Рекурсивно вызвать dfs(cur + 1) как dfs(cur) = 1 + dfs(cur + 1). Убрать ранее переданный баланс от cur: balance_list[nxt] -= balance_list[cur] (откат). Повторить с шага 5 и отслеживать минимальное количество операций cost = min(cost, 1 + dfs(cur + 1)), найденных в итерации. Вернуть cost, когда итерация завершена. Вернуть dfs(0). 😎 Решение:
class Solution {
private $creditList;
function minTransfers($transactions) {
$creditMap = [];
foreach ($transactions as $t) {
if (!isset($creditMap[$t[0]])) $creditMap[$t[0]] = 0;
if (!isset($creditMap[$t[1]])) $creditMap[$t[1]] = 0;
$creditMap[$t[0]] += $t[2];
$creditMap[$t[1]] -= $t[2];
}
$this->creditList = [];
foreach ($creditMap as $amount) {
if ($amount != 0) {
$this->creditList[] = $amount;
}
}
$n = count($this->creditList);
return $this->dfs(0, $n);
}
private function dfs($cur, $n) {
while ($cur < $n && $this->creditList[$cur] == 0) {
$cur++;
}
if ($cur == $n) {
return 0;
}
$cost = PHP_INT_MAX;
for ($nxt = $cur + 1; $nxt < $n; $nxt++) {
if ($this->creditList[$nxt] * $this->creditList[$cur] < 0) {
$this->creditList[$nxt] += $this->creditList[$cur];
$cost = min($cost, 1 + $this->dfs($cur + 1, $n));
$this->creditList[$nxt] -= $this->creditList[$cur];
}
}
return $cost;
}
}1 355
Задача: 423. Reconstruct Original Digits from English
Сложность: medium
Дана строка s, содержащая неупорядоченное английское представление цифр от 0 до 9, верните цифры в порядке возрастания.
Пример:
Input: s = "owoztneoer" Output: "012"👨💻 Алгоритм: 1⃣Подсчитайте количество каждого символа в строке s с помощью хэш-таблицы или массива, чтобы определить количество каждого символа. 2⃣Используйте уникальные символы, присутствующие только в одном числе (например, 'z' для 0, 'w' для 2, 'u' для 4, 'x' для 6, 'g' для 8), чтобы определить количество этих цифр в строке. Затем определите количество остальных цифр, вычитая уже найденные цифры. 3⃣Соберите найденные цифры в строку в порядке возрастания и верните результат. 😎 Решение:
class Solution {
function originalDigits($s) {
$count = array_fill(0, 26, 0);
foreach (str_split($s) as $letter) {
$count[ord($letter) - ord('a')]++;
}
$out = array_fill(0, 10, 0);
$out[0] = $count[ord('z') - ord('a')];
$out[2] = $count[ord('w') - ord('a')];
$out[4] = $count[ord('u') - ord('a')];
$out[6] = $count[ord('x') - ord('a')];
$out[8] = $count[ord('g') - ord('a')];
$out[3] = $count[ord('h') - ord('a')] - $out[8];
$out[5] = $count[ord('f') - ord('a')] - $out[4];
$out[7] = $count[ord('s') - ord('a')] - $out[6];
$out[9] = $count[ord('i') - ord('a')] - $out[5] - $out[6] - $out[8];
$out[1] = $count[ord('n') - ord('a')] - $out[7] - 2 * $out[9];
$output = '';
for ($i = 0; $i < 10; $i++) {
for ($j = 0; $j < $out[$i]; $j++) {
$output .= $i;
}
}
return $output;
}
}1 355
Задача: 1512. Number of Good Pairs
Сложность: easy
Дан массив целых чисел nums, верните количество хороших пар.
Пара (i, j) называется хорошей, если nums[i] == nums[j] и i < j.
Пример:
Input: nums = [1,2,3,1,1,3]
Output: 4
Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5) 0-indexed.class Solution {
function numIdenticalPairs($nums) {
$ans = 0;
for ($i = 0; $i < count($nums); $i++) {
for ($j = $i + 1; $j < count($nums); $j++) {
if ($nums[$i] == $nums[$j]) {
$ans++;
}
}
}
return $ans;
}
}1 355
Задача: 101. Symmetric Tree
Сложность: easy
Дан корень бинарного дерева. Проверьте, является ли это дерево зеркальным отражением самого себя (то есть симметричным относительно своего центра).
Пример:
Input: root = [1,2,2,3,4,4,3] Output: true👨💻 Алгоритм: 1⃣Дерево симметрично, если левое поддерево является зеркальным отражением правого поддерева. 2⃣Два дерева являются зеркальным отражением друг друга, если: Их корни имеют одинаковое значение. Правое поддерево каждого дерева является зеркальным отражением левого поддерева другого дерева. 3⃣Это похоже на человека, смотрящего в зеркало. Отражение в зеркале имеет ту же голову, но правая рука отражения соответствует левой руке настоящего человека и наоборот. Вышеописанное объяснение естественным образом превращается в рекурсивную функцию. 😎 Решение:
class TreeNode {
public $val;
public $left;
public $right;
public function __construct($val = 0, $left = null, $right = null) {
$this->val = $val;
$this->left = $left;
$this->right = $right;
}
}
class Solution {
function isSymmetric($root) {
return $this->isMirror($root, $root);
}
function isMirror($t1, $t2) {
if ($t1 === null && $t2 === null) {
return true;
}
if ($t1 === null || $t2 === null) {
return false;
}
return ($t1->val == $t2->val) && $this->isMirror($t1->right, $t2->left) && $this->isMirror($t1->left, $t2->right);
}
}1 355
Задача: 731. My Calendar II
Сложность: medium
Вы создаете программу для использования в качестве календаря. Мы можем добавить новое событие, если его добавление не приведет к тройному бронированию. Тройное бронирование происходит, когда три события имеют некоторое непустое пересечение (т.е, Событие можно представить в виде пары целых чисел start и end, которая представляет собой бронирование на полуоткрытом интервале [start, end), диапазоне вещественных чисел x таких, что start <= x < end. Реализация класса MyCalendarTwo: MyCalendarTwo() Инициализирует объект календаря. boolean book(int start, int end) Возвращает true, если событие может быть успешно добавлено в календарь, не вызывая тройного бронирования. В противном случае возвращается false и событие не добавляется в календарь.
Пример:
Input ["MyCalendarTwo", "book", "book", "book", "book", "book", "book"] [[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]] Output [null, true, true, true, false, true, true]👨💻 Алгоритм: 1⃣Создайте два списка: один для отслеживания всех событий, второй для отслеживания пересечений. подпоследовательностей. 2⃣При добавлении нового события сначала проверьте, не пересекается ли оно с любыми существующими пересечениями. 3⃣Если пересечение не обнаружено, добавьте новое событие и обновите список пересечений при необходимости. 😎 Решение:
class MyCalendarTwo {
private $events;
private $overlaps;
function __construct() {
$this->events = [];
$this->overlaps = [];
}
function book($start, $end) {
foreach ($this->overlaps as $overlap) {
if ($start < $overlap[1] && $end > $overlap[0]) {
return false;
}
}
foreach ($this->events as $event) {
if ($start < $event[1] && $end > $event[0]) {
$this->overlaps[] = [max($start, $event[0]), min($end, $event[1])];
}
}
$this->events[] = [$start, $end];
return true;
}
}1 355
Задача: 965. Univalued Binary Tree
Сложность: medium
Дан список слов, и нам нужно реализовать проверку орфографии, которая преобразует слово запроса в правильное слово.
Для данного слова запроса, проверка орфографии обрабатывает две категории ошибок правописания:
Заглавные буквы: если запрос совпадает со словом в списке слов (без учета регистра), то слово запроса возвращается с таким же регистром, как и в списке слов.
Пример: wordlist = ["yellow"], query = "YellOw": correct = "yellow"
Пример: wordlist = ["Yellow"], query = "yellow": correct = "Yellow"
Пример: wordlist = ["yellow"], query = "yellow": correct = "yellow"
Ошибки гласных: если после замены гласных ('a', 'e', 'i', 'o', 'u') в слове запроса на любую гласную по отдельности оно совпадает со словом в списке слов (без учета регистра), то слово запроса возвращается с таким же регистром, как и совпадающее слово в списке слов.
Пример: wordlist = ["YellOw"], query = "yollow": correct = "YellOw"
Пример: wordlist = ["YellOw"], query = "yeellow": correct = "" (нет совпадения)
Пример: wordlist = ["YellOw"], query = "yllw": correct = "" (нет совпадения)
Кроме того, проверка орфографии работает по следующим правилам приоритета:
Когда запрос точно совпадает со словом в списке слов (с учетом регистра), вы должны вернуть это же слово.
Когда запрос совпадает со словом за исключением регистра, вы должны вернуть первое такое совпадение в списке слов.
Когда запрос совпадает со словом за исключением ошибок гласных, вы должны вернуть первое такое совпадение в списке слов.
Если запрос не имеет совпадений в списке слов, вы должны вернуть пустую строку.
Дан массив запросов, верните список слов answer, где answer[i] — правильное слово для query = queries[i].
Пример:
Input: wordlist = ["KiTe","kite","hare","Hare"], queries = ["kite","Kite","KiTe","Hare","HARE","Hear","hear","keti","keet","keto"] Output: ["kite","KiTe","KiTe","Hare","hare","","","KiTe","","KiTe"]👨💻 Алгоритм: 1⃣Используйте множество для хранения слов из списка, чтобы проверять точные совпадения. 2⃣Используйте хэш-таблицу для хранения слов в нижнем регистре и соответствующих слов из списка для проверки совпадений без учета регистра. 3⃣Используйте хэш-таблицу для хранения слов в нижнем регистре с замененными гласными символами и соответствующих слов из списка для проверки совпадений с ошибками гласных. 😎 Решение:
class Solution {
private $wordsPerfect;
private $wordsCap;
private $wordsVow;
/**
* @param String[] $wordlist
* @param String[] $queries
* @return String[]
*/
function spellchecker($wordlist, $queries) {
$this->wordsPerfect = array_flip($wordlist);
$this->wordsCap = [];
$this->wordsVow = [];
foreach ($wordlist as $word) {
$wordlow = strtolower($word);
if (!isset($this->wordsCap[$wordlow])) {
$this->wordsCap[$wordlow] = $word;
}
$wordlowDV = $this->devowel($wordlow);
if (!isset($this->wordsVow[$wordlowDV])) {
$this->wordsVow[$wordlowDV] = $word;
}
}
$result = [];
foreach ($queries as $query) {
$result[] = $this->solve($query);
}
return $result;
}
private function solve($query) {
if (isset($this->wordsPerfect[$query])) {
return $query;
}
$queryL = strtolower($query);
if (isset($this->wordsCap[$queryL])) {
return $this->wordsCap[$queryL];
}
$queryLV = $this->devowel($queryL);
if (isset($this->wordsVow[$queryLV])) {
return $this->wordsVow[$queryLV];
}
return "";
}
private function devowel($word) {
return preg_replace('/[aeiou]/', '*', $word);
}
}