PHP | LeetCode

Задача: 1328. Break a Palindrome
Сложность: medium

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

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

Строка a лексикографически меньше строки b (одинаковой длины), если в первой позиции, где они отличаются, у строки a символ строго меньше соответствующего символа в строке b. Например, "abcc" лексикографически меньше "abcd", потому что первой различающейся позицией является четвертая, и 'c' меньше, чем 'd'.

Пример:

Input: palindrome = "abccba"
Output: "aaccba"
Explanation: There are many ways to make "abccba" not a palindrome, such as "zbccba", "aaccba", and "abacba".
Of all the ways, "aaccba" is the lexicographically smallest.

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

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

2⃣Итерируйтесь по строке слева до середины строки: если символ не равен 'a', измените его на 'a' и верните строку.

3⃣Если вы прошли всю левую часть строки и все еще не получили непалиндромическую строку, это означает, что строка состоит только из 'a'. Следовательно, измените последний символ на 'b' и верните полученную строку.

😎 Решение:

class Solution {
    function breakPalindrome($palindrome) {
        $length = strlen($palindrome);
        
        if ($length == 1) {
            return "";
        }
        
        $palindromeArray = str_split($palindrome);
        for ($i = 0; $i < $length / 2; $i++) {
            if ($palindromeArray[$i] != 'a') {
                $palindromeArray[$i] = 'a';
                return implode('', $palindromeArray);
            }
        }
        
        $palindromeArray[$length - 1] = 'b';
        return implode('', $palindromeArray);
    }
}

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

Задача: 320. Generalized Abbreviation
Сложность: medium

Обобщённая аббревиатура слова может быть построена путём замены несмежных и неперекрывающихся подстрок на их длины.
Например, для слова "abcde" возможны сокращения:
"a3e" — "bcd" заменено на "3"
"1bcd1" — "a" и "e" заменены на "1"
"5" — всё слово заменено на длину
"abcde" — без сокращений
Недопустимы:
"23" — замены "ab" и "cde" смежны
"22de" — замены "ab" и "bc" перекрываются
Нужно вернуть все возможные обобщённые аббревиатуры слова word.

Пример:

Input: word = "a"
Output: ["1","a"]

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

1⃣Создание битовых масок
Каждая аббревиатура имеет одно к одному соответствие с n-битным двоичным числом x, где n - длина слова. Используйте эти числа в качестве чертежей для построения соответствующих аббревиатур.

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

3⃣Перебор всех комбинаций
Для каждого числа от 0 до 2^n - 1 используйте его битовое представление для создания соответствующей аббревиатуры. Сканируйте число x побитово, извлекая его последний бит с помощью b = x & 1 и сдвигая x вправо на один бит x >>= 1.

😎 Решение:

class Solution {
    function generateAbbreviations($word) {
        $result = [];
        $n = strlen($word);
        
        for ($x = 0; $x < (1 << $n); $x++) {
            $result[] = $this->abbr($word, $x);
        }
        
        return $result;
    }

    private function abbr($word, $x) {
        $builder = "";
        $k = 0;
        $n = strlen($word);
        
        for ($i = 0; $i < $n; $i++, $x >>= 1) {
            if (($x & 1) == 0) {
                if ($k != 0) {
                    $builder .= $k;
                    $k = 0;
                }
                $builder .= $word[$i];
            } else {
                $k++;
            }
        }
        
        if ($k != 0) $builder .= $k;
        return $builder;
    }
}

$sol = new Solution();
print_r($sol->generateAbbreviations("word"));

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

Задача: 120. Triangle
Сложность: medium

Дан массив в виде треугольника, верните минимальную сумму пути сверху вниз.

На каждом шаге вы можете перейти к соседнему числу в строке ниже. Более формально, если вы находитесь на индексе i в текущей строке, вы можете перейти либо к индексу i, либо к индексу i + 1 в следующей строке.

Пример:

Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: The triangle looks like:
   2
  3 4
 6 5 7
4 1 8 3
The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).

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

1⃣Простейший способ реализации этого заключается в перезаписи входных данных, то есть в использовании алгоритма "на месте". В подходе 2 мы рассмотрим, как модифицировать алгоритм так, чтобы он не перезаписывал входные данные, но при этом не требовал более чем O(n) дополнительного пространства.

2⃣Когда этот алгоритм завершит свою работу, каждая ячейка (строка, столбец) входного треугольника будет перезаписана минимальной суммой пути от (0, 0) (вершины треугольника) до (строка, столбец) включительно.
Совет на собеседовании: Алгоритмы "на месте" перезаписывают входные данные для экономии места, но иногда это может вызвать проблемы. Вот несколько ситуаций, когда алгоритм "на месте" может быть неуместен.

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

