PHP | LeetCode
1.51K subscribers
168 photos
1.05K links
Cайт easyoffer.ru
Реклама @easyoffer_adv
ВП @easyoffer_vp

Тесты t.iss.one/+pSDoLEZBQRZlNmFi
Вопросы собесов t.iss.one/+RJaDhjYaQDo2Njcy
Вакансии t.iss.one/+J-DKRUtjUgMxZGNi
Download Telegram
Задача: 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)` и возвращается из функции.

Таким образом, исправленный код обеспечивает корректную обработку случаев деления на ноль и предотвращает возможные ошибки или неправильные результаты.
👍2👀1
Задача: 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`, содержащий индексы начала вхождений комбинаций слов в строке.

Этот код реализует алгоритм поиска вхождений комбинации слов в строке и возвращает все подходящие индексы начала вхождений.
👍1👀1
Задача: 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👀1
Пояснение:
Данный код представляет класс `Solution` с методом `nextPermutation`, который выполняет операцию нахождения следующей перестановки целочисленного массива `$nums`. Основная идея алгоритма поиска следующей перестановки основана на обмене элементов массива в соответствии с определенными правилами. Давайте рассмотрим основные шаги и методы этого алгоритма:

1. Метод `nextPermutation`:

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


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

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


Алгоритм работы метода `nextPermutation` основан на правильной перестановке элементов массива с учетом заданных условий. Он находит следующую перестановку в лексикографическом порядке и обеспечивает правильное состояние массива после выполнения операции перестановки.
👍1👀1
Задача: 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🤯1👀1
Задача: 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.

Этот метод реализует простой алгоритм поиска элемента в массиве и является одним из самых простых и понятных способов решения данной задачи.
👍2👀1
Задача: 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)];
}
}
}

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

1. Создается пустой массив `$result`, который будет содержать индексы, где найдено значение `$target`.
2. На каждой итерации цикла `foreach` проходится по элементам массива `$nums`.
3. Если текущее значение равно целому числу `$target`, то индекс текущего элемента добавляется в массив `$result`.
4. После завершения прохода по всем элементам массива, проверяется, содержит ли массив `$result` какие-либо индексы.
5. Если массив `$result` пустой (то есть, значение `$target` не встречается в массиве), то возвращается диапазон [-1, -1].
6. Если массив `$result` не пустой, то возвращается массив, содержащий минимальный и максимальный индексы из массива `$result`, где значение `$target` найдено.
7. Функция возвращает этот массив с диапазоном индексов.

Этот метод позволяет эффективно найти все индексы, в которых заданное значение `$target` встречается в массиве, и вернуть их диапазон в виде [минимальный индекс, максимальный индекс]. Если значение не найдено, то возвращается [-1, -1]. Это удобный способ для поиска позиций вхождения элемента в массиве.
👍1👀1
Задача: 35. Search Insert Position #easy
Условие:
Учитывая отсортированный массив различных целых чисел и целевое значение, верните индекс, если цель найдена. Если нет, верните индекс там, где он был бы, если бы он был вставлен по порядку.

Вы должны написать алгоритм со сложностью выполнения O(log n).

Решение:
        foreach($nums as $key => $num){
if($target<$num ||$target===$num){
$target = $key;
return $target;
}
}
return sizeof($nums);

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

Вот как работает этот код:
1. На каждой итерации цикла `foreach` происходит сравнение текущего элемента `$num` с целым числом `$target`.
2. Если текущий элемент `$num` больше либо равен `$target` (или равен ему), то переменной `$target` присваивается индекс текущего элемента `$key`.
3. После этого возвращается переменная `$target`, содержащая индекс первого элемента, который больше или равен `$target`.
4. Если такой элемент не найден после перебора всех элементов, то возвращается размер массива (`sizeof($nums)`), что означает, что все элементы массива меньше `$target`.

Этот код позволяет найти индекс первого элемента в массиве, который больше или равен заданному значению `$target`. Если все элементы массива меньше `$target`, то возвращается размер массива.
👍1👀1
#medium
Задача: 36. Valid Sudoku

Определите, является ли доска Судоку размером 9 на 9 валидной. Необходимо проверить только заполненные ячейки согласно следующим правилам:

