PHP | LeetCode

Задача: 1669. Merge In Between Linked Lists
Сложность: medium

Вам даны два связанных списка: list1 и list2 размером n и m соответственно.

Удалите узлы list1 с ath узла по bth узел и вставьте на их место list2.

Синие ребра и узлы на рисунке в вверху поста указывают на результат:

Пример:

Input: list1 = [10,1,13,6,9,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
Output: [10,1,13,1000000,1000001,1000002,5]
Explanation: We remove the nodes 3 and 4 and put the entire list2 in their place. The blue edges and nodes in the above figure indicate the result.

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

1⃣Инициализация и добавление узлов из list1 до узла a в массив:

Инициализировать переменную index равную 0 и current1 равную list1.
Пока index меньше a, добавлять current1.val в массив mergeArray, перемещаться к следующему узлу current1.next и увеличивать index.

2⃣Добавление узлов из list2 в массив:
Инициализировать current2 равную list2.
Пока current2 не равен null, добавлять current2.val в mergeArray и перемещаться к следующему узлу current2.next.

3⃣Добавление узлов из list1 от узла b + 1 до конца в массив и создание нового связанного списка:
Найти узел на позиции b + 1, перемещая current1 и увеличивая index, пока index меньше b + 1.
Добавлять узлы из current1 в массив, пока current1 не станет null.
Создать новый связанный список из значений в mergeArray, добавляя узлы в начало списка и возвращая его.

😎 Решение:

class Solution {
    function mergeInBetween($list1, $a, $b, $list2) {
        $mergeArray = [];
        $index = 0;
        $current1 = $list1;
        
        while ($index < $a) {
            $mergeArray[] = $current1->val;
            $current1 = $current1->next;
            $index++;
        }
        
        $current2 = $list2;
        while ($current2 !== null) {
            $mergeArray[] = $current2->val;
            $current2 = $current2->next;
        }
        
        while ($index < $b + 1) {
            $current1 = $current1->next;
            $index++;
        }
        
        while ($current1 !== null) {
            $mergeArray[] = $current1->val;
            $current1 = $current1->next;
        }
        
        $resultList = null;
        for ($i = count($mergeArray) - 1; $i >= 0; $i--) {
            $resultList = new ListNode($mergeArray[$i], $resultList);
        }
        
        return $resultList;
    }
}

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

Задача: 437. Path Sum III
Сложность: medium

Дан корень бинарного дерева и целое число targetSum, вернуть количество путей, где сумма значений вдоль пути равна targetSum.
Путь не обязательно должен начинаться или заканчиваться в корне или на листе, но он должен идти вниз (т.е. перемещаться только от родительских узлов к дочерним).

Пример:

Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output: 3
Explanation: The paths that sum to 8 are shown.

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

1⃣Инициализируем счетчик путей в дереве count = 0 и хеш-таблицу h, где ключ - это префиксная сумма, а значение - сколько раз она встречалась. Выполним рекурсивный обход дерева в порядке preorder: узел -> левый -> правый. Функция preorder(node: TreeNode, curr_sum: int) принимает два аргумента: узел дерева и префиксную сумму перед этим узлом. Чтобы запустить рекурсию, вызовем preorder(root, 0).

2⃣Сначала обновим текущую префиксную сумму, добавив значение текущего узла: curr_sum += node.val. Теперь можно обновить счетчик. Рассмотрим две ситуации. В первой ситуации путь в дереве с целевой суммой начинается с корня. Это означает, что текущая префиксная сумма равна целевой сумме curr_sum == k, поэтому увеличиваем счетчик на 1: count += 1. Во второй ситуации путь с целевой суммой начинается где-то ниже. Это означает, что нужно добавить к счетчику количество раз, когда мы видели префиксную сумму curr_sum - target: count += h[curr_sum - target].

3⃣Логика проста: текущая префиксная сумма - это curr_sum, а несколько элементов назад префиксная сумма была curr_sum - target. Все элементы между ними суммируются до curr_sum - (curr_sum - target) = target. Теперь обновим хеш-таблицу: h[curr_sum] += 1. Проанализируем левое и правое поддеревья: preorder(node.left, curr_sum), preorder(node.right, curr_sum). После обработки текущего поддерева удалим текущую префиксную сумму из хеш-таблицы, чтобы не смешивать параллельные поддеревья: h[curr_sum] -= 1. Когда обход в порядке preorder завершен, счетчик обновлен. Вернем его.

😎 Решение:

class Solution {
    function pathSum($root, $sum) {
        $count = 0;
        $k = $sum;
        $h = [];
        
        $preorder = function($node, $curr_sum) use (&$preorder, &$count, &$h, $k) {
            if (!$node) return;
            $curr_sum += $node->val;
            if ($curr_sum == $k) {
                $count++;
            }
            $count += $h[$curr_sum - $k] ?? 0;
            $h[$curr_sum] = ($h[$curr_sum] ?? 0) + 1;
            $preorder($node->left, $curr_sum);
            $preorder($node->right, $curr_sum);
            $h[$curr_sum]--;
        };
        
        $preorder($root, 0);
        return $count;
    }
}

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

Задача: 258. Add Digits
Сложность: easy

Дано целое число num. Повторно складывайте все его цифры, пока результат не станет однозначным, и верните его.

Пример:

Input: num = 38
Output: 2
Explanation: The process is
38 --> 3 + 8 --> 11
11 --> 1 + 1 --> 2 
Since 2 has only one digit, return it.

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

1⃣Инициализируйте переменную digital_root значением 0.

2⃣В цикле, пока num больше 0:
Добавьте к digital_root последнюю цифру num.
Уменьшите num, удалив последнюю цифру.
Если num равно 0 и digital_root больше 9, присвойте num значение digital_root и сбросьте digital_root в 0.

3⃣Верните значение digital_root.

😎 Решение:

class Solution {
    function addDigits($num) {
        $digital_root = 0
        while ($num > 0) {
            $digital_root += $num % 10
            $num = intdiv($num, 10)
            if ($num == 0 && $digital_root > 9) {
                $num = $digital_root
                $digital_root = 0
            }
        }
        return $digital_root
    }
}

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

Задача: 419. Battleships in a Board
Сложность: medium

Если задана матричная доска размером m x n, где каждая клетка - линкор 'X' или пустая '.', верните количество линкоров на доске. Линкоры могут располагаться на доске только горизонтально или вертикально. Другими словами, они могут быть выполнены только в форме 1 x k (1 строка, k столбцов) или k x 1 (k строк, 1 столбец), где k может быть любого размера. Между двумя линкорами есть хотя бы одна горизонтальная или вертикальная клетка (т. е. нет соседних линкоров).

Пример:

Input: board = [["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]]
Output: 2

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

1⃣Пройдите по каждой клетке матрицы.

2⃣Если текущая клетка содержит 'X' и она не является продолжением линкора (т.е. не имеет 'X' сверху или слева), увеличьте счетчик линкоров.

3⃣Верните итоговый счетчик.

😎 Решение:

function countBattleships($board) {
    $m = count($board);
    $n = count($board[0]);
    $count = 0;
    
    for ($i = 0; $i < $m; $i++) {
        for ($j = 0; $j < $n; $j++) {
            if ($board[$i][$j] == 'X') {
                if (($i == 0 || $board[$i-1][$j] != 'X') && ($j == 0 || $board[$i][$j-1] != 'X')) {
                    $count++;
                }
            }
        }
    }
    
    return $count;
}

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

Задача: 986. Interval List Intersections
Сложность: medium

Вам даны два списка закрытых интервалов, firstList и secondList, где firstList[i] = [starti, endi] и secondList[j] = [startj, endj]. Каждый список интервалов является попарно непересекающимся и отсортированным.

Верните пересечение этих двух списков интервалов.

Закрытый интервал [a, b] (где a <= b) обозначает множество действительных чисел x с a <= x <= b.

Пересечение двух закрытых интервалов - это множество действительных чисел, которые либо пусты, либо представлены как закрытый интервал. Например, пересечение [1, 3] и [2, 4] равно [2, 3].

Пример:

Input: firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

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

1⃣Инициализация указателей:
Завести два указателя i и j, указывающие на начало firstList и secondList соответственно.

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

3⃣Возврат результата:
Вернуть список пересечений.

😎 Решение:

class Solution {
    function intervalIntersection($firstList, $secondList) {
        $i = 0;
        $j = 0;
        $result = [];
        
        while ($i < count($firstList) && $j < count($secondList)) {
            $start = max($firstList[$i][0], $secondList[$j][0]);
            $end = min($firstList[$i][1], $secondList[$j][1]);
            
            if ($start <= $end) {
                $result[] = [$start, $end];
            }
            
            if ($firstList[$i][1] < $secondList[$j][1]) {
                $i++;
            } else {
                $j++;
            }
        }
        
        return $result;
    }
}

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

Задача: 406. Queue Reconstruction by Height
Сложность: medium

Вам дан массив людей, people, которые являются атрибутами некоторых людей в очереди (не обязательно по порядку). Каждый people[i] = [hi, ki] представляет собой человека ростом hi, перед которым стоят ровно ki других людей, чей рост больше или равен hi. Реконструируйте и верните очередь, представленную входным массивом people. Возвращаемая очередь должна быть отформатирована как массив queue, где queue[j] = [hj, kj] - это атрибуты j-го человека в очереди (queue[0] - человек, находящийся в начале очереди).

Пример:

Input: people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
Output: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

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

1⃣Отсортируйте массив people по убыванию роста hi. Если два человека имеют одинаковый рост, отсортируйте их по возрастанию значения ki.

2⃣Создайте пустой список для результата. Вставляйте каждого человека из отсортированного массива в список на позицию, соответствующую значению ki.

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

😎 Решение:

function reconstructQueue($people) {
    usort($people, function($a, $b) {
        return $a[0] === $b[0] ? $a[1] <=> $b[1] : $b[0] <=> $a[0];
    });
    $result = [];
    foreach ($people as $person) {
        array_splice($result, $person[1], 0, [$person]);
    }
    return $result;
}

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

Задача: 1533. Find the Index of the Large Integer
Сложность: medium

У нас есть целочисленный массив arr, в котором все элементы равны, кроме одного элемента, который больше остальных. Вам не будет предоставлен прямой доступ к массиву, вместо этого у вас будет API ArrayReader, который имеет следующие функции:

int compareSub(int l, int r, int x, int y): где 0 <= l, r, x, y < ArrayReader.length(), l <= r и x <= y. Функция сравнивает сумму подмассива arr[l..r] с суммой подмассива arr[x..y] и возвращает:
1, если arr[l] + arr[l+1] + ... + arr[r] > arr[x] + arr[x+1] + ... + arr[y].
0, если arr[l] + arr[l+1] + ... + arr[r] == arr[x] + arr[x+1] + ... + arr[y].
-1, если arr[l] + arr[l+1] + ... + arr[r] < arr[x] + arr[x+1] + ... + arr[y].

int length(): Возвращает размер массива.

Вам разрешено вызывать compareSub() не более 20 раз. Вы можете предположить, что обе функции работают за O(1) время.

Верните индекс массива arr, который содержит наибольший элемент.

Пример:

Input: arr = [7,7,7,7,10,7,7,7]
Output: 4
Explanation: The following calls to the API
reader.compareSub(0, 0, 1, 1) // returns 0 this is a query comparing the sub-array (0, 0) with the sub array (1, 1), (i.e. compares arr[0] with arr[1]).
Thus we know that arr[0] and arr[1] doesn't contain the largest element.
reader.compareSub(2, 2, 3, 3) // returns 0, we can exclude arr[2] and arr[3].
reader.compareSub(4, 4, 5, 5) // returns 1, thus for sure arr[4] is the largest element in the array.
Notice that we made only 3 calls, so the answer is valid.

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

1⃣ Установите left = 0 и length = reader.length. left - это самый левый индекс нашего поискового пространства, а length - это размер нашего поискового пространства. Индекс большего числа всегда должен находиться в пределах [left, left + length).

2⃣Пока length > 1:
— Обновите length до length / 2.
— Установите cmp равным reader.compareSub(left, left + length - 1, left + length, left + length + length - 1).
— Если cmp равно 0, верните left + length + length, так как оставшийся элемент является большим числом. Это возможно только если текущее поисковое пространство имеет нечетную длину, поэтому если у нас четная длина, мы не беспокоимся об этом случае.
— Если cmp равно -1, увеличьте left на length.
— Если cmp равно 1, ничего не делайте, так как наш left остается прежним и мы уже разделили length на 2.

3⃣Верните left. Это стандартная процедура для бинарного поиска, когда если поиск завершается без возврата, то левая граница указывает на ответ.

😎 Решение:

class Solution {
    function getIndex($reader) {
        $left = 0;
        $length = $reader->length();
        while ($length > 1) {
            $length = intdiv($length, 2);
            $cmp = $reader->compareSub($left, $left + $length - 1, $left + $length, $left + 2 * $length - 1);
            if ($cmp == 0) {
                return $left + 2 * $length;
            }
            if ($cmp < 0) {
                $left += $length;
            }
        }
        return $left;
    }
}

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

Задача: 106. Construct Binary Tree from Inorder and Postorder Traversal
Сложность: medium

Даны два массива целых чисел: inorder и postorder, где inorder — это массив обхода в глубину бинарного дерева слева направо, а postorder — это массив обхода в глубину после обработки всех потомков узла. Постройте и верните соответствующее бинарное дерево.

Пример:

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]

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

1⃣Создайте хэш-таблицу (hashmap) для хранения соответствия значений и их индексов в массиве обхода inorder.

2⃣Определите вспомогательную функцию helper, которая принимает границы левой и правой части текущего поддерева в массиве inorder. Эти границы используются для проверки, пусто ли поддерево. Если левая граница больше правой (in_left > in_right), то поддерево пустое и функция возвращает None.

3⃣Выберите последний элемент в массиве обхода postorder в качестве корня. Значение корня имеет индекс index в обходе inorder. Элементы от in_left до index - 1 принадлежат левому поддереву, а элементы от index + 1 до in_right — правому поддереву. Согласно логике обхода postorder, сначала рекурсивно строится правое поддерево helper(index + 1, in_right), а затем левое поддерево helper(in_left, index - 1). Возвращается корень.

😎 Решение:

function buildTree($inorder, $postorder) {
    $idx_map = [];
    $post_idx = count($postorder) - 1;
    $helper = function($in_left, $in_right) use (&$helper, &$postorder, &$idx_map, &$post_idx) {
        if ($in_left > $in_right) return null;
        $root_val = $postorder[$post_idx];
        $root = new TreeNode($root_val);
        $index = $idx_map[$root_val];
        $post_idx--;
        $root->right = $helper($index + 1, $in_right);
        $root->left = $helper($in_left, $index - 1);
        return $root;
    };
    foreach ($inorder as $i => $val) {
        $idx_map[$val] = $i;
    }
    return $helper(0, count($inorder) - 1);
}

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

Задача: 849. Maximize Distance to Closest Person
Сложность: medium

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

Верните это максимальное расстояние до ближайшего человека.

Пример:

Input: seats = [1,0,0,0,1,0,1]
Output: 2
Explanation: 
If Alex sits in the second open seat (i.e. seats[2]), then the closest person has distance 2.
If Alex sits in any other open seat, the closest person has distance 1.
Thus, the maximum distance to the closest person is 2.

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

1⃣Следите за prev, занятым местом слева или на текущей позиции i, и future, занятым местом справа или на текущей позиции i.

2⃣Для каждого пустого места i определите ближайшее занятие места как min(i - prev, future - i), с учетом, что i - prev считается бесконечностью, если слева нет занятого места, и future - i считается бесконечностью, если справа нет занятого места.

3⃣Найдите и верните максимальное расстояние до ближайшего занятого места.

😎 Решение:

class Solution {
    /**
     * @param Integer[] $seats
     * @return Integer
     */
    function maxDistToClosest($seats) {
        $n = count($seats);
        $prev = -1;
        $future = 0;
        $ans = 0;

        for ($i = 0; $i < $n; ++$i) {
            if ($seats[$i] == 1) {
                $prev = $i;
            } else {
                while ($future < $n && ($seats[$future] == 0 || $future < $i)) {
                    $future++;
                }
                $left = $prev == -1 ? $n : $i - $prev;
                $right = $future == $n ? $n : $future - $i;
                $ans = max($ans, min($left, $right));
            }
        }

        return $ans;
    }
}

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

Задача: 367. Valid Perfect Square
Сложность: easy

Дано положительное целое число num, вернуть true, если num является идеальным квадратом, или false в противном случае.
Идеальный квадрат — это целое число, являющееся квадратом целого числа. Другими словами, это произведение некоторого целого числа на само себя.
Вы не должны использовать какие-либо встроенные библиотечные функции, такие как sqrt.

Пример:

Input: num = 16
Output: true
Explanation: We return true because 4 * 4 = 16 and 4 is an integer.

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

1⃣Если num < 2, вернуть True. Установить левую границу в 2, а правую границу в num / 2.

2⃣Пока left <= right, взять x = (left + right) / 2, вычислить guess_squared = x * x и сравнить его с num:
Если guess_squared == num, вернуть True.
Если guess_squared > num, сдвинуть правую границу right = x - 1.
В противном случае сдвинуть левую границу left = x + 1.

3⃣Если вышли из цикла, вернуть False.

😎 Решение:

class Solution {
    public function isPerfectSquare(int $num): bool {
        if ($num < 2) {
            return true;
        }

        $x = intdiv($num, 2);
        while ($x * $x > $num) {
            $x = intdiv($x + intdiv($num, $x), 2);
        }
        return $x * $x == $num;
    }
}

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

Задача: 472. Concatenated Words
Сложность: hard

Дан массив строк words (без дубликатов). Верните все составные слова из данного списка слов.
Составное слово определяется как строка, которая полностью состоит как минимум из двух более коротких слов (не обязательно различных) из данного массива.

Пример:

Input: words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
Output: ["catsdogcats","dogcatsdog","ratcatdogcat"]
Explanation: "catsdogcats" can be concatenated by "cats", "dog" and "cats"; 
"dogcatsdog" can be concatenated by "dog", "cats" and "dog"; 
"ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat".

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

1⃣Для каждого слова в списке:
Построить неявный граф, в котором узлы представляют индексы символов в слове, а ребра представляют возможность перехода от одного индекса к другому, если подстрока между ними является словом из списка.

2⃣Использовать поиск в глубину (DFS) для проверки, можно ли достигнуть узел с индексом word.length от узла с индексом 0 в графе.

3⃣Если узел word.length достижим от узла 0, добавить слово в ответ.

😎 Решение:

class Solution {
    private function dfs($word, $length, &$visited, $dictionary) {
        if ($length == strlen($word)) {
            return true;
        }
        if ($visited[$length]) {
            return false;
        }
        $visited[$length] = true;
        for ($i = strlen($word) - ($length == 0 ? 1 : 0); $i > $length; $i--) {
            if (isset($dictionary[substr($word, $length, $i - $length)]) &&
                $this->dfs($word, $i, $visited, $dictionary)) {
                return true;
            }
        }
        return false;
    }

    function findAllConcatenatedWordsInADict($words) {
        $dictionary = array_flip($words);
        $answer = [];
        foreach ($words as $word) {
            $visited = array_fill(0, strlen($word), false);
            if ($this->dfs($word, 0, $visited, $dictionary)) {
                $answer[] = $word;
            }
        }
        return $answer;
    }
}

// Example usage
$solution = new Solution();
$words = ["cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"];
print_r($solution->findAllConcatenatedWordsInADict($words));

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

Задача: 733. Flood Fill
Сложность: easy

Изображение представлено в виде целочисленной сетки m x n, где image[i][j] - значение пикселя изображения. Вам также даны три целых числа sr, sc и color. Вы должны выполнить заливку изображения, начиная с пикселя image[sr][sc]. Чтобы выполнить заливку, рассмотрите начальный пиксель, плюс все пиксели, соединенные по 4-м направлениям с начальным пикселем, того же цвета, что и начальный пиксель, плюс все пиксели, соединенные по 4-м направлениям с этими пикселями (также того же цвета), и так далее. Замените цвет всех вышеупомянутых пикселей на цвет. Верните измененное изображение после выполнения заливки.

Пример:

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]

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

1⃣Получите цвет начального пикселя.

2⃣Используйте обход в глубину (DFS) или обход в ширину (BFS) для замены цвета всех пикселей, которые соединены с начальным пикселем и имеют тот же цвет.

3⃣Обновите изображение и верните его.

😎 Решение:

function floodFill($image, $sr, $sc, $color) {
    $originalColor = $image[$sr][$sc];
    if ($originalColor == $color) {
        return $image;
    }
    
    $dfs = function($x, $y) use (&$image, &$dfs, $originalColor, $color) {
        if ($x < 0 || $x >= count($image) || $y < 0 || $y >= count($image[0]) || $image[$x][$y] != $originalColor) {
            return;
        }
        $image[$x][$y] = $color;
        $dfs($x + 1, $y);
        $dfs($x - 1, $y);
        $dfs($x, $y + 1);
        $dfs($x, $y - 1);
    };
    
    $dfs($sr, $sc);
    return $image;
}

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

Задача: 288. Unique Word Abbreviation
Сложность: medium

Сокращение слова — это объединение его первой буквы, количества символов между первой и последней буквой и последней буквы. Если слово состоит только из двух символов, то оно является сокращением само по себе.
Например:
dog --> d1g, потому что между первой буквой 'd' и последней буквой 'g' одна буква.
internationalization --> i18n, потому что между первой буквой 'i' и последней буквой 'n' 18 букв.
it --> it, потому что любое слово из двух символов является своим собственным сокращением.
Реализуйте класс ValidWordAbbr:
ValidWordAbbr(String[] dictionary) Инициализирует объект со словарем слов.
boolean isUnique(string word) Возвращает true, если выполняется одно из следующих условий (в противном случае возвращает false):
В словаре нет слова, сокращение которого равно сокращению слова word.
Для любого слова в словаре, сокращение которого равно сокращению слова word, это слово и word одинаковы.

Пример:

Input
["ValidWordAbbr", "isUnique", "isUnique", "isUnique", "isUnique", "isUnique"]
[[["deer", "door", "cake", "card"]], ["dear"], ["cart"], ["cane"], ["make"], ["cake"]]
Output
[null, false, true, false, true, true]

Explanation
ValidWordAbbr validWordAbbr = new ValidWordAbbr(["deer", "door", "cake", "card"]);
validWordAbbr.isUnique("dear"); // return false, dictionary word "deer" and word "dear" have the same abbreviation "d2r" but are not the same.
validWordAbbr.isUnique("cart"); // return true, no words in the dictionary have the abbreviation "c2t".
validWordAbbr.isUnique("cane"); // return false, dictionary word "cake" and word "cane" have the same abbreviation  "c2e" but are not the same.
validWordAbbr.isUnique("make"); // return true, no words in the dictionary have the abbreviation "m2e".
validWordAbbr.isUnique("cake"); // return true, because "cake" is already in the dictionary and no other word in the dictionary has "c2e" abbreviation.

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

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

2⃣Генерация сокращений:
При инициализации объекта ValidWordAbbr пройдите через каждое слово в словаре и создайте его сокращение.
Если сокращение уже существует в abbrDict, установите значение в false (не уникальное). В противном случае установите значение в true (уникальное).

3⃣Проверка уникальности:
Для метода isUnique создайте сокращение для входного слова и проверьте, есть ли это сокращение в abbrDict.
Если сокращение отсутствует в abbrDict, возвращайте true.
Если сокращение присутствует и оно уникально, проверьте, есть ли это слово в словаре. Если да, возвращайте true, в противном случае - false.

😎 Решение:

class ValidWordAbbr {
    private $abbrDict = [];
    private $dict;

    function __construct($dictionary) {
        $this->dict = array_flip($dictionary);
        foreach ($dictionary as $word) {
            $abbr = $this->toAbbr($word);
            $this->abbrDict[$abbr] = !isset($this->abbrDict[$abbr]);
        }
    }

    function isUnique($word) {
        $abbr = $this->toAbbr($word);
        $hasAbbr = isset($this->abbrDict[$abbr]);
        return !$hasAbbr || ($this->abbrDict[$abbr] && isset($this->dict[$word]));
    }

    private function toAbbr($word) {
        $n = strlen($word);
        if ($n <= 2) {
            return $word;
        }
        return $word[0] . ($n - 2) . $word[$n - 1];
    }
}

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

Задача: 1058. Minimize Rounding Error to Meet Target
Сложность: medium

Учитывая массив цен [p1,p2...,pn] и цель, округлите каждую цену pi до Roundi(pi) так, чтобы округленный массив [Round1(p1),Round2(p2)...,Roundn(pn)] в сумме достиг заданной цели. Каждая операция Roundi(pi) может быть либо Floor(pi), либо Ceil(pi). Верните строку "-1", если округленный массив невозможно привести к целевому значению. В противном случае возвращается наименьшая ошибка округления, которая определяется как Σ |Roundi(pi) - (pi)| для i от 1 до n, в виде строки с тремя местами после десятичной дроби.

Пример:

Input: prices = ["0.700","2.800","4.900"], target = 8
Output: "1.000"

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

1⃣Округли каждую цену вниз и вычисли текущую сумму округленных цен.
Найди разницу между целевой суммой и текущей суммой.

2⃣Определи количество округлений вверх, необходимых для достижения целевой суммы.
Если разница отрицательная или больше количества элементов в массиве, верни "-1".

3⃣Вычисли ошибки округления для всех элементов и отсортируй их по возрастанию.
Выбери необходимые округления вверх и вычисли общую ошибку округления.

😎 Решение:

function minimizeRoundingError($prices, $target) {
    $floors = array_map(function($p) { return floor(floatval($p)); }, $prices);
    $totalFloor = array_sum($floors);
    
    $difference = $target - $totalFloor;
    if ($difference < 0 || $difference > count($prices)) {
        return "-1";
    }
    
    $roundingErrors = [];
    foreach ($prices as $i => $p) {
        $floatP = floatval($p);
        $roundingErrors[] = [ceil($floatP) - $floors[$i], $floatP - $floors[$i]];
    }
    
    usort($roundingErrors, function($a, $b) {
        return $a[1] <=> $b[1];
    });
    
    $roundingErrorSum = 0;
    foreach ($prices as $i => $p) {
        $roundingErrorSum += ($floors[$i] - floatval($p));
    }
    
    for ($i = 0; $i < $difference; $i++) {
        $roundingErrorSum += $roundingErrors[$i][1];
    }
    
    return number_format($roundingErrorSum, 3, '.', '');
}

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

Задача: 639. Decode Ways II
Сложность: hard

Сообщение, содержащее буквы от A-Z, может быть закодировано в цифры с помощью следующего отображения: 'A' -> "1" 'B' -> "2" ... 'Z' -> "26" Чтобы декодировать закодированное сообщение, все цифры должны быть сгруппированы, а затем снова преобразованы в буквы с помощью обратного отображения (может быть несколько способов). Например, "11106" может быть преобразовано в: "AAJF" с группировкой (1 1 10 6) "KJF" с группировкой (11 10 6) Обратите внимание, что группировка (1 11 06) недействительна, поскольку "06" не может быть преобразовано в "F", так как "6" отличается от "06". В дополнение к вышеуказанным преобразованиям кодированное сообщение может содержать символ "*", который может представлять любую цифру от "1" до "9" ("0" исключается). Например, кодированное сообщение "1*" может представлять любое из кодированных сообщений "11", "12", "13", "14", "15", "16", "17", "18" или "19". Декодирование "1*" эквивалентно декодированию любого из кодированных сообщений, которые оно может представлять. Если задана строка s, состоящая из цифр и символов '*', верните количество способов ее декодирования. Поскольку ответ может быть очень большим, верните его по модулю 109 + 7.

Пример:

Input: s = "*"
Output: 9

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

1⃣Инициализация
Создайте массив dp, где dp[i] представляет количество способов декодирования подстроки s[0:i]. Установите начальные значения dp[0] = 1 (пустая строка имеет один способ декодирования).

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

3⃣Модульное вычисление
Поскольку количество способов декодирования может быть большим, вычисляйте результаты по модулю 10^9 + 7.

😎 Решение:

function numDecodings($s) {
    $MOD = 1000000007;
    $n = strlen($s);
    $dp = array_fill(0, $n + 1, 0);
    $dp[0] = 1;

    for ($i = 1; $i <= $n; $i++) {
        if ($s[$i - 1] == '*') {
            $dp[$i] = 9 * $dp[$i - 1];
        } else if ($s[$i - 1] != '0') {
            $dp[$i] = $dp[$i - 1];
        }

        if ($i > 1) {
            if ($s[$i - 2] == '*') {
                if ($s[$i - 1] == '*') {
                    $dp[$i] += 15 * $dp[$i - 2];
                } else if ($s[$i - 1] >= '0' && $s[$i - 1] <= '6') {
                    $dp[$i] += 2 * $dp[$i - 2];
                } else {
                    $dp[$i] += $dp[$i - 2];
                }
            } else if ($s[$i - 2] == '1') {
                if ($s[$i - 1] == '*') {
                    $dp[$i] += 9 * $dp[$i - 2];
                } else {
                    $dp[$i] += $dp[$i - 2];
                }
            } else if ($s[$i - 2] == '2') {
                if ($s[$i - 1] == '*') {
                    $dp[$i] += 6 * $dp[$i - 2];
                } else if ($s[$i - 1] >= '0' && $s[$i - 1] <= '6') {
                    $dp[$i] += $dp[$i - 2];
                }
            }
        }

        $dp[$i] %= $MOD;
    }

    return $dp[$n];
}

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

Задача: 97. Interleaving String
Сложность: medium

Даны строки s1, s2 и s3. Необходимо определить, может ли строка s3 быть сформирована путем чередования строк s1 и s2.

Чередование двух строк s и t — это конфигурация, при которой s и t делятся на n и m подстрок соответственно так, что:

s = s1 + s2 + ... + sn
t = t1 + t2 + ... + tm
|n - m| ≤ 1
Чередование может быть таким: s1 + t1 + s2 + t2 + s3 + t3 + ... или t1 + s1 + t2 + s2 + t3 + s3 + ...
Примечание: a + b означает конкатенацию строк a и b.

Пример:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Explanation: One way to obtain s3 is:
Split s1 into s1 = "aa" + "bc" + "c", and s2 into s2 = "dbbc" + "a".
Interleaving the two splits, we get "aa" + "dbbc" + "bc" + "a" + "c" = "aadbbcbcac".

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

1⃣В рекурсивном подходе, описанном выше, рассматривается каждая возможная строка, образованная путем чередования двух заданных строк. Однако возникают случаи, когда та же часть s1 и s2 уже была обработана, но в разных порядках (перестановках). Независимо от порядка обработки, если результирующая строка до этого момента совпадает с требуемой строкой (s3), окончательный результат зависит только от оставшихся частей s1 и s2, а не от уже обработанной части. Таким образом, рекурсивный подход приводит к избыточным вычислениям.

2⃣Эту избыточность можно устранить, используя мемоизацию вместе с рекурсией. Для этого мы поддерживаем три указателя i, j, k, которые соответствуют индексу текущего символа s1, s2, s3 соответственно. Также мы поддерживаем двумерный массив memo для отслеживания обработанных до сих пор подстрок. memo[i][j] хранит 1/0 или -1 в зависимости от того, была ли текущая часть строк, то есть до i-го индекса для s1 и до j-го индекса для s2, уже оценена. Мы начинаем с выбора текущего символа s1 (на который указывает i). Если он совпадает с текущим символом s3 (на который указывает k), мы включаем его в обработанную строку и вызываем ту же функцию рекурсивно как: is_Interleave(s1, i+1, s2, j, s3, k+1, memo).

3⃣Таким образом, мы вызвали функцию, увеличив указатели i и k, поскольку часть строк до этих индексов уже была обработана. Аналогично, мы выбираем один символ из второй строки и продолжаем. Рекурсивная функция заканчивается, когда одна из двух строк s1 или s2 полностью обработана. Если, скажем, строка s1 полностью обработана, мы напрямую сравниваем оставшуюся часть s2 с оставшейся частью s3. Когда происходит возврат из рекурсивных вызовов, мы сохраняем значение, возвращенное рекурсивными функциями, в массиве мемоизации memo соответственно, так что когда оно встречается в следующий раз, рекурсивная функция не будет вызвана, но сам массив мемоизации вернет предыдущий сгенерированный результат.

😎 Решение:

class Solution {
    function isInterleave($s1, $s2, $s3) {
        if (strlen($s3) != strlen($s1) + strlen($s2)) {
            return false;
        }

        $dp = array_fill(0, strlen($s1) + 1, array_fill(0, strlen($s2) + 1, false));
        for ($i = 0; $i <= strlen($s1); $i++) {
            for ($j = 0; $j <= strlen($s2); $j++) {
                if ($i == 0 && $j == 0) {
                    $dp[$i][$j] = true;
                } elseif ($i == 0) {
                    $dp[$i][$j] = $dp[$i][$j - 1] && $s2[$j - 1] == $s3[$i + $j - 1];
                } elseif ($j == 0) {
                    $dp[$i][$j] = $dp[$i - 1][$j] && $s1[$i - 1] == $s3[$i + $j - 1];
                } else {
                    $dp[$i][$j] = ($dp[$i - 1][$j] && $s1[$i - 1] == $s3[$i + $j - 1]) || 
                                   ($dp[$i][$j - 1] && $s2[$j - 1] == $s3[$i + $j - 1]);
                }
            }
        }

        return $dp[strlen($s1)][strlen($s2)];
    }
}

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

Задача: 164. Maximum Gap
Сложность: medium

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

Пример:

Input: nums = [3,6,9,1]
Output: 3
Explanation: The sorted form of the array is [1,3,6,9], either (3,6) or (6,9) has the maximum difference 3.

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

1⃣Инициализация:
Определите минимальное и максимальное значения в массиве для расчета возможного максимального интервала (разрыва) между элементами в идеально распределенном массиве.
Вычислите размер ведра (bucket size), необходимый для размещения всех элементов массива так, чтобы если массив был равномерно распределен, каждый ведер должен содержать хотя бы один элемент. Размер ведра = (max_value - min_value) / (количество элементов - 1).

2⃣Размещение элементов в ведрах:
Создайте ведра для хранения минимальных и максимальных значений каждого ведра. Используйте формулу для распределения каждого элемента в соответствующем ведре на основе его значения.
Игнорируйте пустые ведра при расчете максимального интервала.

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

😎 Решение:

class Solution {
    function maximumGap($nums) {
        if (empty($nums) || count($nums) < 2) {
            return 0;
        }

        sort($nums);
        $maxGap = 0;

        for ($i = 0; $i < count($nums) - 1; $i++) {
            $maxGap = max($nums[$i + 1] - $nums[$i], $maxGap);
        }

        return $maxGap;
    }
}

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

Задача: 719. Find K-th Smallest Pair Distance
Сложность: hard

Расстояние между парой целых чисел a и b определяется как абсолютная разность между a и b. Учитывая целочисленный массив nums и целое число k, верните k-е наименьшее расстояние среди всех пар nums[i] и nums[j], где 0 <= i < j < nums.length.

Пример:

Input: nums = [1,3,1], k = 1
Output: 0

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

1⃣Отсортируйте массив nums.

2⃣Определите минимальное и максимальное возможные расстояния.

3⃣Используйте бинарный поиск, чтобы найти k-е наименьшее расстояние, проверяя количество пар с расстоянием меньше или равно текущему среднему значению.

😎 Решение:

function countPairs($nums, $mid) {
    $count = 0;
    $j = 0;
    for ($i = 0; $i < count($nums); $i++) {
        while ($j < count($nums) && $nums[$j] - $nums[$i] <= $mid) {
            $j++;
        }
        $count += $j - $i - 1;
    }
    return $count;
}

function smallestDistancePair($nums, $k) {
    sort($nums);
    $left = 0;
    $right = $nums[count($nums) - 1] - $nums[0];
    while ($left < $right) {
        $mid = (int)(($left + $right) / 2);
        if (countPairs($nums, $mid) < $k) {
            $left = $mid + 1;
        } else {
            $right = $mid;
        }
    }
    return $left;
}

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

Задача: 187. Repeated DNA Sequences
Сложность: medium

ДНК состоит из серии нуклеотидов, обозначаемых как 'A', 'C', 'G' и 'T'.
Например, "ACGAATTCCG" — это последовательность ДНК.
При изучении ДНК полезно определять повторяющиеся последовательности внутри молекулы ДНК.
Дана строка s, представляющая последовательность ДНК. Верните все последовательности длиной 10 букв (подстроки), которые встречаются более одного раза в молекуле ДНК. Ответ можно возвращать в любом порядке.

Пример:

Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output: ["AAAAACCCCC","CCCCCAAAAA"]

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

1⃣Перебираем начальные позиции последовательности от 1 до 𝑁−𝐿, где 𝑁 — длина строки, а 𝐿 — длина подстроки (в данном случае 10):
Если начальная позиция 𝑠𝑡𝑎𝑟𝑡==0, вычисляем хеш первой последовательности 𝑠[0:𝐿].
В противном случае вычисляем скользящий хеш из предыдущего значения хеша.

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

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

😎 Решение:

class Solution {
    function findRepeatedDnaSequences($s) {
        $L = 10; $n = strlen($s);
        if ($n <= $L) return [];
        $a = 4; $aL = pow($a, $L);
        $toInt = ['A' => 0, 'C' => 1, 'G' => 2, 'T' => 3];
        $nums = array_map(function($c) use ($toInt) { return $toInt[$c]; }, str_split($s));
        $h = 0;
        $seen = []; $output = [];
        for ($start = 0; $start < $n - $L + 1; ++$start) {
            if ($start != 0)
                $h = $h * $a - $nums[$start - 1] * $aL + $nums[$start + $L - 1];
            else
                for ($i = 0; $i < $L; ++$i)
                    $h = $h * $a + $nums[$i];
            if (in_array($h, $seen))
                $output[] = substr($s, $start, $L);
            $seen[] = $h;
        }
        return array_unique($output);
    }
}

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

Задача: 1332. Remove Palindromic Subsequences
Сложность: easy


Вам дана строка s, состоящая только из букв 'a' и 'b'. За один шаг вы можете удалить одну палиндромную подпоследовательность из s.

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

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

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

Пример:

Input: s = "ababa"
Output: 1
Explanation: s is already a palindrome, so its entirety can be removed in a single step.

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

1⃣Если строка s уже является палиндромом, верните 1, так как можно удалить всю строку за один шаг.

2⃣Если строка s не является палиндромом, верните 2. В этом случае можно удалить все символы 'a' за один шаг, а затем все символы 'b' за второй шаг (или наоборот).

3⃣Таким образом, минимум шагов для опустошения строки всегда будет либо 1, либо 2, в зависимости от того, является ли строка палиндромом.

😎 Решение:

class Solution {
    function removePalindromeSub($s) {
        if (empty($s)) {
            return 0;
        }
        if (strrev($s) == $s) {
            return 1;
        }
        return 2;
    }
}

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