#hard
Задача: 827. Making A Large Island

Вам дан n x n бинарный матрица grid. Вам разрешено изменить не более одного 0 на 1.

Верните размер самого большого острова в grid после выполнения этой операции.

Остров — это группа 1, соединенных в 4 направлениях.

Пример:

Input: grid = [[1,1],[1,0]]
Output: 4
Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.

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

1⃣Пройдите по матрице и пометьте каждую группу, используя уникальный индекс, и запомните её размер.

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

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

😎 Решение:

class Solution {
    private $dr = [-1, 0, 1, 0];
    private $dc = [0, -1, 0, 1];
    private $grid;
    private $N;

    function largestIsland($grid) {
        $this->grid = $grid;
        $this->N = count($grid);
        
        $index = 2;
        $area = array_fill(0, $this->N * $this->N + 2, 0);
        for ($r = 0; $r < $this->N; ++$r) {
            for ($c = 0; $c < $this->N; ++$c) {
                if ($grid[$r][$c] == 1) {
                    $area[$index] = $this->dfs($r, $c, $index);
                    ++$index;
                }
            }
        }
        
        $ans = max($area);
        for ($r = 0; $r < $this->N; ++$r) {
            for ($c = 0; $c < $this->N; ++$c) {
                if ($grid[$r][$c] == 0) {
                    $seen = [];
                    foreach ($this->neighbors($r, $c) as $move) {
                        if ($grid[$move[0]][$move[1]] > 1) {
                            $seen[$grid[$move[0]][$move[1]]] = true;
                        }
                    }
                    $bns = 1;
                    foreach (array_keys($seen) as $i) {
                        $bns += $area[$i];
                    }
                    $ans = max($ans, $bns);
                }
            }
        }
        
        return $ans;
    }

    function dfs($r, $c, $index) {
        $ans = 1;
        $this->grid[$r][$c] = $index;
        foreach ($this->neighbors($r, $c) as $move) {
            if ($this->grid[$move[0]][$move[1]] == 1) {
                $this->grid[$move[0]][$move[1]] = $index;
                $ans += $this->dfs($move[0], $move[1], $index);
            }
        }
        return $ans;
    }

    function neighbors($r, $c) {
        $ans = [];
        for ($k = 0; $k < 4; ++$k) {
            $nr = $r + $this->dr[$k];
            $nc = $c + $this->dc[$k];
            if ($nr >= 0 && $nr < $this->N && $nc >= 0 && $nc < $this->N) {
                $ans[] = [$nr, $nc];
            }
        }
        return $ans;
    }

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

Задача №17. Letter Combinations of a Phone Number
Сложность: medium

Учитывая строку, содержащую цифры от 2 до 9 включительно, верните все возможные комбинации букв, которые может представлять число. Верните ответ в любом порядке. Соответствие цифр буквам (как на кнопках телефона) приведено ниже. Обратите внимание, что 1 не соответствует никаким буквам.

Пример:

Input: digits = "23"  
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

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

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

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

3⃣Добавлять полученные комбинации в результирующий массив.

😎 Решение:

class Solution { 
 
    public $result = []; 
 
    function letterCombinations($digits) { 
        if(strlen($digits) == 0) { 
            return []; 
        } 
 
        $layouts = [ 
            2 => range('a', 'c'), 
            3 => range('d', 'f'), 
            4 => range('g', 'i'), 
            5 => range('j', 'l'),  
            6 => range('m', 'o'),  
            7 => range('p', 's'), 
            8 => range('t', 'v'), 
            9 => range('w', 'z'), 
        ]; 
 
        return $this->recursive(0, $digits, $layouts); 
    } 
 
