Задача: 1380. Lucky Numbers in a Matrix
Сложность: easy

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

Счастливое число — это элемент матрицы, который является минимальным элементом в своей строке и максимальным в своем столбце.

Пример:

Input: matrix = [[3,7,8],[9,11,13],[15,16,17]]
Output: [15]
Explanation: 15 is the only lucky number since it is the minimum in its row and the maximum in its column.

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

1⃣Сохраните минимум каждой строки в список rowMin и максимум каждого столбца в список colMax.

2⃣Итерируйте по каждому числу в матрице и проверяйте, равно ли оно rowMin[i] и colMax[j].

3⃣Если число удовлетворяет условию, добавьте его в список luckyNumbers и верните luckyNumbers.

😎 Решение:

class Solution {
    function luckyNumbers ($matrix) {
        $N = count($matrix);
        $M = count($matrix[0]);
        
        $rowMin = [];
        for ($i = 0; $i < $N; $i++) {
            $rMin = min($matrix[$i]);
            $rowMin[] = $rMin;
        }
        
        $colMax = [];
        for ($i = 0; $i < $M; $i++) {
            $cMax = PHP_INT_MIN;
            for ($j = 0; $j < $N; $j++) {
                $cMax = max($cMax, $matrix[$j][$i]);
            }
            $colMax[] = $cMax;
        }
        
        $luckyNumbers = [];
        for ($i = 0; $i < $N; $i++) {
            for ($j = 0; $j < $M; $j++) {
                if ($matrix[$i][$j] == $rowMin[$i] && $matrix[$i][$j] == $colMax[$j]) {
                    $luckyNumbers[] = $matrix[$i][$j];
                }
            }
        }
        
        return $luckyNumbers;
    }
}

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

Задача: 631. Design Excel Sum Formula
Сложность: hard

Разработайте базовую функцию Excel и реализуйте функцию формулы суммы. Реализуйте класс Excel: Excel(int height, char width) Инициализирует объект с высотой и шириной листа. Лист представляет собой целочисленную матрицу размером height x width с индексом строки в диапазоне [1, height] и индексом столбца в диапазоне ['A', width]. Все значения должны быть нулевыми изначально. void set(int row, char column, int val) Изменяет значение в mat[row][column] на val. int get(int row, char column) Возвращает значение в mat[row][column]. int sum(int row, char column, List<String> numbers) Устанавливает значение в mat[row][column] как сумму ячеек, представленных числами, и возвращает значение в mat[row][column]. Эта формула суммы должна существовать до тех пор, пока эта ячейка не будет перекрыта другим значением или другой формулой суммы. numbers[i] могут иметь формат: "ColRow", который представляет одну ячейку. Например, "F7" представляет ячейку mat[7]['F']. "ColRow1:ColRow2", который представляет диапазон ячеек. Диапазон всегда будет прямоугольником, где "ColRow1" представляет позицию левой верхней ячейки, а "ColRow2" - позицию правой нижней ячейки.
Например, "B3:F7" представляет ячейки mat[i][j] для 3 <= i <= 7 и 'B' <= j <= 'F'. Примечание: Можно предположить, что не будет никаких ссылок на круговую сумму. Например, mat[1]['A'] == sum(1, "B") и mat[1]['B'] == sum(1, "A").

Пример:

Input
["Excel", "set", "sum", "set", "get"]
[[3, "C"], [1, "A", 2], [3, "C", ["A1", "A1:B2"]], [2, "B", 2], [3, "C"]]
Output
[null, null, 4, null, 6]

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

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

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

3⃣Метод вычисления суммы
Реализуйте метод sum, который будет вычислять сумму значений ячеек, указанных в списке numbers. Метод должен поддерживать как одиночные ячейки, так и диапазоны ячеек.

😎 Решение:

class Excel {
    private $mat;
    private $formulas;

    public function __construct($height, $width) {
        $this->mat = array_fill(0, $height, array_fill(0, ord($width) - ord('A') + 1, 0));
        $this->formulas = [];
    }

    public function set($row, $column, $val) {
        $this->mat[$row - 1][ord($column) - ord('A')] = $val;
        unset($this->formulas["$row$column"]);
    }