😎 Решение:

class Solution {
    public function minimumTotal($triangle) {
        for ($row = 1; $row < count($triangle); $row++) {
            for ($col = 0; $col <= $row; $col++) {
                $smallestAbove = PHP_INT_MAX;
                if ($col > 0) {
                    $smallestAbove = $triangle[$row - 1][$col - 1];
                }
                if ($col < $row) {
                    $smallestAbove = min($smallestAbove, $triangle[$row - 1][$col]);
                }
                $triangle[$row][$col] += $smallestAbove;
            }
        }
        return min($triangle[count($triangle) - 1]);
    }
}

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

Задача: 640. Solve the Equation
Сложность: medium

Решите заданное уравнение и верните значение 'x' в виде строки "x=#value". Уравнение содержит только операции '+', '-', переменную 'x' и ее коэффициент. Вы должны вернуть "No solution", если для уравнения нет решения, или "Infinite solutions", если для уравнения существует бесконечное количество решений. Если для уравнения существует ровно одно решение, мы убеждаемся, что значение 'x' является целым числом.

Пример:

Input: s = "*"
Output: 9

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

1⃣Разделение уравнения
Разделите уравнение на левую и правую части относительно знака равенства '='.

2⃣Парсинг и упрощение
Пройдитесь по каждой части уравнения, упрощая ее до суммы коэффициентов 'x' и числовых значений.

3⃣Решение уравнения
Используйте уравнение вида ax + b = cx + d, чтобы решить для 'x'. Если коэффициенты 'x' равны и числовые значения равны, уравнение имеет бесконечное количество решений. Если коэффициенты 'x' равны, но числовые значения различны, решения нет. В противном случае вычислите значение 'x'.

😎 Решение:

function solveEquation($equation) {
    function parse($s) {
        $coeff = 0;
        $constPart = 0;
        $sign = 1;
        $num = 0;
        $i = 0;
        
        while ($i < strlen($s)) {
            if ($s[$i] === '+') {
                $sign = 1;
                $i++;
            } else if ($s[$i] === '-') {
                $sign = -1;
                $i++;
            } else if (ctype_digit($s[$i])) {
                $num = 0;
                while ($i < strlen($s) && ctype_digit($s[$i])) {
                    $num = $num * 10 + (int)$s[$i];
                    $i++;
                }
                if ($i < strlen($s) && $s[$i] === 'x') {
                    $coeff += $sign * $num;
                    $i++;
                } else {
                    $constPart += $sign * $num;
                }
            } else if ($s[$i] === 'x') {
                $coeff += $sign;
                $i++;
            }
        }
        return [$coeff, $constPart];
    }
    
    list($left, $right) = explode('=', $equation);
    list($leftCoeff, $leftConst) = parse($left);
    list($rightCoeff, $rightConst) = parse($right);
    
    $coeff = $leftCoeff - $rightCoeff;
    $constPart = $rightConst - $leftConst;
    
    if ($coeff == 0) {
        return $constPart == 0 ? "Infinite solutions" : "No solution";
    }
    return "x=" . ($constPart / $coeff);
}

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

Задача: 832. Flipping an Image
Сложность: easy

Дано бинарное изображение размером n x n, необходимо перевернуть изображение по горизонтали, затем инвертировать его и вернуть результат.
Перевернуть изображение по горизонтали означает, что каждая строка изображения будет развернута.
Например, переворот строки [1,1,0] по горизонтали дает [0,1,1].
Инвертировать изображение означает, что каждый 0 заменяется на 1, а каждый 1 заменяется на 0.
Например, инверсия строки [0,1,1] дает [1,0,0].

Пример:

Input: image = [[1,1,0],[1,0,1],[0,0,0]]
Output: [[1,0,0],[0,1,0],[1,1,1]]
Explanation: First reverse each row: [[0,1,1],[1,0,1],[0,0,0]].
Then, invert the image: [[1,0,0],[0,1,0],[1,1,1]]

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

1⃣Переверните каждую строку по горизонтали, обменяв элементы слева направо и наоборот.

2⃣Инвертируйте каждую строку, заменив каждый 0 на 1 и каждый 1 на 0.

3⃣Верните преобразованное изображение.

😎 Решение:

class Solution {
    /**
     * @param Integer[][] $A
     * @return Integer[][]
     */
    function flipAndInvertImage($A) {
        $C = count($A[0]);

        foreach ($A as &$row) {
            for ($i = 0; $i < (int)(($C + 1) / 2); ++$i) {
                $temp = $row[$i] ^ 1;
                $row[$i] = $row[$C - 1 - $i] ^ 1;
                $row[$C - 1 - $i] = $temp;
            }
        }

        return $A;
    }
}

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

Задача: 726. Number of Atoms
Сложность: hard

Если задана строковая формула, представляющая химическую формулу, верните количество атомов. Атомный элемент всегда начинается с прописного символа, затем ноль или более строчных букв, представляющих его название. Если количество больше 1, за ним может следовать одна или более цифр, представляющих количество элементов. Например, "H2O" и "H2O2" возможны, а "H1O2" невозможен. Две формулы объединяются вместе, чтобы получить другую формулу. Например, "H2O2He3Mg4" также является формулой.
Формула, заключенная в круглые скобки, и счет (по желанию) также являются формулами. Например, "(H2O2)" и "(H2O2)3" являются формулами.
Возвращает количество всех элементов в виде строки в следующем виде: первое имя (в отсортированном порядке), затем его количество (если это количество больше 1), затем второе имя (в отсортированном порядке), затем его количество (если это количество больше 1) и т. д. Тестовые примеры генерируются таким образом, чтобы все значения в выводе помещались в 32-битное целое число.

Пример:

Input: formula = "H2O"
Output: "H2O"

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

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

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

3⃣После завершения обработки строки, объедините все словари из стека и отсортируйте результат.

😎 Решение:

function countOfAtoms($formula) {
    $stack = [array()];
    $n = strlen($formula);
    $i = 0;

    while ($i < $n) {
        if ($formula[$i] == '(') {
            array_push($stack, array());
            $i++;
        } else if ($formula[$i] == ')') {
            $top = array_pop($stack);
            $i++;
            $i_start = $i;
            while ($i < $n && is_numeric($formula[$i])) {
                $i++;
            }
            $multiplicity = $i > $i_start ? intval(substr($formula, $i_start, $i - $i_start)) : 1;
            foreach ($top as $name => $count) {
                $stack[count($stack) - 1][$name] = ($stack[count($stack) - 1][$name] ?? 0) + $count * $multiplicity;
            }
        } else {
            $i_start = $i;
            $i++;
            while ($i < $n && ctype_lower($formula[$i])) {
                $i++;
            }
            $name = substr($formula, $i_start, $i - $i_start);
            $i_start = $i;
            while ($i < $n && is_numeric($formula[$i])) {
                $i++;
            }
            $multiplicity = $i > $i_start ? intval(substr($formula, $i_start, $i - $i_start)) : 1;
            $stack[count($stack) - 1][$name] = ($stack[count($stack) - 1][$name] ?? 0) + $multiplicity;
        }
    }

    $countMap = $stack[0];
    ksort($countMap);
    $result = '';
    foreach ($countMap as $name => $count) {
        $result .= $name;
        if ($count > 1) {
            $result .= $count;
        }
    }
    return $result;
}

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

Задача: 341. Flatten Nested List Iterator
Сложность: medium

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

Пример:

Input: nestedList = [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

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

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

2⃣Метод next()
Возвращает следующий целый элемент из стека или очереди. Если текущий элемент является списком, развёртывайте его и добавляйте элементы в стек.

3⃣Метод hasNext()
Проверяет, есть ли в стеке или очереди оставшиеся целые элементы. Если на вершине стека находится список, развёртывайте его до тех пор, пока не встретится целый элемент.

😎 Решение:

class NestedIterator {
    private $stack;
    
    function __construct($nestedList) {
        $this->stack = [];
        $this->flatten($nestedList);
    }
    
    private function flatten($nestedList) {
        for ($i = count($nestedList) - 1; $i >= 0; $i--) {
            array_push($this->stack, $nestedList[$i]);
        }
    }
    
    function next() {
        return array_pop($this->stack)->getInteger();
    }
    
    function hasNext() {
        while (!empty($this->stack) && !$this->stack[count($this->stack) - 1]->isInteger()) {
            $this->flatten(array_pop($this->stack)->getList());
        }
        return !empty($this->stack);
    }
}

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

Задача: 1192. Critical Connections in a Network
Сложность: hard

Существует n серверов, пронумерованных от 0 до n - 1, соединенных неориентированными соединениями "сервер-сервер", образуя сеть, где connections[i] = [ai, bi] представляет собой соединение между серверами ai и bi. Любой сервер может достичь других серверов напрямую или косвенно через сеть.

Критическое соединение — это соединение, удаление которого сделает невозможным достижение некоторыми серверами других серверов.
Верните все критические соединения в сети в любом порядке.

Пример:

Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: [[3,1]] is also accepted.

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

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

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

3⃣Поиск критических соединений:
После завершения обхода DFS преобразуйте оставшиеся соединения в список и верните его.

😎 Решение:

class Solution {
    private $graph;
    private $rank;
    private $connDict;
    
    function criticalConnections($n, $connections) {
        $this->formGraph($n, $connections);
        $this->dfs(0, 0);
        
        $result = [];
        foreach ($this->connDict as $conn => $_) {
            $result[] = explode(",", $conn);
        }
        return $result;
    }
    
    private function dfs($node, $discoveryRank) {
        if (isset($this->rank[$node])) {
            return $this->rank[$node];
        }
        
        $this->rank[$node] = $discoveryRank;
        $minRank = $discoveryRank + 1;
        
        foreach ($this->graph[$node] as $neighbor) {
            if (isset($this->rank[$neighbor]) && $this->rank[$neighbor] == $discoveryRank - 1) {
                continue;
            }
            
            $recursiveRank = $this->dfs($neighbor, $discoveryRank + 1);
            
            if ($recursiveRank <= $discoveryRank) {
                unset($this->connDict[implode(",", [min($node, $neighbor), max($node, $neighbor)])]);
            }
            
            $minRank = min($minRank, $recursiveRank);
        }
        
        return $minRank;
    }
    
    private function formGraph($n, $connections) {
        $this->graph = array_fill(0, $n, []);
        $this->rank = array_fill(0, $n, null);
        $this->connDict = [];
        
        foreach ($connections as $edge) {
            list($u, $v) = $edge;
            $this->graph[$u][] = $v;
            $this->graph[$v][] = $u;
            $this->connDict[implode(",", [min($u, $v), max($u, $v)])] = true;
        }
    }
}

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

Задача: 139. Word Break
Сложность: medium

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

Обратите внимание, что одно и то же слово из словаря может использоваться несколько раз при разделении.

Пример:

Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

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

1⃣Инициализация структур данных:
Преобразуйте wordDict в множество words для быстрой проверки вхождения.
Инициализируйте очередь queue начальным значением 0 (индекс начала строки) и множество seen для отслеживания посещённых индексов.

2⃣Обход в ширину (BFS):
Пока очередь не пуста, извлекайте первый элемент из очереди, обозначающий начальную позицию start.
Если start равен длине строки s, возвращайте true, так как достигнут конец строки, и строку можно разделить на слова из словаря.
Итерируйте end от start + 1 до s.length включительно. Для каждого end, проверьте, посещён ли он уже.

3⃣Проверка подстроки и обновление структур:
Проверьте подстроку начиная с start и заканчивая перед end. Если подстрока находится в множестве words, добавьте end в очередь и отметьте его в seen как посещённый.
Если BFS завершается и конечный узел не достигнут, возвращайте false.

😎 Решение:

function wordBreak($s, $wordDict) {
    $words = array_flip($wordDict); // Use an associative array to simulate a set for quick lookup
    $queue = [0];
    $seen = [];

    while (!empty($queue)) {
        $start = array_shift($queue); // Dequeue the first element
        if ($start == strlen($s)) {
            return true;
        }
        for ($end = $start + 1; $end <= strlen($s); $end++) {
            if (isset($seen[$end])) {
                continue;
            }
            $substring = substr($s, $start, $end - $start);
            if (isset($words[$substring])) {
                array_push($queue, $end); // Enqueue
                $seen[$end] = true; // Mark this end index as seen
            }
        }
    }
    return false;
}

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

Задача: 1365. How Many Numbers Are Smaller Than the Current Number
Сложность: easy

Дан массив nums. Для каждого элемента nums[i] определите, сколько чисел в массиве меньше его. То есть, для каждого nums[i] вам нужно посчитать количество допустимых j, таких что j != i и nums[j] < nums[i].

Верните ответ в виде массива.

Пример:

Input: nums = [6,5,4,8]
Output: [2,1,0,3]

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

1⃣Создание копии и сортировка массива:
Создайте отсортированную копию массива nums, чтобы легко находить количество элементов, меньших текущего.

2⃣Поиск индекса каждого элемента:
Для каждого элемента nums[i] найдите его индекс в отсортированной копии массива. Этот индекс указывает количество элементов, меньших nums[i].

3⃣Формирование ответа:
Сформируйте массив ответов, где каждый элемент будет соответствовать количеству чисел, меньших текущего.

😎 Решение:

class Solution {
    function smallerNumbersThanCurrent($nums) {
        $sortedNums = $nums;
        sort($sortedNums);
        $result = [];
        
        foreach ($nums as $num) {
            $result[] = array_search($num, $sortedNums);
        }
        
        return $result;
    }
}

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

Задача: 1056. Confusing Number
Сложность: easy

Запутанное число - это число, которое при повороте на 180 градусов становится другим числом, каждая цифра которого действительна. Мы можем повернуть цифры числа на 180 градусов, чтобы получить новые цифры. Когда 0, 1, 6, 8 и 9 поворачиваются на 180 градусов, они становятся 0, 1, 9, 8 и 6 соответственно.
При повороте на 180 градусов 2, 3, 4, 5 и 7 становятся недействительными. Обратите внимание, что после поворота числа мы можем игнорировать ведущие нули. Например, после поворота 8000 мы получим 0008, которое считается просто 8. Если задано целое число n, верните true, если это запутанное число, или false в противном случае.

Пример:

Input: n = 6
Output: true

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

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

2⃣Пройди по цифрам числа, проверяя, что все цифры действительны и заменяя их на соответствующие при повороте.

3⃣Проверь, что перевернутая строка отличается от исходной.

😎 Решение:

function isConfusingNumber($n) {
    $rotationMap = ['0' => '0', '1' => '1', '6' => '9', '8' => '8', '9' => '6'];
    $nStr = strval($n);
    $rotatedStr = "";

    for ($i = 0; $i < strlen($nStr); $i++) {
        $char = $nStr[$i];
        if (!isset($rotationMap[$char])) {
            return false;
        }
        $rotatedStr = $rotationMap[$char] . $rotatedStr;
    }

    return $rotatedStr !== $nStr;
}

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

Задача: 678. Valid Parenthesis String
Сложность: medium

Дана строка s, содержащая '(', ')' и '*'. Нужно определить, может ли она быть валидной скобочной последовательностью, если '*' может означать:
'('
')'
пустую строку ""

Пример:

Input: s = "()"
Output: true
Example 2:

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

1⃣Инициализировать 2D вектор memo размером s.size() x s.size() - 1, представляющий неинициализированное состояние. Вызвать вспомогательную функцию isValidString с начальными параметрами index = 0, openCount = 0 и строкой s. Вернуть результат isValidString.

2⃣Вспомогательная функция isValidString. Базовый случай: если index достиг конца строки (index == s.size.), вернуть true, если openCount равен 0 (все скобки сбалансированы), и false в противном случае. Проверить, был ли результат для текущего index и openCount уже вычислен (мемоизирован) в memo. Если да, вернуть мемоизированный результат. Инициализировать isValid как false. Если текущий символ s[index] равен '*': Попробовать трактовать '*' как '(' и вызвать isValidString рекурсивно с index + 1 и openCount + 1. Если рекурсивный вызов вернет true, обновить isValid на true. Если openCount не равен нулю, попробовать трактовать '*' как ')' и вызвать isValidString рекурсивно с index + 1 и openCount - 1. Если рекурсивный вызов вернет true, обновить isValid на true. Попробовать трактовать '*' как пустой символ и вызвать isValidString рекурсивно с index + 1 и тем же openCount. Если рекурсивный вызов вернет true, обновить isValid на true.

3⃣Продолжение функции isValidString. Если текущий символ s[index] равен '(': Вызвать isValidString рекурсивно с index + 1 и openCount + 1. Обновить isValid с результатом рекурсивного вызова. Если текущий символ s[index] равен ')': Если openCount не равен нулю (есть открытые скобки), вызвать isValidString рекурсивно с index + 1 и openCount - 1. Обновить isValid с результатом рекурсивного вызова. Мемоизировать результат isValid в memo[index][openCount]. Вернуть isValid.

😎 Решение:

class Solution {
    function checkValidString($s) {
        $memo = array_fill(0, strlen($s), array_fill(0, strlen($s), -1));
        return $this->isValidString(0, 0, $s, $memo);
    }

    private function isValidString($index, $openCount, $str, &$memo) {
        if ($index == strlen($str)) {
            return $openCount == 0;
        }

        if ($memo[$index][$openCount] != -1) {
            return $memo[$index][$openCount] == 1;
        }

        $isValid = false;

        if ($str[$index] == '*') {
            $isValid = $this->isValidString($index + 1, $openCount + 1, $str, $memo);
            if ($openCount > 0) {
                $isValid = $isValid || $this->isValidString($index + 1, $openCount - 1, $str, $memo);
            }
            $isValid = $isValid || $this->isValidString($index + 1, $openCount, $str, $memo);
        } elseif ($str[$index] == '(') {
            $isValid = $this->isValidString($index + 1, $openCount + 1, $str, $memo);
        } elseif ($openCount > 0) {
            $isValid = $this->isValidString($index + 1, $openCount - 1, $str, $memo);
        }

        $memo[$index][$openCount] = $isValid ? 1 : 0;
        return $isValid;
    }
}

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

Задача: 901. Online Stock Span
Сложность: medium

Разработайте алгоритм, который собирает ежедневные котировки цен на некоторые акции и возвращает размах цены этой акции за текущий день. Размах цены акции за один день - это максимальное количество дней подряд (начиная с этого дня и в обратном направлении), в течение которых цена акции была меньше или равна цене этого дня.

Например, если цены акции за последние четыре дня равны [7,2,1,2], а цена акции сегодня равна 2, то размах сегодняшнего дня равен 4, поскольку, начиная с сегодняшнего дня, цена акции была меньше или равна 2 в течение 4 дней подряд.
Также, если цена акции за последние четыре дня равна [7,34,1,2], а цена акции сегодня равна 8, то размах сегодняшнего дня равен 3, так как начиная с сегодняшнего дня цена акции была меньше или равна 8 в течение 3 дней подряд. Реализация класса StockSpanner: StockSpanner() Инициализирует объект класса. int next(int price) Возвращает размах цены акции, учитывая, что сегодняшняя цена равна price.

Пример:

Input
["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
[[], [100], [80], [60], [70], [60], [75], [85]]
Output
[null, 1, 1, 1, 2, 1, 4, 6]

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

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

2⃣Для метода next:
Установить начальный размах текущего дня равным 1.
Пока стек не пуст и верхний элемент стека имеет цену меньше или равную текущей цене:
Добавить размах верхнего элемента стека к текущему размаху.
Удалить верхний элемент стека.

3⃣Добавить текущую цену и размах на вершину стека.
Вернуть текущий размах.

😎 Решение:

class StockSpanner {
    private $stack;

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

    function next($price) {
        $span = 1;
        while (!empty($this->stack) && end($this->stack)[0] <= $price) {
            $span += array_pop($this->stack)[1];
        }
        array_push($this->stack, [$price, $span]);
        return $span;
    }
}

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

Задача: 1214. Two Sum BSTs
Сложность: medium

Даны корни двух бинарных деревьев поиска, root1 и root2, верните true, если и только если существует узел в первом дереве и узел во втором дереве, значения которых в сумме равны заданному целому числу target.

Пример:

Input: root1 = [0,-10,10], root2 = [5,1,7,0,2], target = 18
Output: false

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

1⃣Создайте два пустых множества node_set1 и node_set2. Выполните обход дерева root1, добавляя значения каждого узла в node_set1, и выполните обход дерева root2, добавляя значения каждого узла в node_set2.

2⃣Итерация по элементам в node_set1: для каждого элемента value1 проверяйте, находится ли target - value1 в node_set2.

3⃣Если target - value1 находится в node_set2, верните true. Если после завершения итерации не найдено ни одной подходящей пары, верните false.

😎 Решение:

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;
    }
}