    function recursive ($index, $chars, $layouts, $combine = '') { 
        foreach($layouts[$chars[$index]] as $currentLayout) { 
            if($layouts[$chars[$index + 1]]) { 
                $this->recursive($index + 1, $chars, $layouts, $combine . $currentLayout); 
            } else { 
                $this->result[] = $combine . $currentLayout; 
            } 
        } 
 
        return $this->result; 
    } 
}

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

Задача: 226. Invert Binary Tree
Сложность: easy

Дан корень бинарного дерева, инвертируйте дерево и верните его корень.

Пример:

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

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

1⃣Рекурсивная инверсия поддеревьев:
Если текущий узел (root) пустой, возвращаем null.
Рекурсивно инвертируем правое поддерево и сохраняем результат в переменную right.
Рекурсивно инвертируем левое поддерево и сохраняем результат в переменную left.

2⃣Обмен поддеревьев:
Устанавливаем левое поддерево текущего узла равным правому поддереву.
Устанавливаем правое поддерево текущего узла равным левому поддереву.

3⃣Возврат корня:
Возвращаем текущий узел (root) как новый корень инвертированного дерева.

😎 Решение:

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

class Solution {
    public function invertTree($root) {
        if ($root === null) {
            return null;
        }
        $right = $this->invertTree($root->right);
        $left = $this->invertTree($root->left);
        $root->left = $right;
        $root->right = $left;
        return $root;
    }
}

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

Задача: 1275. Find Winner on a Tic Tac Toe Game
Сложность: easy

В игру "Крестики-нолики" играют два игрока A и B на сетке 3 x 3. Правила игры "Крестики-нолики" таковы: игроки по очереди помещают символы в пустые квадраты ' '. Первый игрок A всегда помещает символы "X", а второй игрок B - "O". Символы "X" и "O" всегда помещаются в пустые квадраты, а не в заполненные.
Игра заканчивается, когда три одинаковых (непустых) символа заполняют любую строку, столбец или диагональ. Игра также заканчивается, если все клетки непустые. Больше ходов не может быть сыграно, если игра закончена. Учитывая двумерный целочисленный массив moves, где moves[i] = [rowi, coli] указывает, что i-й ход будет сыгран на сетке[rowi][coli]. верните победителя игры, если он существует (A или B). Если игра закончилась вничью, верните "Ничья". Если еще есть ходы для игры, верните "Pending". Можно предположить, что ходы действительны (т.е. соответствуют правилам игры в Крестики-нолики), сетка изначально пуста, и A будет играть первым.

Пример:

Input: moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
Output: "A"

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

1⃣Инициализируйте пустую 3x3 сетку.

2⃣Пройдите по списку ходов и обновите сетку в соответствии с ходами игроков A и B.

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

😎 Решение:

function tictactoe($moves) {
    $grid = array_fill(0, 3, array_fill(0, 3, ''));
    for ($i = 0; $i < count($moves); $i++) {
        $r = $moves[$i][0];
        $c = $moves[$i][1];
        $grid[$r][$c] = $i % 2 == 0 ? 'X' : 'O';
    }

    for ($i = 0; $i < 3; $i++) {
        if ($grid[$i][0] == $grid[$i][1] && $grid[$i][1] == $grid[$i][2] && $grid[$i][0] != '')
            return $grid[$i][0] == 'X' ? 'A' : 'B';
        if ($grid[0][$i] == $grid[1][$i] && $grid[1][$i] == $grid[2][$i] && $grid[0][$i] != '')
            return $grid[0][$i] == 'X' ? 'A' : 'B';
    }

    if ($grid[0][0] == $grid[1][1] && $grid[1][1] == $grid[2][2] && $grid[0][0] != '')
        return $grid[0][0] == 'X' ? 'A' : 'B';
    if ($grid[0][2] == $grid[1][1] && $grid[1][1] == $grid[2][0] && $grid[0][2] != '')
        return $grid[0][2] == 'X' ? 'A' : 'B';

    return count($moves) == 9 ? 'Draw' : 'Pending';
}

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

Задача: 686. Repeated String Match
Сложность: medium

Даны две строки a и b. Верните минимальное количество повторений строки a, чтобы строка b стала её подстрокой. Если сделать b подстрокой a невозможно, верните -1.

Обратите внимание: строка "abc", повторенная 0 раз, это "", повторенная 1 раз - "abc", повторенная 2 раза - "abcabc".

Пример:

Input: a = "abcd", b = "cdabcdab"
Output: 3
Explanation: We return 3 because by repeating a three times "abcdabcdabcd", b is a substring of it.

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

1⃣Найти минимальное количество повторений строки A, чтобы её длина стала больше или равна длине B. Это значение q = ceil(len(B) / len(A)).

2⃣Проверить, является ли B подстрокой строки A, повторенной q раз. Если да, вернуть q. Иначе, проверить строку A, повторенную (q+1) раз. Если B является подстрокой этой строки, вернуть q+1.

3⃣Если B не является подстрокой ни в одном из случаев, вернуть -1.

😎 Решение:

class Solution {
    function repeatedStringMatch($A, $B) {
        $q = 1;
        $S = $A;
        while (strlen($S) < strlen($B)) {
            $S .= $A;
            $q++;
        }
        if (strpos($S, $B) !== false) return $q;
        if (strpos($S . $A, $B) !== false) return $q + 1;
        return -1;
    }
}

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

Задача: 146. LRU Cache
Сложность: medium

Реализуйте класс LRUCache:
LRUCache(int capacity) - инициализирует LRU-кэш с положительным размером capacity.
int get(int key) - возвращает значение по ключу, если ключ существует, в противном случае возвращает -1.
void put(int key, int value) - обновляет значение по ключу, если ключ существует. В противном случае добавляет пару ключ-значение в кэш. Если количество ключей превышает установленную емкость после этой операции, удаляет наименее недавно использованный ключ.

Функции get и put должны выполняться за среднее время O(1).

Пример:

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

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

1⃣Метод добавления узла в конец связного списка (add):
Получите текущий узел в конце списка, это "реальный" хвост: tail.prev, обозначим его как previousEnd.
Вставьте node после previousEnd, установив previousEnd.next = node.
Настройте указатели узла: node.prev = previousEnd и node.next = tail.
Обновите tail.prev = node, делая node новым "реальным" хвостом списка.

2⃣Метод удаления узла из связного списка (remove):
Узел node должен быть удален из списка. Для этого определите узлы nextNode = node.next и prevNode = node.prev.
Чтобы удалить node, переназначьте prevNode.next = nextNode и nextNode.prev = prevNode, эффективно исключая node из списка.
Это превратит, например, последовательность A <-> B <-> C в A <-> C, где prevNode = A и nextNode = C.

3⃣Методы get и put:
get(int key): Проверьте, существует ли ключ в хэш-карте. Если нет, верните -1. Иначе, получите узел, связанный с ключом, переместите его в конец списка с помощью remove(node) и add(node). Верните node.val.
put(int key, int value): Если ключ уже существует, найдите соответствующий узел и удалите его методом remove. Создайте новый узел с key и value, добавьте его в хэш-карту и в конец списка методом add(node). Если размер кэша превышает установленную емкость после добавления, удалите самый редко используемый узел (который находится в голове списка после фиктивного узла head), затем удалите соответствующий ключ из хэш-карты.

😎 Решение:

class Node {
    public $key;
    public $value;
    public $next;
    public $prev;

