Задача: 565. Array Nesting
Сложность: medium

Дан массив целых чисел nums длиной n, где nums является перестановкой чисел в диапазоне [0, n - 1].
Вы должны построить множество s[k] = {nums[k], nums[nums[k]], nums[nums[nums[k]]], ...} при соблюдении следующего правила:
Первый элемент в s[k] начинается с выбора элемента nums[k] с индексом k.
Следующий элемент в s[k] должен быть nums[nums[k]], затем nums[nums[nums[k]]], и так далее.
Мы прекращаем добавлять элементы непосредственно перед тем, как в s[k] появится дубликат.
Верните длину самого длинного множества s[k].

Пример:

Input: nums = [5,4,0,3,1,6,2]
Output: 4
Explanation: 
nums[0] = 5, nums[1] = 4, nums[2] = 0, nums[3] = 3, nums[4] = 1, nums[5] = 6, nums[6] = 2.
One of the longest sets s[k]:
s[0] = {nums[0], nums[5], nums[6], nums[2]} = {5, 6, 2, 0}

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

1⃣Создайте массив для отслеживания посещенных элементов.

2⃣Для каждого элемента в nums, если он не посещен, начните формирование множества s[k], последовательно переходя по элементам, пока не встретится уже посещенный элемент.

3⃣Обновите максимальную длину найденного множества.

😎 Решение:

class Solution {
    function arrayNesting($nums) {
        $visited = array_fill(0, count($nums), false);
        $maxLength = 0;
        
        for ($i = 0; $i < count($nums); $i++) {
            if (!$visited[$i]) {
                $start = $i;
                $count = 0;
                while (!$visited[$start]) {
                    $visited[$start] = true;
                    $start = $nums[$start];
                    $count++;
                }
                $maxLength = max($maxLength, $count);
            }
        }
        
        return $maxLength;
    }
}

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

Задача: 918. Maximum Sum Circular Subarray
Сложность: medium

Если задан круговой целочисленный массив nums длины n, верните максимально возможную сумму непустого подмассива nums. Круговой массив означает, что конец массива соединяется с его началом. Формально, следующий элемент nums[i] равен nums[(i + 1) % n], а предыдущий элемент nums[i] равен nums[(i - 1 + n) % n]. Подмассив может включать каждый элемент фиксированного буфера nums не более одного раза. Формально, для подмассива nums[i], nums[i + 1], ..., nums[j] не существует i <= k1, k2 <= j, при этом k1 % n == k2 % n.

Пример:

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

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

1⃣Найти стандартную максимальную сумму подмассива с помощью алгоритма Кадане.

2⃣Найти минимальную сумму подмассива с помощью алгоритма Кадане и вычесть ее из общей суммы массива.

3⃣Вернуть максимум между стандартной максимальной суммой подмассива и общей суммой массива минус минимальную сумму подмассива, если результат не равен 0 (чтобы учесть случай, когда все числа отрицательные).

😎 Решение:

function maxSubarraySumCircular($nums) {
    function kadane($arr) {
        $currentSum = $arr[0];
        $maxSum = $arr[0];
        for ($i = 1; $i < count($arr); $i++) {
            $currentSum = max($arr[$i], $currentSum + $arr[$i]);
            $maxSum = max($maxSum, $currentSum);
        }
        return $maxSum;
    }

    $maxKadane = kadane($nums);
    $totalSum = array_sum($nums);
    $nums = array_map(function($num) { return -$num; }, $nums);
    $minKadane = kadane($nums);

    return max($maxKadane, $totalSum + $minKadane == 0 ? $maxKadane : $totalSum + $minKadane);
}

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

Задача: 347. Top K Frequent Elements
Сложность: medium

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

Пример:

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

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

1⃣Подсчет частоты:
Используйте хеш-таблицу или словарь для подсчета количества вхождений каждого элемента в массиве nums.

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

3⃣Возврат результата:
Верните k самых частых элементов.

😎 Решение:

class Solution {
    function topKFrequent($nums, $k) {
        $count = array_count_values($nums);
        arsort($count);
        return array_slice(array_keys($count), 0, $k);
    }
}

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

Задача: 203. Remove Linked List Elements
Сложность: easy