Каждая строка должна содержать цифры от 1 до 9 без повторений.
Каждый столбец должен содержать цифры от 1 до 9 без повторений.
Каждая из девяти подзон размером 3 на 3 в сетке должна содержать цифры от 1 до 9 без повторений.

Пример:
Input: board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: true


👨‍💻 Алгоритм:

1️⃣Инициализируйте список из 9 хеш-множеств, где хеш-множество с индексом r будет использоваться для хранения ранее увиденных чисел в строке r судоку. Аналогично инициализируйте списки из 9 хеш-множеств для отслеживания столбцов и блоков.

2️⃣Итерируйтесь по каждой позиции (r, c) в судоку. На каждой итерации, если на текущей позиции есть число:
Проверьте, существует ли это число в хеш-множестве для текущей строки, столбца или блока. Если да, верните false, потому что это второе появление числа в текущей строке, столбце или блоке.

3️⃣В противном случае обновите множество, отвечающее за отслеживание ранее увиденных чисел в текущей строке, столбце и блоке. Индекс текущего блока рассчитывается как (r / 3) * 3 + (c / 3), где / означает деление нацело.
Если дубликаты не были найдены после посещения каждой позиции на доске судоку, то судоку валидно, поэтому верните true.

😎 Решение:
function isValidSudoku($board) {
$N = 9;
$rows = array_fill(0, $N, []);
$cols = array_fill(0, $N, []);
$boxes = array_fill(0, $N, []);

for ($r = 0; $r < $N; $r++) {
for ($c = 0; $c < $N; $c++) {
$val = $board[$r][$c];
if ($val == ".") {
continue;
}
if (isset($rows[$r][$val])) {
return false;
}
$rows[$r][$val] = true;
if (isset($cols[$c][$val])) {
return false;
}
$cols[$c][$val] = true;
$idx = intval($r / 3) * 3 + intval($c / 3);
if (isset($boxes[$idx][$val])) {
return false;
}
$boxes[$idx][$val] = true;
}
}
return true;
}


🪙 385 вопроса вопроса на PHP разработчика

🔒 База собесов | 🔒 База тестовых
Please open Telegram to view this post
VIEW IN TELEGRAM
👀1
#hard
Задача: 37. Sudoku Solver

Напишите программу для решения головоломки Судоку, заполнив пустые ячейки.

Решение Судоку должно удовлетворять всем следующим правилам:

Каждая из цифр от 1 до 9 должна встречаться ровно один раз в каждой строке.
Каждая из цифр от 1 до 9 должна встречаться ровно один раз в каждом столбце.
Каждая из цифр от 1 до 9 должна встречаться ровно один раз в каждом из 9 подблоков 3x3 сетки.
Символ '.' обозначает пустые ячейки.