    public function __construct($key, $value) {
        $this->key = $key;
        $this->value = $value;
        $this->next = null;
        $this->prev = null;
    }
}

class LRUCache {
    private $capacity;
    private $dic = [];
    private $head;
    private $tail;
    
    public function __construct($capacity) {
        $this->capacity = $capacity;
        $this->head = new Node(-1, -1);
        $this->tail = new Node(-1, -1);
        $this->head->next = $this->tail;
        $this->tail->prev = $this->head;
    }

    public function get($key) {
        if (!array_key_exists($key, $this->dic)) {
            return -1;
        }
        $node = $this->dic[$key];
        $this->remove($node);
        $this->add($node);
        return $node->value;
    }

    public function put($key, $value) {
        if (array_key_exists($key, $this->dic)) {
            $this->remove($this->dic[$key]);
        }
        $node = new Node($key, $value);
        $this->add($node);
        $this->dic[$key] = $node;
        if (count($this->dic) > $this->capacity) {
            $nodeToDelete = $this->head->next;
            $this->remove($nodeToDelete);
            unset($this->dic[$nodeToDelete->key]);
        }
    }

    private function add($node) {
        $pre = $this->tail->prev;
        $pre->next = $node;
        $node->prev = $pre;
        $node->next = $this->tail;
        $this->tail->prev = $node;
    }

