Задача: №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;  
    }  
} 

Пояснение:

1. Сначала мы сортируем массив $nums в порядке возрастания.2. Затем мы используем две указателя - $key_left и $key_right, которые указывают на начало и конец массива соответственно.
3. Для каждой пары чисел $nums[$key_left] и $nums[$key_right] мы ищем третье число, которое делает сумму этих трех чисел максимально близкой к $target. Для этого мы используем двоичный поиск в оставшейся части массива.4. Во время двоичного поиска мы отслеживаем наиболее близкое к $target значение суммы трех чисел и обновляем $res соответственно.
5. После того, как мы нашли наиболее близкую сумму, мы двигаем указатели $key_left и $key_right к центру, чтобы найти следующую пару чисел.
Ключевые моменты:
1. Использование функции $fIsCloserS для определения, какая сумма ближе к $target.2. Применение двоичного поиска для поиска третьего числа, которое делает сумму наиболее близкой к $target.
3. Обновление $res (наиболее близкой суммы) после каждой итерации.4. Перемещение указателей $key_left и $key_right к центру, чтобы найти следующую пару чисел.
Общая временная сложность этого решения - O(n^2 * log n), где n - длина массива $nums. Это связано с сортировкой массива (O(n * log n)) и двумя вложенными циклами, каждый из которых выполняет двоичный поиск (O(log n)).

Задача: №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. Проверяем, является ли входная строка пустой. Если да, возвращаем пустой массив.
2. Создаем ассоциативный массив $layouts, в котором каждой цифре соответствует массив букв, которые можно набрать на телефонной клавиатуре.
3. Вызываем рекурсивную функцию recursive(), передавая ей следующие аргументы: - $index - индекс текущей цифры в входной строке;
- $chars - входная строка, состоящая из цифр; - $layouts - ассоциативный массив с соответствием цифр и букв;
- $combine - строка, представляющая текущую комбинацию букв.
4. В рекурсивной функции recursive(): - Перебираем все буквы, соответствующие текущей цифре в $layouts.
- Если есть следующая цифра в $chars, то рекурсивно вызываем recursive(), передавая новый индекс, текущую комбинацию букв и обновленные $chars и $layouts. - Если следующей цифры нет, то добавляем текущую комбинацию букв в результирующий массив $result.
- Возвращаем $result.
5. Возвращаем конечный результат из основной функции letterCombinations().
Временная сложность этого решения - O(3^N * 4^M), где N - количество цифр, которые имеют 3 соответствующие буквы, а M - количество цифр, которые имеют 4 соответствующие буквы. Это связано с тем, что для каждой цифры мы перебираем все возможные комбинации букв.
Пространственная сложность - O(3^N * 4^M), поскольку мы храним все возможные комбинации букв в результирующем массиве.

Задача: №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. Сортировка входного массива: Сначала мы сортируем входной массив $nums в порядке возрастания. Это необходимо для эффективного поиска решений.
2. Реализация функции kSum: Эта функция рекурсивно находит все уникальные наборы из $k чисел, сумма которых равна $target. Она использует следующую логику: - Если $k == 2, вызываем функцию twoSum для поиска всех пар чисел, сумма которых равна $target.
- Если $k > 2, то перебираем все числа в $nums, пропуская дубликаты, и рекурсивно вызываем kSum для оставшейся части массива с $k-1 и $target - $nums[$i].
3. Реализация функции twoSum: Эта функция используется внутри kSum для поиска всех уникальных пар чисел, сумма которых равна $target. Она использует два указателя: $lo и $hi, указывающие на начало и конец отсортированного массива. Эти указатели двигаются навстречу друг другу, пока не найдут все решения.
4. Возвращение результата: Основная функция fourSum сначала сортирует входной массив, затем вызывает kSum с $k=4 и $target, и возвращает результат.
Временная сложность этого решения - O(n^(k-1)), где n - длина входного массива $nums, и k - количество чисел, которые нужно найти. Это связано с тем, что для каждого числа в массиве мы рекурсивно вызываем kSum с $k-1.
Пространственная сложность - O(n^(k-1)), поскольку мы сохраняем все уникальные наборы чисел в результирующем массиве.

