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

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

Задача: 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 int countNegatives(int[][] grid) {
        int count = 0;
        for (int[] row : grid) {
            for (int element : row) {
                if (element < 0) {
                    count++;
                }
            }
        }
        return count;
    }
}

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

Задача: 1114. Print in Order
Сложность: easy

Предположим, у нас есть класс:

public class Foo {
  public void first() { print("first"); }
  public void second() { print("second"); }
  public void third() { print("third"); }
}

Один и тот же экземпляр Foo будет передан трем разным потокам. Поток A вызовет first(), поток B вызовет second(), и поток C вызовет third(). Спроектируйте механизм и модифицируйте программу, чтобы гарантировать, что second() выполняется после first(), а third() выполняется после second().

Примечание:
Мы не знаем, как потоки будут планироваться в операционной системе, даже если числа в вводе подразумевают порядок выполнения. Формат ввода, который вы видите, в основном предназначен для обеспечения полноты наших тестов.

Пример:

Input: nums = [1,2,3]
Output: "firstsecondthird"
Explanation: There are three threads being fired asynchronously. The input [1,2,3] means thread A calls first(), thread B calls second(), and thread C calls third(). "firstsecondthird" is the correct output.

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

1⃣Инициализация переменных:
Инициализируйте координационные переменные firstJobDone и secondJobDone, чтобы указать, что задания еще не выполнены.

2⃣Функция first():
В этой функции нет зависимости, поэтому можно сразу приступить к выполнению задания. В конце функции обновите переменную firstJobDone, чтобы указать, что первое задание выполнено.

3⃣Функции second() и third():
В функции second() проверьте статус firstJobDone. Если она не обновлена, подождите, иначе переходите к выполнению второго задания. В конце функции обновите переменную secondJobDone, чтобы отметить завершение второго задания.
В функции third() проверьте статус secondJobDone. Аналогично функции second(), подождите сигнала secondJobDone перед тем, как приступить к выполнению третьего задания.

😎 Решение:

class Foo {
    private $firstJobDone;
    private $secondJobDone;

    public function __construct() {
        $this->firstJobDone = false;
        $this->secondJobDone = false;
    }

    public function first($printFirst) {
        $printFirst();
        $this->firstJobDone = true;
    }

    public function second($printSecond) {
        while (!$this->firstJobDone) {
            usleep(100);
        }
        $printSecond();
        $this->secondJobDone = true;
    }

    public function third($printThird) {
        while (!$this->secondJobDone) {
            usleep(100);
        }
        $printThird();
    }
}

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

Задача: 617. Merge Two Binary Trees
Сложность: medium

Вам даны два бинарных дерева root1 и root2. Представьте, что при наложении одного из них на другое некоторые узлы двух деревьев перекрываются, а другие - нет. Вам нужно объединить эти два дерева в новое бинарное дерево. Правило слияния таково: если два узла пересекаются, то в качестве нового значения объединенного узла используется сумма значений узлов. В противном случае в качестве узла нового дерева будет использоваться узел NOT null. Возвращается объединенное дерево. Примечание: Процесс объединения должен начинаться с корневых узлов обоих деревьев.

Пример:

Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
Output: [3,4,5,5,4,null,7]

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

1⃣Если один из узлов пуст (null), возвращаем другой узел. Если оба узла пустые, возвращаем null.

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

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

😎 Решение:

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

function mergeTrees($root1, $root2) {
    if ($root1 === null) {
        return $root2;
    }
    if ($root2 === null) {
        return $root1;
    }
    
    $mergedNode = new TreeNode($root1->val + $root2->val);
    $mergedNode->left = mergeTrees($root1->left, $root2->left);
    $mergedNode->right = mergeTrees($root1->right, $root2->right);
    
    return $mergedNode;
}

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

Задача: 1199. Minimum Time to Build Blocks
Сложность: hard

Вам дан список блоков, где blocks[i] = t означает, что на строительство i-го блока требуется t единиц времени. Блок может быть построен только одним рабочим.
Рабочий может либо разделиться на двух рабочих (количество рабочих увеличивается на одного), либо построить блок и уйти домой. Оба решения требуют некоторого времени.
Время, затраченное на разделение одного рабочего на двух, задано целым числом split. Обратите внимание, что если два рабочих разделяются одновременно, они разделяются параллельно, поэтому затраты времени будут равны split.

Выведите минимальное время, необходимое для строительства всех блоков.

Изначально есть только один рабочий.

Пример:

Input: blocks = [1,2,3], split = 1
Output: 4
Explanation: Split 1 worker into 2, then assign the first worker to the last block and split the second worker into 2.
Then, use the two unassigned workers to build the first two blocks.
The cost is 1 + max(3, 1 + max(1, 2)) = 4.

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

1⃣Подготовка кучи строительного времени:
Инициализируйте кучу строительного времени, изначально содержащую все значения времени из массива blocks.

2⃣Обработка кучи:
Пока в куче больше одного элемента:
- извлеките минимальное значение из кучи, обозначим его как x.
- извлеките следующее минимальное значение из кучи, обозначим его как y.
- создайте новое время строительства, которое равно split + y, и вставьте его обратно в кучу.

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

😎 Решение:

class Solution {
    function minBuildTime($blocks, $split) {
        sort($blocks);
        $pq = new SplPriorityQueue();
        foreach ($blocks as $block) {
            $pq->insert($block, -$block);
        }
        
        while ($pq->count() > 1) {
            $x = $pq->extract();
            $y = $pq->extract();
            $pq->insert($split + $y, -($split + $y));
        }
        
        return $pq->extract();
    }
}

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

Задача: 1361. Validate Binary Tree Nodes
Сложность: easy

У вас есть n узлов бинарного дерева, пронумерованных от 0 до n-1, где узел i имеет двух детей: leftChild[i] и rightChild[i]. Верните true, если и только если все заданные узлы образуют ровно одно допустимое бинарное дерево.

Если у узла i нет левого ребенка, то leftChild[i] будет равен -1, аналогично для правого ребенка.

Обратите внимание, что узлы не имеют значений и мы используем только номера узлов в этой задаче.

Пример:

Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1]
Output: true

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

1⃣Проверка количества родителей для каждого узла:
Создайте массив для отслеживания количества родителей для каждого узла. Проходите через leftChild и rightChild, увеличивая счетчик для каждого ребенка. Если какой-либо узел имеет более одного родителя, возвращайте false.

2⃣Поиск корневого узла и проверка на единственное дерево:
Найдите корневой узел (узел с нулевым количеством родителей). Если корневых узлов нет или больше одного, верните false. Используйте BFS или DFS, чтобы проверить, что все узлы достижимы от корня и что нет циклов.

3⃣Проверка на достижение всех узлов:
Проверьте, что количество посещенных узлов равно n. Если нет, верните false. В противном случае, верните true.

😎 Решение:

class Solution {
    function validateBinaryTreeNodes($n, $leftChild, $rightChild) {
        $parents = array_fill(0, $n, 0);

        for ($i = 0; $i < $n; $i++) {
            if ($leftChild[$i] != -1) {
                $parents[$leftChild[$i]]++;
                if ($parents[$leftChild[$i]] > 1) {
                    return false;
                }
            }
            if ($rightChild[$i] != -1) {
                $parents[$rightChild[$i]]++;
                if ($parents[$rightChild[$i]] > 1) {
                    return false;
                }
            }
        }

        $root = -1;
        for ($i = 0; $i < $n; $i++) {
            if ($parents[$i] == 0) {
                if ($root == -1) {
                    $root = $i;
                } else {
                    return false;
                }
            }
        }

        if ($root == -1) {
            return false;
        }

        $visited = [];
        $queue = [$root];

        while (!empty($queue)) {
            $node = array_shift($queue);
            if (in_array($node, $visited)) {
                return false;
            }
            $visited[] = $node;
            if ($leftChild[$node] != -1) {
                $queue[] = $leftChild[$node];
            }
            if ($rightChild[$node] != -1) {
                $queue[] = $rightChild[$node];
            }
        }

        return count($visited) == $n;
    }
}

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

Задача: 1009. Complement of Base 10 Integer
Сложность: easy

Дополнение целого числа - это целое число, которое получается, если перевернуть все 0 в 1 и все 1 в 0 в его двоичном представлении. Например, целое число 5 - это "101" в двоичном представлении, а его дополнение - "010", то есть целое число 2. Если задано целое число n, верните его дополнение.

Пример:

Input: n = 5
Output: 2

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

1⃣Определение длины двоичного представления:
Найдите длину двоичного представления числа n.

2⃣Создание маски:
Создайте маску, которая состоит из всех единиц и имеет ту же длину, что и двоичное представление числа n.

3⃣Вычисление дополнения:
Примените побитовую операцию XOR между числом n и маской, чтобы получить дополнение числа.

😎 Решение:

class Solution {
    function findComplement($num) {
        $length = strlen(decbin($num));
        $mask = (1 << $length) - 1;
        return $num ^ $mask;
    }
}

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