    private function remove($node) {
        $pre = $node->prev;
        $nxt = $node->next;
        $pre->next = $nxt;
        $nxt->prev = $pre;
    }
}

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

Задача: 946. Validate Stack Sequences
Сложность: medium

Учитывая, что два целочисленных массива pushed и popped имеют разные значения, верните true, если это могло быть результатом последовательности операций push и pop на изначально пустом стеке, или false в противном случае.

Пример:

Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true

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

1⃣Инициализировать пустой стек.
Использовать указатель j для отслеживания текущей позиции в массиве popped.

2⃣Пройти по каждому элементу в массиве pushed:
Добавить элемент в стек.
Проверить верхний элемент стека:
Если он совпадает с текущим элементом в popped, удалить элемент из стека и увеличить указатель j.

3⃣В конце вернуть true, если указатель j достиг конца массива popped, иначе вернуть false.

😎 Решение:

function validateStackSequences($pushed, $popped) {
    $stack = [];
    $j = 0;
    foreach ($pushed as $x) {
        $stack[] = $x;
        while (!empty($stack) && $j < count($popped) && end($stack) == $popped[$j]) {
            array_pop($stack);
            $j++;
        }
    }
    return $j == count($popped);
}

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

Задача: 1021. Remove Outermost Parentheses
Сложность: easy

Например, "", "()", "(" + A + ")" или A + B, где A и B - допустимые строки со скобками, а + означает объединение строк. Все допустимые строки со скобками - "", "()", "(())()" и "(()(())".
Допустимая строка со скобками s является примитивной, если она непустая и не существует способа разбить ее на s = A + B, причем A и B - непустые допустимые строки со скобками. Если дана допустимая строка со скобками s, рассмотрим ее примитивное разложение: s = P1 + P2 + ... + Pk, где Pi - примитивные допустимые строки со скобками. Верните s после удаления крайних скобок из каждой примитивной строки в примитивном разложении s.

Пример:

Input: s = "(()())(())"
Output: "()()()"

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

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

2⃣Обработка строки:
Итерируйте по каждому символу строки.
Если встречаете (, увеличивайте счетчик уровня вложенности. Если уровень вложенности больше 1, добавьте ( в результат.
Если встречаете ), уменьшайте счетчик уровня вложенности. Если уровень вложенности больше 0 перед уменьшением, добавьте ) в результат.

3⃣Возврат результата:
Верните результат, содержащий строку без крайних скобок из каждой примитивной строки.

😎 Решение:

class Solution {
    function removeOuterParentheses($s) {
        $result = '';
        $level = 0;
        
        for ($i = 0; $i < strlen($s); $i++) {
            if ($s[$i] == '(') {
                if ($level > 0) {
                    $result .= $s[$i];
                }
                $level++;
            } else {
                $level--;
                if ($level > 0) {
                    $result .= $s[$i];
                }
            }
        }
        
        return $result;
    }
}

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

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

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

Задача: 1209. Remove All Adjacent Duplicates in String II
Сложность: medium

Вам дана строка s и целое число k. Удаление k дубликатов состоит в выборе k соседних и одинаковых букв из s и их удалении, что приводит к соединению левой и правой части удаленной подстроки вместе.
Мы повторяем удаление k дубликатов в s до тех пор, пока не сможем больше этого сделать.
Верните итоговую строку после всех таких удалений дубликатов. Гарантируется, что ответ уникален.

Пример:

Input: s = "deeedbbcccbdaa", k = 3
Output: "aa"
Explanation: 
First delete "eee" and "ccc", get "ddbbbdaa"
Then delete "bbb", get "dddaa"
Finally delete "ddd", get "aa"

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

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

2⃣Перемещать быстрый указатель i по строке s:
Копировать s[i] в s[j].
Если s[j] совпадает с s[j - 1], увеличить значение на вершине стека.
Иначе добавить 1 в стек.
Если количество символов равно k, уменьшить j на k и извлечь из стека.

3⃣Вернуть первые j символов строки.

😎 Решение:

class Solution {
    function removeDuplicates($s, $k) {
        $counts = [];
        $sa = str_split($s);
        $j = 0;
        
        for ($i = 0; $i < count($sa); ++$i, ++$j) {
            $sa[$j] = $sa[$i];
            if ($j == 0 || $sa[$j] != $sa[$j - 1]) {
                array_push($counts, 1);
            } else {
                $incremented = array_pop($counts) + 1;
                if ($incremented == $k) {
                    $j -= $k;
                } else {
                    array_push($counts, $incremented);
                }
            }
        }
        return implode('', array_slice($sa, 0, $j));
    }
}

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

Задача: 34. Find First and Last Position of Element in Sorted Array
Сложность: medium

Дан массив nums, отсортированный в порядке неубывания, и число target. Необходимо найти начальную и конечную позицию target в nums.
Если target не найден, вернуть [-1, -1].
Алгоритм должен работать за O(log n).

Пример:

Input: nums = [5,7,7,8,8,10], target = 8  
Output: [3,4]  

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

1⃣Используем бинарный поиск, чтобы найти первое вхождение target.

2⃣Аналогично находим последнее вхождение target.

3⃣Возвращаем найденные индексы или [-1, -1], если target отсутствует.

😎 Решение:

class Solution {
    function searchRange($nums, $target) {
        return [$this->binarySearch($nums, $target, true), $this->binarySearch($nums, $target, false)];
    }

