PHP | LeetCode
前往频道在 Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
显示更多
网络:1 354
订阅者
-124 小时
-37 天
-830 天
帖子存档
1 354
Задача: 34. Find First and Last Position of Element in Sorted Array #medium
Условие:
Учитывая массив целых чисел, отсортированных в порядке неубывания, найдите начальную и конечную позицию заданного целевого значения. Если цель не найдена в массиве, верните [-1, -1]. Вы должны написать алгоритм со сложностью выполнения O(log n).Решение:
class Solution {
/**
* @param Integer[] $nums
* @param Integer $target
* @return Integer[]
*/
function searchRange($nums, $target) {
$result = [];
foreach ($nums as $key => $value) {
if ($value === $target) {
$result[] = $key;
}
}
if(empty($result)){
$result = [-1,-1];
return $result;
}else{
return [min($result), max($result)];
}
}
}1 354
Задача: 33. Search in Rotated Sorted Array #medium
Условие:
Существует целочисленный массив nums, отсортированный по возрастанию (с разными значениями). Перед передачей в вашу функцию nums, возможно, поворачивается с неизвестным индексом поворота k (1 <= k < nums.length), так что результирующий массив имеет вид [nums[k], nums[k+1],... , nums[n-1], nums[0], nums[1], ..., nums[k-1]] (с индексом 0). Например, [0,1,2,4,5,6,7] можно повернуть с опорным индексом 3 и превратить в [4,5,6,7,0,1,2]. Учитывая массив nums после возможного поворота и целочисленную цель, верните индекс цели, если он находится в nums, или -1, если он не в nums. Вы должны написать алгоритм со сложностью выполнения O(log n).Решение:
class Solution {
/**
* @param Integer[] $nums
* @param Integer $target
* @return Integer
*/
function search($nums, $target) {
for($i=0;$i<count($nums);$i++){
if($nums[$i]==$target){
return $i;
}
}
return -1;
}
}1 354
Задача: 32. Longest Valid Parentheses #hard
Условие:
Учитывая строку, содержащую только символы «(» и «)», верните длину самых длинных допустимых (правильно сформированных) круглых скобок. подстрокаРешение:
class Solution {
/**
* @param String $s
* @return Integer
*/
function longestValidParentheses($s) {
$s2 = ')'.$s;
$n = strlen($s2);
$dp = array_fill(0, $n, 0);
for ($i = 1; $i < $n; $i++) {
if ($s2[$i] === ')' && $s2[$i-$dp[$i-1]-1] === '(') {
$dp[$i] = $dp[$i-1] + $dp[$i-$dp[$i-1]-2] + 2;
}
}
return max($dp);
}
}Solution с методом longestValidParentheses, который находит длину самой длинной подстроки правильных скобочных последовательностей ("(" и ")") в строке $s. Вот как работает этот метод:
1. Создается дополнительная строка $s2, в которую вставляется символ ")" в начало строки $s.
2. Вычисляется длина строки $s2 и создается массив $dp длиной $n, заполненный нулями. Этот массив будет хранить длину самой длинной подстроки правильных скобочных последовательностей, заканчивающихся в позиции $i.
3. Запускается цикл от второго элемента до конца строки $s2.
4. На каждой итерации проверяется, если текущий символ - ")" и символ слева от него (на расстоянии $dp[$i-1] + 1) равен "(". То есть, проверяется, если имеется закрывающая скобка ")" и соответствующая ей открывающая скобка "(".
5. Если условие выполняется, то длина текущей правильной последовательности увеличивается на сумму длины предыдущей последовательности ($dp[$i-1]), длины последовательности перед предыдущей открывающей скобкой ($dp[$i-dp[$i-1]-2]) и на 2 (для текущей закрывающей скобки и открывающей скобки).
6. На выходе возвращается максимальное значение из массива $dp, которое и представляет длину самой длинной подстроки правильных скобочных последовательностей в строке $s.
Этот алгоритм использует динамическое программирование для эффективного нахождения длины самой длинной подстроки правильных скобочных последовательностей открытых и закрывающих скобок в строке.1 354
Пояснение:
Данный код представляет класс `Solution` с методом `nextPermutation`, который выполняет операцию нахождения следующей перестановки целочисленного массива `$nums`. Основная идея алгоритма поиска следующей перестановки основана на обмене элементов массива в соответствии с определенными правилами. Давайте рассмотрим основные шаги и методы этого алгоритма:
1. Метод `nextPermutation`:
- Проверяется размер массива `$nums`. Если размер равен 1, то возвращается, так как перестановка невозможна.
- Если размер равен 2, происходит обмен двух элементов с помощью метода `swap`.
- Переменной `$n` присваивается размер массива.
- Запускается цикл по всем элементам массива, начиная с предпоследнего.
- Для каждого элемента проверяется, если он находится в возрастающем порядке справа, тогда его место меняется с предпоследним элементом.
- Если элемент не находится в возрастающем порядке справа, то происходит поиск следующего максимального элемента после текущего и его обмен местами с текущим.
- Массив с элементами начиная с текущего индекса сортируется по возрастанию.
- Если ни одно из условий не выполняется, то весь массив сортируется по возрастанию.
- Метод `swap` производит обмен элементов массива в указанных позициях.
2. Дополнительные методы:
- `swap`: Обмен значений двух элементов массива.
- `checkAsc`: Проверка, находятся ли элементы массива с указанного индекса до конца в возрастающем порядке.
- `getNextMax`: Поиск следующего максимального элемента после указанного индекса и обмен его местами с текущим.
- `arrangeAsc`: Сортировка оставшихся элементов массива по возрастанию.
Алгоритм работы метода `nextPermutation` основан на правильной перестановке элементов массива с учетом заданных условий. Он находит следующую перестановку в лексикографическом порядке и обеспечивает правильное состояние массива после выполнения операции перестановки.
1 354
Задача: 31. Next Permutation #medium
Условие:
Перестановка массива целых чисел — это расположение его членов в последовательность или линейный порядок. Например, для arr = [1,2,3] следующие перестановки arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1]. Следующая перестановка массива целых чисел — это следующая лексикографически большая перестановка его целого числа. Более формально, если все перестановки массива отсортированы в одном контейнере в соответствии с их лексикографическим порядком, то следующей перестановкой этого массива будет перестановка, следующая за ней в отсортированном контейнере. Если такое расположение невозможно, массив необходимо переупорядочить в наименьшем возможном порядке (т. е. отсортировать по возрастанию). Например, следующая перестановка arr = [1,2,3] — это [1,3,2]. Аналогично, следующая перестановка arr = [2,3,1] — это [3,1,2]. А следующая перестановка arr = [3,2,1] — это [1,2,3], потому что [3,2,1] не имеет более крупной лексикографической перестановки. Учитывая массив целых чисел nums, найдите следующую перестановку чисел. Замена должна быть на месте и использовать только постоянную дополнительную память.Решение:
class Solution {
/**
* @param Integer[] $nums
* @return NULL
*/
function nextPermutation(&$nums) {
if(sizeof($nums) == 1) return;
if(sizeof($nums) == 2) return $this->swap($nums, 0, 1);
$n = sizeof($nums);
for($i= $n-2; $i>0; $i--){
if( $this->checkAsc($nums, $i)){
$this->swap($nums, $n-1, $n-2);
return;
}else{
//get the next max number next to $i and place it $i pos
if($this->getNextMax($nums, $i-1)){
// rearrange in asc order after $i
$this->arrangeAsc($nums, $i);
return;
}
}
}
sort($nums);
return;
}
function swap(&$nums, $i, $j){
$temp = $nums[$i];
$nums[$i] = $nums[$j];
$nums[$j] = $temp;
}
function checkAsc(&$nums, $i){
$n = sizeof($nums);
for($j=$n-1; $j>$i; $j--){
if($nums[$j]<$nums[$j-1]|| $nums[$j] == $nums[$j-1])
return false;
}
return true;
}
//get the next max after i position and swap.
function getNextMax(&$nums, $i){
$min = $i+1;
for($j=$i+1; $j<=sizeof($nums)-1;$j++){
if($nums[$j]<$nums[$min] && $nums[$j]>$nums[$i]){
$min = $j;
}
}
echo "next min is " . $nums[$min] ."<br />";
if($nums[$min] > $nums[$i]){
$this->swap($nums, $i, $min);
return true;
}
return false;
}
//arrange the numbers after $i.
function arrangeAsc(&$nums, $i){
$n = sizeof($nums);
for($j= $i;$j<=$n-2;$j++){
for($k=$j+1; $k<=$n-1;$k++){
if($nums[$j]>$nums[$k]) $this->swap($nums, $j, $k);
}
}
return;
}
}1 354
Задача: 30. Substring with Concatenation of All Words #hard
Условие:
Вам дана строка s и массив строк-слов. Все строки слов имеют одинаковую длину. Объединенная строка — это строка, которая в точности содержит все строки любой перестановки объединенных слов. Например, если слова = ["ab", "cd", "ef"], то "abcdef", "abefcd", "cdabef", "cdefab", "efabcd" и "efcdab" являются объединенными строками. «acdbef» не является объединенной строкой, поскольку не является объединением какой-либо перестановки слов. Возвращает массив начальных индексов всех объединенных подстрок в s. Вы можете вернуть ответ в любом порядке.Решение:
$result = []; if (count($words) < 1) return $result; $strLength = strlen($s); $wordLength = strlen($words[0]); $subLength = $wordLength * count($words);
sort($words); for ($i = 0; $i <= ($strLength-$subLength); $i++) {
$strToArr = str_split(substr($s, $i, $subLength), $wordLength); sort($strToArr);
if (count($words) === count($strToArr)
&& empty(array_diff_assoc($strToArr, $words))
){
$result[] = $i;
}
}
return $result;
}
'''1 354
⚡️В сети начали находить курсы и книги известных онлайн школ в открытом доступе
Вот отсортированная база с тонной материала(постепенно пополняется):
🔗 БАЗА (3385 видео):
(343 видео, 87 книги) — Java
(176 видео, 32 книги) — Git
(293 видео, 63 книги) — C#
(352 видео, 89 книги) — С++
(167 видео, 53 книги) — PHP
(227 видео, 83 книги) — SQL
(163 видео, 29 книги) — Linux
(363 видео, 122 книги) — Python
(415 видео, 168 книги) — Frontend
(143 видео, 33 книги) — Flask
(167 видео, 43 книги) — Django
(197 видео, 49 книги) — Разработка ботов
(137 видео, 93 книги) — Data Science
(113 видео, 82 книги) — GameDev
(129 видео, 73 книги) — QA
Скачивать ничего не нужно — все выложили в Telegram и на YouTube с доступом по ссылке
1 354
Задача: 29. Divide Two Integers #medium
Условие:
Учитывая два целых числа: делимое и делитель, разделите два целых числа, не используя операторы умножения, деления и модификатора. Целочисленное деление должно сокращаться до нуля, что означает потерю дробной части. Например, 8,345 будет сокращено до 8, а -2,7335 будет сокращено до -2. Возвращает частное после деления делимого на делитель. Примечание. Предположим, мы имеем дело со средой, которая может хранить целые числа только в пределах 32-битного целого диапазона со знаком: [−2^31, 2^31 − 1]. В этой задаче, если частное строго больше 2^31 - 1, верните 2^31 - 1, а если частное строго меньше -2^31, верните -2^31.Решение:
class Solution {
/**
* @param Integer $dividend
* @param Integer $divisor
* @return Integer
*/
function divide($dividend, $divisor) {
$result = $dividend / $divisor;
if(pow(2,31)-1 < $result){
$result = pow(2,31)-1;
}else if(pow(-2,31) > $result){
$result = pow(-2,31);
}
return (int)$result;
}
}1 354
Задача: 28. Find the Index of the First Occurrence in a String #easy
Условие:
Учитывая две строки, игла и стог сена, верните индекс первого вхождения иглы в стоге сена или -1, если игла не является частью стога сена.Решение:
class Solution {
/**
* @param String $haystack
* @param String $needle
* @return Integer
*/
function strStr($haystack, $needle) {
$needleLen = strlen($needle);
$haylen = strlen($haystack);
$start = 0;
while (true) {
$substring = substr($haystack, $start, $needleLen);
if ($substring == $needle) {
return $start;
}
if ($start == $haylen-1) {
return -1;
}
$start++;
}
return -1;
}
}strStr, который принимает две строки: $haystack (основная строка) и $needle (подстрока). Метод ищет первое вхождение подстроки $needle в строку $haystack и возвращает позицию начала вхождения в строке $haystack. Если подстрока не найдена в строке, то возвращается значение -1.
Алгоритм поиска реализован при помощи цикла while, который будет выполняться до тех пор, пока не будет найдено вхождение или закончится строка $haystack. На каждой итерации цикла из строки $haystack извлекается подстрока длины $needleLen начиная с позиции $start с помощью функции substr. Затем проверяется, равна ли эта подстрока подстроке $needle. Если равна, то метод возвращает текущую позицию $start в строке $haystack.
Если подстрока не равна и достигнут конец строки $haystack, метод возвращает -1, что означает отсутствие подстроки в строке. В конце метод также возвращает -1, в случае, если произошло некорректное завершение поиска.
Этот метод реализует простой подход к реализации поиска подстроки в строке, но следует отметить, что для более сложных и эффективных алгоритмов поиска, таких как алгоритм Кнута-Морриса-Пратта или алгоритм Бойера-Мура, требуется более сложная реализация.1 354
Задача: 27. Remove Element #easy
Условие:
Учитывая целочисленный массив nums и целочисленное значение, удалите все вхождения val в nums на месте. Порядок элементов может быть изменен. Затем верните количество элементов в виде чисел, которые не равны val. Учитывайте количество элементов в nums, которые не равны val be k. Чтобы вас приняли, вам необходимо сделать следующее: Измените массив nums так, чтобы первые k элементов nums содержали элементы, не равные val. Остальные элементы nums не важны, как и размер nums. Вернуть К.Решение:
/**
* @param Integer[] $nums * @param Integer $val
* @return Integer
*/
function removeElement(&$a, $val) {
$k =0; for ($i =0 ; $i < count($a);$i++){ if($a[$i] != $val){
$a[$k] = $a[$i];
$k++; } } return $k;
} removeElement, которая принимает массив $a по ссылке и значение $val для удаления из этого массива. Функция удаляет все вхождения значения $val из массива и возвращает новую длину массива после удаления элементов.
Внутри функции определяется переменная $k, которая инициализируется с 0. Затем запускается цикл for, который итерирует по всем элементам массива $a. Внутри цикла проверяется условие: если текущий элемент $a[$i] не равен значению $val, то текущий элемент сохраняется на позицию $k в массиве $a. Затем значение переменной $k увеличивается на 1 с помощью оператора инкремента $k++.
Таким образом, все элементы массива, не равные значению $val, остаются на месте, а все элементы, равные $val, переносятся на конец массива и заменяются уникальными элементами. После завершения цикла функция возвращает значение $k, представляющее новую длину массива без элементов со значением $val.1 354
Задача: 26. Remove Duplicates from Sorted Array #easy
Условие:
Учитывая целочисленный массив чисел, отсортированный в неубывающем порядке, удалите дубликаты на месте так, чтобы каждый уникальный элемент появлялся только один раз. Относительный порядок элементов должен оставаться неизменным. Затем верните количество уникальных элементов в числах. Считайте, что количество уникальных элементов чисел равно k. Чтобы вас приняли, вам нужно сделать следующее: Измените массив nums так, чтобы первые k элементов nums содержали уникальные элементы в том порядке, в котором они присутствовали в nums изначально. Остальные элементы nums не важны, как и размер nums. Вернуть К.Решение:
class Solution {
function removeDuplicates(&$nums) { $index = 1;
for ($i = 1; $i < count($nums); $i++) {
if($nums[$i] !== $nums[$i-1]){
$nums[$index++] = $nums[$i];
}
}
return $index;
}
}removeDuplicates, которая принимает массив чисел по ссылке и удаляет дубликаты из этого массива. Функция возвращает новую длину массива после удаления дубликатов и модифицирует сам массив, оставляя только уникальные элементы.
Внутри функции задается индекс $index, который начинается с 1. Затем запускается цикл for, проходящий по всем элементам массива, начиная со второго элемента ($i = 1). Внутри цикла проверяется условие: если текущий элемент $nums[$i] не равен предыдущему элементу $nums[$i-1], то текущий элемент добавляется в массив на позицию $index с помощью оператора постфиксного инкремента $index++. Это позволяет удалять дубликаты, так как только уникальные элементы будут добавлены на новые позиции.
После завершения цикла функция возвращает значение $index, которое представляет новую длину массива без дубликатов. Таким образом, в массиве $nums остаются только уникальные элементы, а его длина изменена на количество уникальных элементов.1 354
Задача: 25. Reverse Nodes in k-Group #hard
Условие:
Учитывая заголовок связанного списка, поменяйте местами узлы списка k за раз и верните измененный список. k — целое положительное число, меньшее или равное длине связанного списка. Если количество узлов не кратно k, то пропущенные узлы в конечном итоге должны остаться такими, какие они есть. Вы не можете изменять значения в узлах списка, можно изменять только сами узлы.Решение:
/**
* Definition for a singly-linked list.
* class ListNode {
* public $val = 0;
* public $next = null;
* function __construct($val = 0, $next = null) {
* $this->val = $val;
* $this->next = $next;
* }
* }
*/
class Solution {
public function reverseKGroup($head, $k) {
if ($head === null || $k === 1) {
return $head;
}
$dummy = new ListNode(0);
$dummy->next = $head;
$groupPrev = $dummy;
while (true) {
$kth = $this->getKthNode($groupPrev, $k);
if ($kth === null) {
break;
}
$groupNext = $kth->next;
// Reverse group
$prev = $groupNext;
$curr = $groupPrev->next;
while ($curr !== $groupNext) {
$tmp = $curr->next;
$curr->next = $prev;
$prev = $curr;
$curr = $tmp;
}
$tmp = $groupPrev->next;
$groupPrev->next = $kth;
$groupPrev = $tmp;
}
return $dummy->next;
}
private function getKthNode($curr, $k) {
while ($curr !== null && $k > 0) {
$curr = $curr->next;
$k--;
}
return $curr;
}
}
// Helper function to convert array to linked list
function arrayToList($arr) {
$dummy = new ListNode();
$current = $dummy;
foreach ($arr as $val) {
$current->next = new ListNode($val);
$current = $current->next;
}
return $dummy->next;
}
// Helper function to convert linked list to array
function listToArray($head) {
$arr = [];
while ($head !== null) {
$arr[] = $head->val;
$head = $head->next;
}
return $arr;
}1 354
Задача: 24. Swap Nodes in Pairs #medium
Условие:
Учитывая связанный список, поменяйте местами каждые два соседних узла и верните его голову. Вы должны решить проблему, не изменяя значения в узлах списка (т. е. изменять можно только сами узлы).Решение:
/**
* Definition for a singly-linked list.
* class ListNode {
* public $val = 0;
* public $next = null;
* function __construct($val = 0, $next = null) {
* $this->val = $val;
* $this->next = $next;
* }
* }
*/
class Solution {
/**
* @param ListNode $head
* @return ListNode
*/
function swapPairs($head) {
if($head == null) {
return [];
}
$iteration = 1;
$current = $head;
while($current->next != null) {
if($iteration % 2 != 0) {
$currentNodeValue = $current->val;
$nextNodeValue = $current->next->val;
$current->next->val = $currentNodeValue;
$current->val = $nextNodeValue;
}
$current = $current->next;
$iteration++;
}
return $head;
}
}teration равной 1. Эта переменная используется для отслеживания текущей итерации.
2. Перебирает узлы в списке, используя переменную current.
3. На каждой итерации, если iteration нечетно (т. е. 1, 3, 5...), то выполняется обмен значений между текущим узлом и следующим узлом:
- currentNodeValue получает значение текущего узла. - nextNodeValue получает значение следующего узла.
- Значение следующего узла обновляется до currentNodeValue. - Значение текущего узла обновляется до nextNodeValue.
4. Перемещает указатель current на следующий узел.
5. Увеличивает iteration на 1.
6. После перебора всех узлов в списке функция возвращает измененный список head.1 354
Задача: 22. Generate Parentheses #medium
Условие:
Учитывая n пар круглых скобок, напишите функцию, которая генерирует все комбинации правильных круглых скобок.Решение:
class Solution {
private array $answer = [];
private string $current = '';
/**
* @param Integer $n
* @return String[]
*/
function generateParenthesis($n) {
$this->generateParentheses($n, 0);
return $this->answer;
}
function generateParentheses($toOpen, $toClose) {
if ($toOpen == 0 && $toClose == 0) {
$this->answer[] = $this->current;
return;
}
if ($toOpen > 0) {
$this->current .= '(';
$this->generateParentheses($toOpen - 1, $toClose + 1);
$this->current = substr($this->current, 0, -1);
}
if ($toClose > 0) {
$this->current .= ')';
$this->generateParentheses($toOpen, $toClose - 1);
$this->current = substr($this->current, 0, -1);
}
}
}1 354
Задача: №21. Merge Two Sorted Lists #easy
Условие:
Вам даны заголовки двух отсортированных связанных списков list1 и list2. Объедините два списка в один отсортированный список. Список должен быть составлен путем сращивания узлов первых двух списков. Возвращает заголовок объединенного связанного списка.Решение:
/
* Definition for a singly-linked list.
* class ListNode {
* public $val = 0;
* public $next = null;
* function __construct($val = 0, $next = null) {
* $this->val = $val;
* $this->next = $next;
* }
* }
*/
class Solution {
/
* @param ListNode $list1
* @param ListNode $list2
* @return ListNode
*/
function mergeTwoLists($list1, $list2) {
$newList = new ListNode();
$current = $newList;
while($list1 || $list2) {
if ($list1 && !$list2) {
$current->next = new ListNode($list1->val);
$current = $current->next;
$list1 = $list1->next;
} elseif (!$list1 && $list2) {
$current->next = new ListNode($list2->val);
$current = $current->next;
$list2 = $list2->next;
} else {
if ($list1->val === $list2->val) {
$current->next = new ListNode($list1->val);
$current = $current->next;
$current->next = new ListNode($list2->val);
$current = $current->next;
$list1 = $list1->next;
$list2 = $list2->next;
} elseif ($list1->val < $list2->val) {
$current->next = new ListNode($list1->val);
$current = $current->next;
$list1 = $list1->next;
} else {
$current->next = new ListNode($list2->val);
$current = $current->next;
$list2 = $list2->next;
}
}
}
return $newList->next;
}
}1 354
Задача: №20. Valid Parentheses #easy
Условие:
Учитывая строку s, содержащую только символы '(', ')', '{', '}', '[' и ']', определите, является ли входная строка допустимой. Входная строка действительна, если: Открытые скобки должны закрываться скобками того же типа. Открытые скобки должны закрываться в правильном порядке.Каждой закрывающей скобке соответствует открытая скобка того же типа.Решение:
class Solution
{
/**
* @param String $s
* @return Boolean
*/
function isValid(string $s): bool {
$sLength = strlen($s);
if ($sLength % 2 !== 0) return false;
$bracketSet = ['(' => ')', '[' => ']', '{' => '}'];
$bracketStack = [];
for ($i = 0; $i < $sLength; $i++) {
if (array_key_exists($s[$i], $bracketSet)) {
$bracketStack[] = $bracketSet[$s[$i]];
} elseif (array_pop($bracketStack) !== $s[$i]) {
return false;
}
}
return count($bracketStack) === 0;
}
}1 354
Задача: №19. Remove Nth Node From End of List #medium
Условие:
Учитывая заголовок связанного списка, удалите n-й узел из конца списка и верните его заголовок.Решение:
class Solution {
/**
* @param ListNode $head
* @param Integer $n
* @return ListNode
*/
function removeNthFromEnd($head, $n) {
// Paso #1
$tamaño = 0;
$aux = $head;
while ($aux !== null) {
$aux = $aux->next;
$tamaño++;
}
// Paso #2
if ($tamaño == 1) {
return null;
}
if ($tamaño == $n) {
return $head->next;
}
// Paso #3
$aux = $head;
for ($i = 0; $i < $tamaño - $n - 1; $i++) {
$aux = $aux->next;
}
// Paso #4
$aux->next = $aux->next->next;
// Paso #5
return $head;
}
}1 354
Задача: №18. 4Sum #medium
Условие:
Учитывая массив nums из n целых чисел, верните массив всех уникальных четверок [nums[a], nums[b], nums[c], nums[d]] таких, что: 0 <= a, b, c, d < na, b, c и d различны. nums[a] + nums[b] + nums[c] + nums[d] == цельВы можете вернуть ответ в любом порядке.Решение:
class Solution {
/**
* @param Integer[] $nums
* @param Integer $target
* @return Integer[][]
*/
function fourSum($nums, $target) {
sort($nums);
return $this->kSum($nums, $target, 4);
}
function kSum($nums, $target, $k)
{
$res = [];
if (!count($nums)) {
return $res;
}
$averageValue = $target / $k;
if ($averageValue < $nums[0] || $nums[count($nums)-1] < $averageValue) {
return $res;
}
if ($k == 2) {
return $this->twoSum($nums, $target);
}
for ($i = 0; $i < count($nums); $i++) {
if ($i == 0 || $nums[$i - 1] != $nums[$i]) {
$kSum = $this->kSum(array_slice($nums, $i+1), $target - $nums[$i], $k - 1);
foreach ($kSum as $item) {
$res[] = array_merge([$nums[$i]], $item);
}
}
}
return $res;
}
function twoSum($nums, $target)
{
$res = [];
$lo = 0;
$hi = count($nums) - 1;
while ($lo < $hi) {
$currSum = $nums[$lo] + $nums[$hi];
if ($currSum < $target || ( $lo > 0 && $nums[$lo] == $nums[$lo - 1])) {
$lo++;
} elseif ($currSum > $target || ($hi < count($nums) - 1 && $nums[$hi] == $nums[$hi + 1])) {
$hi--;
} else {
$res[] = [$nums[$lo], $nums[$hi]];
$lo++;
$hi--;
}
}
return $res;
}
}1 354
Задача: №17. Letter Combinations of a Phone Number #medium
Условие:
Учитывая строку, содержащую цифры от 2 до 9 включительно, верните все возможные комбинации букв, которые может представлять число. Верните ответ в любом порядке. Соответствие цифр буквам (как на кнопках телефона) приведено ниже. Обратите внимание, что 1 не соответствует никаким буквам.Решение:
class Solution {
public $result = [];
/**
* @param String $digits
* @return String[]
*/
function letterCombinations($digits) {
if(strlen($digits) == 0) {
return [];
}
$layouts = [
2 => range('a', 'c'),
3 => range('d', 'f'),
4 => range('g', 'i'),
5 => range('j', 'l'),
6 => range('m', 'o'),
7 => range('p', 's'),
8 => range('t', 'v'),
9 => range('w', 'z'),
];
return $this->recursive(0, $digits, $layouts);
}
function recursive ($index, $chars, $layouts, $combine = '') {
foreach($layouts[$chars[$index]] as $currentLayout) {
if($layouts[$chars[$index + 1]]) {
$this->recursive($index + 1, $chars, $layouts, $combine . $currentLayout);
} else {
$this->result[] = $combine . $currentLayout;
}
}
return $this->result;
}
}1 354
Задача: №16. 3Sum Closest #medium
Условие:
Учитывая целочисленный массив nums длины n и целочисленную цель, найдите три целых числа в nums, сумма которых наиболее близка к цели. Возвращает сумму трех целых чисел. Вы можете предположить, что каждый вход будет иметь ровно одно решение.Решение:
class Solution {
function threeSumClosest($nums, $target) {
$fIsCloserS = function ($base, $f, $s) {
return abs($base - $f) < abs($base - $s);
};
sort($nums);
$res = $middle = INF;
$key_left = 0;
$key_right = array_key_last($nums);
while ($key_left + 1 < $key_right) {
$needle = $target - $nums[$key_right] - $nums[$key_left];
$bin_key_left = $key_left + 1;
$bin_key_right = $key_right - 1;
while ($bin_key_left <= $bin_key_right) {
$bin_key_middle = (int)round(($bin_key_left + $bin_key_right) / 2);
if ($fIsCloserS($needle, $nums[$bin_key_middle], $middle)) {
$middle = $nums[$bin_key_middle];
}
if (($needle - $nums[$bin_key_middle]) < 0) {
$bin_key_right = $bin_key_middle - 1;
}
else $bin_key_left = $bin_key_middle + 1;
}
$sum = $nums[$key_right] + $nums[$key_left] + $middle;
if ($fIsCloserS($target, $sum, $res)) {
if ($sum === $target) {
return $sum;
}
$res = $sum;
}
$new_left = $nums[$key_left + 1];
$new_right = $nums[$key_right - 1];
if ($fIsCloserS($needle, $new_left, $new_right)
|| ($new_left === $new_right && $new_left === $nums[$key_left])
) $key_right--;
else $key_left++;
}
return $res;
}
} 