Для заданного начала связного списка и целого числа val удалите все узлы связного списка, у которых Node.val равно val, и верните новое начало списка.

Пример:

Input: head = [1,2,6,3,4,5,6], val = 6
Output: [1,2,3,4,5]

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

1⃣Инициализируйте сторожевой узел как ListNode(0) и установите его новым началом: sentinel.next = head. Инициализируйте два указателя для отслеживания текущего узла и его предшественника: curr и prev.

2⃣Пока curr не является нулевым указателем, сравните значение текущего узла со значением для удаления. Если значения равны, удалите текущий узел: prev.next = curr.next, иначе установите предшественника равным текущему узлу. Переместитесь к следующему узлу: curr = curr.next.

3⃣Верните sentinel.next.

😎 Решение:

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

function deleteNode($head, $value) {
    $sentinel = new ListNode(0);
    $sentinel->next = $head;
    $prev = $sentinel;
    $curr = $head;

    while ($curr !== null) {
        if ($curr->val === $value) {
            $prev->next = $curr->next;
        } else {
            $prev = $curr;
        }
        $curr = $curr->next;
    }
    return $sentinel->next;
}

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

Задача: 905. Sort Array By Parity
Сложность: easy

Если задан целочисленный массив nums, переместите все четные числа в начало массива, а затем все нечетные. Верните любой массив, удовлетворяющий этому условию.

Пример:

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

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

1⃣Создать два списка: один для четных чисел, другой для нечетных.

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

3⃣Объединить два списка и вернуть результат.

😎 Решение:

function sortArrayByParity($nums) {
    $evens = [];
    $odds = [];
    foreach ($nums as $num) {
        if ($num % 2 == 0) {
            $evens[] = $num;
        } else {
            $odds[] = $num;
        }
    }
    return array_merge($evens, $odds);
}

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

Сложность: medium
Задача: 1135. Connecting Cities With Minimum Cost

Есть n городов, пронумерованных от 1 до n. Вам даны целое число n и массив connections, где connections[i] = [xi, yi, costi] указывает, что стоимость соединения города xi и города yi (двунаправленное соединение) равна costi.

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

Стоимость - это сумма использованных стоимостей соединений.

Пример:

Input: n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]]
Output: 6
Explanation: Choosing any 2 edges will connect all cities so we choose the minimum 2.

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

1⃣Сортировка рёбер:
Отсортируйте все соединения (рёбра) в графе по их весам (стоимости) в порядке возрастания.

2⃣Итерация по рёбрам и объединение:
Используйте структуру данных Disjoint Set (Union-Find) для проверки циклов и объединения поддеревьев. Для каждого ребра проверьте, принадлежат ли его концы разным поддеревьям, и если да, объедините их, добавив ребро в минимальное остовное дерево (MST).

3⃣Проверка соединённости:
Подсчитайте количество рёбер в MST. Если оно меньше n-1, верните -1, так как соединить все города невозможно. Иначе верните суммарную стоимость рёбер в MST.

😎 Решение:

class DisjointSet {
    private $parent;

    public function __construct($n) {
        $this->parent = range(0, $n);
    }

    public function find($x) {
        if ($this->parent[$x] !== $x) {
            $this->parent[$x] = $this->find($this->parent[$x]);
        }
        return $this->parent[$x];
    }

    public function union($x, $y) {
        $rootX = $this->find($x);
        $rootY = $this->find($y);
        if ($rootX !== $rootY) {
            $this->parent[$rootY] = $rootX;
        }
    }
}

class Solution {
    function minimumCost($n, $connections) {
        usort($connections, function($a, $b) {
            return $a[2] - $b[2];
        });

        $disjointSet = new DisjointSet($n);
        $totalCost = 0;
        $edgesUsed = 0;

        foreach ($connections as $connection) {
            list($x, $y, $cost) = $connection;
            if ($disjointSet->find($x) !== $disjointSet->find($y)) {
                $disjointSet->union($x, $y);
                $totalCost += $cost;
                $edgesUsed++;
                if ($edgesUsed === $n - 1) {
                    return $totalCost;
                }
            }
        }
        return $edgesUsed === $n - 1 ? $totalCost : -1;
    }
}

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