    function binarySearch($nums, $target, $findFirst) {
        $left = 0;
        $right = count($nums) - 1;
        $index = -1;

        while ($left <= $right) {
            $mid = intdiv($left + $right, 2);

            if ($nums[$mid] == $target) {
                $index = $mid;
                if ($findFirst) {
                    $right = $mid - 1;
                } else {
                    $left = $mid + 1;
                }
            } elseif ($nums[$mid] < $target) {
                $left = $mid + 1;
            } else {
                $right = $mid - 1;
            }
        }

        return $index;
    }
}

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

Задача: 830. Positions of Large Groups
Сложность: easy

В строке s из строчных букв эти буквы образуют последовательные группы одного и того же символа.
Например, строка s = "abbxxxxzyy" имеет группы "a", "bb", "xxxx", "z" и "yy".
Группа идентифицируется интервалом [start, end], где start и end обозначают начальный и конечный индексы (включительно) группы. В приведенном выше примере "xxxx" имеет интервал [3,6].
Группа считается большой, если в ней 3 или более символов.

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

Пример:

Input: s = "abcdddeeeeaabbbcd"
Output: [[3,5],[6,9],[12,14]]
Explanation: The large groups are "ddd", "eeee", and "bbb".

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

1⃣Поддерживайте указатели i и j, где i <= j. Указатель i представляет начало текущей группы, а j будет инкрементироваться вперед, пока не достигнет конца группы.

2⃣Когда j достигнет конца строки или S[j] != S[j+1], у нас будет группа [i, j]. Если длина группы больше или равна 3, добавьте её в результат.

3⃣Обновите i = j + 1 и начните новую группу.

😎 Решение:

class Solution {
    /**
     * @param String $S
     * @return Integer[][]
     */
    function largeGroupPositions($S) {
        $ans = [];
        $i = 0;
        $N = strlen($S);

        for ($j = 0; $j < $N; ++$j) {
            if ($j == $N - 1 || $S[$j] != $S[$j + 1]) {
                if ($j - $i + 1 >= 3) {
                    $ans[] = [$i, $j];
                }
                $i = $j + 1;
            }
        }

        return $ans;
    }
}

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

Задача: 1062. Longest Repeating Substring
Сложность: medium

Дана строка s. Вернуть длину самой длинной повторяющейся подстроки. Если повторяющаяся подстрока отсутствует, вернуть 0.

Пример:

Input: s = "abcd"
Output: 0
Explanation: There is no repeating substring.

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

1⃣Перемещайте скользящее окно длиной L по строке длиной N.

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

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

😎 Решение:

class Solution {
    function search($L, $n, $S) {
        $seen = [];
        for ($start = 0; $start <= $n - $L; ++$start) {
            $tmp = substr($S, $start, $L);
            if (in_array($tmp, $seen)) return $start;
            $seen[] = $tmp;
        }
        return -1;
    }