Задача: №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. Определение размера связного списка: - Создаем вспомогательную переменную $aux и присваиваем ей значение $head (начало списка).
- Пока $aux не равен null, увеличиваем счетчик $tamaño и перемещаем $aux на следующий узел. - Таким образом, мы определяем количество узлов в списке и сохраняем его в $tamaño.
2. Обработка граничных случаев:
- Если размер списка равен 1, то мы возвращаем null, так как удаление единственного узла оставит список пустым. - Если $n равно размеру списка, то мы возвращаем $head->next, так как мы удаляем первый узел.
3. Перемещение по списку до нужного узла:
- Создаем вспомогательную переменную $aux и снова присваиваем ей значение $head. - Используем цикл, чтобы переместить $aux на $tamaño - $n - 1 узлов. Это позволит нам найти узел, предшествующий узлу, который нужно удалить.
4. Удаление узла:
- После того, как мы нашли нужный узел, мы просто обновляем ссылку $aux->next, чтобы пропустить узел, который нужно удалить.
5. Возвращение обновленного списка: - Наконец, мы возвращаем $head - корень обновленного связного списка.
Временная сложность этого решения - O(n), где n - количество узлов в списке. Это связано с тем, что мы проходим по списку дважды: один раз, чтобы определить его размер, и второй раз, чтобы найти узел, предшествующий узлу, который нужно удалить.
Пространственная сложность - O(1), поскольку мы используем только несколько вспомогательных переменных и не создаем дополнительные структуры данных.

Задача: №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. Длина строки: - Сначала мы проверяем длину входной строки $s. Если длина нечетная, то строка не может быть валидной, так как каждой открывающей скобке должна соответствовать закрывающая скобка. Поэтому возвращаем false.
2. Создание словаря соответствия скобок:
- Создаем ассоциативный массив $bracketSet, в котором хранятся пары открывающих и закрывающих скобок.
3. Обход строки: - Создаем стек $bracketStack, в котором будем хранить ожидаемые закрывающие скобки.
- Проходим по каждому символу в строке $s: - Если символ является открывающей скобкой, то добавляем соответствующую ей закрывающую скобку в стек.
- Если символ является закрывающей скобкой, то сравниваем его с последним элементом в стеке. Если они не соответствуют, то возвращаем false, так как мы встретили неожиданную закрывающую скобку. - Если они соответствуют, то извлекаем последний элемент из стека.
4. Проверка пустоты стека:
- После обхода всей строки, если стек пуст, то это означает, что все открывающие скобки нашли свои закрывающие пары, и возвращаем true. - Если в стеке остались элементы, то это означает, что не все открывающие скобки нашли свои закрывающие пары, и возвращаем false.
Временная сложность этого решения - O(n), где n - длина входной строки. Это связано с тем, что мы проходим по всей строке один раз, выполняя простые операции с элементами стека.
Пространственная сложность - O(n), так как в худшем случае, когда все скобки в строке являются открывающими, мы добавим все их в стек.

Задача: №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: Инициализация
Мы начинаем с создания нового узла списка $newList, который будет служить якорем для нашего нового отсортированного списка. $current указывает на текущий узел нового списка.

Шаг 2: Цикл слияния


Этот цикл продолжается до тех пор, пока хотя бы один из исходных списков не станет пустым.

Шаг 3: Добавление элементов в новый список
- Случай 1: Только $list1 не пустой

Если только $list1 не пустой, добавляем его текущий элемент в новый список и переходим к следующему элементу $list1.

- Случай 2: Только $list2 не пустой
Если только $list2 не пустой, добавляем его текущий элемент в новый список и переходим к следующему элементу $list2.

- Случай 3: Оба списка не пустые

- Если значения текущих узлов обоих списков равны, мы добавляем оба элемента в новый список.
- Если значение текущего узла $list1 меньше значения текущего узла $list2, добавляем элемент из $list1.
- В других случаях, добавляем элемент из $list2.
Шаг 4: Возвращаем результат

Возвращаем начальную часть нашего нового списка $newList (пропуская первый псевдоузел).

Задача: 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. Базовый случай: Если количество открывающихся и закрывающихся скобок равно нулю, текущая скобочная последовательность действительна, и она добавляется в массив $answer.2. Если количество открывающихся скобок больше нуля:
* Добавляется открывающаяся скобка к $current. * Рекурсивно вызывается метод generateParenthesis с уменьшенным значением $toOpen и увеличенным значением $toClose.
* Открывающаяся скобка удаляется из $current.3. Если количество закрывающихся скобок больше нуля:
* Добавляется закрывающаяся скобка к $current. * Рекурсивно вызывается метод generateParenthesis с тем же значением $toOpen и уменьшенным значением $toClose.
* Закрывающаяся скобка удаляется из $current.