Задача: 76. Minimum Window Substring
Сложность: hard

Даны две строки s и t длиной m и n соответственно. Верните наименьшую подстроку строки s так, чтобы каждый символ из строки t (включая дубликаты) входил в эту подстроку. Если такой подстроки не существует, верните пустую строку "".

Тестовые примеры будут сформированы таким образом, что ответ будет уникальным.

Пример:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

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

1⃣Мы начинаем с двух указателей, left и right, которые изначально указывают на первый элемент строки S.

2⃣Мы используем указатель right для расширения окна до тех пор, пока не получим желаемое окно, т.е. окно, которое содержит все символы из T.

3⃣Как только у нас есть окно со всеми символами, мы можем передвигать указатель left вперёд по одному. Если окно по-прежнему желаемое, мы продолжаем обновлять размер минимального окна. Если окно больше не желаемое, мы повторяем шаг 2 и далее.

😎 Решение:

function minWindow($s, $t) {
    if (strlen($s) === 0 || strlen($t) === 0) {
        return "";
    }
    
    $dictT = [];
    for ($i = 0; $i < strlen($t); $i++) {
        $char = $t[$i];
        if (!array_key_exists($char, $dictT)) {
            $dictT[$char] = 0;
        }
        $dictT[$char]++;
    }
    
    $required = count($dictT);
    $l = 0;
    $r = 0;
    $formed = 0;
    $windowCounts = [];
    $ans = [-1, 0, 0];
    
    while ($r < strlen($s)) {
        $c = $s[$r];
        if (!array_key_exists($c, $windowCounts)) {
            $windowCounts[$c] = 0;
        }
        $windowCounts[$c]++;
        
        if (array_key_exists($c, $dictT) && $windowCounts[$c] === $dictT[$c]) {
            $formed++;
        }
        
        while ($l <= $r && $formed === $required) {
            $c = $s[$l];
            if ($ans[0] === -1 || $r - $l + 1 < $ans[0]) {
                $ans = [$r - $l + 1, $l, $r];
            }
            
            $windowCounts[$c]--;
            if (array_key_exists($c, $dictT) && $windowCounts[$c] < $dictT[$c]) {
                $formed--;
            }
            $l++;
        }
        $r++;
    }
    
    return $ans[0] === -1 ? "" : substr($s, $ans[1], $ans[2] - $ans[1] + 1);
}

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

Задача: 1015. Smallest Integer Divisible by K
Сложность: medium

Задано целое положительное число k, необходимо найти длину наименьшего целого положительного числа n, такого, что n делится на k, и n содержит только цифру 1. Верните длину n. Если такого n не существует, верните -1. Примечание: n может не поместиться в 64-битное знаковое целое число.

Пример:

Input: k = 1
Output: 1

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

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

2⃣Итеративное нахождение числа:
Используйте цикл, чтобы умножать num на 10 и добавлять 1 в каждой итерации, и каждый раз вычисляйте остаток от деления num на k.
Увеличивайте length на 1 в каждой итерации.
Если в какой-то итерации num % k == 0, верните length.

3⃣Проверка бесконечного цикла:
Если цикл длится слишком долго (например, 10^6 итераций), верните -1, чтобы предотвратить бесконечный цикл для случаев, когда решение не существует.

😎 Решение:

class Solution {
    function smallestRepunitDivByK($k) {
        $num = 1;
        $length = 1;
        $seen = [];
        
        while ($num % $k != 0) {
            if (in_array($num % $k, $seen)) {
                return -1;
            }
            $seen[] = $num % $k;
            $num = ($num * 10 + 1) % $k;
            $length++;
        }
        
        return $length;
    }
}

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

Задача: 93. Restore IP Addresses
Сложность: medium

Сообщение, содержащее буквы от 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".

Для данной строки s, содержащей только цифры, верните количество способов декодирования.

Тестовые случаи сформированы таким образом, что ответ укладывается в 32-битное целое число.

Пример:

Input: s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).

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

1⃣Входим в рекурсию с данной строкой, начиная с индекса 0.