Задача: 363. Max Sum of Rectangle No Larger Than K
Сложность: hard

Дана матрица размером m x n и целое число k, вернуть максимальную сумму прямоугольника в матрице, такая что его сумма не превышает k.
Гарантируется, что будет прямоугольник с суммой, не превышающей k.

Пример:

Input: matrix = [[1,0,1],[0,-2,3]], k = 2
Output: 2
Explanation: Because the sum of the blue rectangle [[0, 1], [-2, 3]] is 2, and 2 is the max number no larger than k (k = 2).

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

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

2⃣Преобразовать каждую подматрицу в одномерный массив и применить к ней функцию updateResult.

3⃣Вернуть максимальную найденную сумму.

😎 Решение:

class Solution {
    private $result;

    function __construct() {
        $this->result = PHP_INT_MIN;
    }

    private function updateResult($nums, $k) {
        $sum = 0;
        $sortedSum = [0];

        foreach ($nums as $num) {
            $sum += $num;
            $idx = $this->binarySearch($sortedSum, $sum - $k);
            if ($idx < count($sortedSum)) {
                $this->result = max($this->result, $sum - $sortedSum[$idx]);
            }
            array_push($sortedSum, $sum);
            sort($sortedSum);
        }
    }

    private function binarySearch($arr, $target) {
        $left = 0;
        $right = count($arr);
        while ($left < $right) {
            $mid = intval(($left + $right) / 2);
            if ($arr[$mid] < $target) $left = $mid + 1;
            else $right = $mid;
        }
        return $left;
    }

    function maxSumSubmatrix($matrix, $k) {
        $rows = count($matrix);
        $cols = count($matrix[0]);

        for ($i = 0; $i < $rows; $i++) {
            $rowSum = array_fill(0, $cols, 0);
            for ($row = $i; $row < $rows; $row++) {
                for ($col = 0; $col < $cols; $col++) {
                    $rowSum[$col] += $matrix[$row][$col];
                }
                $this->updateResult($rowSum, $k);
                if ($this->result == $k) {
                    return $this->result;
                }
            }
        }
        return $this->result;
    }
}

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

Задача: 506. Relative Ranks
Сложность: easy

Вам дан целочисленный массив score размером n, где score[i] — это результат i-го спортсмена на соревновании. Все результаты гарантированно уникальны.
Спортсмены размещаются на основе своих результатов: спортсмен, занявший 1-е место, имеет наивысший результат, спортсмен, занявший 2-е место, имеет второй по величине результат и так далее. Размещение каждого спортсмена определяет его ранг:
Ранг спортсмена, занявшего 1-е место, — "Gold Medal".
Ранг спортсмена, занявшего 2-е место, — "Silver Medal".
Ранг спортсмена, занявшего 3-е место, — "Bronze Medal".
Для спортсменов, занявших с 4-го по n-е место, их ранг соответствует их номеру в размещении (т.е. ранг спортсмена, занявшего x-е место, — "x").
Верните массив answer размером n, где answer[i] — это ранг i-го спортсмена.

Пример:

Input: score = [5,4,3,2,1]
Output: ["Gold Medal","Silver Medal","Bronze Medal","4","5"]
Explanation: The placements are [1st, 2nd, 3rd, 4th, 5th].

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

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

2⃣Создание вспомогательных структур
Инициализируйте массив scoreToIndex размером M + 1, где M — это максимальное значение в массиве score. Заполните scoreToIndex таким образом, чтобы для каждого score[i] его индекс сохранялся в scoreToIndex[score[i]].

3⃣Присваивание рангов и формирование ответа
Создайте массив rank для хранения рангов спортсменов. Используйте цикл для присваивания медалей и рангов в зависимости от значений в scoreToIndex, начиная с наибольшего.

😎 Решение:

class Solution {
    function findRelativeRanks($score) {
        $N = count($score);
        $maxScore = max($score);
        $scoreToIndex = array_fill(0, $maxScore + 1, 0);
        
        foreach ($score as $i => $s) {
            $scoreToIndex[$s] = $i + 1;
        }
        
        $MEDALS = ["Gold Medal", "Silver Medal", "Bronze Medal"];
        $rank = array_fill(0, $N, "");
        $place = 1;
        
        for ($i = $maxScore; $i >= 0; $i--) {
            if ($scoreToIndex[$i] != 0) {
                $originalIndex = $scoreToIndex[$i] - 1;
                if ($place < 4) {
                    $rank[$originalIndex] = $MEDALS[$place - 1];
                } else {
                    $rank[$originalIndex] = strval($place);
                }
                $place++;
            }
        }
        
        return $rank;
    }
}

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