    function longestRepeatingSubstring($S) {
        $n = strlen($S);
        $left = 1; $right = $n;
        while ($left <= $right) {
            $L = $left + intdiv($right - $left, 2);
            if ($this->search($L, $n, $S) !== -1) {
                $left = $L + 1;
            } else {
                $right = $L - 1;
            }
        }
        return $left - 1;
    }
}

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

Задача: 892. Surface Area of 3D Shapes
Сложность: easy

Вам дана сетка n x n, на которой вы разместили несколько кубиков 1 x 1 x 1. Каждое значение v = grid[i][j] представляет собой башню из v кубиков, размещенных на вершине ячейки (i, j). После размещения кубиков вы решили склеить все непосредственно прилегающие кубики друг с другом, образовав несколько неправильных 3D-фигур. Верните общую площадь поверхности получившихся фигур. Примечание: нижняя грань каждой фигуры учитывается в площади ее поверхности.

Пример:

Input: grid = [[1,2],[3,4]]
Output: 34

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

1⃣Пройти по всей сетке и для каждой башни (ячейки) посчитать начальную площадь поверхности: добавить площадь верхней и нижней граней, а также четыре боковые грани.

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

3⃣Просуммировать все значения площадей для получения итоговой площади поверхности.

😎 Решение:

function surfaceArea($grid) {
    $n = count($grid);
    $area = 0;
    for ($i = 0; $i < $n; $i++) {
        for ($j = 0; $j < $n; $j++) {
            if ($grid[$i][$j] > 0) {
                $area += ($grid[$i][$j] * 4) + 2;
            }
            if ($i > 0) {
                $area -= min($grid[$i][$j], $grid[$i-1][$j]) * 2;
            }
            if ($j > 0) {
                $area -= min($grid[$i][$j], $grid[$i][$j-1]) * 2;
            }
        }
    }
    return $area;
}

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

Задача №19. Remove Nth Node From End of List
Сложность: medium

Учитывая заголовок связанного списка, удалите n-й узел из конца списка и верните его заголовок.

Пример:

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

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

1⃣Определить длину списка, пройдясь по нему один раз.

2⃣Найти узел, предшествующий удаляемому, используя второй проход.

3⃣Изменить ссылки, чтобы удалить целевой узел.

😎 Решение:

class Solution { 
 