2⃣Для окончательного случая рекурсии мы проверяем конец строки. Если мы достигли конца строки, возвращаем 1. Каждый раз, когда мы входим в рекурсию, это для подстроки исходной строки. Если первый символ в подстроке равен 0, то прекращаем этот путь, возвращая 0. Таким образом, этот путь не будет влиять на количество способов.

3⃣Мемоизация помогает снизить сложность, которая иначе была бы экспоненциальной. Мы проверяем словарь memo, чтобы увидеть, существует ли уже результат для данной подстроки. Если результат уже находится в memo, мы возвращаем этот результат. В противном случае количество способов для данной строки определяется путем рекурсивного вызова функции с индексом +1 для следующей подстроки и индексом +2 после проверки на валидность двузначного декодирования. Результат также сохраняется в memo с ключом как текущий индекс, чтобы сохранить его для будущих пересекающихся подзадач.

😎 Решение:

class Solution {
    private function valid($s, $start, $length) {
        if ($length == 1) {
            return true;
        }
        if ($s[$start] == '0') {
            return false;
        }
        if ($length > 3) {
            return false;
        }
        $num = substr($s, $start, $length);
        return (int)$num <= 255;
    }

    private function helper($s, $startIndex, &$dots, &$ans) {
        $remainingLength = strlen($s) - $startIndex;
        $remainingNumberOfIntegers = 4 - count($dots);
        if ($remainingLength > $remainingNumberOfIntegers * 3 || $remainingLength < $remainingNumberOfIntegers) {
            return;
        }
        if (count($dots) == 3) {
            if ($this->valid($s, $startIndex, $remainingLength)) {
                $temp = "";
                $last = 0;
                foreach ($dots as $dot) {
                    $temp .= substr($s, $last, $dot) . ".";
                    $last += $dot;
                }
                $temp .= substr($s, $startIndex);
                $ans[] = $temp;
            }
            return;
        }
        for ($curPos = 1; $curPos <= min(3, $remainingLength); $curPos++) {
            $dots[] = $curPos;
            if ($this->valid($s, $startIndex, $curPos)) {
                $this->helper($s, $startIndex + $curPos, $dots, $ans);
            }
            array_pop($dots);
        }
    }

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

Задача: 211. Design Add and Search Words Data Structure
Сложность: medium

Спроектируйте структуру данных, которая поддерживает добавление новых слов и проверку, соответствует ли строка любому ранее добавленному слову.
Реализуйте класс WordDictionary:
WordDictionary() инициализирует объект.
void addWord(word) добавляет слово в структуру данных, оно может быть сопоставлено позже.
bool search(word) возвращает true, если в структуре данных есть строка, которая соответствует слову, или false в противном случае. Слово может содержать точки '.', где точки могут быть сопоставлены с любой буквой.

Пример:

Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]

Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

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

1⃣Инициализация и добавление слова:
Создайте класс WordDictionary с конструктором, который инициализирует корневой узел TrieNode.
Метод addWord(String word) добавляет слово в структуру данных. Инициализируйте текущий узел как корневой и пройдите по каждому символу слова. Если символ отсутствует среди дочерних узлов текущего узла, создайте новый узел. Перемещайтесь к следующему узлу. В конце отметьте текущий узел как конец слова.

2⃣Поиск слова в узле:
Метод searchInNode(String word, TrieNode node) ищет слово в переданном узле TrieNode. Пройдите по каждому символу слова. Если символ не найден среди дочерних узлов текущего узла, проверьте, является ли символ точкой '.'. Если да, рекурсивно выполните поиск в каждом дочернем узле текущего узла. Если символ не точка и не найден, верните false. Если символ найден, перейдите к следующему узлу. В конце проверьте, является ли текущий узел концом слова.

3⃣Поиск слова в структуре данных:
Метод search(String word) использует метод searchInNode() для поиска слова, начиная с корневого узла. Верните результат поиска. Если слово найдено, верните true, иначе false.

😎 Решение:

class TrieNode {
    public $children;
    public $isWord;

    public function __construct() {
        $this->children = [];
        $this->isWord = false;
    }
}

class WordDictionary {
    private $root;

    public function __construct() {
        $this->root = new TrieNode();
    }