Пример:
Input: board = 
[["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]]
Output:
[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]


👨‍💻 Алгоритм:

1️⃣Теперь все готово для написания функции обратного поиска backtrack(row = 0, col = 0). Начните с верхней левой ячейки row = 0, col = 0. Продолжайте, пока не дойдете до первой свободной ячейки.

2️⃣Итерируйте по числам от 1 до 9 и попробуйте поставить каждое число d в ячейку (row, col).
Если число d еще не в текущей строке, столбце и блоке:
Поместите d в ячейку (row, col).
Запишите, что d теперь присутствует в текущей строке, столбце и блоке.

3️⃣Если вы на последней ячейке row == 8, col == 8:
Это означает, что судоку решено.
В противном случае продолжайте размещать дальнейшие числа.
Откат, если решение еще не найдено: удалите последнее число из ячейки (row, col).

😎 Решение:
function solveSudoku(&$board) {
$N = 9;
$rows = array_fill(0, $N, []);
$columns = array_fill(0, $N, []);
$boxes = array_fill(0, $N, []);
$sudoku_solved = false;

function box_index($row, $col) {
return intval($row / 3) * 3 + intval($col / 3);
}

function could_place($d, $row, $col, &$rows, &$columns, &$boxes) {
$boxIdx = box_index($row, $col);
return !isset($rows[$row][$d]) && !isset($columns[$col][$d]) && !isset($boxes[$boxIdx][$d]);
}

function place_number($d, $row, $col, &$board, &$rows, &$columns, &$boxes) {
$boxIdx = box_index($row, $col);
$rows[$row][$d] = ($rows[$row][$d] ?? 0) + 1;
$columns[$col][$d] = ($columns[$col][$d] ?? 0) + 1;
$boxes[$boxIdx][$d] = ($boxes[$boxIdx][$d] ?? 0) + 1;
$board[$row][$col] = strval($d);
}

function remove_number($d, $row, $col, &$board, &$rows, &$columns, &$boxes) {
$boxIdx = box_index($row, $col);
unset($rows[$row][$d], $columns[$col][$d], $boxes[$boxIdx][$d]);
$board[$row][$col] = ".";
}

function place_next_numbers($row, $col, &$board, &$rows, &$columns, &$boxes, &$sudoku_solved) {
global $N;
if ($col == $N - 1 && $row == $N - 1) {
$sudoku_solved = true;
} else {
if ($col == $N - 1) backtrack($row + 1, 0, $board, $rows, $columns, $boxes, $sudoku_solved);
else backtrack($row, $col + 1, $board, $rows, $columns, $boxes, $sudoku_solved);
}
}


🪙 385 вопроса вопроса на PHP разработчика

🔒 База собесов | 🔒 База тестовых
Please open Telegram to view this post
VIEW IN TELEGRAM
👍1👀1
#medium
Задача: 38. Count and Say

Последовательность "считай и скажи" — это последовательность строк цифр, определяемая с помощью рекурсивной формулы:

countAndSay(1) = "1"
countAndSay(n) — это кодирование длин серий из countAndSay(n - 1).
Кодирование длин серий (RLE) — это метод сжатия строк, который работает путём замены последовательных идентичных символов (повторяющихся 2 или более раз) на конкатенацию символа и числа, обозначающего количество символов (длину серии). Например, чтобы сжать строку "3322251", мы заменяем "33" на "23", "222" на "32", "5" на "15" и "1" на "11". Таким образом, сжатая строка становится "23321511".

Для заданного положительного целого числа n верните n-й элемент последовательности "считай и скажи".

Пример:
Input: n = 4

Output: "1211"

Explanation:

countAndSay(1) = "1"
countAndSay(2) = RLE of "1" = "11"
countAndSay(3) = RLE of "11" = "21"
countAndSay(4) = RLE of "21" = "1211"


👨‍💻 Алгоритм:

1️⃣Мы хотим использовать шаблон, который соответствует строкам из одинаковых символов, таких как "4", "7777", "2222222".
Если у вас есть опыт работы с регулярными выражениями, вы можете обнаружить, что шаблон (.)\1* работает.

2️⃣Мы можем разбить это регулярное выражение на три части:
(.): оно определяет группу, содержащую один символ, который может быть чем угодно.

3️⃣*: этот квалификатор, следующий за ссылкой на группу \1, указывает, что мы хотели бы видеть повторение группы ноль или более раз.
Таким образом, шаблон соответствует строкам, которые состоят из некоторого символа, а затем ноль или более повторений этого символа после его первого появления. Это то, что нам нужно.
Мы находим все совпадения с регулярным выражением, а затем конкатенируем результаты.

😎 Решение:
function countAndSay($n) {
$s = "1";
for ($i = 2; $i <= $n; $i++) {
$t = "";
$regex = '/(.)\\1*/';
preg_match_all($regex, $s, $matches, PREG_SET_ORDER);
foreach ($matches as $match) {
$t .= strlen($match[0]) . $match[1];
}
$s = $t;
}
return $s;
}


🪙 385 вопроса вопроса на PHP разработчика

🔒 База собесов | 🔒 База тестовых
Please open Telegram to view this post
VIEW IN TELEGRAM
👀1
#medium
Задача: 39. Combination Sum

Дан массив уникальных целых чисел candidates и целевое целое число target. Верните список всех уникальных комбинаций из candidates, где выбранные числа в сумме дают target. Комбинации можно возвращать в любом порядке.

Одно и то же число может быть выбрано из массива candidates неограниченное количество раз. Две комбинации считаются уникальными, если частота хотя бы одного из выбранных чисел отличается.

Тестовые случаи сгенерированы таким образом, что количество уникальных комбинаций, дающих в сумме target, меньше 150 комбинаций для данного ввода.

Пример:
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]


👨‍💻 Алгоритм:

1️⃣Как видно, вышеописанный алгоритм обратного отслеживания разворачивается как обход дерева в глубину (DFS - Depth-First Search), который часто реализуется с помощью рекурсии.
Здесь мы определяем рекурсивную функцию backtrack(remain, comb, start) (на Python), которая заполняет комбинации, начиная с текущей комбинации (comb), оставшейся суммы для выполнения (remain) и текущего курсора (start) в списке кандидатов.
Следует отметить, что сигнатура рекурсивной функции немного отличается в Java, но идея остается той же.

2️⃣Для первого базового случая рекурсивной функции, если remain == 0, то есть мы достигаем желаемой целевой суммы, поэтому мы можем добавить текущую комбинацию в итоговый список.
Как другой базовый случай, если remain < 0, то есть мы превышаем целевое значение, мы прекращаем исследование на этом этапе.

3️⃣Помимо вышеупомянутых двух базовых случаев, мы затем продолжаем исследовать подсписок кандидатов, начиная с [start ... n].
Для каждого из кандидатов мы вызываем рекурсивную функцию саму с обновленными параметрами.
Конкретно, мы добавляем текущего кандидата в комбинацию.
С добавленным кандидатом у нас теперь меньше суммы для выполнения, то есть remain - candidate.
Для следующего исследования мы все еще начинаем с текущего курсора start.
В конце каждого исследования мы делаем откат, удаляя кандидата из комбинации.

😎 Решение:
class Solution {
function backtrack($remain, &$comb, $start, $candidates, &$results) {
if ($remain == 0) {
$results[] = $comb;
return;
} else if ($remain < 0) {
return;
}

for ($i = $start; $i < count($candidates); ++$i) {
$comb[] = $candidates[$i];
$this->backtrack($remain - $candidates[$i], $comb, $i, $candidates, $results);
array_pop($comb);
}
}

function combinationSum($candidates, $target) {
$results = [];
$comb = [];

$this->backtrack($target, $comb, 0, $candidates, $results);
return $results;
}
}


🪙 385 вопроса вопроса на PHP разработчика

🔒 База собесов | 🔒 База тестовых
Please open Telegram to view this post
VIEW IN TELEGRAM
👍1👀1
#medium
Задача: 40. Combination Sum II

Дана коллекция кандидатов (candidates) и целевое число (target). Найдите все уникальные комбинации в candidates, где числа кандидатов в сумме дают target.

Каждое число в candidates может быть использовано только один раз в комбинации.

Примечание: Набор решений не должен содержать повторяющихся комбинаций.

Пример:
Input: candidates = [10,1,2,7,6,1,5], target = 8
Output:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]


👨‍💻 Алгоритм:

1️⃣Во-первых, мы создаём таблицу счётчиков из предоставленного списка чисел. Затем мы используем эту таблицу счётчиков в процессе обратного поиска, который мы определяем как функцию backtrack(comb, remain, curr, candidate_groups, results). Для сохранения состояния на каждом этапе обратного поиска мы используем несколько параметров в функции:
comb: комбинация, которую мы построили на данный момент.
remain: оставшаяся сумма, которую нам нужно заполнить, чтобы достичь целевой суммы.
curr: курсор, который указывает на текущую группу чисел, используемую из таблицы счётчиков.
counter: текущая таблица счётчиков.
results: окончательные комбинации, которые достигают целевой суммы.

2️⃣При каждом вызове функции обратного поиска мы сначала проверяем, достигли ли мы целевой суммы (то есть sum(comb) = target), и нужно ли прекратить исследование, потому что сумма текущей комбинации превышает желаемую целевую сумму.

3️⃣Если осталась сумма для заполнения, мы затем перебираем текущую таблицу счётчиков, чтобы выбрать следующего кандидата. После выбора кандидата мы продолжаем исследование, вызывая функцию backtrack() с обновлёнными состояниями. Более важно, что в конце каждого исследования нам нужно вернуть состояние, которое мы обновили ранее, чтобы начать с чистого листа для следующего исследования. Именно из-за этой операции обратного поиска алгоритм получил своё название.

😎 Решение:
function combinationSum2($candidates, $target) {
sort($candidates);
$res = [];
findCombinationSum2($candidates, $target, 0, [], $res);
return $res;
}

function findCombinationSum2($candidates, $target, $start, $current, &$res) {
if ($target === 0) {
$res[] = $current;
return;
}
for ($i = $start; $i < count($candidates); $i++) {
if ($i > $start && $candidates[$i] === $candidates[$i - 1]) {
continue;
}
if ($candidates[$i] > $target) {
break;
}
$current[] = $candidates[$i];
findCombinationSum2(
$candidates,
$target - $candidates[$i],
$i + 1,
$current,
$res
);
array_pop($current);
}
}


🪙 385 вопроса вопроса на PHP разработчика

🔒 База собесов | 🔒 База тестовых
Please open Telegram to view this post
VIEW IN TELEGRAM
👀1
#hard
Задача: 41. First Missing Positive

Дан неотсортированный массив целых чисел nums. Верните наименьшее положительное целое число, которого нет в массиве nums.

Необходимо реализовать алгоритм, который работает за время O(n) и использует O(1) дополнительной памяти.

Пример:
Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is in the array but 2 is missing.


👨‍💻 Алгоритм:

1️⃣Инициализировать переменную n длиной массива nums. Создать массив seen размером n + 1. Отметить элементы в массиве nums как просмотренные в массиве seen.
Для каждого числа num в массиве nums, если num больше 0 и меньше или равно n, установить seen[num] в значение true.

2️⃣Найти наименьшее недостающее положительное число:
Проитерировать от 1 до n, и если seen[i] не равно true, вернуть i как наименьшее недостающее положительное число.

3️⃣Если массив seen содержит все элементы от 1 до n, вернуть n + 1 как наименьшее недостающее положительное число.

😎 Решение:
function firstMissingPositive($nums) {
$n = count($nums);
$seen = array_fill(0, $n + 1, false);
foreach ($nums as $num) {
if ($num > 0 && $num <= $n) {
$seen[$num] = true;
}
}
for ($i = 1; $i <= $n; $i++) {
if (!$seen[$i]) {
return $i;
}
}
return $n + 1;
}


🪙 385 вопроса вопроса на PHP разработчика

🔒 База собесов | 🔒 База тестовых
Please open Telegram to view this post
VIEW IN TELEGRAM
👀1
#hard
Задача: 42. Trapping Rain Water

Дано n неотрицательных целых чисел, представляющих карту высот, где ширина каждого столбца равна 1. Вычислите, сколько воды он может удержать после дождя.

Пример:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6


👨‍💻 Алгоритм:

1️⃣Найдите максимальную высоту столбца с левого конца до индекса i в массиве left_max.

2️⃣Найдите максимальную высоту столбца с правого конца до индекса i в массиве right_max.

3️⃣Итерируйте по массиву высот height и обновляйте ans: добавьте min(left_max[i], right_max[i]) - height[i] к ans.

😎 Решение:
function trap($height) {
if (count($height) == 0) return 0;
$ans = 0;
$size = count($height);
$left_max = array_fill(0, $size, 0);
$right_max = array_fill(0, $size, 0);

$left_max[0] = $height[0];
for ($i = 1; $i < $size; $i++) {
$left_max[$i] = max($height[$i], $left_max[$i - 1]);
}

$right_max[$size - 1] = $height[$size - 1];
for ($i = $size - 2; $i >= 0; $i--) {
$right_max[$i] = max($height[$i], $right_max[$i + 1]);
}

for ($i = 1; $i < $size - 1; $i++) {
$ans += min($left_max[$i], $right_max[$i]) - $height[$i];
}
return $ans;
}


🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых
Please open Telegram to view this post
VIEW IN TELEGRAM
👍2👀1
#hard
Задача: 43. Multiply Strings

Даны два неотрицательных целых числа num1 и num2, представленные в виде строк. Верните произведение num1 и num2, также представленное в виде строки.

Примечание: Вы не должны использовать встроенную библиотеку BigInteger или прямо преобразовывать входные данные в целые числа.

Пример:
Input: num1 = "2", num2 = "3"
Output: "6"


👨‍💻 Алгоритм:

1️⃣Переверните оба числа. Инициализируйте массив ans с (N+M) нулями. Для каждой цифры в secondNumber:
Инициализируйте переменную carry, первоначально равную 0.
Инициализируйте массив (currentResult), который начинается с некоторого количества нулей, основываясь на позиции цифры в secondNumber.

2️⃣Для каждой цифры в firstNumber:
Умножьте цифру из secondNumber на цифру из firstNumber и добавьте предыдущий carry к умножению.
Возьмите остаток от деления умножения на 10, чтобы получить последнюю цифру.
Добавьте последнюю цифру в массив currentResult.
Разделите умножение на 10, чтобы получить новое значение для carry.

3️⃣После итерации по каждой цифре в первом числе, если carry не равен нулю, добавьте carry в currentResult.
Добавьте currentResult к ans.
Если последняя цифра в ans равна нулю, перед тем как перевернуть ans, необходимо удалить ноль из ans. В противном случае в финальном ответе будет ведущий ноль.
Переверните ans и верните его.

😎 Решение:
function addStrings($num1, $num2) {
$ans = [];
$carry = 0;
$length = max(strlen($num1), strlen($num2));

for ($i = 0; $i < $length; $i++) {
$digit1 = $i < strlen($num1) ? $num1[strlen($num1) - 1 - $i] : 0;
$digit2 = $i < strlen($num2) ? $num2[strlen($num2) - 1 - $i] : 0;

$sum = $digit1 + $digit2 + $carry;
$carry = intdiv($sum, 10);
array_unshift($ans, $sum % 10);
}

if ($carry) {
array_unshift($ans, $carry);
}
return $ans;
}

function multiplyOneDigit($firstNumber, $secondNumberDigit, $numZeros) {
$currentResult = array_fill(0, $numZeros, 0);
$carry = 0;

for ($i = 0; $i < strlen($firstNumber); $i++) {
$multiplication = (int)$secondNumberDigit * (int)$firstNumber[strlen($firstNumber) - 1 - $i] + $carry;
$carry = intdiv($multiplication, 10);
array_unshift($currentResult, $multiplication % 10);
}

if ($carry) {
array_unshift($currentResult, $carry);
}
return $currentResult;
}

function multiply($num1, $num2) {
if ($num1 === "0" || $num2 === "0") {
return "0";
}

$firstNumber = $num1;
$secondNumber = $num2;

$ans = array_fill(0, strlen($firstNumber) + strlen($secondNumber), 0);

for ($i = 0; $i < strlen($secondNumber); $i++) {
$ans = addStrings(
multiplyOneDigit($firstNumber, $secondNumber[strlen($secondNumber) - 1 - $i], $i),
$ans
);
}

if (end($ans) === 0) {
array_pop($ans);
}
return implode("", array_reverse($ans));
}


🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых
Please open Telegram to view this post
VIEW IN TELEGRAM
👀1
#hard
Задача: 44. Wildcard Matching

Дана входная строка (s) и шаблон (p), реализуйте сопоставление с шаблоном с поддержкой символов '?' и '*' где:

'?' соответствует любому одиночному символу.
'*' соответствует любой последовательности символов (включая пустую последовательность).
Сопоставление должно покрывать всю входную строку (не частично).

Пример:
Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".


👨‍💻 Алгоритм:

1️⃣Очистите входные данные, заменив несколько звездочек подряд одной звездочкой: p = remove_duplicate_stars(p).
Инициируйте хеш-карту для мемоизации dp.
Верните вспомогательную функцию с очищенным входом: helper(s, p).

2️⃣Функция helper(s, p):
Если пара (s, p) уже известна и сохранена в dp, верните значение.
Если строки равны (p == s) или шаблон соответствует любой строке (p == '*'), добавьте dp[(s, p)] = True.
В противном случае, если p пусто или s пусто, добавьте dp[(s, p)] = False.
Если текущие символы совпадают (p[0] == s[0] или p[0] == '?'), то сравните следующие и добавьте dp[(s, p)] = helper(s[1:], p[1:]).

3️⃣Если текущий символ шаблона - звездочка (p[0] == '*'), то возможны две ситуации: звездочка не соответствует никаким символам, и звездочка соответствует одному или нескольким символам: dp[(s, p)] = helper(s, p[1:]) или helper(s[1:], p).
Если p[0] != s[0], тогда добавьте dp[(s, p)] = False.
Когда значение вычислено, верните его: dp[(s, p)].

😎 Решение:
function isMatch($s, $p) {
$dp = [];

function removeDuplicateStars($p) {
$newString = "";
for ($i = 0; $i < strlen($p); $i++) {
if ($newString === "" || $p[$i] !== "*") {
$newString .= $p[$i];
} elseif ($newString[strlen($newString) - 1] !== "*") {
$newString .= $p[$i];
}
}
return $newString;
}

function helper($si, $pi, $s, $p, &$dp) {
$key = $si . "," . $pi;
if (array_key_exists($key, $dp)) {
return $dp[$key];
}

if ($pi == strlen($p)) {
$dp[$key] = $si == strlen($s);
} elseif ($si == strlen($s)) {
$dp[$key] = $pi + 1 == strlen($p) && $p[$pi] == "*";
} elseif ($p[$pi] == $s[$si] || $p[$pi] == "?") {
$dp[$key] = helper($si + 1, $pi + 1, $s, $p, $dp);
} elseif ($p[$pi] == "*") {
$dp[$key] = helper($si, $pi + 1, $s, $p, $dp) || helper($si + 1, $pi, $s, $p, $dp);
} else {
$dp[$key] = false;
}
return $dp[$key];
}

$p = removeDuplicateStars($p);
return helper(0, 0, $s, $p, $dp);
}


🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых
Please open Telegram to view this post
VIEW IN TELEGRAM
👀1
#medium
Задача: 45. Jump Game II

Вам дан массив целых чисел nums с индексацией с нуля и длиной n. Изначально вы находитесь в позиции nums[0].

Каждый элемент nums[i] представляет максимальную длину прыжка вперед с индекса i. Другими словами, если вы находитесь в nums[i], вы можете прыгнуть на любой nums[i + j], где:

0 <= j <= nums[i] и
i + j < n
Верните минимальное количество прыжков, чтобы достичь nums[n - 1]. Тестовые случаи сгенерированы таким образом, что вы можете достичь nums[n - 1].

Пример:
Input: nums = [2,3,0,1,4]
Output: 2


👨‍💻 Алгоритм:

1️⃣Инициализируйте curEnd = 0, curFar = 0 и количество прыжков как answer = 0.

2️⃣Итерируйтесь по массиву nums. Для каждого индекса i наибольший индекс, до которого мы можем добраться из i, равен i + nums[i]. Обновите curFar = max(curFar, i + nums[i]).

3️⃣Если i = curEnd, это означает, что текущий прыжок завершен, и следует перейти к следующему прыжку. Увеличьте answer и установите curEnd = curFar как наибольшее расстояние, которое мы можем преодолеть следующим прыжком. Повторите с шага 2.

😎 Решение:
function jump($nums) {
$answer = 0;
$n = count($nums);
$curEnd = 0;
$curFar = 0;
for ($i = 0; $i < $n - 1; ++$i) {
$curFar = max($curFar, $i + $nums[$i]);
if ($i === $curEnd) {
++$answer;
$curEnd = $curFar;
}
}
return $answer;
}


🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых
Please open Telegram to view this post
VIEW IN TELEGRAM
1👀1
#medium
Задача: 46. Permutations

Дан массив nums, состоящий из различных целых чисел, верните все возможные перестановки. Вы можете вернуть ответ в любом порядке.

Пример:
Input: nums = [0,1]
Output: [[0,1],[1,0]]


👨‍💻 Алгоритм:

1️⃣Если длина curr равна длине nums, добавьте копию curr в ans и вернитесь.

2️⃣Итерируйтесь по nums. Для каждого num, если num не в curr, выполните следующее:
Добавьте num в curr и вызовите backtrack(curr), затем удалите num из curr.

3️⃣Вызовите backtrack с изначально пустым curr.
Верните ans.

😎 Решение:
function permute($nums) {
$ans = [];
$backtrack = function (&$curr) use (&$ans, &$backtrack, $nums) {
if (count($curr) === count($nums)) {
$ans[] = $curr;
return;
}
foreach ($nums as $num) {
if (!in_array($num, $curr)) {
$curr[] = $num;
$backtrack($curr);
array_pop($curr);
}
}
};
$backtrack([]);
return $ans;
}


🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых
Please open Telegram to view this post
VIEW IN TELEGRAM
👀1
#medium
Задача: 47. Permutations II

Дана коллекция чисел, nums, которая может содержать дубликаты. Верните все возможные уникальные перестановки в любом порядке.

Пример:
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]


