Задача: 1519. Number of Nodes in the Sub-Tree With the Same Label
Сложность: medium

Вам дано дерево (т.е. связный неориентированный граф без циклов), состоящее из n узлов, пронумерованных от 0 до n - 1, и ровно n - 1 ребра. Корнем дерева является узел 0, и каждый узел дерева имеет метку, которая является строчной буквой, указанной в строке labels (т.е. узел с номером i имеет метку labels[i]).

Массив edges дан в форме edges[i] = [ai, bi], что означает, что существует ребро между узлами ai и bi в дереве.

Верните массив размера n, где ans[i] — это количество узлов в поддереве узла i, которые имеют ту же метку, что и узел i.

Поддерево дерева T — это дерево, состоящее из узла в T и всех его дочерних узлов.

Пример:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = "abaedcd"
Output: [2,1,1,1,1,1,1]
Explanation: Node 0 has label 'a' and its sub-tree has node 2 with label 'a' as well, thus the answer is 2. Notice that any node is part of its sub-tree.
Node 1 has a label 'b'. The sub-tree of node 1 contains nodes 1,4 and 5, as nodes 4 and 5 have different labels than node 1, the answer is just 1 (the node itself).

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

1⃣Создайте список смежности, где adj[X] содержит всех соседей узла X.

2⃣Инициализируйте массив ans, хранящий ответ для каждого узла, и заполните его нулями.

3⃣Начните обход в глубину (DFS).

😎 Решение:

class Solution {
    function dfs($node, $parent, $adj, $labels, &$ans) {
        $nodeCounts = array_fill(0, 26, 0);
        $nodeCounts[ord($labels[$node]) - ord('a')] = 1;

        if (!isset($adj[$node])) return $nodeCounts;

        foreach ($adj[$node] as $child) {
            if ($child == $parent) continue;
            $childCounts = $this->dfs($child, $node, $adj, $labels, $ans);
            for ($i = 0; $i < 26; $i++) {
                $nodeCounts[$i] += $childCounts[$i];
            }
        }

        $ans[$node] = $nodeCounts[ord($labels[$node]) - ord('a')];
        return $nodeCounts;
    }

    function countSubTrees($n, $edges, $labels) {
        $adj = [];
        foreach ($edges as $edge) {
            $adj[$edge[0]][] = $edge[1];
            $adj[$edge[1]][] = $edge[0];
        }

        $ans = array_fill(0, $n, 0);
        $this->dfs(0, -1, $adj, $labels, $ans);
        return $ans;
    }
}

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

Задача: 168. Excel Sheet Column Title
Сложность: easy

Дано целое число columnNumber, верните соответствующий заголовок столбца, как он отображается в таблице Excel.

Например:
A -> 1
B -> 2
C -> 3
Z -> 26
AA -> 27
AB -> 28

Пример:

Input: columnNumber = 1
Output: "A"

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

1⃣Инициализация пустой строки ans:
Создайте пустую строку ans, которая будет хранить заголовок столбца.

2⃣Циклическое преобразование числа в буквы:
Пока columnNumber больше 0, выполняйте следующие действия:
Вычтите 1 из columnNumber для корректировки индекса (Excel использует 1-индексацию).
Найдите символ, соответствующий остатку от деления columnNumber на 26, и добавьте его в начало строки ans.
Присвойте columnNumber значение от деления columnNumber на 26

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

😎 Решение:

class Solution {
    function convertToTitle($columnNumber) {
        $ans = "";

        while ($columnNumber > 0) {
            $columnNumber--;
            $ans = chr($columnNumber % 26 + ord('A')) . $ans;
            $columnNumber = intdiv($columnNumber, 26);
        }

        return $ans;
    }
}

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

Задача: 1129. Shortest Path with Alternating Colors
Сложность: medium

Вам дано целое число n, количество узлов в ориентированном графе, где узлы помечены от 0 до n - 1. Каждое ребро в этом графе может быть красным или синим, и могут быть самопетли и параллельные ребра.