class Solution {
    private function dfs($node, &$nodeSet) {
        if ($node === null) return;
        $this->dfs($node->left, $nodeSet);
        $nodeSet[] = $node->val;
        $this->dfs($node->right, $nodeSet);
    }

    function twoSumBSTs($root1, $root2, $target) {
        $nodeSet1 = [];
        $nodeSet2 = [];
        $this->dfs($root1, $nodeSet1);
        $this->dfs($root2, $nodeSet2);
        
        foreach ($nodeSet1 as $value1) {
            if (in_array($target - $value1, $nodeSet2)) {
                return true;
            }
        }
        
        return false;
    }
}

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

Задача: 819. Most Common Word
Сложность: easy

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

Слова в paragraph нечувствительны к регистру, и ответ должен быть возвращен в нижнем регистре.

Пример:

Input: paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.", banned = ["hit"]
Output: "ball"
Explanation: 
"hit" occurs 3 times, but it is a banned word.
"ball" occurs twice (and no other word does), so it is the most frequent non-banned word in the paragraph. 
Note that words in the paragraph are not case sensitive,
that punctuation is ignored (even if adjacent to words, such as "ball,"), 
and that "hit" isn't the answer even though it occurs more because it is banned.

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

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

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

3⃣Затем итерируемся по словам, чтобы подсчитать количество появлений каждого уникального слова, исключая слова из списка запрещенных. С помощью хеш-таблицы {слово->количество} проходим по всем элементам, чтобы найти слово с наивысшей частотой.