👨‍💻 Алгоритм:

1️⃣Для реализации алгоритма сначала определим функцию под названием backtrack(comb, counter), которая генерирует все перестановки, начиная с текущей комбинации (comb) и оставшихся чисел (counter).

2️⃣После реализации функции достаточно вызвать её с начальной пустой комбинацией и хеш-таблицей, построенной из входного массива, чтобы решить задачу.

3️⃣Это позволяет эффективно и систематически исследовать все возможные уникальные перестановки, учитывая дубликаты в исходном наборе чисел.

😎 Решение:
function permuteUnique($nums) {
$results = [];
$counter = [];
foreach ($nums as $num) {
if (!array_key_exists($num, $counter)) {
$counter[$num] = 0;
}
$counter[$num]++;
}

$backtrack = function (&$comb, $N) use (&$results, &$counter, &$backtrack) {
if (count($comb) === $N) {
$results[] = $comb;
return;
}
foreach ($counter as $num => $count) {
if ($count === 0) continue;
$comb[] = $num;
$counter[$num]--;
$backtrack($comb, $N);
$counter[$num]++;
array_pop($comb);
}
};
$backtrack([], count($nums));
return $results;
}


🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых
Please open Telegram to view this post
VIEW IN TELEGRAM
👍2👀1
#medium
Задача: 55. Jump Game