Вам даны два массива redEdges и blueEdges, где:
redEdges[i] = [ai, bi] указывает, что в графе существует направленное красное ребро от узла ai к узлу bi, и
blueEdges[j] = [uj, vj] указывает, что в графе существует направленное синее ребро от узла uj к узлу vj.
Верните массив answer длины n, где каждый answer[x] — это длина кратчайшего пути от узла 0 до узла x, такого что цвета ребер чередуются вдоль пути, или -1, если такого пути не существует.

Пример:

Input: n = 3, redEdges = [[0,1],[1,2]], blueEdges = []
Output: [0,1,-1]

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

1⃣Создание структуры данных и инициализация:
Создайте список смежности adj, который будет содержать пары (сосед, цвет) для каждого узла.
Создайте массив answer длиной n, инициализированный значением -1, чтобы хранить длину кратчайшего пути для каждого узла.
Создайте 2D массив visit для отслеживания, были ли узлы посещены с использованием ребра определённого цвета.

2⃣Инициализация очереди и начальных условий:
Создайте очередь для хранения трёх значений (узел, количество шагов, цвет предыдущего ребра).
Добавьте в очередь начальный узел (0, 0, -1) и установите visit[0][0] и visit[0][1] в true, так как повторное посещение узла 0 бессмысленно.

3⃣Обработка очереди и обновление результата:
Пока очередь не пуста, извлекайте элемент из очереди и получайте (узел, количество шагов, цвет предыдущего ребра).
Для каждого соседа, если сосед не был посещён с использованием ребра текущего цвета и текущий цвет не равен предыдущему, обновите массив answer и добавьте соседа в очередь.

😎 Решение:

class Solution {
    function shortestAlternatingPaths($n, $redEdges, $blueEdges) {
        $adj = [];
        foreach ($redEdges as $edge) {
            $adj[$edge[0]][] = [$edge[1], 0];
        }
        foreach ($blueEdges as $edge) {
            $adj[$edge[0]][] = [$edge[1], 1];
        }

        $answer = array_fill(0, $n, -1);
        $visit = array_fill(0, $n, [false, false]);
        $queue = [[0, 0, -1]];
        $answer[0] = 0;
        $visit[0][0] = true;
        $visit[0][1] = true;

        while ($queue) {
            list($node, $steps, $prevColor) = array_shift($queue);
            if (!isset($adj[$node])) continue;
            foreach ($adj[$node] as $nei) {
                list($neighbor, $color) = $nei;
                if (!$visit[$neighbor][$color] && $color != $prevColor) {
                    if ($answer[$neighbor] == -1) {
                        $answer[$neighbor] = $steps + 1;
                    }
                    $visit[$neighbor][$color] = true;
                    $queue[] = [$neighbor, $steps + 1, $color];
                }
            }
        }
        return $answer;
    }
}

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

Задача: 526. Beautiful Arrangement
Сложность: medium

Предположим, у вас есть n целых чисел, пронумерованных от 1 до n. Перестановка этих n целых чисел perm (нумерация с 1) считается красивой, если для каждого i (1 <= i <= n) выполняется одно из следующих условий:
perm[i] делится на i.
i делится на perm[i].
Дано целое число n, верните количество красивых перестановок, которые вы можете создать.

Пример:

Input: n = 2
Output: 2
Explanation: 
The first beautiful arrangement is [1,2]:
    - perm[1] = 1 is divisible by i = 1
    - perm[2] = 2 is divisible by i = 2
The second beautiful arrangement is [2,1]:
    - perm[1] = 2 is divisible by i = 1
    - i = 2 is divisible by perm[2] = 1

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

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

2⃣Рекурсивное создание перестановок и проверка условий:
Напишите рекурсивную функцию для создания всех возможных перестановок массива, начиная с текущей позиции l.
На каждом шаге перестановки проверяйте, удовлетворяет ли текущий элемент условиям делимости. Если условие выполняется, продолжайте создание перестановок рекурсивно для следующей позиции.

3⃣Возврат результата:
В основной функции вызовите рекурсивную функцию с начальной позицией 0 и верните значение счетчика красивых перестановок.

😎 Решение:

class Solution {
    private $count = 0;
    