😎 Решение:

class Solution {
    function mostCommonWord($paragraph, $banned) {
        $normalizedStr = preg_replace('/[^a-zA-Z0-9 ]/', ' ', strtolower($paragraph));
        $words = preg_split('/\s+/', $normalizedStr, -1, PREG_SPLIT_NO_EMPTY);
        $wordCount = [];
        $bannedWords = array_flip($banned);

        foreach ($words as $word) {
            if (!isset($bannedWords[$word])) {
                if (!isset($wordCount[$word])) {
                    $wordCount[$word] = 0;
                }
                $wordCount[$word]++;
            }
        }

        return array_search(max($wordCount), $wordCount);
    }
}

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

Задача: 346. Moving Average from Data Stream
Сложность: easy

Дан поток целых чисел и размер окна, вычислите скользящее среднее всех целых чисел в скользящем окне.

Реализуйте класс MovingAverage:

MovingAverage(int size) Инициализирует объект с размером окна size.
double next(int val) Возвращает скользящее среднее последних size значений потока.

Пример:

Input
["MovingAverage", "next", "next", "next", "next"]
[[3], [1], [10], [3], [5]]
Output
[null, 1.0, 5.5, 4.66667, 6.0]

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

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

2⃣Добавление нового значения:
Добавьте новое значение в очередь.
Обновите текущую сумму, добавив новое значение.
Если размер очереди превышает size, удалите самое старое значение и обновите сумму, вычтя это значение.

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