Задача: 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; 
    } 
}

Пояснение:
1. Устанавливает переменную iteration равной 1. Эта переменная используется для отслеживания текущей итерации.
2. Перебирает узлы в списке, используя переменную current.
3. На каждой итерации, если iteration нечетно (т. е. 1, 3, 5...), то выполняется обмен значений между текущим узлом и следующим узлом:
- currentNodeValue получает значение текущего узла. - nextNodeValue получает значение следующего узла.
- Значение следующего узла обновляется до currentNodeValue. - Значение текущего узла обновляется до nextNodeValue.
4. Перемещает указатель current на следующий узел.
5. Увеличивает iteration на 1.
6. После перебора всех узлов в списке функция возвращает измененный список head.

Задача: 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)Создается класс listnode для представления узла связанного списка, который содержит значение узла и ссылку на следующий узел.

2)Создается класс solution, который содержит метод reversekgroup для переворачивания групп узлов размером k.

3)В методе reversekgroup проверяется, если головной узел равен null или k равно 1, то возвращается головной узел.

4)Создается фиктивный узел dummy, который является заголовочным узлом и его next указывает на головной узел.

5)Затем начинается цикл, в котором извлекается k-ый узел группы с помощью метода getkthnode.

6)Если k-ый узел не существует, происходит выход из цикла.

7)Выделяется следующий после группы узлов узел и происходит переворот этой группы узлов.

8)После переворота группы узлов обновляются ссылки узлов и продолжается цикл для следующей группы.

9)В конце возвращается обновленный головной узел из dummy->next.

10)Есть также вспомогательные функции arraytolist для преобразования массива в связанный список и listtoarray для преобразования связанного списка в массив.

Задача: 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 остаются только уникальные элементы, а его длина изменена на количество уникальных элементов.

Задача: 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.

Задача: 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, в случае, если произошло некорректное завершение поиска.

Этот метод реализует простой подход к реализации поиска подстроки в строке, но следует отметить, что для более сложных и эффективных алгоритмов поиска, таких как алгоритм Кнута-Морриса-Пратта или алгоритм Бойера-Мура, требуется более сложная реализация.

Задача: 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;
    }
}

Пояснение:
Данный код представляет метод `divide`, который принимает два целых числа `$dividend` (делимое) и `$divisor` (делитель). Функция выполняет деление делимого на делитель и возвращает целочисленный результат этого деления. Однако в коде изначально отсутствуют проверки на случай деления на ноль, что может привести к ошибке выполнения программы.

Для исправления этой проблемы были добавлены две проверки:
1. Если делимое `$dividend` равно 0, то функция возвращает 0, так как в этом случае результат деления также будет равен 0.
2. Если делитель `$divisor` равен 0, то вместо выполнения деления функция сразу же возвращает максимальное целочисленное значение, представленное константой `PHP_INT_MAX`. Это предотвращает возможное деление на ноль и возвращает максимально возможное значение целочисленного типа в PHP.

Далее в функции вычисляется результат деления `$result` путем деления `$dividend` на `$divisor`. Затем происходят проверки:
- Если значение `$result` больше максимального значения целочисленного типа в PHP (`PHP_INT_MAX`), то функция возвращает `PHP_INT_MAX`.
- Если значение `$result` меньше минимального значения целочисленного типа в PHP (`PHP_INT_MIN`), то функция возвращает `PHP_INT_MIN`.

Наконец, если результат находится в диапазоне допустимых целочисленных значений, он приводится к целому числу с помощью явного преобразования `(int)` и возвращается из функции.

Таким образом, исправленный код обеспечивает корректную обработку случаев деления на ноль и предотвращает возможные ошибки или неправильные результаты.

