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

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