    function removeNthFromEnd($head, $n) { 
        $tamaño = 0; 
        $aux = $head; 
 
        while ($aux !== null) { 
            $aux = $aux->next; 
            $tamaño++; 
        } 
 
        if ($tamaño == 1) { 
            return null; 
        } 
        if ($tamaño == $n) { 
            return $head->next; 
        } 
 
        $aux = $head; 
        for ($i = 0; $i < $tamaño - $n - 1; $i++) { 
            $aux = $aux->next; 
        } 
 
        $aux->next = $aux->next->next; 
 
        return $head; 
    } 
}

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

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

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

Пример:

Input: s = "abc"
Output: 3

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

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

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

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

😎 Решение:

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

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

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

    return $totalCount;
}

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

Задача: 1485. Clone Binary Tree With Random Pointer
Сложность: medium

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

Дерево представлено в том же формате ввода/вывода, что и обычные бинарные деревья, где каждый узел представлен в виде пары [val, random_index], где:
- val: целое число, представляющее Node.val
- random_index: индекс узла (во входных данных), на который указывает случайный указатель, или null, если он не указывает ни на один узел.

Вам будет дано дерево в классе Node, и вы должны вернуть клонированное дерево в классе NodeCopy. Класс NodeCopy является клоном класса Node с такими же атрибутами и конструкторами.

Пример:

Input: root = [[1,null],null,[4,3],[7,0]]
Output: [[1,null],null,[4,3],[7,0]]
Explanation: The original binary tree is [1,null,4,7].
The random pointer of node one is null, so it is represented as [1, null].
The random pointer of node 4 is node 7, so it is represented as [4, 3] where 3 is the index of node 7 in the array representing the tree.
The random pointer of node 7 is node 1, so it is represented as [7, 0] where 0 is the index of node 1 in the array representing the tree.

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

1⃣Глубокое копирование дерева:
Инициализируйте хэш-таблицу newOldPairs, которая сопоставляет узлы старого дерева с узлами нового дерева.
Создайте функцию deepCopy(root), которая принимает корень данного дерева и возвращает корень нового дерева. Эта функция создаёт новый узел с теми же значениями, что и корневой узел, и рекурсивно копирует левое и правое поддеревья. Затем она сохраняет пару старого и нового узлов в хэш-таблицу и возвращает новый корень.

2⃣Сопоставление случайных указателей:
Создайте функцию mapRandomPointers(oldNode), которая принимает корень старого дерева и рекурсивно сопоставляет случайные указатели нового дерева с соответствующими узлами старого дерева, используя хэш-таблицу newOldPairs.

3⃣Возвращение клонированного дерева:
Создайте глубокую копию дерева, используя функцию deepCopy(root), и сопоставьте все случайные указатели нового дерева с помощью функции mapRandomPointers(root). Верните новый корень.

😎 Решение:

class Node {
    public $val;
    public $left;
    public $right;
    public $random;

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

class NodeCopy {
    public $val;
    public $left;
    public $right;
    public $random;

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

class Solution {
    private $newOldPairs = [];

    private function deepCopy($root) {
        if ($root === null) {
            return null;
        }
        $newRoot = new NodeCopy($root->val);
        $newRoot->left = $this->deepCopy($root->left);
        $newRoot->right = $this->deepCopy($root->right);
        $this->newOldPairs[spl_object_id($root)] = $newRoot;
        return $newRoot;
    }

    private function mapRandomPointers($oldNode) {
        if ($oldNode === null) {
            return;
        }
        $newNode = $this->newOldPairs[spl_object_id($oldNode)];
        if ($newNode) {
            $newNode->random = $this->newOldPairs[spl_object_id($oldNode->random)] ?? null;
            $this->mapRandomPointers($oldNode->left);
            $this->mapRandomPointers($oldNode->right);
        }
    }