Задача: 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;
}
'''

Пояснение:
Данный код представляет функцию, которая выполняет поиск всех вхождений комбинации слов из массива `$words` в строке `$s`. Код работает следующим образом:

1. Создается пустой массив `$result`, в который будут добавляться индексы начала вхождения комбинации слов.
2. Если количество слов в массиве `$words` меньше 1, то функция сразу возвращает пустой массив `$result`.
3. Получаем длину строки `$s` и длину одного слова из массива `$words[0]`.
4. Вычисляем общую длину комбинации слов `$subLength`, которая равна длине одного слова из массива умноженной на количество слов в массиве.
5. Сортируем слова в массиве `$words`.
6. Запускаем цикл `for`, который будет перебирать индексы начала возможных комбинаций слов в строке `$s`. Цикл завершается в момент, когда до конца строки остается место для комбинации слов длиной `$subLength`.
7. На каждой итерации цикла:
- Получаем комбинацию слов размером `$subLength` из строки `$s` начиная с индекса `$i`.
- Разбиваем комбинацию слов на отдельные слова размером `$wordLength` с помощью `str_split`.
- Сортируем отдельные слова комбинации `$strToArr`.
- Проверяем, если количество слов в массиве `$words` совпадает с количеством слов в комбинации `$strToArr` и если все слова совпадают с помощью `array_diff_assoc`.
- Если условия выполняются, то добавляем индекс `$i` в массив `$result`.
8. По завершении цикла возвращаем массив `$result`, содержащий индексы начала вхождений комбинаций слов в строке.

Этот код реализует алгоритм поиска вхождений комбинации слов в строке и возвращает все подходящие индексы начала вхождений.

Задача: 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;
    }
}

Пояснение:
Данный код представляет класс `Solution` с методом `nextPermutation`, который выполняет операцию нахождения следующей перестановки целочисленного массива `$nums`. Основная идея алгоритма поиска следующей перестановки основана на обмене элементов массива в соответствии с определенными правилами. Давайте рассмотрим основные шаги и методы этого алгоритма:

1. Метод `nextPermutation`:

- Проверяется размер массива `$nums`. Если размер равен 1, то возвращается, так как перестановка невозможна.
- Если размер равен 2, происходит обмен двух элементов с помощью метода `swap`.
- Переменной `$n` присваивается размер массива.
- Запускается цикл по всем элементам массива, начиная с предпоследнего.
- Для каждого элемента проверяется, если он находится в возрастающем порядке справа, тогда его место меняется с предпоследним элементом.
- Если элемент не находится в возрастающем порядке справа, то происходит поиск следующего максимального элемента после текущего и его обмен местами с текущим.
- Массив с элементами начиная с текущего индекса сортируется по возрастанию.
- Если ни одно из условий не выполняется, то весь массив сортируется по возрастанию.
- Метод `swap` производит обмен элементов массива в указанных позициях.


2. Дополнительные методы:

- `swap`: Обмен значений двух элементов массива.
- `checkAsc`: Проверка, находятся ли элементы массива с указанного индекса до конца в возрастающем порядке.
- `getNextMax`: Поиск следующего максимального элемента после указанного индекса и обмен его местами с текущим.
- `arrangeAsc`: Сортировка оставшихся элементов массива по возрастанию.


Алгоритм работы метода `nextPermutation` основан на правильной перестановке элементов массива с учетом заданных условий. Он находит следующую перестановку в лексикографическом порядке и обеспечивает правильное состояние массива после выполнения операции перестановки.

Задача: 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.

Этот алгоритм использует динамическое программирование для эффективного нахождения длины самой длинной подстроки правильных скобочных последовательностей открытых и закрывающих скобок в строке.

Задача: 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;
    }
}

Пояснение:
Данный код представляет класс `Solution` с методом `search`, который осуществляет поиск заданного целого числа `$target` в массиве `$nums`. Вот как работает этот метод:

1. Запускается цикл `for`, который проходит по каждому элементу массива `$nums`.
2. На каждой итерации проверяется, если значение элемента массива `$nums[$i]` равно целому числу `$target`.
3. Если значение найдено, то функция возвращает индекс данного элемента в массиве `$i`.
4. Если значение не найдено после завершения цикла, функция возвращает -1, что указывает на то, что элемент не был найден в массиве.

Основная цель этого метода - найти индекс элемента в массиве, который соответствует заданному значению `$target`. Подход с использованием цикла `for` позволяет простым способом пройтись по всем элементам массива и выполнить сравнение. Если совпадение найдено, возвращается индекс элемента, иначе возвращается -1.

Этот метод реализует простой алгоритм поиска элемента в массиве и является одним из самых простых и понятных способов решения данной задачи.