    public function addWord($word) {
        $node = $this->root;
        for ($i = 0; $i < strlen($word); $i++) {
            $ch = $word[$i];
            if (!isset($node->children[$ch])) {
                $node->children[$ch] = new TrieNode();
            }
            $node = $node->children[$ch];
        }
        $node->isWord = true;
    }

    private function searchInNode($word, $node) {
        for ($i = 0; $i < strlen($word); $i++) {
            $ch = $word[$i];
            if (!isset($node->children[$ch])) {
                if ($ch === '.') {
                    foreach ($node->children as $child) {
                        if ($this->searchInNode(substr($word, $i + 1), $child)) {
                            return true;
                        }
                    }
                }
                return false;
            } else {
                $node = $node->children[$ch];
            }
        }
        return $node->isWord;
    }

    public function search($word) {
        return $this->searchInNode($word, $this->root);
    }
}

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

Задача: 1271. Hexspeak
Сложность: easy

Десятичное число можно преобразовать в его шестнадцатеричное представление, сначала преобразовав его в прописную шестнадцатеричную строку, а затем заменив все вхождения цифры '0' на букву 'O', а цифры '1' - на букву 'I'. Такое представление допустимо тогда и только тогда, когда оно состоит только из букв набора {'A', 'B', 'C', 'D', 'E', 'F', 'I', 'O'}. Получив строку num, представляющую десятичное целое число n, верните шестнадцатеричное представление n, если оно допустимо, иначе верните "ERROR".

Пример:

Input: num = "257"
Output: "IOI"

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

1⃣Преобразуйте десятичное число в шестнадцатеричную строку в верхнем регистре.

2⃣Замените все вхождения цифры '0' на букву 'O', а цифры '1' на букву 'I'

3⃣Проверьте, что преобразованная строка содержит только допустимые символы. Если это так, верните строку, иначе верните "ERROR".

😎 Решение:

function toHexString($num) {
    $hexStr = strtoupper(dechex($num));
    $hexStr = str_replace(['0', '1'], ['O', 'I'], $hexStr);
    foreach (str_split($hexStr) as $char) {
        if (!in_array($char, str_split('ABCDEFIO'))) {
            return "ERROR";
        }
    }
    return $hexStr;
}

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

Задача: 951. Flip Equivalent Binary Trees
Сложность: medium

Для бинарного дерева T мы можем определить операцию переворота следующим образом: выбираем любой узел и меняем местами левое и правое дочерние поддеревья. Бинарное дерево X эквивалентно бинарному дереву Y тогда и только тогда, когда мы можем сделать X равным Y после некоторого количества операций переворота. Учитывая корни двух бинарных деревьев root1 и root2, верните true, если эти два дерева эквивалентны перевороту, или false в противном случае.

Пример:

Input: root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7]
Output: true

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

1⃣Если оба дерева пусты, они эквивалентны, вернуть true. Если одно дерево пустое, а другое нет, они не эквивалентны, вернуть false.

2⃣Если значения корней деревьев не совпадают, вернуть false.
Проверить два условия:
Левое поддерево первого дерева эквивалентно левому поддереву второго дерева и правое поддерево первого дерева эквивалентно правому поддереву второго дерева.
Левое поддерево первого дерева эквивалентно правому поддереву второго дерева и правое поддерево первого дерева эквивалентно левому поддереву второго дерева.

3⃣Вернуть true, если выполняется хотя бы одно из этих условий.

😎 Решение:

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

function flipEquiv($root1, $root2) {
    if ($root1 == null && $root2 == null) return true;
    if ($root1 == null || $root2 == null) return false;
    if ($root1->val != $root2->val) return false;
    
    return (flipEquiv($root1->left, $root2->left) && flipEquiv($root1->right, $root2->right)) ||
           (flipEquiv($root1->left, $root2->right) && flipEquiv($root1->right, $root2->left));
}

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

Задача: 1518. Water Bottles
Сложность: easy

У вас есть numBottles полных бутылок воды. За каждые numExchange пустых бутылок можно получить одну полную. Посчитайте, сколько всего бутылок воды можно выпить, если каждый раз менять пустые на новые.

Пример:

Input: numBottles = 9, numExchange = 3
Output: 13
Explanation: You can exchange 3 empty bottles to get 1 full water bottle.
Number of water bottles you can drink: 9 + 3 + 1 = 13.

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

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

2⃣Продолжайте выполнять следующие действия, пока количество numBottles больше или равно numExchange: Выпейте numExchange количество полных бутылок, т.е. добавьте numExchange к consumedBottles. Уменьшите numExchange от доступных полных бутылок numBottles. Обменяйте пустые бутылки на одну полную бутылку, т.е. увеличьте numBottles на одну.

3⃣Верните consumedBottles + numBottles.

😎 Решение:

class Solution {
    function numWaterBottles($numBottles, $numExchange) {
        $consumedBottles = 0;

        while ($numBottles >= $numExchange) {
            $consumedBottles += $numExchange;
            $numBottles -= $numExchange;
            $numBottles++;
        }

        return $consumedBottles + $numBottles;
    }
}

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

Задача: 900. RLE Iterator
Сложность: medium

Для кодирования последовательности целых чисел мы можем использовать кодирование по длине строки (т. е. RLE). В кодированном по длине пробега массиве четной длины (с индексацией 0) для всех четных i значение encoding[i] говорит нам о том, сколько раз неотрицательное целое значение encoding[i + 1] повторяется в последовательности.

Например, последовательность arr = [8,8,8,5,5] может быть закодирована как encoding = [3,8,2,5]. encoding = [3,8,0,9,2,5] и encoding = [2,8,1,8,2,5] также являются допустимыми RLE для arr.
Задав кодированный по длине пробега массив, разработайте итератор для его итерации. Реализуйте класс RLEIterator: RLEIterator(int[] encoded) Инициализирует объект с кодированным массивом encoded. int next(int n) Исчерпывает следующие n элементов и возвращает последний исчерпанный таким образом элемент. Если не осталось элементов для исчерпания, возвращает -1.

Пример:

Input
["RLEIterator", "next", "next", "next", "next"]
[[[3, 8, 0, 9, 2, 5]], [2], [1], [1], [2]]
Output
[null, 8, 8, 5, -1]

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

1⃣Инициализировать итератор с закодированным массивом и индексом, указывающим на текущую позицию.

2⃣При вызове метода next(n), уменьшить текущий счетчик на n или перейти к следующему числу, если текущий счетчик равен нулю.

3⃣Возвращать текущий элемент или -1, если все элементы исчерпаны.

😎 Решение:

class RLEIterator {
    private $encoding;
    private $index;

    function __construct($encoding) {
        $this->encoding = $encoding;
        $this->index = 0;
    }

    function next($n) {
        while ($this->index < count($this->encoding)) {
            if ($n > $this->encoding[$this->index]) {
                $n -= $this->encoding[$this->index];
                $this->index += 2;
            } else {
                $this->encoding[$this->index] -= $n;
                return $this->encoding[$this->index + 1];
            }
        }
        return -1;
    }
}

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

Задача: 417. Pacific Atlantic Water Flow
Сложность: medium

Имеется прямоугольный остров размером m x n, который граничит с Тихим и Атлантическим океанами. Тихий океан касается левого и верхнего краев острова, а Атлантический океан - правого и нижнего краев. Остров разбит на сетку квадратных ячеек. Вам дана целочисленная матрица heights размером m x n, где heights[r][c] - высота над уровнем моря клетки с координатами (r, c). На острове выпадает много осадков, и дождевая вода может стекать в соседние клетки прямо на север, юг, восток и запад, если высота соседней клетки меньше или равна высоте текущей клетки. Вода может течь из любой клетки, прилегающей к океану, в океан. Верните двумерный список координат сетки result, где result[i] = [ri, ci] означает, что дождевая вода может течь из клетки (ri, ci) как в Тихий, так и в Атлантический океаны.

Пример:

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

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

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

2⃣Выполните поиск для каждого океана, обновляя матрицы достижимости.

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

😎 Решение:

function pacificAtlantic($heights) {
    $m = count($heights);
    $n = count($heights[0]);
    $pacific = array_fill(0, $m, array_fill(0, $n, false));
    $atlantic = array_fill(0, $m, array_fill(0, $n, false));
    $directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    
    function dfs($r, $c, &$ocean, $heights, $directions) {
        $ocean[$r][$c] = true;
        foreach ($directions as [$dr, $dc]) {
            $nr = $r + $dr;
            $nc = $c + $dc;
            if ($nr >= 0 && $nc >= 0 && $nr < count($heights) && $nc < count($heights[0]) && !$ocean[$nr][$nc] && $heights[$nr][$nc] >= $heights[$r][$c]) {
                dfs($nr, $nc, $ocean, $heights, $directions);
            }
        }
    }
    
    for ($i = 0; $i < $m; $i++) {
        dfs($i, 0, $pacific, $heights, $directions);
        dfs($i, $n - 1, $atlantic, $heights, $directions);
    }
    for ($j = 0; $j < $n; $j++) {
        dfs(0, $j, $pacific, $heights, $directions);
        dfs($m - 1, $j, $atlantic, $heights, $directions);
    }
    
    $result = [];
    for ($i = 0; $i < $m; $i++) {
        for ($j = 0; $j < $n; $j++) {
            if ($pacific[$i][$j] && $atlantic[$i][$j]) {
                $result[] = [$i, $j];
            }
        }
    }
    return $result;
}

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

Задача: 1240. Tiling a Rectangle with the Fewest Squares
Сложность: hard

Если задан прямоугольник размером n x m, верните минимальное количество квадратов с целочисленными сторонами, которые покрывают этот прямоугольник.

Пример:

Input: n = 2, m = 3
Output: 3

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

1⃣Инициализация рекурсивной функции:
Функция принимает размеры прямоугольника n x m.

2⃣Базовый случай:
Если n = 0 или m = 0, возвращаем 0, так как не осталось пространства для покрытия.

3⃣Рекурсивный случай:
Находим наибольший возможный квадрат, который может быть размещен в текущем прямоугольнике. Это квадрат со стороной min(n, m).
Размещаем этот квадрат в левом верхнем углу и рекурсивно покрываем оставшиеся три части:
Прямоугольник слева от квадрата.
Прямоугольник сверху от квадрата.
Прямоугольник справа и снизу от квадрата.

😎 Решение:

function tilingRectangle($n, $m) {
    $dp = array_fill(0, $n + 1, array_fill(0, $m + 1, PHP_INT_MAX));
    
    for ($i = 1; $i <= min($n, $m); $i++) {
        $dp[$i][$i] = 1;
    }
    
    for ($h = 1; $h <= $n; $h++) {
        for ($w = 1; $w <= $m; $w++) {
            if ($h == $w) continue;
            for ($i = 1; $i <= intdiv($h, 2); $i++) {
                $dp[$h][$w] = min($dp[$h][$w], $dp[$i][$w] + $dp[$h - $i][$w]);
            }
            for ($j = 1; $j <= intdiv($w, 2); $j++) {
                $dp[$h][$w] = min($dp[$h][$w], $dp[$h][$j] + $dp[$h][$w - $j]);
            }
        }
    }
    return $dp[$n][$m];
}

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

Задача: 895. Maximum Frequency Stack
Сложность: hard

Разработайте структуру данных, похожую на стек, чтобы заталкивать элементы в стек и вытаскивать из него самый частый элемент. Реализуйте класс FreqStack: FreqStack() строит пустой стек частот. void push(int val) заталкивает целое число val на вершину стека. int pop() удаляет и возвращает самый частый элемент в стеке. Если есть равенство в выборе самого частого элемента, то удаляется и возвращается элемент, который ближе всего к вершине стека.

Пример:

Input
["FreqStack", "push", "push", "push", "push", "push", "push", "pop", "pop", "pop", "pop"]
[[], [5], [7], [5], [7], [4], [5], [], [], [], []]
Output
[null, null, null, null, null, null, null, 5, 7, 5, 4]

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

1⃣Создать два словаря: freq для хранения частоты каждого элемента и group для хранения стека элементов для каждой частоты.

2⃣При добавлении элемента увеличивать его частоту в freq и добавлять его в стек соответствующей частоты в group.

