Задача: 942. DI String Match
Сложность: easy

Перестановка perm из n + 1 целых чисел всех целых чисел в диапазоне [0, n] может быть представлена в виде строки s длины n, где: s[i] == 'I', если perm[i] < perm[i + 1], и s[i] == 'D', если perm[i] > perm[i + 1]. Получив строку s, восстановите перестановку perm и верните ее. Если существует несколько допустимых перестановок perm, верните любую из них.

Пример:

Input: s = "IDID"
Output: [0,4,1,3,2]

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

1⃣Инициализировать два указателя low и high для отслеживания минимального и максимального числа, которые можно использовать в перестановке.

2⃣Создать массив perm длиной n + 1.
Пройти по строке s:
Если текущий символ равен 'I', добавить low в текущую позицию perm и увеличить low.
Если текущий символ равен 'D', добавить high в текущую позицию perm и уменьшить high.
Добавить оставшееся значение (low или high, так как они будут равны) в последнюю позицию perm.

3⃣Вернуть массив perm.

😎 Решение:

function diStringMatch($s) {
    $n = strlen($s);
    $low = 0;
    $high = $n;
    $perm = array_fill(0, $n + 1, 0);
    
    for ($i = 0; $i < $n; $i++) {
        if ($s[$i] == 'I') {
            $perm[$i] = $low++;
        } else {
            $perm[$i] = $high--;
        }
    }
    
    $perm[$n] = $low;
    return $perm;
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 246. Strobogrammatic Number
Сложность: easy

Дана строка num, представляющая собой целое число. Верните true, если num является стробограмматическим числом.
Стробограмматическое число — это число, которое выглядит одинаково при повороте на 180 градусов (если посмотреть вверх ногами).

Пример:

Input: num = "69"
Output: true

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

1⃣Создайте новую строку, перебирая оригинальную строку num в обратном порядке. Для каждого символа проверьте, является ли он допустимым для поворота (0, 1, 6, 8, 9). Если символ недопустим (2, 3, 4, 5, 7), немедленно верните false.

2⃣Для каждого допустимого символа добавьте его соответствующее значение после поворота (0 ⟶ 0, 1 ⟶ 1, 6 ⟶ 9, 8 ⟶ 8, 9 ⟶ 6) в новую строку.

3⃣Сравните полученную строку с исходной строкой num. Если они равны, верните true, в противном случае верните false.

😎 Решение:

class Solution {
    function isStrobogrammatic($num) {
        $rotated = '';
        for ($i = strlen($num) - 1; $i >= 0; $i--) {
            $c = $num[$i];
            if ($c == '0' || $c == '1' || $c == '8') {
                $rotated .= $c;
            } else if ($c == '6') {
                $rotated .= '9';
            } else if ($c == '9') {
                $rotated .= '6';
            } else {
                return false;
            }
        }
        return $num == $rotated;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1345. Jump Game IV
Сложность: hard

Дан массив целых чисел arr, изначально вы находитесь на первом индексе массива.

За один шаг вы можете прыгнуть с индекса i на индекс:

- i + 1, где: i + 1 < arr.length.
- i - 1, где: i - 1 >= 0.
- j, где: arr[i] == arr[j] и i != j.

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

Обратите внимание, что нельзя прыгать за пределы массива в любой момент времени.

Пример:

Input: arr = [100,-23,-23,404,100,23,23,23,3,404]
Output: 3
Explanation: You need three jumps from index 0 --> 4 --> 3 --> 9. Note that index 9 is the last index of the array.

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

1⃣Построить граф, где ключи - значения из массива, а значения - списки индексов этих значений. Начать с первого индекса, добавив его в очередь текущего слоя и инициализировать набор посещенных индексов.

2⃣Выполнять BFS: для каждого индекса текущего слоя проверять соседние индексы (i + 1, i - 1 и все j, где arr[i] == arr[j]), добавляя непосещенные индексы в очередь следующего слоя.

3⃣Повторять шаг 2, увеличивая счетчик шагов до достижения последнего индекса или пока не закончится очередь.

😎 Решение:

class Solution {
    public function minJumps($arr) {
        $n = count($arr);
        if ($n <= 1) {
            return 0;
        }

        $graph = [];
        for ($i = 0; $i < $n; $i++) {
            if (!isset($graph[$arr[$i]])) {
                $graph[$arr[$i]] = [];
            }
            $graph[$arr[$i]][] = $i;
        }

        $curs = [0];
        $visited = [0 => true];
        $step = 0;

        while (!empty($curs)) {
            $nex = [];

            foreach ($curs as $node) {
                if ($node == $n - 1) {
                    return $step;
                }

                foreach ($graph[$arr[$node]] as $child) {
                    if (!isset($visited[$child])) {
                        $visited[$child] = true;
                        $nex[] = $child;
                    }
                }

                $graph[$arr[$node]] = [];

                if ($node + 1 < $n && !isset($visited[$node + 1])) {
                    $visited[$node + 1] = true;
                    $nex[] = $node + 1;
                }
                if ($node - 1 >= 0 && !isset($visited[$node - 1])) {
                    $visited[$node - 1] = true;
                    $nex[] = $node - 1;
                }
            }

            $curs = $nex;
            $step++;
        }

        return -1;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1282. Group the People Given the Group Size They Belong To
Сложность: medium

Есть n человек, которые разделены на неизвестное количество групп. Каждый человек имеет уникальный ID от 0 до n - 1.

Вам дан целочисленный массив groupSizes, где groupSizes[i] - это размер группы, в которой находится человек i. Например, если groupSizes[1] = 3, то человек 1 должен быть в группе размером 3.

Верните список групп таким образом, чтобы каждый человек i находился в группе размером groupSizes[i].

Каждый человек должен быть ровно в одной группе, и каждый человек должен быть в группе. Если существует несколько ответов, верните любой из них. Гарантируется, что для данного ввода существует хотя бы одно правильное решение.

Пример:

Input: groupSizes = [3,3,3,3,3,1,3]
Output: [[5],[0,1,2],[3,4,6]]
Explanation: 
The first group is [5]. The size is 1, and groupSizes[5] = 1.
The second group is [0,1,2]. The size is 3, and groupSizes[0] = groupSizes[1] = groupSizes[2] = 3.
The third group is [3,4,6]. The size is 3, and groupSizes[3] = groupSizes[4] = groupSizes[6] = 3.
Other possible solutions are [[2,1,6],[5],[0,4,3]] and [[5],[0,6,2],[4,3,1]].

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

1⃣Инициализируйте пустой список списков ans для хранения индексов групп. Создайте хэш-таблицу szToGroup, где ключи — целые числа, представляющие размеры групп, а значения — массивы соответствующих индексов в группе.

2⃣Итерируйте по массиву groupSizes, для каждого индекса i:
Вставьте индекс i в список szToGroup[groupSizes[i]].
Если размер списка становится равным groupSizes[i], добавьте его в ans и очистите массив для ключа groupSizes[i] в хэш-таблице szToGroup.

3⃣Верните ans.


😎 Решение:

class Solution {
    function groupThePeople($groupSizes) {
        $ans = [];
        $szToGroup = [];
        
        for ($i = 0; $i < count($groupSizes); $i++) {
            $size = $groupSizes[$i];
            if (!isset($szToGroup[$size])) {
                $szToGroup[$size] = [];
            }
            $szToGroup[$size][] = $i;
            
            if (count($szToGroup[$size]) == $size) {
                $ans[] = $szToGroup[$size];
                $szToGroup[$size] = [];
            }
        }
        
        return $ans;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 674. Longest Continuous Increasing Subsequence
Сложность: easy

Дан неотсортированный массив целых чисел nums, верните длину самой длинной непрерывной возрастающей подпоследовательности (т.е. подмассива). Подпоследовательность должна быть строго возрастающей.
Непрерывная возрастающая подпоследовательность определяется двумя индексами l и r (l < r) так, что она имеет вид [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] и для каждого l <= i < r выполняется nums[i] < nums[i + 1].

Пример:

Input: nums = [1,3,5,4,7]
Output: 3
Explanation: The longest continuous increasing subsequence is [1,3,5] with length 3.
Even though [1,3,5,7] is an increasing subsequence, it is not continuous as elements 5 and 7 are separated by element
4.

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

1⃣Каждая (непрерывная) возрастающая подпоследовательность не пересекается, и граница каждой такой подпоследовательности возникает, когда nums[i-1] >= nums[i]. В этом случае начинается новая возрастающая подпоследовательность с nums[i], и мы сохраняем такой i в переменной anchor.

2⃣Например, если nums = [7, 8, 9, 1, 2, 3], то anchor начинается с 0 (nums[anchor] = 7) и затем устанавливается на anchor = 3 (nums[anchor] = 1). Независимо от значения anchor, мы записываем кандидата на ответ длиной i - anchor + 1, длина подмассива nums[anchor], nums[anchor+1], ..., nums[i], и наш ответ обновляется соответствующим образом.

3⃣Возвращаем максимальную длину найденной непрерывной возрастающей подпоследовательности.

😎 Решение:

class Solution {
    function findLengthOfLCIS($nums) {
        $ans = 0;
        $anchor = 0;
        for ($i = 0; $i < count($nums); ++$i) {
            if ($i > 0 && $nums[$i - 1] >= $nums[$i]) {
                $anchor = $i;
            }
            $ans = max($ans, $i - $anchor + 1);
        }
        return $ans;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 224. Basic Calculator
Сложность: hard

Дана строка s, представляющая собой допустимое выражение, реализуйте базовый калькулятор для его вычисления и верните результат вычисления.
Примечание: нельзя использовать встроенные функции, которые оценивают строки как математические выражения, такие как eval().

Пример:

Input: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23

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

1⃣Итерация строки выражения в обратном порядке:
Читаем выражение символ за символом, формируя операнды из нескольких цифр, если символ - цифра.
Сохраняем операнды в стек, как только встречаем нецифровой символ.

2⃣Обработка выражения внутри скобок:
Когда встречаем открывающую скобку '(', оцениваем выражение, удаляя операнды и операторы из стека до соответствующей закрывающей скобки.
Результат выражения помещаем обратно в стек.

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

😎 Решение:

class Solution {
    private function evaluateExpr(&$stack) {
        if (empty($stack) || !is_int(end($stack))) {
            array_push($stack, 0);
        }

        $res = array_pop($stack);

        while (!empty($stack) && end($stack) !== ')') {
            $sign = array_pop($stack);

            if ($sign === '+') {
                $res += array_pop($stack);
            } else {
                $res -= array_pop($stack);
            }
        }
        return $res;
    }

    public function calculate($s) {
        $operand = 0;
        $n = 0;
        $stack = array();

        for ($i = strlen($s) - 1; $i >= 0; $i--) {
            $ch = $s[$i];

            if (ctype_digit($ch)) {
                $operand = pow(10, $n) * ((int) $ch) + $operand;
                $n += 1;
            } else if ($ch !== ' ') {
                if ($n !== 0) {
                    array_push($stack, $operand);
                    $n = 0;
                    $operand = 0;
                }
                if ($ch === '(') {
                    $res = $this->evaluateExpr($stack);
                    array_pop($stack);
                    array_push($stack, $res);
                } else {
                    array_push($stack, $ch);
                }
            }
        }

        if ($n !== 0) {
            array_push($stack, $operand);
        }

        return $this->evaluateExpr($stack);
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 948. Bag of Tokens
Сложность: medium

Вы начинаете с начальной силой, равной power, начальным счетом 0 и мешком жетонов, представленным в виде целочисленного массива tokens, где каждый tokens[i] обозначает значение tokeni. Ваша цель - максимизировать общее количество очков, стратегически разыгрывая эти жетоны. За один ход вы можете разыграть неразыгранный жетон одним из двух способов (но не обоими для одного и того же жетона): лицом вверх: Если ваша текущая сила не меньше жетонов[i], вы можете сыграть токени, потеряв силу жетонов[i] и получив 1 очко. Лицом вниз: Если ваш текущий счет не меньше 1, вы можете сыграть токени, получив силу токенов[i] и потеряв 1 счет. Верните максимально возможный счет, который вы можете получить, сыграв любое количество токенов.

Пример:

Input: tokens = [100], power = 50

Output: 0

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

1⃣Отсортировать массив tokens.
Использовать два указателя: left и right, чтобы отслеживать начало и конец массива токенов.
Инициализировать переменные для текущей силы power, текущего счета score и максимального счета maxScore

2⃣Повторять следующие шаги, пока left не превысит right:
Если текущая сила power достаточна для разыгрывания токена tokens[left] лицом вверх, разыграть его и увеличить счет.
Если текущая сила недостаточна, но счет больше 0, разыграть токен tokens[right] лицом вниз и уменьшить счет.
Обновить максимальный счет, если текущий счет больше максимального.

3⃣Вернуть максимальный счет.

😎 Решение:

function bagOfTokensScore($tokens, $power) {
    sort($tokens);
    $left = 0;
    $right = count($tokens) - 1;
    $score = 0;
    $maxScore = 0;
    
    while ($left <= $right) {
        if ($power >= $tokens[$left]) {
            $power -= $tokens[$left];
            $score++;
            $left++;
            $maxScore = max($maxScore, $score);
        } elseif ($score > 0) {
            $power += $tokens[$right];
            $score--;
            $right--;
        } else {
            break;
        }
    }
    
    return $maxScore;
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 598. Range Addition II
Сложность: Easy

Вам дана матрица M размером m x n, инициализированная нулями, и массив операций ops, где ops[i] = [ai, bi] означает, что значение M[x][y] должно быть увеличено на единицу для всех 0 <= x < ai и 0 <= y < bi.
Подсчитайте и верните количество максимальных чисел в матрице после выполнения всех операций.

Пример:

Input: m = 3, n = 3, ops = [[2,2],[3,3]]
Output: 4
Explanation: The maximum integer in M is 2, and there are four of it in M. So return 4.

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

1⃣Все операции выполняются на прямоугольной подматрице изначальной матрицы M, заполненной нулями, с верхним левым углом в точке (0,0) и нижним правым углом для операции [i,j] в точке (i,j).

2⃣Максимальный элемент будет тем, на который выполнены все операции. Максимальные элементы будут находиться в области пересечения прямоугольников, представляющих операции. Для определения этой области нужно найти нижний правый угол пересекающейся области (x,y), который равен (min(op[0]), min(op[1])).

3⃣Количество элементов, находящихся в области пересечения, определяется как произведение координат x и y.

😎 Решение:

class Solution {
    function maxCount($m, $n, $ops) {
        $minA = $m;
        $minB = $n;
        foreach ($ops as $op) {
            $minA = min($minA, $op[0]);
            $minB = min($minB, $op[1]);
        }
        return $minA * $minB;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 995. Minimum Number of K Consecutive Bit Flips
Сложность: hard

Дан бинарный массив nums и целое число k.

Операция переворота k-бит заключается в выборе подмассива длиной k из nums и одновременном изменении каждого 0 в подмассиве на 1 и каждого 1 в подмассиве на 0.

Верните минимальное количество k-битных переворотов, необходимых для того, чтобы в массиве не осталось 0. Если это невозможно, верните -1.

Подмассив - это непрерывная часть массива.

Пример:

Input: nums = [0,1,0], k = 1
Output: 2
Explanation: Flip nums[0], then flip nums[2].

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

1⃣Инициализация переменных:
Создайте массив flip, чтобы отслеживать, сколько раз был перевернут каждый элемент.
Инициализируйте flips для отслеживания количества текущих переворотов.

2⃣Перебор элементов массива:
Для каждого элемента определите, необходимо ли его переворачивать, учитывая текущее количество переворотов и значение в массиве.
Если нужно перевернуть, увеличьте счетчик переворотов и обновите массив flip.

3⃣Проверка возможности выполнения задачи:
Если количество переворотов больше длины массива, верните -1.

😎 Решение:

class Solution {
    function minKBitFlips($nums, $k) {
        $n = count($nums);
        $flip = 0;
        $flips = 0;
        $flipQueue = array_fill(0, $n, 0);
        
        for ($i = 0; $i < $n; $i++) {
            if ($i >= $k) {
                $flip ^= $flipQueue[$i - $k];
            }
            if ($nums[$i] == $flip) {
                if ($i + $k > $n) return -1;
                $flips++;
                $flip ^= 1;
                $flipQueue[$i] = 1;
            }
        }
        return $flips;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 340. Longest Substring with At Most K Distinct Characters
Сложность: medium

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

Пример:

Input: n = 27
Output: true
Explanation: 27 = 3^3

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

1⃣Инициализация
Используйте два указателя (left и right) для отслеживания текущего окна в строке. Создайте словарь для отслеживания количества каждого символа в текущем окне. Инициализируйте переменные для хранения максимальной длины подстроки (max_length).

2⃣Раздвижение окна
Перемещайте правый указатель (right) по строке и обновляйте словарь. Если количество различных символов в словаре превышает k, перемещайте левый указатель (left) вправо, уменьшая счетчик символов, пока количество различных символов снова не станет меньше или равно k.

3⃣Обновление максимальной длины
На каждом шаге проверяйте и обновляйте максимальную длину подстроки, если текущее окно содержит не более k различных символов. В конце верните максимальную длину подстроки.

😎 Решение:

class Solution {
    function lengthOfLongestSubstringKDistinct($s, $k) {
        $left = 0;
        $right = 0;
        $charCount = [];
        $maxLength = 0;
        
        while ($right < strlen($s)) {
            $charCount[$s[$right]] = ($charCount[$s[$right]] ?? 0) + 1;
            while (count($charCount) > $k) {
                $charCount[$s[$left]]--;
                if ($charCount[$s[$left]] == 0) {
                    unset($charCount[$s[$left]]);
                }
                $left++;
            }
            $maxLength = max($maxLength, $right - $left + 1);
            $right++;
        }
        
        return $maxLength;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1057. Campus Bikes
Сложность: medium

В городке, изображенном на плоскости X-Y, есть n рабочих и m велосипедов, причем n <= m. Вам дан массив workers длины n, где workers[i] = [xi, yi] - положение i-го рабочего. Вам также дан массив bikes длины m, где bikes[j] = [xj, yj] - позиция j-го велосипеда. Все заданные позиции уникальны. Назначаем велосипед каждому работнику. Среди доступных велосипедов и работников мы выбираем пару (workeri, bikej) с наименьшим манхэттенским расстоянием между ними и назначаем велосипед этому работнику. Если существует несколько пар (workeri, bikej) с одинаковым наименьшим манхэттенским расстоянием, мы выбираем пару с наименьшим индексом работника. Если существует несколько способов сделать это, мы выбираем пару с наименьшим индексом велосипеда. Повторяем этот процесс до тех пор, пока не останется свободных работников. Возвращаем массив answer длины n, где answer[i] - индекс (с индексом 0) велосипеда, на который назначен i-й работник. Манхэттенское расстояние между двумя точками p1 и p2 равно Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.

Пример:

Input: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]
Output: [1,0]

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

1⃣Для каждой пары (работник, велосипед) вычисли Манхэттенское расстояние и сохрани все пары вместе с расстоянием в список.

2⃣Отсортируй список пар по расстоянию, а затем по индексу работника и велосипеда.
Назначь велосипеды работникам, следуя отсортированному списку пар и отслеживая, какие работники и велосипеды уже были использованы.

3⃣Заполни и верни массив назначений.

😎 Решение:

function assignBikes($workers, $bikes) {
    $pairs = [];
    
    for ($i = 0; $i < count($workers); $i++) {
        for ($j = 0; $j < count($bikes); $j++) {
            $distance = abs($workers[$i][0] - $bikes[$j][0]) + abs($workers[$i][1] - $bikes[$j][1]);
            $pairs[] = [$distance, $i, $j];
        }
    }
    
    usort($pairs, function($a, $b) {
        if ($a[0] !== $b[0]) return $a[0] - $b[0];
        if ($a[1] !== $b[1]) return $a[1] - $b[1];
        return $a[2] - $b[2];
    });
    
    $result = array_fill(0, count($workers), -1);
    $bikeTaken = array_fill(0, count($bikes), false);
    $workerAssigned = array_fill(0, count($workers), false);
    
    foreach ($pairs as [$distance, $workerIdx, $bikeIdx]) {
        if (!$workerAssigned[$workerIdx] && !$bikeTaken[$bikeIdx]) {
            $result[$workerIdx] = $bikeIdx;
            $bikeTaken[$bikeIdx] = true;
            $workerAssigned[$workerIdx] = true;
        }
    }
    
    return $result;
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1372. Longest ZigZag Path in a Binary Tree
Сложность: medium

Вам дан корень бинарного дерева.

Зигзагообразный путь для бинарного дерева определяется следующим образом:

Выберите любой узел в бинарном дереве и направление (вправо или влево).
Если текущее направление вправо, перейдите к правому дочернему узлу текущего узла; иначе перейдите к левому дочернему узлу.
Измените направление с вправо на влево или с влево на вправо.
Повторяйте второй и третий шаги, пока не сможете двигаться по дереву.
Длина зигзагообразного пути определяется как количество посещенных узлов минус 1 (один узел имеет длину 0).

Верните длину самого длинного зигзагообразного пути, содержащегося в этом дереве.

Пример:

Input: s = "rat"
Output: "art"
Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.

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

1⃣Рекурсивная функция DFS:
Создайте рекурсивную функцию dfs, которая будет выполнять обход дерева и отслеживать текущую длину зигзагообразного пути и направление движения (влево или вправо).

2⃣Обновление максимальной длины пути:
При каждом вызове рекурсивной функции обновляйте максимальную длину зигзагообразного пути, если текущая длина больше текущего максимума.

3⃣Рекурсивный вызов для левого и правого дочерних узлов:
Рекурсивно вызывайте функцию dfs для левого и правого дочерних узлов с обновленными параметрами длины и направления.

😎 Решение:

class TreeNode {
    public $val;
    public $left;
    public $right;
    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

class Solution {
    private $maxLength = 0;

    function longestZigZag($root) {
        $this->dfs($root, true, 0);
        $this->dfs($root, false, 0);
        return $this->maxLength;
    }

    private function dfs($node, $isLeft, $length) {
        if ($node === null) return;
        $this->maxLength = max($this->maxLength, $length

Ставь 👍 и забирай 📚 Базу знаний

Задача: 126.Word Ladder II
Сложность: Hard

Последовательность преобразований от слова beginWord до слова endWord с использованием словаря wordList — это последовательность слов beginWord -> s1 -> s2 -> ... -> sk, для которой выполняются следующие условия:
Каждая пара соседних слов отличается ровно одной буквой.
Каждое si для 1 <= i <= k находится в wordList. Отметим, что beginWord не обязательно должно быть в wordList.
sk == endWord.
Для двух слов, beginWord и endWord, и словаря wordList, вернуть все самые короткие последовательности преобразований от beginWord до endWord или пустой список, если такая последовательность не существует. Каждая последовательность должна возвращаться в виде списка слов [beginWord, s1, s2, ..., sk].

Пример:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
Explanation: There are 2 shortest transformation sequences:
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
"hit" -> "hot" -> "lot" -> "log" -> "cog"

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

1⃣Сохранение слов из списка слов (wordList) в хэш-таблицу (unordered set) для эффективного удаления слов в процессе поиска в ширину (BFS).

2⃣Выполнение BFS, добавление связей в список смежности (adjList). После завершения уровня удалять посещенные слова из wordList.

3⃣Начать с beginWord и отслеживать текущий путь как currPath, просматривать все возможные пути, и когда путь ведет к endWord, сохранять путь в shortestPaths.

😎 Решение:

class Solution {
    function findLadders($beginWord, $endWord, $wordList) {
        $adjList = [];
        $wordSet = array_flip($wordList);
        $this->bfs($beginWord, $endWord, $wordSet, $adjList);
        $this->currPath = [$endWord];
        $this->shortestPaths = [];
        $this->backtrack($endWord, $beginWord, $adjList);
        return $this->shortestPaths;
    }

    function findNeighbors($word, &$wordSet) {
        $neighbors = [];
        $charList = str_split($word);
        for ($i = 0; $i < strlen($word); $i++) {
            $oldChar = $charList[$i];
            foreach (range('a', 'z') as $c) {
                if ($c != $oldChar) {
                    $charList[$i] = $c;
                    $newWord = implode('', $charList);
                    if (isset($wordSet[$newWord])) {
                        $neighbors[] = $newWord;
                    }
                }
            }
            $charList[$i] = $oldChar;
        }
        return $neighbors;
    }

    function backtrack($source, $destination, &$adjList) {
        if ($source == $destination) {
            $this->shortestPaths[] = array_reverse($this->currPath);
        } else if (isset($adjList[$source])) {
            foreach ($adjList[$source] as $neighbor) {
                array_push($this->currPath, $neighbor);
                $this->backtrack($neighbor, $destination, $adjList);
                array_pop($this->currPath);
            }
        }
    }

    function bfs($beginWord, $endWord, &$wordSet, &$adjList) {
        $queue = [$beginWord];
        unset($wordSet[$beginWord]);

        while ($queue) {
            $currentWord = array_shift($queue);
            $neighbors = $this->findNeighbors($currentWord, $wordSet);

            foreach ($neighbors as $neighbor) {
                $adjList[$neighbor][] = $currentWord;
                if (isset($wordSet[$neighbor])) {
                    unset($wordSet[$neighbor]);
                    $queue[] = $neighbor;
                }
            }
        }
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1207. Unique Number of Occurrences
Сложность: easy

Дан массив целых чисел arr. Верните true, если количество вхождений каждого значения в массиве уникально, или false в противном случае.

Пример:

Input: arr = [1,2,2,1,1,3]
Output: true
Explanation: The value 1 has 3 occurrences, 2 has 2 and 3 has 1. No two values have the same number of occurrences.

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

1⃣Сохраните частоты элементов массива arr в хэш-таблице freq.

2⃣Итерируйтесь по хэш-таблице freq и вставьте частоты всех уникальных элементов массива arr в хэш-набор freqSet.

3⃣Верните true, если размер хэш-набора freqSet равен размеру хэш-таблицы freq, иначе верните false.

😎 Решение:

class Solution {
    /**
     * @param Integer[] $arr
     * @return Boolean
     */
    function uniqueOccurrences($arr) {
        $freq = array_count_values($arr);
        $freqSet = array_unique(array_values($freq));
        return count($freq) == count($freqSet);
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1230. Toss Strange Coins
Сложность: medium

У вас есть несколько монет. Вероятность выпадения орла для i-й монеты равна prob[i].

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

Пример:

Input: prob = [0.5,0.5,0.5,0.5,0.5], target = 0
Output: 0.03125

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

1⃣Инициализация:
Создайте переменную n и инициализируйте её размером массива prob.
Создайте 2D массив dp размером n + 1 строк и target + 1 столбцов, где dp[i][j] хранит вероятность получить j орлов, используя первые i монет.
Установите базовый случай dp[0][0] = 1.

2⃣Итерация:
Используйте два вложенных цикла для заполнения массива dp.
Внешний цикл итерируется от i = 1 до n. Для каждого i установите dp[i][0], что обозначает вероятность получить 0 орлов при использовании i монет: dp[i][0] = dp[i - 1][0] * (1 - prob[i - 1]).
Внутренний цикл итерируется от j = 1 до target. Для каждого j вычислите dp[i][j] по формуле: dp[i][j] = dp[i - 1][j - 1] * prob[i - 1] + dp[i - 1][j] * (1 - prob[i - 1]).

3⃣Возврат результата:
Верните значение dp[n][target], которое содержит искомую вероятность.

😎 Решение:

class Solution {
    function probabilityOfHeads($prob, $target) {
        $n = count($prob);
        $dp = array_fill(0, $n + 1, array_fill(0, $target + 1, 0));
        $dp[0][0] = 1.0;

        for ($i = 1; $i <= $n; $i++) {
            $dp[$i][0] = $dp[$i - 1][0] * (1 - $prob[$i - 1]);
            for ($j = 1; $j <= $target; $j++) {
                if ($j <= $i) {
                    $dp[$i][$j] = $dp[$i - 1][$j - 1] * $prob[$i - 1] + $dp[$i - 1][$j] * (1 - $prob[$i - 1]);
                }
            }
        }

        return $dp[$n][$target];
    }
}

Ставь 👍 и забирай 📚 Базу знаний