Задача: 228. Summary Ranges
Сложность: easy

Вам дан отсортированный массив уникальных целых чисел nums.
Диапазон [a,b] - это множество всех целых чисел от a до b (включительно).
Верните наименьший отсортированный список диапазонов, которые покрывают все числа в массиве точно. То есть, каждый элемент nums покрывается ровно одним из диапазонов, и не существует такого целого числа x, чтобы x находился в одном из диапазонов, но не находился в nums.
Каждый диапазон [a,b] в списке должен быть представлен в формате:
"a->b" если a != b
"a" если a == b

Пример:

Input: nums = [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]
Explanation: The ranges are:
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"

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

1⃣Создайте список строк ranges, который будет содержать решение задачи, и начните итерацию по всем элементам nums с указателем i = 0. Каждая итерация внешнего цикла представляет собой поиск одного диапазона. Для начала сохраните начало текущего диапазона в start = nums[i].

2⃣Проверьте, отличается ли следующий элемент в nums на индексе i + 1 от nums[i] на 1 или больше. Если следующий элемент отличается на 1, увеличьте i на 1, чтобы включить (i+1)-й элемент в этот диапазон и продолжайте проверку следующего элемента. Продолжайте добавлять элементы в этот диапазон, пока последовательные элементы отличаются на 1, используя цикл while для выполнения этой логики.

3⃣Если следующий элемент отличается более чем на 1 или если все элементы в nums уже обработаны, проверьте, равен ли start значению nums[i]. Если start == nums[i], добавьте только start как строку в ranges, так как у нас есть только один элемент в этом диапазоне. Если start != nums[i], добавьте строку start->nums[i] в ranges. Увеличьте i на 1, чтобы начать новый диапазон.

😎 Решение:

class Solution {
    function summaryRanges($nums) {
        $ranges = [];
        $i = 0;
        while ($i < count($nums)) {
            $start = $nums[$i];
            while ($i + 1 < count($nums) && $nums[$i] + 1 == $nums[$i + 1]) {
                $i++;
            }
            if ($start != $nums[$i]) {
                $ranges[] = $start . "->" . $nums[$i];
            } else {
                $ranges[] = (string)$start;
            }
            $i++;
        }
        return $ranges;
    }
}

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

Задача: 115. Distinct Subsequences
Сложность: hard

"Даны две строки s и t. Верните количество различных подпоследовательностей строки s, которые равны строке t.

Тестовые примеры сгенерированы таким образом, что ответ укладывается в 32-битное целое число со знаком."

Пример:

Input: s = "rabbbit", t = "rabbit"
Output: 3
Explanation:
As shown below, there are 3 ways you can generate "rabbit" from s.
rabbbit
rabbbit
rabbbit

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

1⃣Определите функцию с названием recurse, которая принимает два целочисленных значения i и j. Первое значение представляет текущий обрабатываемый символ в строке S, а второе - текущий символ в строке T. Инициализируйте словарь под названием memo, который будет кэшировать результаты различных вызовов рекурсии.**

2⃣Проверьте базовый случай. Если одна из строк закончилась, возвращается 0 или 1 в зависимости от того, удалось ли обработать всю строку T или нет. Есть ещё один базовый случай, который следует рассмотреть. Если оставшаяся длина строки S меньше, чем у строки T, то совпадение невозможно. Если это обнаруживается, то рекурсия также обрезается и возвращается 0.**

3⃣Затем проверяем, существует ли текущая пара индексов в нашем словаре. Если да, то просто возвращаем сохранённое/кэшированное значение. Если нет, то продолжаем обычную обработку. Сравниваем символы s[i] и t[j]. Сохраняем результат вызова recurse(i + 1, j) в переменную. Как упоминалось ранее, результат этой рекурсии необходим, независимо от совпадения символов. Если символы совпадают, добавляем к переменной результат вызова recurse(i + 1, j + 1). Наконец, сохраняем значение этой переменной в словаре с ключом (i, j) и возвращаем это значение в качестве ответа.

😎 Решение:

class Solution {
    private $memo = [];

    public function numDistinct($s, $t) {
        return $this->uniqueSubsequences($s, $t, 0, 0);
    }