    public function get($row, $column) {
        $key = "$row$column";
        if (isset($this->formulas[$key])) {
            return $this->evaluateFormula($key);
        }
        return $this->mat[$row - 1][ord($column) - ord('A')];
    }

    public function sum($row, $column, $numbers) {
        $key = "$row$column";
        $this->formulas[$key] = $numbers;
        return $this->evaluateFormula($key);
    }

    private function evaluateFormula($key) {
        $numbers = $this->formulas[$key];
        $total = 0;
        foreach ($numbers as $number) {
            if (strpos($number, ':') !== false) {
                list($start, $end) = explode(':', $number);
                $startRow = (int)substr($start, 1);
                $startCol = $start[0];
                $endRow = (int)substr($end, 1);
                $endCol = $end[0];
                for ($r = $startRow; $r <= $endRow; $r++) {
                    for ($c = ord($startCol); $c <= ord($endCol); $c++) {
                        $total += $this->get($r, chr($c));
                    }
                }
            } else {
                $r = (int)substr($number, 1);
                $c = $number[0];
                $total += $this->get($r, $c);
            }
        }
        return $total;
    }
}

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

Задача: 1005. Maximize Sum Of Array After K Negations
Сложность: easy

Учитывая целочисленный массив nums и целое число k, измените массив следующим образом: выберите индекс i и замените nums[i] на -nums[i]. Вы должны применить этот процесс ровно k раз. Вы можете выбрать один и тот же индекс i несколько раз. Верните наибольшую возможную сумму массива после его модификации таким образом.

Пример:

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

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

1⃣Сортировка массива:
Отсортируйте массив nums по возрастанию, чтобы наибольшее количество раз менять самые маленькие (отрицательные) значения на их противоположные.

2⃣Модификация массива:
Пройдитесь по отсортированному массиву и замените k наименьших значений на их противоположные (умножьте на -1). Если встретите 0, прекратите дальнейшие изменения, так как изменение 0 на -0 не имеет смысла.

3⃣Проверка остатка изменений:
Если после первого прохода остались изменения (k нечетное), то найдите минимальное значение в измененном массиве и еще раз поменяйте его знак. Это обеспечит максимальную сумму.

😎 Решение:

class Solution {
    function largestSumAfterKNegations($nums, $k) {
        sort($nums);
        
        for ($i = 0; $i < count($nums); $i++) {
            if ($k > 0 && $nums[$i] < 0) {
                $nums[$i] = -$nums[$i];
                $k--;
            }
        }
        
        if ($k % 2 == 1) {
            sort($nums);
            $nums[0] = -$nums[0];
        }
        
        return array_sum($nums);
    }
}

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

Задача: 1335. Minimum Difficulty of a Job Schedule
Сложность: hard

Вы хотите составить расписание списка заданий на d дней. Задания зависят друг от друга (т.е. чтобы выполнить задание i, вы должны закончить все задания j, где 0 <= j < i).

Вы должны выполнять как минимум одно задание каждый день. Сложность расписания заданий — это сумма сложностей каждого дня из d дней. Сложность дня — это максимальная сложность задания, выполненного в этот день.

Вам дан массив целых чисел jobDifficulty и целое число d. Сложность i-го задания равна jobDifficulty[i].

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

Пример:

Input: jobDifficulty = [6,5,4,3,2,1], d = 2
Output: 7
Explanation: First day you can finish the first 5 jobs, total difficulty = 6.
Second day you can finish the last job, total difficulty = 1.
The difficulty of the schedule = 6 + 1 = 7 

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

1⃣Определение состояния:
Индекс i (индекс первой задачи на сегодняшний день в массиве jobDifficulty) и день d (количество оставшихся дней) будут определять состояние динамического программирования. min_diff(i, d) обозначает минимальную сложность при начале с i-й задачи с оставшимися d днями. min_diff(0, d) будет окончательным ответом, так как он представляет начало с начала массива задач и завершение всех задач за ровно d дней.