Вам дан массив целых чисел nums. Изначально вы находитесь на первом индексе массива, и каждый элемент массива представляет вашу максимальную длину прыжка в этой позиции.

Верните true, если вы можете достичь последнего индекса, или false в противном случае.

Пример:
Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.


👨‍💻Алгоритм:

1️⃣ Инициализация таблицы памяти:
Изначально все элементы таблицы памяти имеют статус UNKNOWN, за исключением последнего, который является (тривиально) GOOD (может достичь сам себя).

2️⃣Модификация алгоритма обратного трассирования:
Измените алгоритм обратного трассирования таким образом, чтобы на рекурсивном шаге сначала проверялось, известен ли индекс (GOOD/BAD).
Если индекс известен, тогда возвращается True/False.

3️⃣Выполнение и сохранение результатов:
Если индекс не известен, выполняйте шаги обратного трассирования, как ранее.
После определения значения текущего индекса, сохраните его в таблице памяти.

😎 Решение:
<?php

enum Index {
case GOOD;
case BAD;
case UNKNOWN;
}

class Solution {
private array $memo;

public function __construct(array $nums) {
$this->memo = array_fill(0, count($nums), Index::UNKNOWN);
$this->memo[count($nums) - 1] = Index::GOOD;
}

private function canJumpFromPosition(int $position, array $nums): bool {
if ($this->memo[$position] !== Index::UNKNOWN) {
return $this->memo[$position] === Index::GOOD;
}

$furthestJump = min($position + $nums[$position], count($nums) - 1);
for ($nextPosition = $position + 1; $nextPosition <= $furthestJump; $nextPosition++) {
if ($this->canJumpFromPosition($nextPosition, $nums)) {
$this->memo[$position] = Index::GOOD;
return true;
}
}

$this->memo[$position] = Index::BAD;
return false;
}

public function canJump(array $nums): bool {
return $this->canJumpFromPosition(0, $nums);
}
}

// Пример использования
$nums = [2, 3, 1, 1, 4];
$solution = new Solution($nums);
var_dump($solution->canJump($nums));


🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых
Please open Telegram to view this post
VIEW IN TELEGRAM
1👍1👀1