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

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