    function countArrangement($N) {
        $nums = range(1, $N);
        $this->permute($nums, 0);
        return $this->count;
    }
    
    private function permute(&$nums, $l) {
        if ($l == count($nums)) {
            $this->count++;
        }
        for ($i = $l; $i < count($nums); $i++) {
            $this->swap($nums, $i, $l);
            if ($nums[$l] % ($l + 1) == 0 || ($l + 1) % $nums[$l] == 0) {
                $this->permute($nums, $l + 1);
            }
            $this->swap($nums, $i, $l);
        }
    }
    
    private function swap(&$nums, $x, $y) {
        $temp = $nums[$x];
        $nums[$x] = $nums[$y];
        $nums[$y] = $temp;
    }
}

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

Задача: 409. Longest Palindrome
Сложность: easy

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

Пример:

Input: s = "abccccdd"
Output: 7

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

1⃣Создайте словарь для подсчета количества каждого символа в строке.

2⃣Пройдитесь по словарю и добавьте четное количество каждого символа к длине палиндрома. Если встречается нечетное количество символа, добавьте (count - 1) к длине палиндрома.

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

😎 Решение:

function longestPalindrome($s) {
    $charCount = [];
    foreach (str_split($s) as $char) {
        if (isset($charCount[$char])) {
            $charCount[$char]++;
        } else {
            $charCount[$char] = 1;
        }
    }
    $length = 0;
    $oddFound = false;
    foreach ($charCount as $count) {
        if ($count % 2 == 0) {
            $length += $count;
        } else {
            $length += $count - 1;
            $oddFound = true;
        }
    }
    return $oddFound ? $length + 1 : $length;
}

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

Задача: 1244. Design A Leaderboard
Сложность: medium

Разработайте класс Leaderboard, который содержит 3 функции: addScore(playerId, score): Обновляет таблицу лидеров, добавляя счет к счету данного игрока. Если в таблице лидеров нет игрока с таким id, добавьте его в таблицу лидеров с заданным счетом. top(K): Возвращает сумму очков K лучших игроков. reset(playerId): Сбрасывает счет игрока с заданным идентификатором в 0 (другими словами, стирает его из таблицы лидеров). Гарантируется, что игрок был добавлен в таблицу лидеров до вызова этой функции. Изначально таблица лидеров пуста.

Пример:

Input: 
["Leaderboard","addScore","addScore","addScore","addScore","addScore","top","reset","reset","addScore","top"]
[[],[1,73],[2,56],[3,39],[4,51],[5,4],[1],[1],[2],[2,51],[3]]
Output: 
[null,null,null,null,null,null,73,null,null,null,141]

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

1⃣addScore(playerId, score):
Если игрок уже существует в таблице лидеров, добавляем к его текущему счету новое значение.
Если игрок не существует, добавляем его с заданным счетом.

2⃣top(K):
Сортируем игроков по их счету в порядке убывания.
Возвращаем сумму очков K лучших игроков.

3⃣reset(playerId):
Устанавливаем счет игрока в 0.

😎 Решение:

class Leaderboard {
    private $scores;

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

    public function addScore($playerId, $score) {
        if (isset($this->scores[$playerId])) {
            $this->scores[$playerId] += $score;
        } else {
            $this->scores[$playerId] = $score;
        }
    }

    public function top($K) {
        arsort($this->scores);
        return array_sum(array_slice($this->scores, 0, $K));
    }

    public function reset($playerId) {
        $this->scores[$playerId] = 0;
    }
}

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

Задача: 1382. Balance a Binary Search Tree
Сложность: medium

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

Бинарное дерево поиска считается сбалансированным, если глубина двух поддеревьев каждого узла никогда не отличается более чем на 1.

Пример:

Input: root = [1,null,2,null,3,null,4,null,null]
Output: [2,1,3,null,null,null,4]
Explanation: This is not the only correct answer, [3,1,4,null,2] is also correct.

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

1⃣Инициализация. Создайте пустой список inorder для хранения значений узлов после обхода в порядке возрастания.

2⃣Выполнение обхода в порядке возрастания. Обойдите бинарное дерево поиска (BST) и заполните список inorder значениями узлов в отсортированном порядке.

