PHP | LeetCode

Задача: 1351. Count Negative Numbers in a Sorted Matrix
Сложность: easy

Дана матрица m x n grid, которая отсортирована по убыванию как по строкам, так и по столбцам. Вернуть количество отрицательных чисел в grid.

Пример:

Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
Output: 8
Explanation: There are 8 negatives number in the matrix.

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

1⃣Инициализировать переменную count = 0 для подсчета общего числа отрицательных элементов в матрице.

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

3⃣Вернуть count.

😎 Решение:

class Solution {
    public function countNegatives($grid) {
        $count = 0;
        foreach ($grid as $row) {
            foreach ($row as $element) {
                if ($element < 0) {
                    $count++;
                }
            }
        }
        return $count;
    }
}

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

Задача: 1055. Shortest Way to Form String
Сложность: medium

Подпоследовательность строки - это новая строка, которая образуется из исходной строки путем удаления некоторых (можно ни одного) символов без нарушения взаимного расположения оставшихся символов. (например, "ace" является подпоследовательностью "abcde", а "aec" - нет). Если даны две строки source и target, верните минимальное количество подпоследовательностей source, чтобы их объединение равнялось target. Если задача невыполнима, верните -1.

Пример:

Input: source = "abc", target = "abcbc"
Output: 2

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

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

2⃣Перебирай символы строки source, пока не найдешь совпадающий символ в target.
Если ты прошел всю строку source и не нашел все символы target, увеличь счетчик количества подпоследовательностей и начни снова с начала source.

3⃣Повтори шаги 2 и 3 до тех пор, пока не пройдешь всю строку target.

😎 Решение:

function minSubsequences($source, $target) {
    $subsequencesCount = 0;
    $targetIndex = 0;

    while ($targetIndex < strlen($target)) {
        $sourceIndex = 0;
        $subsequencesCount++;
        $startIndex = $targetIndex;

        while ($sourceIndex < strlen($source) && $targetIndex < strlen($target)) {
            if ($source[$sourceIndex] === $target[$targetIndex]) {
                $targetIndex++;
            }
            $sourceIndex++;
        }

        if ($targetIndex === $startIndex) {
            return -1;
        }
    }

    return $subsequencesCount;
}

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

Задача: 906. Super Palindromes
Сложность: hard

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

Пример:

Input: left = "4", right = "1000"
Output: 4

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

1⃣Найти все палиндромы до корня из right.

2⃣Проверить, являются ли квадраты этих палиндромов палиндромами и лежат ли в диапазоне [left, right].

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

😎 Решение:

function isPalindrome($x) {
    $s = strval($x);
    return $s == strrev($s);
}

function superpalindromesInRange($left, $right) {
    $leftNum = intval($left);
    $rightNum = intval($right);
    $count = 0;

    for ($i = 1; $i < 100000; $i++) {
        $s = strval($i);
        $palin1 = intval($s . strrev($s));
        $palin2 = intval($s . strrev(substr($s, 0, -1)));

        if ($palin1 * $palin1 > $rightNum) {
            break;
        }
        if ($palin1 * $palin1 >= $leftNum && isPalindrome($palin1 * $palin1)) {
            $count++;
        }
        if ($palin2 * $palin2 >= $leftNum && $palin2 * $palin2 <= $rightNum && isPalindrome($palin2 * $palin2)) {
            $count++;
        }
    }

    return $count;
}

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

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

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

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

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

Задача: 1010. Pairs of Songs With Total Durations Divisible by 60
Сложность: medium

Вам дан список песен, в котором длительность i-й песни составляет time[i] секунд. Верните количество пар песен, для которых их общая длительность в секундах делится на 60. Формально, нам нужно количество индексов i, j таких, что i < j при (time[i] + time[j]) % 60 == 0.

Пример:

Input: time = [30,20,150,100,40]
Output: 3

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

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

2⃣Подсчет пар:
Пройдитесь по каждой песне в списке и для каждого элемента:
Вычислите остаток от деления времени песни на 60.
Если остаток равен 0, добавьте количество песен с остатком 0 к результату (поскольку (0 + 0) % 60 == 0).
Иначе, добавьте количество песен с остатком (60 - текущий остаток) к результату (поскольку (текущий остаток + (60 - текущий остаток)) % 60 == 0).
Обновите массив остатков, увеличивая количество песен с текущим остатком на 1.

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

😎 Решение:

class Solution {
    function numPairsDivisibleBy60($time) {
        $remainders = array_fill(0, 60, 0);
        $count = 0;
        
        foreach ($time as $t) {
            if ($t % 60 == 0) {
                $count += $remainders[0];
            } else {
                $count += $remainders[60 - $t % 60];
            }
            $remainders[$t % 60]++;
        }
        
        return $count;
    }
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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