3⃣При извлечении элемента найти максимальную частоту, удалить элемент из стека соответствующей частоты и уменьшить его частоту в freq. Если стек для данной частоты становится пустым, удалить его.

😎 Решение:

class FreqStack {
    private $freq;
    private $group;
    private $maxfreq;

    function __construct() {
        $this->freq = [];
        $this->group = [];
        $this->maxfreq = 0;
    }

    function push($val) {
        $f = ($this->freq[$val] ?? 0) + 1;
        $this->freq[$val] = $f;
        if ($f > $this->maxfreq) {
            $this->maxfreq = $f;
            $this->group[$f] = [];
        }
        $this->group[$f][] = $val;
    }

    function pop() {
        $val = array_pop($this->group[$this->maxfreq]);
        $this->freq[$val]--;
        if (empty($this->group[$this->maxfreq])) {
            $this->maxfreq--;
        }
        return $val;
    }
}

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

Задача: 73. Set Matrix Zeroes
Сложность: medium

Дана матрица размером m×n, состоящая из целых чисел. Если элемент матрицы равен 0, установите в 0 все элементы его строки и столбца.

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

Пример:

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]

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

1⃣Мы перебираем матрицу и отмечаем первую ячейку строки i и первую ячейку столбца j, если условие в приведенном выше псевдокоде выполняется, т.е. если cell[i][j] == 0.

2⃣Первая ячейка строки и столбца для первой строки и первого столбца совпадают, т.е. cell[0][0]. Поэтому мы используем дополнительную переменную, чтобы узнать, был ли отмечен первый столбец, а cell[0][0] используется для того же для первой строки.

3⃣Теперь мы перебираем исходную матрицу, начиная со второй строки и второго столбца, т.е. с matrix[1][1]. Для каждой ячейки мы проверяем, были ли ранее отмечены строка r или столбец c, проверяя соответствующую первую ячейку строки или первую ячейку столбца. Если любая из них была отмечена, мы устанавливаем значение в ячейке на 0. Обратите внимание, что первая строка и первый столбец служат как row_set и column_set, которые мы использовали в первом подходе. Затем мы проверяем, равна ли cell[0][0] нулю, если это так, мы отмечаем первую строку как ноль. И, наконец, если первый столбец был отмечен, мы делаем все записи в нем нулевыми.

😎 Решение:

function setZeroes(&$matrix) {
    $isCol = false;
    $R = count($matrix);
    $C = count($matrix[0]);

    for ($i = 0; $i < $R; $i++) {
        if ($matrix[$i][0] == 0) {
            $isCol = true;
        }
        for ($j = 1; $j < $C; $j++) {
            if ($matrix[$i][$j] == 0) {
                $matrix[0][$j] = 0;
                $matrix[$i][0] = 0;
            }
        }
    }

    for ($i = 1; $i < $R; $i++) {
        for ($j = 1; $j < $C; $j++) {
            if ($matrix[$i][0] == 0 || $matrix[0][$j] == 0) {
                $matrix[$i][$j] = 0;
            }
        }
    }

    if ($matrix[0][0] == 0) {
        for ($j = 0; $j < $C; $j++) {
            $matrix[0][$j] = 0;
        }
    }

    if ($isCol) {
        for ($i = 0; $i < $R; $i++) {
            $matrix[$i][0] = 0;
        }
    }
}

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

Задача: 46. Permutations
Сложность: medium

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

Пример:

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

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

1⃣Если длина curr равна длине nums, добавьте копию curr в ans и вернитесь.

2⃣Итерируйтесь по nums. Для каждого num, если num не в curr, выполните следующее:
Добавьте num в curr и вызовите backtrack(curr), затем удалите num из curr.

3⃣Вызовите backtrack с изначально пустым curr.
Верните ans.

😎 Решение:

function permute($nums) {
    $ans = [];
    $backtrack = function (&$curr) use (&$ans, &$backtrack, $nums) {
        if (count($curr) === count($nums)) {
            $ans[] = $curr;
            return;
        }
        foreach ($nums as $num) {
            if (!in_array($num, $curr)) {
                $curr[] = $num;
                $backtrack($curr);
                array_pop($curr);
            }
        }
    };
    $backtrack([]);
    return $ans;
}

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