3⃣Перестроение сбалансированного BST. Определите рекурсивную функцию createBalancedBST, которая принимает список inorder, начальный индекс и конечный индекс в качестве параметров. Если начальный индекс больше конечного, верните null (или эквивалент). Вычислите средний индекс как середину текущего диапазона. Создайте новый узел дерева со значением в среднем индексе. Рекурсивно создайте левое поддерево, используя левую половину текущего диапазона. Рекурсивно создайте правое поддерево, используя правую половину текущего диапазона. Верните корень вновь построенного сбалансированного BST.

😎 Решение:

class Solution {
    function balanceBST($root) {
        if (!$root) return null;

        $vineHead = new TreeNode(0);
        $vineHead->right = $root;
        $current = $vineHead;

        while ($current->right) {
            if ($current->right->left) {
                $this->rightRotate($current, $current->right);
            } else {
                $current = $current->right;
            }
        }

        $nodeCount = 0;
        $current = $vineHead->right;
        while ($current) {
            $nodeCount++;
            $current = $current->right;
        }

        $m = pow(2, floor(log($nodeCount + 1, 2))) - 1;
        $this->makeRotations($vineHead, $nodeCount - $m);
        while ($m > 1) {
            $m /= 2;
            $this->makeRotations($vineHead, $m);
        }

        return $vineHead->right;
    }

    private function rightRotate($parent, $node) {
        $tmp = $node->left;
        $node->left = $tmp->right;
        $tmp->right = $node;
        $parent->right = $tmp;
    }

    private function leftRotate($parent, $node) {
        $tmp = $node->right;
        $node->right = $tmp->left;
        $tmp->left = $node;
        $parent->right = $tmp;
    }

    private function makeRotations($vineHead, $count) {
        $current = $vineHead;
        for ($i = 0; $i < $count; $i++) {
            $tmp = $current->right;
            $this->leftRotate($current, $tmp);
            $current = $current->right;
        }
    }
}

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

Задача №22. Generate Parentheses
Сложность: medium

Учитывая n пар круглых скобок, напишите функцию, которая генерирует все комбинации правильных круглых скобок.

Пример:

Input: n = 3  
Output: ["((()))","(()())","(())()","()(())","()()()"]

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

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

2⃣Если еще можно открыть скобку — добавляем ( и уменьшаем счетчик открытых.

3⃣Если есть закрытые скобки, которые можно закрыть — добавляем ).

😎 Решение:

class Solution { 

    private array $answer = []; 
    private string $current = ''; 

    function generateParenthesis($n) { 
        $this->generateParentheses($n, 0); 
        return $this->answer; 
    } 

    function generateParentheses($toOpen, $toClose) { 
        if ($toOpen == 0 && $toClose == 0) { 
            $this->answer[] = $this->current; 
            return; 
        } 

        if ($toOpen > 0) { 
            $this->current .= '('; 
            $this->generateParentheses($toOpen - 1, $toClose + 1); 
            $this->current = substr($this->current, 0, -1); 
        } 

        if ($toClose > 0) { 
            $this->current .= ')'; 
            $this->generateParentheses($toOpen, $toClose - 1); 
            $this->current = substr($this->current, 0, -1); 
        }         
    } 
}

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

Задача: 237. Delete Node in a Linked List
Сложность: medium

Дан односвязный список, требуется удалить конкретный узел, не имея доступа к head.
Гарантируется, что node не последний.

Пример:

Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.

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

1⃣Копирование данных: Скопируйте значение из следующего узла (node.next) в текущий узел (node). Таким образом, текущий узел будет иметь значение, которое было в следующем узле.

2⃣Обновление указателя: Обновите указатель next текущего узла, чтобы он ссылался на узел, следующий за узлом node.next. Это effectively удалит следующий узел из списка.

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

😎 Решение:

class Solution {
    function deleteNode($node) {
        $node->val = $node->next->val;
        $node->next = $node->next->next;
    }
}

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

Задача: 205. Isomorphic Strings
Сложность: easy