    private function uniqueSubsequences($s, $t, $i, $j) {
        $M = strlen($s);
        $N = strlen($t);

        if ($i == $M || $j == $N || $M - $i < $N - $j) {
            return (int)($j == strlen($t));
        }

        if (isset($this->memo["$i,$j"])) {
            return $this->memo["$i,$j"];
        }

        $ans = $this->uniqueSubsequences($s, $t, $i + 1, $j);

        if ($s[$i] == $t[$j]) {
            $ans += $this->uniqueSubsequences($s, $t, $i + 1, $j + 1);
        }

        $this->memo["$i,$j"] = $ans;
        return $ans;
    }
}

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

Задача: 1043. Partition Array for Maximum Sum
Сложность: medium

Если задан целочисленный массив arr, разбейте его на (смежные) подмассивы длины не более k. После разбиения значения каждого подмассива меняются так, чтобы стать максимальным значением этого подмассива. Верните наибольшую сумму заданного массива после разбиения. Тестовые примеры генерируются таким образом, чтобы ответ умещался в 32-битное целое число.

Пример:

Input: arr = [1,15,7,9,2,5,10], k = 3
Output: 84

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

1⃣Инициализация:
Создаем массив dp, где dp[i] будет хранить наибольшую сумму подмассива, заканчивающегося в позиции i.

2⃣Заполнение массива dp:
Проходим по массиву arr и для каждой позиции i пытаемся разбить подмассив длины до k и обновить dp[i] с максимальной возможной суммой.

3⃣Поддержание максимального значения в подмассиве:
Для каждого подмассива длины 1 до k, вычисляем максимальное значение в этом подмассиве и обновляем dp[i].

😎 Решение:

function maxSumAfterPartitioning($arr, $k) {
    $n = count($arr);
    $dp = array_fill(0, $n, 0);
    
    for ($i = 0; $i < $n; $i++) {
        $maxVal = 0;
        for ($j = 1; $j <= $k; $j++) {
            if ($i - $j + 1 >= 0) {
                $maxVal = max($maxVal, $arr[$i - $j + 1]);
                if ($i - $j >= 0) {
                    $dp[$i] = max($dp[$i], $dp[$i - $j] + $maxVal * $j);
                } else {
                    $dp[$i] = max($dp[$i], $maxVal * $j);
                }
            }
        }
    }
    
    return $dp[$n - 1];
}

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

Задача: 1039. Minimum Score Triangulation of Polygon
Сложность: medium

У вас есть выпуклый n-сторонний многоугольник, каждая вершина которого имеет целочисленное значение. Вам дан целочисленный массив values, где values[i] - это значение i-й вершины (т.е. по часовой стрелке). Вы должны триангулировать многоугольник на n - 2 треугольника. Для каждого треугольника значение этого треугольника равно произведению значений его вершин, а общий балл триангуляции равен сумме этих значений для всех n - 2 треугольников в триангуляции. Верните наименьший возможный общий балл, который вы можете получить с помощью некоторой триангуляции многоугольника.

Пример:

Input: values = [1,2,3]
Output: 6

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

1⃣Инициализация:
Создаем двумерный массив dp, где dp[i][j] будет хранить минимальный возможный общий балл триангуляции многоугольника, состоящего из вершин от i до j.

2⃣Основное заполнение dp:
Проходим по всем возможным длинам подмногоугольников, начиная с треугольников (длина 3) до всего многоугольника (длина n).
Для каждого подмногоугольника находим минимальный возможный общий балл, проверяя все возможные треугольники, которые могут быть образованы из этого подмногоугольника.
Заполнение dp для каждого подмногоугольника:
Для каждого подмногоугольника от i до j, и для каждой возможной вершины k между i и j, обновляем значение dp[i][j], как сумму минимальных значений триангуляций левой и правой частей подмногоугольника, а также значения текущего треугольника, образованного вершинами i, k и j.

3⃣Возврат результата:
Ответ будет в dp[0][n-1], который хранит минимальный возможный общий балл триангуляции для всего многоугольника.

😎 Решение:

function minScoreTriangulation($values) {
    $n = count($values);
    $dp = array_fill(0, $n, array_fill(0, $n, 0));
    
    for ($length = 2; $length < $n; $length++) {
        for ($i = 0; $i < $n - $length; $i++) {
            $j = $i + $length;
            $dp[$i][$j] = PHP_INT_MAX;
            for ($k = $i + 1; $k < $j; $k++) {
                $dp[$i][$j] = min($dp[$i][$j], $dp[$i][$k] + $dp[$k][$j] + $values[$i] * $values[$j] * $values[$k]);
            }
        }
    }
    
    return $dp[0][$n - 1];
}

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