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

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

Задача: 260. Single Number III
Сложность: medium

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

Пример:

Input: nums = [1,2,1,3,2,5]
Output: [3,5]
Explanation:  [5, 3] is also a valid answer.

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

1⃣Выполните XOR для всех элементов массива nums. Это даст результат, который является XOR двух уникальных чисел.

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

3⃣Выполните XOR для каждой группы, чтобы найти два уникальных числа.

😎 Решение:

class Solution {
    public function singleNumber($nums) {
        $xor = 0;
        foreach ($nums as $num) {
            $xor ^= $num;
        }
        $diff = $xor & -$xor;
        $res = [0, 0];
        foreach ($nums as $num) {
            if (($num & $diff) == 0) {
                $res[0] ^= $num;
            } else {
                $res[1] ^= $num;
            }
        }
        return $res;
    }
}

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

Задача: 128. Longest Consecutive Sequence
Сложность: Medium

Дан несортированный массив целых чисел nums. Верните длину самой длинной последовательности последовательных элементов.

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

Пример:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

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

1⃣Проверка базового случая:
Перед началом работы проверяем базовый случай с пустым массивом.
Самая длинная последовательность в пустом массиве, очевидно, равна 0, поэтому мы можем просто вернуть это значение.

2⃣Обработка чисел в массиве:
Для всех других случаев мы сортируем массив nums и рассматриваем каждое число, начиная со второго (поскольку нам нужно сравнивать каждое число с предыдущим).
Если текущее число и предыдущее равны, то текущая последовательность не удлиняется и не прерывается, поэтому мы просто переходим к следующему числу.
Если числа не равны, то нужно проверить, удлиняет ли текущее число последовательность (т.е. nums[i] == nums[i-1] + 1). Если удлиняет, то мы увеличиваем наш текущий счёт и продолжаем.

3⃣Завершение обработки и возврат результата:
В противном случае последовательность прерывается, и мы записываем нашу текущую последовательность и сбрасываем её до 1 (чтобы включить число, которое прервало последовательность).
Возможно, что последний элемент массива nums является частью самой длинной последовательности, поэтому мы возвращаем максимум из текущей последовательности и самой длинной.

😎 Решение:

function arrayContains($arr, $num) {
    foreach ($arr as $item) {
        if ($item === $num) {
            return true;
        }
    }
    return false;
}

function longestConsecutive($nums) {
    $longestStreak = 0;
    foreach ($nums as $num) {
        $currentNum = $num;
        $currentStreak = 1;
        while (arrayContains($nums, $currentNum + 1)) {
            $currentNum += 1;
            $currentStreak += 1;
        }
        if ($currentStreak > $longestStreak) {
            $longestStreak = $currentStreak;
        }
    }
    return $longestStreak;
}

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

Задача: 647. Palindromic Substrings
Сложность: medium

Если задана строка s, верните количество палиндромных подстрок в ней. Строка является палиндромом, если она читается так же, как задом наперед. Подстрока - это непрерывная последовательность символов в строке.

Пример:

Input: s = "abc"
Output: 3

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

1⃣Инициализируйте счетчик для подсчета палиндромных подстрок.

2⃣Для каждой позиции в строке используйте два метода расширения: один для палиндромов нечетной длины и один для палиндромов четной длины.

3⃣Расширяйте от центра, проверяя, является ли подстрока палиндромом, и увеличивайте счетчик, если условие выполняется.

😎 Решение:

function countSubstrings($s) {
    $totalCount = 0;

    function expandAroundCenter($s, $left, $right) {
        $count = 0;
        while ($left >= 0 && $right < strlen($s) && $s[$left] == $s[$right]) {
            $count++;
            $left--;
            $right++;
        }
        return $count;
    }

    for ($i = 0; $i < strlen($s); $i++) {
        $totalCount += expandAroundCenter($s, $i, $i);
        $totalCount += expandAroundCenter($s, $i, $i + 1);
    }

    return $totalCount;
}

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

Задача: 291. Word Pattern II
Сложность: medium

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

Пример:

Input: pattern = "abab", s = "redblueredblue"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "red"
'b' -> "blue"

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

1⃣Инициализация структур данных и определение рекурсивной функции:
Создайте хеш-таблицу symbolMap для отображения символов шаблона на подстроки строки s.
Создайте множество wordSet для хранения уникальных подстрок строки s, которые были отображены на символ.
Определите рекурсивную функцию isMatch, принимающую индексы в строке s (sIndex) и в шаблоне (pIndex), чтобы определить, соответствует ли строка s шаблону.

2⃣Рекурсивная проверка соответствия:
Базовый случай: если pIndex равно длине шаблона, верните true, если sIndex равно длине строки s; иначе верните false.
Получите символ из шаблона по индексу pIndex.
Если символ уже ассоциирован с подстрокой, проверьте, совпадают ли следующие символы в строке s с этой подстрокой. Если нет, верните false. Если совпадают, вызовите isMatch для следующего символа в шаблоне.

3⃣Отображение новых подстрок:
Если символ новый, попробуйте сопоставить его с новыми подстроками строки s, начиная с sIndex и до конца строки.
Для каждой новой подстроки проверьте, существует ли она уже в `

😎 Решение:

class Solution {
    function wordPatternMatch($pattern, $s) {
        $symbolMap = [];
        $wordSet = [];
        return $this->isMatch($s, 0, $pattern, 0, $symbolMap, $wordSet);
    }

    private function isMatch($s, $sIndex, $pattern, $pIndex, &$symbolMap, &$wordSet) {
        if ($pIndex == strlen($pattern)) {
            return $sIndex == strlen($s);
        }
        $symbol = $pattern[$pIndex];
        if (isset($symbolMap[$symbol])) {
            $word = $symbolMap[$symbol];
            if (substr($s, $sIndex, strlen($word)) !== $word) {
                return false;
            }
            return $this->isMatch($s, $sIndex + strlen($word), $pattern, $pIndex + 1, $symbolMap, $wordSet);
        }
        for ($k = $sIndex + 1; $k <= strlen($s); $k++) {
            $newWord = substr($s, $sIndex, $k - $sIndex);
            if (in_array($newWord, $wordSet)) {
                continue;
            }
            $symbolMap[$symbol] = $newWord;
            $wordSet[] = $newWord;
            if ($this->isMatch($s, $k, $pattern, $pIndex + 1, $symbolMap, $wordSet)) {
                return true;
            }
            unset($symbolMap[$symbol]);
            array_pop($wordSet);
        }
        return false;
    }
}
?>

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

Задача: 1071. Greatest Common Divisor of Strings
Сложность: easy

Для двух строк s и t мы говорим, что "t делит s", если и только если s = t + t + t + ... + t (т.е. t соединена сама с собой один или более раз).

Даны две строки str1 и str2, верните наибольшую строку x, такую что x делит и str1, и str2.

Пример:

Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"

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

1⃣Найдите более короткую строку среди str1 и str2, для простоты пусть это будет str1.

2⃣Начните с base = str1 и проверьте, состоят ли обе строки str1 и str2 из множителей строки base. Если это так, верните base. В противном случае, попробуйте более короткую строку, удалив последний символ из base.

3⃣Если вы проверили все префиксные строки и не нашли строку GCD, верните "".

😎 Решение:

class Solution {
    function valid($str1, $str2, $k) {
        $len1 = strlen($str1);
        $len2 = strlen($str2);
        if ($len1 % $k > 0 || $len2 % $k > 0) {
            return false;
        } else {
            $base = substr($str1, 0, $k);
            $n1 = intval($len1 / $k);
            $n2 = intval($len2 / $k);
            return $str1 == $this->joinWords($base, $n1) && $str2 == $this->joinWords($base, $n2);
        }
    }

    function joinWords($str, $k) {
        $ans = "";
        for ($i = 0; $i < $k; ++$i) {
            $ans .= $str;
        }
        return $ans;
    }

    function gcdOfStrings($str1, $str2) {
        $len1 = strlen($str1);
        $len2 = strlen($str2);
        for ($i = min($len1, $len2); $i >= 1; --$i) {
            if ($this->valid($str1, $str2, $i)) {
                return substr($str1, 0, $i);
            }
        }
        return "";
    }
}

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

Задача: 675. Cut Off Trees for Golf Event
Сложность: hard

Есть лес в виде матрицы. В каждой ячейке:
0 — непроходимо
1 — проходимо
>1 — дерево (высота = значение)
Нужно срубить все деревья в порядке возрастания высоты, начиная с (0, 0), минимизируя количество шагов. Если добраться до какого-то дерева невозможно — вернуть -1.

Пример:

Input: forest = [[1,2,3],[0,0,4],[7,6,5]]
Output: 6
Explanation: Following the path above allows you to cut off the trees from shortest to tallest in 6 steps.

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

1⃣Начиная с (0, 0), для каждого дерева в порядке возрастания высоты будем вычислять расстояние от текущего местоположения до следующего дерева (и перемещаться туда), добавляя это расстояние к ответу.

2⃣Формулируем задачу как предоставление функции расстояния dist(forest, sr, sc, tr, tc), которая вычисляет расстояние от точки (sr, sc) до цели (tr, tc) с учетом препятствий, где dist[i][j] == 0. (Эта функция расстояния вернет -1, если путь невозможен.)

3⃣Далее следует код и анализ сложности, которые общие для всех трех подходов. Затем алгоритмы, представленные в наших подходах, будут сосредоточены только на предоставлении нашей функции dist.

😎 Решение:

function cutOffTree($forest) {
    $trees = [];
    $rows = count($forest);
    $cols = count($forest[0]);

    for ($r = 0; $r < $rows; $r++) {
        for ($c = 0; $c < $cols; $c++) {
            if ($forest[$r][$c] > 1) {
                $trees[] = [$forest[$r][$c], $r, $c];
            }
        }
    }

    usort($trees, function($a, $b) {
        return $a[0] - $b[0];
    });

    $sr = 0;
    $sc = 0;
    $ans = 0;

    foreach ($trees as $tree) {
        [$value, $tr, $tc] = $tree;
        $d = dist($forest, $sr, $sc, $tr, $tc);
        if ($d < 0) {
            return -1;
        }
        $ans += $d;
        $sr = $tr;
        $sc = $tc;
    }

    return $ans;
}

function dist($forest, $sr, $sc, $tr, $tc) {
    
    return 0;
}

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

Задача: 130. Surrounded Regions
Сложность: Medium

Вам дана матрица размером m на n, которая содержит буквы 'X' и 'O'. Захватите регионы, которые окружены:

Соединение: Ячейка соединена с соседними ячейками по горизонтали или вертикали.
Регион: Для формирования региона соедините каждую ячейку 'O'.
Окружение: Регион окружён ячейками 'X', если можно соединить регион с ячейками 'X', и ни одна из ячеек региона не находится на краю доски.
Окруженный регион захватывается путём замены всех 'O' на 'X' в исходной матрице.

Пример:

Input: board = [["X"]]

Output: [["X"]]

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

1⃣Выбор начальных ячеек и инициация DFS:
Начинаем с выбора всех ячеек, расположенных на границах доски.
Затем, начиная с каждой выбранной ячейки на границе, выполняем обход в глубину (DFS).

2⃣Логика и выполнение DFS:
Если ячейка на границе оказывается 'O', это означает, что эта ячейка "жива", вместе с другими ячейками 'O', соединёнными с этой граничной ячейкой. Две ячейки считаются соединёнными, если между ними существует путь, состоящий только из букв 'O'.
Цель нашего обхода DFS будет заключаться в том, чтобы отметить все такие связанные ячейки 'O', которые исходят из границы, каким-либо отличительным символом, например, 'E'.

3⃣Классификация и финальная обработка ячеек:
После обхода всех граничных ячеек мы получаем три типа ячеек:
Ячейки с буквой 'X': эти ячейки можно считать стеной.
Ячейки с буквой 'O': эти ячейки не затрагиваются в нашем обходе DFS, то есть они не имеют соединения с границей, следовательно, они захвачены. Эти ячейки следует заменить на букву 'X'.
Ячейки с буквой 'E': это ячейки, отмеченные в ходе нашего обхода DFS, то есть ячейки, имеющие хотя бы одно соединение с границами, следовательно, они не захвачены. В результате мы должны вернуть этим ячейкам их исходную букву 'O'.

😎 Решение:

function solve(&$board) {
    if ($board == null || count($board) == 0) {
        return;
    }
    $ROWS = count($board);
    $COLS = count($board[0]);
    $borders = [];
    for ($r = 0; $r < $ROWS; ++$r) {
        array_push($borders, [$r, 0], [$r, $COLS - 1]);
    }
    for ($c = 0; $c < $COLS; ++$c) {
        array_push($borders, [0, $c], [$ROWS - 1, $c]);
    }
    foreach ($borders as $pair) {
        dfs($board, $pair[0], $pair[1]);
    }
    for ($r = 0; $r < $ROWS; ++$r) {
        for ($c = 0; $c < $COLS; ++$c) {
            if ($board[$r][$c] == "O") $board[$r][$c] = "X";
            if ($board[$r][$c] == "E") $board[$r][$c] = "O";
        }
    }
}

function dfs(&$board, $row, $col) {
    if ($board[$row][$col] != "O") return;
    $board[$row][$col] = "E";
    $ROWS = count($board);
    $COLS = count($board[0]);
    if ($col < $COLS - 1) dfs($board, $row, $col + 1);
    if ($row < $ROWS - 1) dfs($board, $row + 1, $col);
    if ($col > 0) dfs($board, $row, $col - 1);
    if ($row > 0) dfs($board, $row - 1, $col);
}

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

Задача: 382. Linked List Random Node
Сложность: medium

Дан односвязный список, вернуть значение случайного узла из списка. Каждый узел должен иметь одинаковую вероятность быть выбранным.
Реализуйте класс Solution:
Solution(ListNode head) Инициализирует объект с головой односвязного списка head.
int getRandom() Выбирает узел случайным образом из списка и возвращает его значение. Все узлы списка должны иметь равные шансы быть выбранными.

Пример:

Input
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
Output
[null, 1, 3, 2, 2, 3]

Explanation
Solution solution = new Solution([1, 2, 3]);
solution.getRandom(); // return 1
solution.getRandom(); // return 3
solution.getRandom(); // return 2
solution.getRandom(); // return 2
solution.getRandom(); // return 3
// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.

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

1⃣Реализуйте интерфейс init(head), который будет вызываться при создании объекта. Преобразуйте связанный список в массив для дальнейшего использования.

2⃣В интерфейсе init(head) преобразуйте переданный связанный список в массив, чтобы его можно было использовать позже.

3⃣Реализуйте функцию getRandom(), которая будет выбирать случайный элемент из массива, созданного на первом этапе.

😎 Решение:

class ListNode {
    public $val;
    public $next;
    public function __construct($val = 0, $next = null) {
        $this->val = $val;
        $this->next = $next;
    }
}

class Solution {
    private $range = array();

    public function __construct($head) {
        while ($head !== null) {
            $this->range[] = $head->val;
            $head = $head->next;
        }
    }

    public function getRandom() {
        $pick = rand(0, count($this->range) - 1);
        return $this->range[$pick];
    }
}
?>

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

Задача: 1247. Minimum Swaps to Make Strings Equal
Сложность: hard

Вам даны две строки s1 и s2 одинаковой длины, состоящие только из букв "x" и "y". Ваша задача - сделать эти две строки равными друг другу. Вы можете поменять местами любые два символа, принадлежащие разным строкам, что означает: поменять местами s1[i] и s2[j]. Верните минимальное количество обменов, необходимое для того, чтобы сделать s1 и s2 равными, или верните -1, если это невозможно сделать.

Пример:

Input: arr = [1,2]
Output: 2

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

1⃣Подсчет несоответствующих пар:
Пройдите по строкам s1 и s2, чтобы подсчитать количество пар xy и yx. Пара xy возникает, когда s1[i] равно 'x', а s2[i] равно 'y'. Пара yx возникает, когда s1[i] равно 'y', а s2[i] равно 'x'.

2⃣Проверка четности:
Если сумма количества пар xy и yx нечетная, то невозможно сделать строки равными, поскольку каждая замена уменьшает сумму несоответствующих пар на 2. В этом случае верните -1.

3⃣Вычисление минимального количества замен:
Если количество пар xy четное и количество пар yx четное, то каждые две пары xy и каждые две пары yx можно обменять за один ход. Поэтому минимальное количество замен равно xy // 2 + yx // 2.
Если количество пар xy нечетное и количество пар yx нечетное, то мы можем обменять одну пару xy и одну пару yx за два хода. Поэтому минимальное количество замен равно xy // 2 + yx // 2 + 2.

😎 Решение:

function minimumSwap($s1, $s2) {
    $xy = 0;
    $yx = 0;
    for ($i = 0; $i < strlen($s1); $i++) {
        if ($s1[$i] === 'x' && $s2[$i] === 'y') {
            $xy++;
        } else if ($s1[$i] === 'y' && $s2[$i] === 'x') {
            $yx++;
        }
    }
    if (($xy + $yx) % 2 != 0) {
        return -1;
    }
    return intdiv($xy, 2) + intdiv($yx, 2) + ($xy % 2) * 2;
}

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

Задача: 78. Subsets
Сложность: medium

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

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

Пример:

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

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

1⃣Определяем функцию обратного отслеживания под названием backtrack(first, curr), которая принимает индекс первого элемента, который нужно добавить, и текущую комбинацию в качестве аргументов.

2⃣Если текущая комбинация завершена, мы добавляем её в итоговый вывод.

3⃣В противном случае перебираем индексы i от first до длины всей последовательности n, добавляем элемент nums[i] в текущую комбинацию curr, продолжаем добавлять больше чисел в комбинацию: backtrack(i + 1, curr) и возвращаемся, удаляя nums[i] из curr.

😎 Решение:

function subsets($nums) {
    $output = [];
    $n = count($nums);
    
    function backtrack($first, $curr, $k, &$output, $nums, $n) {
        if (count($curr) == $k) {
            $output[] = $curr;
            return;
        }
        for ($i = $first; $i < $n; $i++) {
            $curr[] = $nums[$i];
            backtrack($i + 1, $curr, $k, $output, $nums, $n);
            array_pop($curr);
        }
    }
    
    for ($k = 0; $k <= $n; $k++) {
        backtrack(0, [], $k, $output, $nums, $n);
    }
    return $output;
}

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

Задача: 134. Gas Station
Сложность: medium

Вдоль кругового маршрута расположены n заправочных станций, на каждой из которых находится определённое количество топлива gas[i].
У вас есть автомобиль с неограниченным топливным баком, и для проезда от i-й станции к следующей (i + 1)-й станции требуется cost[i] топлива. Путешествие начинается с пустым баком на одной из заправочных станций.
Учитывая два массива целых чисел gas и cost, верните индекс начальной заправочной станции, если вы можете проехать вокруг цепи один раз по часовой стрелке, в противном случае верните -1. Если решение существует, оно гарантированно будет уникальным.

Пример:

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.

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

1⃣Инициализируйте переменные curr_gain, total_gain и answer значением 0.

2⃣Пройдите по массивам gas и cost. Для каждого индекса i увеличивайте total_gain и curr_gain на gas[i] - cost[i].
Если curr_gain меньше 0, проверьте, может ли станция i + 1 быть начальной станцией: установите answer как i + 1, сбросьте curr_gain до 0 и повторите шаг 2.

3⃣По завершении итерации, если total_gain меньше 0, верните -1. В противном случае верните answer.

😎 Решение:

function canCompleteCircuit($gas, $cost) {
    $currGain = 0;
    $totalGain = 0;
    $answer = 0;
    for ($i = 0; $i < count($gas); ++$i) {
        $totalGain += $gas[$i] - $cost[$i];
        $currGain += $gas[$i] - $cost[$i];
        if ($currGain < 0) {
            $answer = $i + 1;
            $currGain = 0;
        }
    }
    return $totalGain >= 0 ? $answer : -1;
}

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

Задача: 762. Prime Number of Set Bits in Binary Representation
Сложность: hard

Если даны два целых числа left и right, верните количество чисел в диапазоне [left, right], имеющих простое число битов в двоичном представлении. Напомним, что число битов в двоичном представлении - это количество единиц, присутствующих в числе 1. Например, 21 в двоичном представлении - это 10101, которое имеет 3 бита.

Пример:

Input: left = 10, right = 15
Output: 5

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

1⃣Создайте функцию для подсчета количества единиц в двоичном представлении числа.

2⃣Создайте функцию для проверки, является ли число простым.

3⃣Пройдите через все числа в диапазоне [left, right] и подсчитайте числа, у которых количество битов в двоичном представлении является простым числом.

😎 Решение:

function countPrimeSetBits($left, $right) {
    function countBits($x) {
        return substr_count(decbin($x), '1');
    }
    
    function isPrime($x) {
        if ($x < 2) return false;
        for ($i = 2; $i * $i <= $x; $i++) {
            if ($x % $i == 0) return false;
        }
        return true;
    }
    
    $count = 0;
    for ($num = $left; $num <= $right; $num++) {
        if (isPrime(countBits($num))) {
            $count++;
        }
    }
    return $count;
}

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

Задача: 734. Sentence Similarity
Сложность: easy

Мы можем представить предложение в виде массива слов, например, предложение "I am happy with leetcode" можно представить как arr = ["I", "am",happy", "with", "leetcode"].
Даны два предложения sentence1 и sentence2, каждое из которых представлено в виде массива строк, и массив пар строк similarPairs, где similarPairs[i] = [xi, yi] указывает, что два слова xi и yi похожи. Возвращается true, если предложения sentence1 и sentence2 похожи, или false, если они не похожи. Два предложения похожи, если: у них одинаковая длина (т.е, Заметьте, что слово всегда похоже само на себя, также обратите внимание, что отношение сходства не является транзитивным. Например, если слова a и b похожи, а слова b и c похожи, то a и c не обязательно похожи.

Пример:

Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","fine"],["drama","acting"],["skills","talent"]]
Output: true

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

1⃣Проверьте, равны ли длины предложений sentence1 и sentence2. Если нет, верните false.

2⃣Создайте словарь для хранения всех пар похожих слов.

3⃣Проверьте каждую пару слов из предложений sentence1 и sentence2 на схожесть, используя словарь и правило, что слово всегда похоже на само себя.

😎 Решение:

function areSentencesSimilar($sentence1, $sentence2, $similarPairs) {
    if (count($sentence1) != count($sentence2)) {
        return false;
    }

    $similar = [];
    foreach ($similarPairs as $pair) {
        list($x, $y) = $pair;
        if (!isset($similar[$x])) {
            $similar[$x] = [];
        }
        if (!isset($similar[$y])) {
            $similar[$y] = [];
        }
        $similar[$x][] = $y;
        $similar[$y][] = $x;
    }

    for ($i = 0; $i < count($sentence1); $i++) {
        $w1 = $sentence1[$i];
        $w2 = $sentence2[$i];
        if ($w1 != $w2 && (!isset($similar[$w1]) || !in_array($w2, $similar[$w1]))) {
            return false;
        }
    }

    return true;
}

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

Задача: 677. Map Sum Pairs
Сложность: medium

Создайте карту, которая позволяет выполнять следующие действия:
Отображает строковый ключ на заданное значение.
Возвращает сумму значений, у которых ключ имеет префикс, равный заданной строке.
Реализуйте класс MapSum:
MapSum() Инициализирует объект MapSum.
void insert(String key, int val) Вставляет пару ключ-значение в карту. Если ключ уже существовал, исходная пара ключ-значение будет заменена на новую.
int sum(string prefix) Возвращает сумму всех значений пар, у которых ключ начинается с данного префикса.

Пример:

Input
["MapSum", "insert", "sum", "insert", "sum"]
[[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]
Output
[null, null, 3, null, 5]

Explanation
MapSum mapSum = new MapSum();
mapSum.insert("apple", 3);  
mapSum.sum("ap");           // return 3 (apple = 3)
mapSum.insert("app", 2);    
mapSum.sum("ap");           // return 5 (apple + app = 3 + 2 = 5)

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

1⃣Для каждого ключа в карте проверить, начинается ли этот ключ с данного префикса.

2⃣Если ключ начинается с префикса, добавить его значение к ответу.

3⃣Вернуть полученную сумму как результат.

😎 Решение:

class MapSum {
    private $mapData;

    public function __construct() {
        $this->mapData = [];
    }

    public function insert($key, $val) {
        $this->mapData[$key] = $val;
    }

    public function sum($prefix) {
        $ans = 0;
        foreach ($this->mapData as $key => $val) {
            if (strpos($key, $prefix) === 0) {
                $ans += $val;
            }
        }
        return $ans;
    }
}

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

Задача: 322. Coin Change
Сложность: medium

Дан целочисленный массив coins, представляющий монеты разных номиналов, и целое число amount, представляющее общую сумму денег.
Верните минимальное количество монет, необходимых для составления этой суммы. Если эту сумму невозможно составить с помощью комбинации монет, верните -1.
Вы можете предположить, что у вас есть неограниченное количество монет каждого типа.

Пример:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

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

1⃣Инициализация и вызов функции backtracking
Инициализируйте переменные для хранения минимального количества монет и вызовите функцию backtracking с начальными параметрами.

2⃣Функция backtracking
Внутри функции backtracking для каждой монеты из массива coins:
Проверьте все возможные количества монет данного номинала (от 0 до максимального количества, которое можно использовать без превышения amount). Для каждой комбинации монет обновите сумму и вызовите функцию рекурсивно для проверки оставшейся суммы. Если текущая комбинация дает меньшую сумму монет, обновите минимальное количество монет.

3⃣Возврат результата
Если комбинация, дающая сумму amount, найдена, верните минимальное количество монет, иначе верните -1.

😎 Решение:

class Solution {
    public function coinChange($coins, $amount) {
        return $this->coinChangeHelper(0, $coins, $amount);
    }

    private function coinChangeHelper($idxCoin, $coins, $amount) {
        if ($amount == 0) return 0;
        if ($idxCoin < count($coins) && $amount > 0) {
            $maxVal = intdiv($amount, $coins[$idxCoin]);
            $minCost = PHP_INT_MAX;
            for ($x = 0; $x <= $maxVal; $x++) {
                if ($amount >= $x * $coins[$idxCoin]) {
                    $res = $this->coinChangeHelper($idxCoin + 1, $coins, $amount - $x * $coins[$idxCoin]);
                    if ($res != -1) {
                        $minCost = min($minCost, $res + $x);
                    }
                }
            }
            return $minCost == PHP_INT_MAX ? -1 : $minCost;
        }
        return -1;
    }
}

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

Задача: 459. Repeated Substring Pattern
Сложность: easy

Дана строка s, проверьте, может ли она быть построена путем взятия подстроки и добавления нескольких копий этой подстроки друг за другом.

Пример:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

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

1⃣Создайте целочисленную переменную n, равную длине строки s.

2⃣Итерация по всем префиксным подстрокам длины i от 1 до n/2:
Если i делит n, объявите пустую строку pattern. Используйте внутренний цикл, который выполняется n/i раз для конкатенации подстроки, сформированной из первых i символов строки s.
Если pattern равен s, вернуть true.

3⃣Если нет подстроки, которую можно повторить для формирования s, вернуть false.

😎 Решение:

class Solution {
    public function repeatedSubstringPattern($s) {
        $n = strlen($s);
        for ($i = 1; $i <= $n / 2; $i++) {
            if ($n % $i == 0) {
                $pattern = "";
                $substr = substr($s, 0, $i);
                for ($j = 0; $j < $n / $i; $j++) {
                    $pattern .= $substr;
                }
                if ($s == $pattern) {
                    return true;
                }
            }
        }
        return false;
    }
}

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