Даны две строки s и t, определите, являются ли они изоморфными.
Две строки s и t являются изоморфными, если символы в s могут быть заменены для получения t.
Все вхождения одного символа должны быть заменены другим символом, сохраняя порядок символов. Два символа не могут отображаться в один и тот же символ, но один символ может отображаться сам на себя.

Пример:

Input: s = "egg", t = "add"
Output: true

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

1⃣Определите два словаря: mapping_s_t для отображения символов из строки s в символы строки t, и mapping_t_s для отображения символов из строки t в символы строки s.

2⃣Итеративно пройдитесь по символам строк s и t. Для каждого символа c1 из s и соответствующего c2 из t, если c1 нет в mapping_s_t и c2 нет в mapping_t_s, добавьте соответствующие отображения; если одно из отображений существует, проверьте, соответствует ли оно ожидаемому значению.

3⃣Если в процессе проверки какое-либо отображение неверно, верните false. Если все проверки пройдены успешно, верните true после окончания итерации по строкам.

😎 Решение:

class Solution {
    function isIsomorphic($s, $t) {
        $mappingStoT = [];
        $mappingTtoS = [];

        for ($i = 0; $i < strlen($s); ++$i) {
            $c1 = $s[$i];
            $c2 = $t[$i];

            if (!isset($mappingStoT[$c1]) && !isset($mappingTtoS[$c2])) {
                $mappingStoT[$c1] = $c2;
                $mappingTtoS[$c2] = $c1;
            } else if (($mappingStoT[$c1] ?? null) !== $c2 || ($mappingTtoS[$c2] ?? null) !== $c1) {
                return false;
            }
        }

        return true;
    }
}

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

Задача: 785. Is Graph Bipartite?
Сложность: medium

Есть неориентированный граф с n узлами, где каждый узел пронумерован от 0 до n - 1. Вам дан двумерный массив graph, где graph[u] — это массив узлов, смежных с узлом u. Более формально, для каждого v в graph[u] существует неориентированное ребро между узлом u и узлом v. Граф обладает следующими свойствами:

Нет петель (graph[u] не содержит u).
Нет параллельных ребер (graph[u] не содержит дублирующихся значений).
Если v есть в graph[u], то u есть в graph[v] (граф неориентированный).
Граф может быть несвязным, то есть могут существовать два узла u и v, между которыми нет пути.
Граф является двудольным, если узлы можно разделить на два независимых множества A и B так, что каждое ребро в графе соединяет узел из множества A с узлом из множества B.

Верните true, если и только если граф является двудольным.

Пример:

Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output: false
Explanation: There is no way to partition the nodes into two independent sets such that every edge connects a node in one and a node in the other.

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

1⃣Мы будем хранить массив (или hashmap) для поиска цвета каждого узла: color[node]. Цвета могут быть 0, 1 или неокрашенные (-1 или null).

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

3⃣Для выполнения поиска в глубину мы используем стек. Для каждого неокрашенного соседа в graph[node] мы будем его окрашивать и добавлять в наш стек, который действует как своего рода "список дел" для узлов, которые нужно посетить дальше. Наш внешний цикл для start... гарантирует, что мы окрасим каждый узел.

😎 Решение:

class Solution {
    function isBipartite($graph) {
        $color = [];
        for ($node = 0; $node < count($graph); $node++) {
            if (!isset($color[$node])) {
                $stack = [$node];
                $color[$node] = 0;
                while (!empty($stack)) {
                    $currentNode = array_pop($stack);
                    foreach ($graph[$currentNode] as $neighbor) {
                        if (!isset($color[$neighbor])) {
                            $stack[] = $neighbor;
                            $color[$neighbor] = $color[$currentNode] ^ 1;
                        } elseif ($color[$neighbor] == $color[$currentNode]) {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }
}

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

Задача: 583. Delete Operation for Two Strings
Сложность: medium

Даны две строки word1 и word2, вернуть минимальное количество шагов, необходимых для того, чтобы сделать word1 и word2 одинаковыми.
На одном шаге можно удалить ровно один символ в любой строке.

Пример:

Input: word1 = "sea", word2 = "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

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

1⃣Инициализация массива:
Создайте одномерный массив dp для хранения минимального количества удалений, необходимых для уравнивания строк word1 и word2.

2⃣Заполнение массива:
Используйте временный массив temp для обновления значений dp, представляющих текущую строку. Обновите temp с использованием значений dp предыдущей строки.

3⃣Обновление и результат:
Скопируйте временный массив temp обратно в dp после обработки каждой строки. В конце верните значение из dp, представляющее минимальное количество удалений.

😎 Решение:

class Solution {
    function minDistance($word1, $word2) {
        $m = strlen($word1);
        $n = strlen($word2);
        $dp = array_fill(0, $n + 1, 0);

        for ($i = 0; $i <= $m; $i++) {
            $temp = array_fill(0, $n + 1, 0);
            for ($j = 0; $j <= $n; $j++) {
                if ($i == 0 || $j == 0) {
                    $temp[$j] = $i + $j;
                } else if ($word1[$i - 1] == $word2[$j - 1]) {
                    $temp[$j] = $dp[$j - 1];
                } else {
                    $temp[$j] = 1 + min($dp[$j], $temp[$j - 1]);
                }
            }
            $dp = $temp;
        }

        return $dp[$n];
    }
}

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

Задача: 836. Rectangle Overlap
Сложность: easy

Прямоугольник, выровненный по осям, представляется в виде списка [x1, y1, x2, y2], где (x1, y1) — координата его нижнего левого угла, а (x2, y2) — координата его верхнего правого угла. Его верхняя и нижняя грани параллельны оси X, а левая и правая грани параллельны оси Y.

Два прямоугольника перекрываются, если площадь их пересечения положительна. Для ясности, два прямоугольника, которые касаются только в углу или по краям, не перекрываются.

Даны два выровненных по осям прямоугольника rec1 и rec2, вернуть true, если они перекрываются, в противном случае вернуть false.

Пример:

Input: rec1 = [0,0,2,2], rec2 = [1,1,3,3]
Output: true

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

1⃣Рассчитайте ширину пересечения: пересечение по оси x положительно, если min(rec1[2], rec2[2]) > max(rec1[0], rec2[0]).

2⃣Рассчитайте высоту пересечения: пересечение по оси y положительно, если min(rec1[3], rec2[3]) > max(rec1[1], rec2[1]).

3⃣Если и ширина, и высота пересечения положительны, прямоугольники перекрываются.

😎 Решение:

class Solution {
    /**
     * @param Integer[] $rec1
     * @param Integer[] $rec2
     * @return Boolean
     */
    function isRectangleOverlap($rec1, $rec2) {
        return min($rec1[2], $rec2[2]) > max($rec1[0], $rec2[0]) &&
               min($rec1[3], $rec2[3]) > max($rec1[1], $rec2[1]);
    }
}

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

Задача: 977. Squares of a Sorted Array
Сложность: easy

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

Пример:

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].

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

1⃣Создайте массив квадратов каждого элемента.

2⃣Отсортируйте массив квадратов.

3⃣Верните отсортированный массив квадратов.

😎 Решение:

class Solution {
    function sortedSquares($nums) {
        $ans = array_map(function($num) {
            return $num * $num;
        }, $nums);
        sort($ans);
        return $ans;
    }
}

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

Задача: 1472. Design Browser History
Сложность: medium

У вас есть браузер с одной вкладкой, где вы начинаете на домашней странице и можете посетить другой URL, вернуться назад на определённое количество шагов в истории или переместиться вперёд на определённое количество шагов в истории.

Реализуйте класс BrowserHistory:
BrowserHistory(string homepage) Инициализирует объект с домашней страницей браузера.
void visit(string url) Посещает URL с текущей страницы. Это очищает всю историю вперёд.
string back(int steps) Перемещает на steps шагов назад в истории. Если вы можете вернуться только на x шагов в истории, а steps > x, вы вернётесь только на x шагов. Возвращает текущий URL после перемещения назад в истории на не более чем steps шагов.
string forward(int steps) Перемещает на steps шагов вперёд в истории. Если вы можете переместиться только на x шагов вперёд в истории, а steps > x, вы переместитесь только на x шагов. Возвращает текущий URL после перемещения вперёд в истории на не более чем steps шагов.

Пример:

Input:
["BrowserHistory","visit","visit","visit","back","back","forward","visit","forward","back","back"]
[["leetcode.com"],["google.com"],["facebook.com"],["youtube.com"],[1],[1],[1],["linkedin.com"],[2],[2],[7]]
Output:
[null,null,null,null,"facebook.com","google.com","facebook.com",null,"linkedin.com","google.com","leetcode.com"]

Explanation:
BrowserHistory browserHistory = new BrowserHistory("leetcode.com");
browserHistory.visit("google.com");       // You are in "leetcode.com". Visit "google.com"
browserHistory.visit("facebook.com");     // You are in "google.com". Visit "facebook.com"
browserHistory.visit("youtube.com");      // You are in "facebook.com". Visit "youtube.com"
browserHistory.back(1);                   // You are in "youtube.com", move back to "facebook.com" return "facebook.com"
browserHistory.back(1);                   // You are in "facebook.com", move back to "google.com" return "google.com"
browserHistory.forward(1);                // You are in "google.com", move forward to "facebook.com" return "facebook.com"
browserHistory.visit("linkedin.com");     // You are in "facebook.com". Visit "linkedin.com"
browserHistory.forward(2);                // You are in "linkedin.com", you cannot move forward any steps.

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

1⃣Инициализация:
Создайте класс BrowserHistory с двумя стеками (history и future) и строковой переменной current для хранения текущего URL. Инициализируйте current с домашней страницей.

2⃣Посещение URL:
Метод visit(url) сохраняет текущий URL в стеке history, устанавливает url как текущий и очищает стек future.

3⃣Навигация назад и вперед:
Метод back(steps) перемещает текущий URL в стек future и извлекает URL из стека history, пока шаги не будут исчерпаны или стек history не станет пустым.
Метод forward(steps) перемещает текущий URL в стек history и извлекает URL из стека future, пока шаги не будут исчерпаны или стек future не станет пустым.

😎 Решение:

class BrowserHistory {
    private $history;
    private $future;
    private $current;
    
    function __construct($homepage) {
        $this->history = [];
        $this->future = [];
        $this->current = $homepage;
    }
    
    function visit($url) {
        array_push($this->history, $this->current);
        $this->current = $url;
        $this->future = [];
    }
    
    function back($steps) {
        while ($steps > 0 && count($this->history) > 0) {
            array_push($this->future, $this->current);
            $this->current = array_pop($this->history);
            $steps--;
        }
        return $this->current;
    }
    
    function forward($steps) {
        while ($steps > 0 && count($this->future) > 0) {
            array_push($this->history, $this->current);
            $this->current = array_pop($this->future);
            $steps--;
        }
        return $this->current;
    }
}

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

Задача: 384. Shuffle an Array
Сложность: medium

Дан целочисленный массив nums. Разработайте алгоритм для случайного перемешивания массива. Все перестановки массива должны быть равновероятны в результате перемешивания.
Реализуйте класс Solution:
Solution(int[] nums): Инициализирует объект целочисленным массивом nums.
int[] reset(): Сбрасывает массив в его исходную конфигурацию и возвращает его.
int[] shuffle(): Возвращает случайное перемешивание массива.

Пример:

Input: ransomNote = "a", magazine = "b"
Output: false

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

1⃣Алгоритм Фишера-Йейтса удивительно похож на решение грубой силы. На каждой итерации алгоритма мы генерируем случайное целое число между текущим индексом и последним индексом массива.

2⃣Затем мы меняем местами элементы на текущем индексе и выбранном индексе. Это симулирует выбор (и удаление) элемента из "шляпы", так как следующий диапазон, из которого мы выбираем случайный индекс, не будет включать последний обработанный элемент.

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

😎 Решение:

class Solution {
    private $original;
    private $array;

    function __construct($nums) {
        $this->original = $nums;
        $this->array = $nums;
    }

    function reset() {
        $this->array = $this->original;
        return $this->original;
    }

    function shuffle() {
        $n = count($this->array);
        for ($i = 0; $i < $n; $i++) {
            $randIndex = rand($i, $n - 1);
            $temp = $this->array[$i];
            $this->array[$i] = $this->array[$randIndex];
            $this->array[$randIndex] = $temp;
        }
        return $this->array;
    }
}
?>

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

Задача: 209. Minimum Size Subarray Sum
Сложность: medium

Дан массив положительных целых чисел nums и положительное целое число target. Верните минимальную длину подмассива, сумма которого больше или равна target. Если такого подмассива нет, верните 0.

Пример:

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

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

1⃣Инициализация переменных:
Создайте три целочисленные переменные left, right и sumOfCurrentWindow. Переменные left и right формируют подмассив, указывая на начальные и конечные индексы текущего подмассива (или окна), а sumOfCurrentWindow хранит сумму этого окна. Инициализируйте все их значением 0.
Создайте еще одну переменную res для хранения ответа на задачу. Инициализируйте ее большим целым значением.

2⃣Итерация по массиву:
Итерируйте по массиву nums с помощью right, начиная с right = 0 до nums.length - 1, увеличивая right на 1 после каждой итерации. Выполняйте следующее внутри этой итерации:
Добавьте элемент с индексом right к текущему окну, увеличив sumOfCurrentWindow на nums[right].
Проверьте, если sumOfCurrentWindow >= target. Если да, у нас есть подмассив, который удовлетворяет условию. В результате, попытайтесь обновить переменную ответа res длиной этого подмассива. Выполните res = min(res, right - left + 1). Затем удалите первый элемент из этого окна, уменьшив sumOfCurrentWindow на nums[left] и увеличив left на 1. Этот шаг повторяется во внутреннем цикле, пока sumOfCurrentWindow >= target.

3⃣Возврат результата:
Текущая сумма окна теперь меньше target. Нужно добавить больше элементов в окно. В результате, увеличивается right на 1.
Верните res.

😎 Решение:

class Solution {
    public function minSubArrayLen($target, $nums) {
        $left = 0;
        $sumOfCurrentWindow = 0;
        $res = PHP_INT_MAX;

        for ($right = 0; $right < count($nums); $right++) {
            $sumOfCurrentWindow += $nums[$right];

            while ($sumOfCurrentWindow >= $target) {
                $res = min($res, $right - $left + 1);
                $sumOfCurrentWindow -= $nums[$left];
                $left++;
            }
        }

        return $res == PHP_INT_MAX ? 0 : $res;
    }
}

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

Задача: 605. Can Place Flowers
Сложность: Easy

У вас есть длинная клумба, на которой некоторые участки засажены, а некоторые нет. Однако цветы нельзя сажать на соседних участках.
Дан целочисленный массив flowerbed, содержащий 0 и 1, где 0 означает пустой участок, а 1 — занятый участок, и целое число n. Верните true, если n новых цветов можно посадить на клумбе, не нарушая правила о соседних цветах, и false в противном случае.

Пример:

Input: flowerbed = [1,0,0,0,1], n = 1
Output: true

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

1⃣Решение очень простое. Мы можем определить максимальное количество дополнительных цветов, count, которые можно посадить для данного расположения клумбы. Для этого мы проходим по всем элементам массива flowerbed и находим те элементы, которые равны 0 (означает пустую позицию).

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

3⃣Если полученное количество count больше или равно n, требуемому количеству цветов для посадки, мы можем посадить n цветов на пустые места, иначе - нет.

😎 Решение:

class Solution {
    function canPlaceFlowers($flowerbed, $n) {
        $count = 0;
        for ($i = 0; $i < count($flowerbed); $i++) {
            if ($flowerbed[$i] == 0) {
                $emptyLeft = $i == 0 || $flowerbed[$i - 1] == 0;
                $emptyRight = $i == count($flowerbed) - 1 || $flowerbed[$i + 1] == 0;
                if ($emptyLeft && $emptyRight) {
                    $flowerbed[$i] = 1;
                    $count++;
                }
            }
        }
        return $count >= $n;
    }
}

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

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

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

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

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