    public function copyRandomBinaryTree($root) {
        $newRoot = $this->deepCopy($root);
        $this->mapRandomPointers($root);
        return $newRoot;
    }
}

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

Задача: 1022. Sum of Root To Leaf Binary Numbers
Сложность: easy

Вам дан корень двоичного дерева, в котором каждый узел имеет значение 0 или 1. Каждый путь от корня к листьям представляет собой двоичное число, начиная со старшего бита. Например, если путь 0 -> 1 -> 1 -> 0 -> 1, то в двоичном виде это может представлять 01101, что равно 13. Для всех листьев дерева рассмотрите числа, представленные путем от корня к этому листу. Верните сумму этих чисел. Тестовые примеры генерируются таким образом, чтобы ответ помещался в 32-битовое целое число.

Пример:

Input: root = [1,0,1,0,1,0,1]
Output: 22

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

1⃣Рекурсивный обход дерева:
Используйте функцию DFS (поиск в глубину) для обхода дерева, начиная от корня. Передавайте текущее значение числа по пути как параметр.

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

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

😎 Решение:

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

class Solution {
    function sumRootToLeaf($root) {
        return $this->dfs($root, 0);
    }
    
    private function dfs($node, $currentValue) {
        if ($node === null) return 0;
        $currentValue = ($currentValue << 1) | $node->val;
        if ($node->left === null && $node->right === null) return $currentValue;
        return $this->dfs($node->left, $currentValue) + $this->dfs($node->right, $currentValue);
    }
}

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

Задача: 1329. Sort the Matrix Diagonally
Сложность: medium

Диагональ матрицы — это диагональная линия ячеек, начинающаяся с какой-либо ячейки в самой верхней строке или в самом левом столбце и идущая в направлении вниз-вправо до конца матрицы. Например, диагональ матрицы, начинающаяся с mat[2][0], где mat — это матрица размером 6 x 3, включает ячейки mat[2][0], mat[3][1] и mat[4][2].

Дана матрица mat размером m x n, состоящая из целых чисел. Отсортируйте каждую диагональ матрицы по возрастанию и верните полученную матрицу.

Пример:

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

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

1⃣Сохраните размеры матрицы m и n. Создайте хеш-карту из минимальных куч для хранения элементов диагоналей.

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

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

😎 Решение:

class Solution {
    function diagonalSort($mat) {
        $m = count($mat);
        $n = count($mat[0]);
        $diagonals = [];

        for ($row = 0; $row < $m; $row++) {
            for ($col = 0; $col < $n; $col++) {
                $key = $row - $col;
                if (!isset($diagonals[$key])) {
                    $diagonals[$key] = [];
                }
                $diagonals[$key][] = $mat[$row][$col];
            }
        }

        foreach ($diagonals as &$diagonal) {
            sort($diagonal);
        }

        for ($row = 0; $row < $m; $row++) {
            for ($col = 0; $col < $n; $col++) {
                $key = $row - $col;
                $mat[$row][$col] = array_shift($diagonals[$key]);
            }
        }

        return $mat;
    }
}

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

    return true;
}

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

Задача: 61. Rotate List
Сложность: medium

Дан указатель на начало связного списка, поверните список вправо на k позиций.

Пример:

Input: head = [0,1,2], k = 4
Output: [2,0,1]

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

1⃣Найдите старый хвост и соедините его с головой (old_tail.next = head), чтобы замкнуть кольцо. Одновременно вычислите длину списка n.

2⃣Найдите новый хвост, который находится на позиции (n - k % n - 1) от головы, и новую голову, которая находится на позиции (n - k % n).

3⃣Разорвите кольцо (new_tail.next = None) и верните new_head.

😎 Решение:

function rotateRight($head, $k) {
    if ($head === null) return null;
    if ($head->next === null) return $head;

    $oldTail = $head;
    $n = 1;
    while ($oldTail->next !== null) {
        $oldTail = $oldTail->next;
        $n++;
    }
    $oldTail->next = $head;

    $newTail = $head;
    for ($i = 0; $i < $n - $k % $n - 1; $i++) {
        $newTail = $newTail->next;
    }
    $newHead = $newTail->next;

    $newTail->next = null;
    return $newHead;
}

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