😎 Решение:

class MovingAverage {
    private $size;
    private $queue;
    private $sum;
    
    function __construct($size) {
        $this->size = $size;
        $this->queue = [];
        $this->sum = 0;
    }
    
    function next($val) {
        array_push($this->queue, $val);
        $this->sum += $val;
        if (count($this->queue) > $this->size) {
            $this->sum -= array_shift($this->queue);
        }
        return $this->sum / count($this->queue);
    }
}

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

Задача №24. Swap Nodes in Pairs
Сложность: medium

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

Пример:

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

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

1⃣Использовать указатели для перестановки соседних узлов.

2⃣Пройти по списку, меняя местами пары узлов.

3⃣Обновить связи так, чтобы список остался целостным.

😎 Решение:

class Solution { 
    function swapPairs($head) { 
        $dummy = new ListNode(0, $head); 
        $prev = $dummy; 

        while ($head && $head->next) { 
            $first = $head; 
            $second = $head->next; 

            $prev->next = $second; 
            $first->next = $second->next; 
            $second->next = $first; 

            $prev = $first; 
            $head = $first->next; 
        } 

        return $dummy->next; 
    } 
}

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

Задача: 994. Rotting Oranges
Сложность: medium

Дан m x n сетка, где каждая ячейка может иметь одно из трех значений:

0, представляющее пустую ячейку,
1, представляющее свежий апельсин,
2, представляющее гнилой апельсин.
Каждую минуту любой свежий апельсин, который находится в 4-х направленно смежной ячейке с гнилым апельсином, становится гнилым.

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

Пример:

Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

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

1⃣Инициализация очереди и подсчет апельсинов:
Пройдите по всей сетке, добавьте все гнилые апельсины в очередь и подсчитайте общее количество свежих апельсинов.
Если нет свежих апельсинов, верните 0.

2⃣Использование BFS для распространения гнили:
Выполняйте BFS, начиная с всех гнилых апельсинов, добавленных в очередь.
Каждый раз, когда апельсин становится гнилым, уменьшайте счетчик свежих апельсинов.
Если свежих апельсинов больше не осталось, верните текущее количество минут.

3⃣Проверка оставшихся свежих апельсинов:
Если после завершения BFS все еще остаются свежие апельсины, верните -1.

😎 Решение:

class Solution {
    function orangesRotting($grid) {
        $queue = [];
        $freshCount = 0;
        $minutes = 0;
        $directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
        
        for ($i = 0; $i < count($grid); $i++) {
            for ($j = 0; $j < count($grid[0]); $j++) {
                if ($grid[$i][$j] == 2) {
                    $queue[] = [$i, $j];
                } elseif ($grid[$i][$j] == 1) {
                    $freshCount++;
                }
            }
        }
        
        if ($freshCount == 0) return 0;
        
        while (count($queue) > 0) {
            $size = count($queue);
            for ($i = 0; $i < $size; $i++) {
                list($x, $y) = array_shift($queue);
                foreach ($directions as $dir) {
                    $nx = $x + $dir[0];
                    $ny = $y + $dir[1];
                    if ($nx >= 0 && $nx < count($grid) && $ny >= 0 && $ny < count($grid[0]) && $grid[$nx][$ny] == 1) {
                        $grid[$nx][$ny] = 2;
                        $freshCount--;
                        $queue[] = [$nx, $ny];
                    }
                }
            }
            if (count($queue) > 0) {
                $minutes++;
            }
        }
        
        return $freshCount == 0 ? $minutes : -1;
    }
}

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

Задача: 95. Unique Binary Search Trees II
Сложность: medium

Дано целое число n. Верните все структурно уникальные деревья бинарного поиска (BST), которые содержат ровно n узлов с уникальными значениями от 1 до n. Ответ может быть представлен в любом порядке.

Пример:

Input: n = 3
Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

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

1⃣Создайте хеш-карту memo, где memo[(start, end)] содержит список корневых узлов всех возможных BST (деревьев бинарного поиска) с диапазоном значений узлов от start до end. Реализуем рекурсивную функцию allPossibleBST, которая принимает начальный диапазон значений узлов start, конечный диапазон end и memo в качестве параметров. Она возвращает список TreeNode, соответствующих всем BST, которые могут быть сформированы с этим диапазоном значений узлов. Вызываем allPossibleBST(1, n, memo) и выполняем следующее:

2⃣Объявляем список TreeNode под названием res для хранения списка корневых узлов всех возможных BST. Если start > end, мы добавляем null в res и возвращаем его. Если мы уже решили эту подзадачу, т.е. memo содержит пару (start, end), мы возвращаем memo[(start, end)].

3⃣Выбираем значение корневого узла от i = start до end, увеличивая i на 1 после каждой итерации. Рекурсивно вызываем leftSubtrees = allPossibleBST(start, i - 1, memo) и rightSubTrees = allPossibleBST(i + 1, end, memo). Перебираем все пары между leftSubtrees и rightSubTrees и создаем новый корень со значением i для каждой пары. Добавляем корень новообразованного BST в res. Устанавливаем memo[(start, end)] = res и возвращаем res.

😎 Решение:

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 allPossibleBST($start, $end, &$memo) {
        $res = [];
        if ($start > $end) {
            $res[] = null;
            return $res;
        }
        if (array_key_exists("{$start},{$end}", $memo)) {
            return $memo["{$start},{$end}"];
        }

        for ($i = $start; $i <= $end; ++$i) {
            $leftSubTrees = $this->allPossibleBST($start, $i - 1, $memo);
            $rightSubTrees = $this->allPossibleBST($i + 1, $end, $memo);
            foreach ($leftSubTrees as $left) {
                foreach ($rightSubTrees as $right) {
                    $root = new TreeNode($i, $left, $right);
                    $res[] = $root;
                }
            }
        }

        $memo["{$start},{$end}"] = $res;
        return $res;
    }

    public function generateTrees($n) {
        $memo = [];
        return $this->allPossibleBST(1, $n, $memo);
    }
}

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

Задача: 400. Nth Digit
Сложность: medium

Дано целое число n, вернуть n-ю цифру бесконечной последовательности чисел [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...].

Пример:

Input: n = 3
Output: 3

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

1⃣Определение диапазона:
Начните с определения количества цифр в числах текущего диапазона (1-9, 10-99, 100-999 и т.д.).
Уменьшайте значение n, вычитая количество цифр в текущем диапазоне, пока не найдете диапазон, в который попадает n-я цифра.

2⃣Нахождение конкретного числа:
Когда определите диапазон, найдите точное число, содержащее n-ю цифру.
Определите индекс цифры в этом числе.

3⃣Возвращение n-й цифры:
Извлеките и верните n-ю цифру из найденного числа.

😎 Решение:

class Solution {
    function findNthDigit($n) {
        $length = 1;
        $count = 9;
        $start = 1;
        
        while ($n > $length * $count) {
            $n -= $length * $count;
            $length++;
            $count *= 10;
            $start *= 10;
        }
        
        $start += intval(($n - 1) / $length);
        $s = strval($start);
        return intval($s[($n - 1) % $length]);
    }
}

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