PHP | LeetCode
Відкрити в Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @sendme_ads
Показати більше
1 315
Підписники
-224 години
-117 днів
-2730 днів
Архів дописів
1 315
Задача: 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 315
Задача: №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 315
Задача: №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 315
Задача: №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 315
Задача: №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 315
Задача: №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 315
Задача: №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;
}
} 