2⃣Функция перехода состояния:
Задача с индексом j будет первой задачей на следующий день, следовательно, задачи, которые должны быть завершены сегодня, это все задачи с индексами между i и j, то есть jobDifficulty[i
]. Поскольку сложность дня — это максимальная сложность выполненной в этот день задачи, к сумме сложностей задач будет добавляться максимум из jobDifficulty[i
]. Формулируем функцию перехода состояния следующим образом: min_diff(i, d) = min_diff(j, d - 1) + max(jobDifficulty[i
]) для всех j > i.

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

😎 Решение:

class Solution {
    function minDifficulty($jobDifficulty, $d) {
        $n = count($jobDifficulty);
        if ($n < $d) return -1;
        
        $mem = array_fill(0, $n, array_fill(0, $d + 1, -1));
        
        function minDiff($i, $daysRemaining, $jobDifficulty, &$mem) {
            if ($mem[$i][$daysRemaining] != -1) {
                return $mem[$i][$daysRemaining];
            }
            
            if ($daysRemaining == 1) {
                return max(array_slice($jobDifficulty, $i));
            }
            
            $res = PHP_INT_MAX;
            $dailyMaxJobDiff = 0;
            
            for ($j = $i; $j < count($jobDifficulty) - $daysRemaining + 1; $j++) {
                $dailyMaxJobDiff = max($dailyMaxJobDiff, $jobDifficulty[$j]);
                $res = min($res, $dailyMaxJobDiff + minDiff($j + 1, $daysRemaining - 1, $jobDifficulty, $mem));
            }
            
            $mem[$i][$daysRemaining] = $res;
            return $res;
        }
        
        return minDiff(0, $d, $jobDifficulty, $mem);
    }
}

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

Задача: 373. Find K Pairs with Smallest Sums
Сложность: medium

Вам даны два целочисленных массива nums1 и nums2, отсортированных в неубывающем порядке, и целое число k.
Определим пару (u, v), которая состоит из одного элемента из первого массива и одного элемента из второго массива.
Верните k пар (u1, v1), (u2, v2), ..., (uk, vk) с наименьшими суммами.

Пример:

Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output: [[1,2],[1,4],[1,6]]
Explanation: The first 3 pairs are returned from the sequence: [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

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

1⃣Создайте две целочисленные переменные m и n, инициализируйте их размерами массивов nums1 и nums2 соответственно. Создайте список ans для хранения пар с наименьшими суммами, которые будут возвращены в качестве ответа. Создайте множество visited для отслеживания просмотренных пар.

2⃣Инициализируйте минимальную кучу minHeap, которая содержит тройки целых чисел: сумму пары, индекс первого элемента пары в nums1 и индекс второго элемента пары в nums2. Вставьте в minHeap первую пару из обоих массивов, т.е. nums1[0] + nums2[0], 0, 0, и добавьте пару (0, 0) в visited.

3⃣Повторяйте до получения k пар и пока minHeap не пуст:
Извлеките верхний элемент из minHeap и установите i = top[1] и j = top[2].
Добавьте пару (nums1[i], nums2[j]) в ans.
Если i + 1 < m и пары (i + 1, j) нет в visited, добавьте новую пару nums1[i + 1] + nums2[j], i + 1, j в minHeap.
Если j + 1 < n и пары (i, j + 1) нет в visited, добавьте новую пару nums1[i] + nums2[j + 1], i, j + 1 в minHeap.
Верните ans.

😎 Решение:

class Solution {
    function kSmallestPairs($nums1, $nums2, $k) {
        $m = count($nums1);
        $n = count($nums2);
        $ans = [];
        $visited = [];
        $minHeap = new SplPriorityQueue();
        $minHeap->setExtractFlags(SplPriorityQueue::EXTR_BOTH);
        $minHeap->insert([0, 0], -($nums1[0] + $nums2[0]));
        $visited["0,0"] = true;

        while ($k > 0 && !$minHeap->isEmpty()) {
            $top = $minHeap->extract();
            list($i, $j) = $top['data'];
            $ans[] = [$nums1[$i], $nums2[$j]];

            if ($i + 1 < $m && !isset($visited[($i + 1) . ",$j"])) {
                $minHeap->insert([$i + 1, $j], -($nums1[$i + 1] + $nums2[$j]));
                $visited[($i + 1) . ",$j"] = true;
            }

            if ($j + 1 < $n && !isset($visited["$i," . ($j + 1)])) {
                $minHeap->insert([$i, $j + 1], -($nums1[$i] + $nums2[$j + 1]));
                $visited["$i," . ($j + 1)] = true;
            }
            $k--;
        }

        return $ans;
    }
}

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

Задача: 624. Maximum Distance in Arrays
Сложность: medium

Вам дано m массивов, где каждый массив отсортирован по возрастанию. Вы можете взять два целых числа из двух разных массивов (каждый массив выбирает одно) и вычислить расстояние. Мы определяем расстояние между двумя целыми числами a и b как их абсолютную разность |a - b|. Верните максимальное расстояние.

Пример:

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

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

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

2⃣Рассчитайте максимальное расстояние между минимальным и максимальным элементами.

3⃣Верните это максимальное расстояние.

😎 Решение:

function maxDistance($arrays) {
    $minElement = $arrays[0][0];
    $maxElement = end($arrays[0]);
    $maxDistance = 0;
    
    for ($i = 1; $i < count($arrays); $i++) {
        $array = $arrays[$i];
        $maxDistance = max($maxDistance, abs(end($array) - $minElement), abs($maxElement - $array[0]));
        $minElement = min($minElement, $array[0]);
        $maxElement = max($maxElement, end($array));
    }
    
    return $maxDistance;
}

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

Задача: 687. Longest Univalue Path
Сложность: medium

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

Длина пути между двумя узлами представлена количеством рёбер между ними.

Пример:

Input: root = [5,4,5,1,1,null,5]
Output: 2
Explanation: The shown image shows that the longest path of the same value (i.e. 5).

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

1⃣Определить рекурсивную функцию solve(), принимающую текущий узел root и значение родительского узла parent. Если root равен NULL, вернуть 0. Рекурсивно вызвать solve() для левого и правого дочернего узлов, передав значение текущего узла как значение родительского узла.

2⃣Обновить переменную ans, если сумма значений для левого и правого узлов больше текущего значения ans. Если значение текущего узла равно значению родительского узла, вернуть max(left, right) + 1, иначе вернуть 0.

3⃣Вызвать solve() с корневым узлом и значением родительского узла -1. Вернуть максимальную длину пути ans..

😎 Решение:

class Solution {
    public $ans = 0;

    function solve($root, $parent) {
        if ($root === null) {
            return 0;
        }

        $left = $this->solve($root->left, $root->val);
        $right = $this->solve($root->right, $root->val);
        
        $this->ans = max($this->ans, $left + $right);
        
        return $root->val === $parent ? max($left, $right) + 1 : 0;
    }

    function longestUnivaluePath($root) {
        $this->solve($root, -1);
        return $this->ans;
    }
}

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

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

Дана сетка символов размером m на n, называемая board, и строка word. Верните true, если слово word существует в сетке.

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

Пример:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

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

1⃣Общий подход к алгоритмам обратной трассировки: В каждом алгоритме обратной трассировки существует определенный шаблон кода. Например, один из таких шаблонов можно найти в нашем разделе "Рекурсия II". Скелет алгоритма представляет собой цикл, который проходит через каждую ячейку в сетке. Для каждой ячейки вызывается функция обратной трассировки (backtrack()), чтобы проверить, можно ли найти решение, начиная с этой ячейки.

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

3⃣Исследование и завершение: Если текущий шаг допустим, начинается исследование с использованием стратегии DFS. Сначала текущая ячейка помечается как посещенная, например, любой неалфавитный символ подойдет. Затем осуществляется итерация через четыре возможных направления: вверх, вправо, вниз и влево. Порядок направлений может быть изменен по предпочтениям пользователя. В конце исследования ячейка возвращается к своему исходному состоянию, и возвращается результат исследования.

😎 Решение:

function exist($board, $word) {
    $ROWS = count($board);
    $COLS = count($board[0]);
    
    $backtrack = function($row, $col, $suffix) use (&$backtrack, $board, $ROWS, $COLS) {
        if (strlen($suffix) == 0) return true;
        if (
            $row < 0 ||
            $row == $ROWS ||
            $col < 0 ||
            $col == $COLS ||
            $board[$row][$col] != $suffix[0]
        )
            return false;
        
        $ret = false;
        $temp = $board[$row][$col];
        $board[$row][$col] = '#';
        $directions = [
            [0, 1],
            [1, 0],
            [0, -1],
            [-1, 0],
        ];
        
        foreach ($directions as list($rowOffset, $colOffset)) {
            $ret = $backtrack($row + $rowOffset, $col + $colOffset, substr($suffix, 1));
            if ($ret) break;
        }
        
        $board[$row][$col] = $temp;
        return $ret;
    };
    
    for ($row = 0; $row < $ROWS; ++$row) {
        for ($col = 0; $col < $COLS; ++$col) {
            if ($backtrack($row, $col, $word)) return true;
        }
    }
    return false;
}

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

Задача: 242. Valid Anagram
Сложность: easy

Даны две строки s и t, верните true, если t является анаграммой s, и false в противном случае.
Анаграмма — это слово или фраза, сформированная путём перестановки букв другого слова или фразы, обычно используя все исходные буквы ровно один раз.

Пример:

Input: s = "anagram", t = "nagaram"
Output: true

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

1⃣Создайте массив размером 26 для подсчета частот каждой буквы (поскольку s и t содержат только буквы от 'a' до 'z').

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

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

😎 Решение:

function isAnagram($s, $t) {
    if (strlen($s) != strlen($t)) {
        return false;
    }
    $count = array_fill(0, 26, 0);
    for ($i = 0; $i < strlen($s); $i++) {
        $count[ord($s[$i]) - ord('a')]++;
        $count[ord($t[$i]) - ord('a')]--;
    }
    foreach ($count as $c) {
        if ($c != 0) {
            return false;
        }
    }

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

Задача: 212. Word Search II
Сложность: hard

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

Пример:

Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]

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

1⃣Построение Trie:
Постройте структуру Trie из слов в словаре. Trie будет использоваться для процесса сопоставления позже.

2⃣Запуск обхода в глубину (Backtracking) с каждой ячейки:
Начните обход доски с каждой ячейки. Если существует слово в словаре, которое начинается с буквы в данной ячейке, начните рекурсивный вызов функции backtracking(cell).

3⃣Обход соседних ячеек:
В функции backtracking(cell) исследуйте соседние ячейки (i.e. neighborCell) вокруг текущей ячейки для следующего рекурсивного вызова backtracking(neighborCell).
На каждом вызове проверяйте, соответствует ли последовательность букв, которую мы прошли до сих пор, какому-либо слову в словаре, используя структуру Trie, построенную в начале.

😎

class TrieNode {
    public $children;
    public $word;

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

class Solution {
    private $board;
    private $result;

    public function findWords($board, $words) {
        $root = $this->buildTrie($words);
        $this->board = $board;
        $this->result = [];

        for ($row = 0; $row < count($board); ++$row) {
            for ($col = 0; $col < count($board[0]); ++$col) {
                if (isset($root->children[$board[$row][$col]])) {
                    $this->backtrack($row, $col, $root);
                }
            }
        }
        return $this->result;
    }

    private function buildTrie($words) {
        $root = new TrieNode();
        foreach ($words as $word) {
            $node = $root;
            for ($i = 0; $i < strlen($word); ++$i) {
                $letter = $word[$i];
                if (!isset($node->children[$letter])) {
                    $node->children[$letter] = new TrieNode();
                }
                $node = $node->children[$letter];
            }
            $node->word = $word;
        }
        return $root;
    }

    private function backtrack($row, $col, $parent) {
        $letter = $this->board[$row][$col];
        $currNode = $parent->children[$letter];

        if ($currNode->word !== null) {
            $this->result[] = $currNode->word;
            $currNode->word = null;
        }

        $this->board[$row][$col] = '#';

        $rowOffset = [-1, 0, 1, 0];
        $colOffset = [0, 1, 0, -1];
        for ($i = 0; $i < 4; ++$i) {
            $newRow = $row + $rowOffset[$i];
            $newCol = $col + $colOffset[$i];
            if (
                $newRow >= 0 && $newRow < count($this->board) &&
                $newCol >= 0 && $newCol < count($this->board[0])
            ) {
                if (isset($currNode->children[$this->board[$newRow][$newCol]])) {
                    $this->backtrack($newRow, $newCol, $currNode);
                }
            }
        }

        $this->board[$row][$col] = $letter;

        if (empty($currNode->children)) {
            unset($parent->children[$letter]);
        }
    }
}

// Example usage:
$solution = new Solution();
$board = [
    ['o', 'a', 'a', 'n'],
    ['e', 't', 'a', 'e'],
    ['i', 'h', 'k', 'r'],
    ['i', 'f', 'l', 'v']
];
$words = ["oath", "pea", "eat", "rain"];
print_r($solution->findWords($board, $words));

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

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

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

Задача: 316. Remove Duplicate Letters
Сложность: medium

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

Пример:

Input: s = "bcabc"
Output: "abc"

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

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

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

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

😎 Решение:

class Solution {
    function removeDuplicateLetters($s) {
        $stack = [];
        $seen = [];
        $lastOccurrence = [];
        for ($i = 0; $i < strlen($s); $i++) {
            $lastOccurrence[$s[$i]] = $i;
        }

        for ($i = 0; $i < strlen($s); $i++) {
            $c = $s[$i];
            if (!isset($seen[$c])) {
                while (!empty($stack) && $c < end($stack) && $i < $lastOccurrence[end($stack)]) {
                    unset($seen[array_pop($stack)]);
                }
                $seen[$c] = true;
                $stack[] = $c;
            }
        }
        return implode('', $stack);
    }
}

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

Задача: 997. Find the Town Judge
Сложность: easy

В городе есть n человек, помеченных от 1 до n. Ходят слухи, что один из этих людей тайно является городским судьей. Если городской судья существует, то: городской судья никому не доверяет. Все (кроме городского судьи) доверяют городскому судье. Существует ровно один человек, удовлетворяющий свойствам 1 и 2. Вам дан массив trust, где trust[i] = [ai, bi], представляющий, что человек, помеченный ai, доверяет человеку, помеченному bi. Если в массиве trust не существует доверительных отношений, то таких отношений не существует. Верните метку городского судьи, если городской судья существует и может быть идентифицирован, или верните -1 в противном случае.

Пример:

Input: n = 2, trust = [[1,2]]
Output: 2

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

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

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

3⃣Проверка условий судьи:
Пройдитесь по массиву людей и найдите того, кто никому не доверяет (количество доверий равно 0) и кому доверяют все остальные (количество доверенных людей равно n-1). Верните метку этого человека. Если такого человека нет, верните -1.

😎 Решение:

class Solution {
    function findJudge($n, $trust) {
        if (empty($trust) && $n == 1) {
            return 1;
        }

        $trustCount = array_fill(0, $n + 1, 0);
        $trustedBy = array_fill(0, $n + 1, 0);

        foreach ($trust as $t) {
            $trustCount[$t[0]]++;
            $trustedBy[$t[1]]++;
        }

        for ($i = 1; $i <= $n; $i++) {
            if ($trustCount[$i] == 0 && $trustedBy[$i] == $n - 1) {
                return $i;
            }
        }

        return -1;
    }
}

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

Задача: 144. Binary Tree Preorder Traversal
Сложность: easy

Дан корень бинарного дерева, верните предварительный обход значений его узлов.

Пример:

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

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

1⃣Определение структуры узла дерева:
Определите класс TreeNode, который будет использоваться в реализации. Каждый узел TreeNode содержит значение и ссылки на левого и правого потомков.

2⃣Инициализация процесса обхода:
Начните обход с корневого узла дерева. Используйте стек для хранения узлов дерева, которые нужно обойти, начиная с корня.

3⃣Итеративный обход дерева:
На каждой итерации извлекайте текущий узел из стека и добавляйте его значение в выходной список.
Сначала добавьте в стек правого потомка (если он существует), затем левого потомка (если он существует). Это гарантирует, что узлы будут обрабатываться в порядке слева направо, так как стек работает по принципу LIFO (последний пришел - первый ушел).
Повторяйте процесс, пока стек не опустеет, что означает завершение обхода всех узлов.

😎 Решение:

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

function preorderTraversal($root) {
    if (!$root) {
        return [];
    }

    $stack = [$root];
    $output = [];

    while (count($stack) != 0) {
        $root = array_pop($stack);
        if ($root) {
            array_push($output, $root->val);
            if ($root->right) {
                array_push($stack, $root->right);
            }
            if ($root->left) {
                array_push($stack, $root->left);
            }
        }
    }

    return $output;
}

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

Задача: 650. 2 Keys Keyboard
Сложность: medium

На экране блокнота есть только один символ 'A'. Для каждого шага можно выполнить одну из двух операций над этим блокнотом: Copy All: скопировать все символы, присутствующие на экране (частичное копирование не допускается). Paste: Вы можете вставить символы, которые были скопированы в прошлый раз. Учитывая целое число n, верните минимальное количество операций, чтобы символ 'A' появился на экране ровно n раз.

Пример:

Input: n = 3
Output: 3

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

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

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

3⃣Возвращайте значение из таблицы динамического программирования для n.

😎 Решение:

function minSteps($n) {
    if ($n == 1) return 0;
    $dp = array_fill(0, $n + 1, 0);
    for ($i = 2; $i <= $n; $i++) {
        $dp[$i] = $i;
        for ($j = 1; $j <= $i / 2; $j++) {
            if ($i % $j == 0) {
                $dp[$i] = min($dp[$i], $dp[$j] + $i / $j);
            }
        }
    }
    return $dp[$n];
}

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

Задача: 735. Asteroid Collision
Сложность: medium

Нам дан массив asteroids, состоящий из целых чисел, представляющих астероиды в ряд. Для каждого астероида абсолютное значение обозначает его размер, а знак - направление движения (положительное - вправо, отрицательное - влево). Каждый астероид движется с одинаковой скоростью. Определите состояние астероидов после всех столкновений. Если два астероида столкнутся, меньший из них взорвется. Если оба одинакового размера, то взорвутся оба. Два астероида, движущиеся в одном направлении, никогда не встретятся.

Пример:

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

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

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

2⃣Пройдите по массиву астероидов: Если астероид движется вправо, добавьте его в стек. Если астероид движется влево, сравните его с последним астероидом в стеке (если он есть и движется вправо): Если движущийся вправо астероид больше, текущий взорвется. Если движущийся влево астероид больше, последний астероид в стеке взорвется, и продолжите сравнение. Если они одинакового размера, оба взорвутся.

3⃣Добавьте оставшиеся астероиды из стека и текущий астероид в результат.

😎 Решение:

function asteroidCollision($asteroids) {
    $stack = [];
    
    foreach ($asteroids as $asteroid) {
        $alive = true;
        while ($alive && $asteroid < 0 && !empty($stack) && end($stack) > 0) {
            $last = array_pop($stack);
            if ($last == -$asteroid) {
                $alive = false;
            } elseif ($last > -$asteroid) {
                $stack[] = $last;
                $alive = false;
            }
        }
        if ($alive) {
            $stack[] = $asteroid;
        }
    }
    
    return $stack;
}

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

Задача: 58. Length of Last Word
Сложность: easy

Дана строка s, состоящая из слов и пробелов. Верните длину последнего слова в строке.
Слово — это максимальная подстрока, состоящая только из символов, не являющихся пробелами.

Пример:

Input: s = "Hello World"
Output: 5
Explanation: The last word is "World" with length 5.

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

1⃣Поиск последнего слова:
Сначала мы пытаемся найти последнее слово, начиная с конца строки. Итерируем строку в обратном порядке, пропуская пробелы. Когда мы встречаем первый непробельный символ, мы знаем, что нашли последний символ последнего слова.

2⃣Определение длины последнего слова:
После того как последнее слово найдено, мы подсчитываем его длину, начиная с его последнего символа. Здесь также можно использовать цикл.

3⃣Итог:
Используя обратную итерацию и пропуск пробелов, определяется начало и конец последнего слова в строке для вычисления его длины.

😎 Решение:

class Solution {
    public function lengthOfLastWord($s) {
        $p = strlen($s) - 1;
        while ($p >= 0 && $s[$p] == ' ') {
            $p--;
        }
        $length = 0;
        while ($p >= 0 && $s[$p] != ' ') {
            $p--;
            $length++;
        }
        return $length;
    }
}

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

Задача: 1196. How Many Apples Can You Put into the Basket
Сложность: easy

У вас есть несколько яблок и корзина, которая может выдержать до 5000 единиц веса.

Дан целочисленный массив weight, где weight[i] — это вес i-го яблока. Верните максимальное количество яблок, которые можно положить в корзину.

Пример:

Input: weight = [100,200,150,1000]
Output: 4
Explanation: All 4 apples can be carried by the basket since their sum of weights is 1450.

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

1⃣Преобразование массива в мин-кучу:
Преобразуйте массив weight в мин-кучу, чтобы получить минимальные элементы первым.

2⃣Инициализация переменных:
Инициализируйте переменные apples для подсчета количества яблок и units для записи текущего веса корзины.

3⃣Добавление яблок в корзину:
Пока текущий вес корзины меньше 5000 единиц и в куче остаются элементы:
Увеличивайте apples на 1.
Увеличивайте units на значение, извлеченное из кучи.

😎 Решение:

class Solution {
    function maxNumberOfApples($weight) {
        sort($weight);
        $apples = 0;
        $units = 0;

        foreach ($weight as $w) {
            if ($units + $w <= 5000) {
                $units += $w;
                $apples++;
            } else {
                break;
            }
        }
        return $apples;
    }
}

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

Задача: 1025. Divisor Game
Сложность: easy

Алиса и Боб играют в игру по очереди, причем Алиса начинает первой. Изначально на доске мелом написано число n. В свой ход каждый игрок делает ход, состоящий из: выбора любого x при 0 < x < n и n % x == 0. Замены числа n на доске на n - x. Также, если игрок не может сделать ход, он проигрывает игру. Возвращается true тогда и только тогда, когда Алиса выигрывает игру, предполагая, что оба игрока играют оптимально.

Пример:

Input: n = 2
Output: true

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

1⃣Определение выигрыша:
Заметим, что если число n четное, Алиса всегда выигрывает, потому что она может уменьшить n на 1, и оставить Боба с нечетным числом.
Если число n нечетное, Алиса всегда проигрывает, потому что Боб может уменьшить n на 1, и оставить Алису с четным числом.

2⃣Проверка четности числа:
Проверяем, четное ли число n. Если n четное, возвращаем true, если нечетное, возвращаем false.

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

😎 Решение:

class Solution {
    function divisorGame($n) {
        return $n % 2 === 0;
    }
}

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

Задача: 1189. Maximum Number of Balloons
Сложность: easy

Дана строка text. Вы хотите использовать символы строки text, чтобы сформировать как можно больше экземпляров слова "balloon".

Каждый символ строки text можно использовать не более одного раза. Верните максимальное количество экземпляров, которые можно сформировать.

Пример:

Input: text = "nlaebolko"
Output: 1

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

1⃣Подсчитайте количество появлений каждого символа 'b', 'a', 'l', 'o', 'n' в строке text.

2⃣Вычислите потенциал для каждого символа: для 'b' и 'a' потенциал равен количеству их появлений, для 'l' и 'o' потенциал равен количеству их появлений, деленному на 2, а для 'n' потенциал равен количеству его появлений.

3⃣Найдите символ с наименьшим потенциалом среди 'b', 'a', 'l', 'o', 'n', который ограничивает количество возможных слов "balloon", и верните это значение.

😎 Решение:

class Solution {
    function maxNumberOfBalloons($text) {
        $bCount = 0;
        $aCount = 0;
        $lCount = 0;
        $oCount = 0;
        $nCount = 0;

        for ($i = 0; $i < strlen($text); $i++) {
            if ($text[$i] == 'b') {
                $bCount++;
            } else if ($text[$i] == 'a') {
                $aCount++;
            } else if ($text[$i] == 'l') {
                $lCount++;
            } else if ($text[$i] == 'o') {
                $oCount++;
            } else if ($text[$i] == 'n') {
                $nCount++;
            }
        }

        $lCount = intdiv($lCount, 2);
        $oCount = intdiv($oCount, 2);

        return min($bCount, $aCount, $lCount, $oCount, $nCount);
    }
}

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