Задача: 121. Best Time to Buy and Sell Stock
Сложность: easy

Вам дан массив цен, где prices[i] является ценой данной акции в i-й день.

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

Верните максимальную прибыль, которую вы можете получить от этой операции. Если прибыль получить невозможно, верните 0.

Пример:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

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

1⃣Инициализируем minPrice значением PHP_INT_MAX, maxProfit — 0.

2⃣Проходим по всем ценам:
Если текущая цена меньше minPrice, обновляем minPrice.
Если текущая прибыль (price - minPrice) больше maxProfit, обновляем maxProfit.

3⃣Возвращаем maxProfit.

😎 Решение:

class Solution {
    public function maxProfit($prices) {
        $minPrice = PHP_INT_MAX;
        $maxProfit = 0;
        foreach ($prices as $price) {
            if ($price < $minPrice) {
                $minPrice = $price;
            } elseif ($price - $minPrice > $maxProfit) {
                $maxProfit = $price - $minPrice;
            }
        }
        return $maxProfit;
    }
}

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

Задача: 971. Flip Binary Tree To Match Preorder Traversal
Сложность: medium

Дано корневое дерево с n узлами, где каждому узлу уникально присвоено значение от 1 до n. Также дана последовательность из n значений voyage, которая является желаемым обходом дерева в порядке pre-order.

Любой узел в бинарном дереве можно перевернуть, поменяв местами его левое и правое поддеревья. Например, переворот узла 1 будет иметь следующий эффект:

Переверните минимальное количество узлов, чтобы обход дерева в порядке pre-order соответствовал voyage.

Верните список значений всех перевернутых узлов. Вы можете вернуть ответ в любом порядке. Если невозможно перевернуть узлы в дереве, чтобы сделать обход в порядке pre-order соответствующим voyage, верните список [-1].

Пример:

Input: root = [1,2], voyage = [2,1]
Output: [-1]
Explanation: It is impossible to flip the nodes such that the pre-order traversal matches voyage.

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

1⃣Выполните поиск в глубину. Если в каком-либо узле значение узла не соответствует значению в voyage, верните [-1].

2⃣Иначе определите, когда нужно перевернуть: если следующее ожидаемое число в voyage (voyage[i]) отличается от следующего потомка.

3⃣Переверните узел, добавьте его значение в список перевернутых узлов и продолжите обход дерева, пока весь порядок обхода pre-order не будет соответствовать voyage.

😎 Решение:

class Solution {
    public $flipped;
    public $index;
    public $voyage;

    function flipMatchVoyage($root, $voyage) {
        $this->flipped = [];
        $this->index = 0;
        $this->voyage = $voyage;

        $this->dfs($root);
        if (!empty($this->flipped) && $this->flipped[0] == -1) {
            return [-1];
        }

        return $this->flipped;
    }

    function dfs($node) {
        if ($node !== null) {
            if ($node->val != $this->voyage[$this->index++]) {
                $this->flipped = [-1];
                return;
            }

            if ($this->index < count($this->voyage) && $node->left !== null && $node->left->val != $this->voyage[$this->index]) {
                $this->flipped[] = $node->val;
                $this->dfs($node->right);
                $this->dfs($node->left);
            } else {
                $this->dfs($node->left);
                $this->dfs($node->right);
            }
        }
    }
}

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

Задача: 1356. Sort Integers by The Number of 1 Bits
Сложность: easy

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

Верните массив после сортировки.

Пример:

Input: arr = [1024,512,256,128,64,32,16,8,4,2,1]
Output: [1,2,4,8,16,32,64,128,256,512,1024]
Explantion: All integers have 1 bit in the binary representation, you should just sort them in ascending order.

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

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

2⃣Сортировка массива:
Используйте встроенную функцию сортировки, передавая ей пользовательскую функцию сравнения, которая использует количество единиц в двоичном представлении чисел для сортировки. Если количество единиц одинаковое, используйте само число для сортировки.

3⃣Возврат отсортированного массива:
Верните отсортированный массив.

😎 Решение:

class Solution {
    function sortByBits($arr) {
        usort($arr, function($a, $b) {
            $countA = substr_count(decbin($a), '1');
            $countB = substr_count(decbin($b), '1');
            return $countA === $countB ? $a - $b : $countA - $countB;
        });
        return $arr;
    }
}

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

Задача: 273. Integer to English Words
Сложность: hard

Преобразуйте неотрицательное целое число num в его словесное представление на английском языке.

Пример:

Input: num = 123
Output: "One Hundred Twenty Three"

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

1⃣Обработка чисел до 20 и кратных 10 до 90:
Создать массивы или словари для чисел от 1 до 19 и для кратных 10 от 20 до 90.
Если число попадает в эти диапазоны, сразу вернуть соответствующее словесное представление.

2⃣Обработка сотен, тысяч, миллионов и миллиардов:
Разделить число на группы по три цифры (единицы, тысячи, миллионы, миллиарды).
Для каждой группы сформировать словесное представление с использованием рекурсивной функции для чисел от 1 до 999.

3⃣Формирование окончательного результата:
Собрать словесное представление всех групп, добавив соответствующие суффиксы (тысячи, миллионы, миллиарды).
Соединить все части в одну строку, удалив лишние пробелы.

😎 Решение:

class Solution {
    private $belowTwenty = ["", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"];
    private $tens = ["", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"];
    private $thousands = ["", "Thousand", "Million", "Billion"];
    
    function numberToWords($num) {
        if ($num == 0) return "Zero";
        $result = "";
        $i = 0;
        
        while ($num > 0) {
            if ($num % 1000 != 0) {
                $result = $this->helper($num % 1000) . $this->thousands[$i] . " " . $result;
            }
            $num = intval($num / 1000);
            $i++;
        }
        return trim($result);
    }

    private function helper($num) {
        if ($num == 0) return "";
        else if ($num < 20) return $this->belowTwenty[$num] . " ";
        else if ($num < 100) return $this->tens[intval($num / 10)] . " " . $this->helper($num % 10);
        else return $this->belowTwenty[intval($num / 100)] . " Hundred " . $this->helper($num % 100);
    }
}

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

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

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

Задача: 421. Maximum XOR of Two Numbers in an Array
Сложность: medium

Дан целочисленный массив nums, верните максимальный результат nums[i] XOR nums[j], где 0 <= i <= j < n.

Пример:

Input: nums = [3,10,5,25,2,8]
Output: 28
Explanation: The maximum result is 5 XOR 25 = 28.

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

1⃣Вычислите количество битов L для использования. Это длина максимального числа в двоичном представлении. Инициализируйте max_xor = 0.

2⃣Запустите цикл от i = L−1 до i = 0 (от самого левого бита L−1 до самого правого бита 0):
Сдвигайте max_xor влево, чтобы освободить следующий бит.
Инициализируйте переменную curr_xor = max_xor | 1, установив 1 в самом правом бите max_xor. Теперь проверьте, можно ли выполнить curr_xor, используя доступные префиксы.

3⃣Вычислите все возможные префиксы длины L−i, итерируя по nums:
Поместите в HashSet префиксы префикс текущего числа длиной L−i: num >> i.
Итерируйте по всем префиксам и проверьте, можно ли выполнить curr_xor, используя два из них: p1 ^ p2 == curr_xor. Используя свойство самопреобразования XOR p1 ^ p2 ^ p2 = p1, можно переписать это как p1 == curr_xor ^ p2 и просто проверить для каждого p, если curr_xor ^ p есть в префиксах. Если так, установите max_xor равным curr_xor, т.е. установите 1-бит в самом правом бите. В противном случае, пусть max_xor оставит 0-бит в самом правом бите.

😎 Решение:

class Solution {
    function findMaximumXOR($nums) {
        $maxNum = $nums[0];
        foreach ($nums as $num) {
            if ($num > $maxNum) {
                $maxNum = $num;
            }
        }
        $L = strlen(decbin($maxNum));

        $maxXor = 0;
        for ($i = $L - 1; $i >= 0; $i--) {
            $maxXor <<= 1;
            $currXor = $maxXor | 1;
            $prefixes = [];
            foreach ($nums as $num) {
                $prefixes[$num >> $i] = true;
            }
            foreach ($prefixes as $p => $true) {
                if (isset($prefixes[$currXor ^ $p])) {
                    $maxXor = $currXor;
                    break;
                }
            }
        }
        return $maxXor;
    }
}
?>

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

Задача: 269. Alien Dictionary
Сложность: hard

Есть новый инопланетный язык, который использует английский алфавит. Однако порядок букв в нем неизвестен.
Вам дан список строк words из словаря инопланетного языка. Утверждается, что строки в words отсортированы лексикографически по правилам этого нового языка.
Если это утверждение неверно и данное расположение строк в words не может соответствовать никакому порядку букв, верните "".
В противном случае верните строку из уникальных букв нового инопланетного языка, отсортированных в лексикографическом порядке по правилам нового языка. Если существует несколько решений, верните любое из них.

Пример:

Input: words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"

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

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

2⃣Подсчет числа входящих ребер:
Подсчитать количество входящих ребер (in-degree) для каждой буквы.
Построить исходящий список смежности и одновременно считать входящие ребра для каждой буквы.

3⃣Обход в ширину (BFS):
Инициализировать очередь буквами с нулевым in-degree.
Выполнять BFS, добавляя буквы в результат, когда их in-degree становится нулевым.
Продолжать до тех пор, пока очередь не станет пустой.
Проверить наличие циклов и вернуть результат.

😎 Решение:

function alienOrder($words) {
    $adjList = [];
    $inDegree = [];

    foreach ($words as $word) {
        foreach (str_split($word) as $char) {
            $inDegree[$char] = 0;
        }
    }

    for ($i = 0; $i < count($words) - 1; $i++) {
        $firstWord = $words[$i];
        $secondWord = $words[$i + 1];
        for ($j = 0; $j < min(strlen($firstWord), strlen($secondWord)); $j++) {
            $c = $firstWord[$j];
            $d = $secondWord[$j];
            if ($c !== $d) {
                if (!isset($adjList[$c])) {
                    $adjList[$c] = [];
                }
                if (!in_array($d, $adjList[$c])) {
                    $adjList[$c][] = $d;
                    $inDegree[$d]++;
                }
                break;
            }
        }
        if (strlen($secondWord) < strlen($firstWord) && strpos($firstWord, $secondWord) === 0) {
            return "";
        }
    }

    $output = [];
    $queue = [];

    foreach ($inDegree as $char => $degree) {
        if ($degree == 0) {
            $queue[] = $char;
        }
    }

    while (!empty($queue)) {
        $c = array_shift($queue);
        $output[] = $c;
        if (isset($adjList[$c])) {
            foreach ($adjList[$c] as $d) {
                $inDegree[$d]--;
                if ($inDegree[$d] == 0) {
                    $queue[] = $d;
                }
            }
        }
    }

    if (count($output) < count($inDegree)) {
        return "";
    }

    return implode("", $output);
}

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

Задача: 587. Erect the Fence
Сложность: hard

Вам дан массив trees, где trees[i] = [xi, yi] представляет местоположение дерева в саду.
Оградите весь сад с использованием минимальной длины веревки, так как это дорого. Сад хорошо огорожен только в том случае, если все деревья окружены.
Верните координаты деревьев, которые находятся точно на периметре ограды. Вы можете вернуть ответ в любом порядке.

Пример:

Input: trees = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
Output: [[1,1],[2,0],[4,2],[3,3],[2,4]]
Explanation: All the trees will be on the perimeter of the fence except the tree at [2, 2], which will be inside the fence.

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

1⃣Сортировка точек и построение нижней оболочки:
Отсортируйте точки по их x-координатам, а в случае совпадения x-координат, по y-координатам.
Постройте нижнюю оболочку, добавляя точки к оболочке и удаляя последние точки, если они не образуют против часовой стрелки поворот.

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

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

😎 Решение:

class Solution {
    private function orientation($p, $q, $r) {
        return ($q[1] - $p[1]) * ($r[0] - $q[0]) - ($q[0] - $p[0]) * ($r[1] - $q[1]);
    }

    function outerTrees($points) {
        usort($points, function($a, $b) {
            return $a[0] === $b[0] ? $a[1] - $b[1] : $a[0] - $b[0];
        });

        $hull = [];

        foreach ($points as $point) {
            while (count($hull) >= 2 && $this->orientation($hull[count($hull) - 2], $hull[count($hull) - 1], $point) > 0) {
                array_pop($hull);
            }
            $hull[] = $point;
        }

        array_pop($hull);

        for ($i = count($points) - 1; $i >= 0; $i--) {
            while (count($hull) >= 2 && $this->orientation($hull[count($hull) - 2], $hull[count($hull) - 1], $points[$i]) > 0) {
                array_pop($hull);
            }
            $hull[] = $points[$i];
        }

        $uniqueHull = [];
        foreach ($hull as $h) {
            $uniqueHull[implode(',', $h)] = $h;
        }

        return array_values($uniqueHull);
    }
}

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

Задача: 600. Non-negative Integers without Consecutive Ones
Сложность: Hard

Дано положительное целое число n, верните количество чисел в диапазоне [0, n], бинарные представления которых не содержат последовательных единиц.

Пример:

Input: n = 5
Output: 5
Explanation:
Here are the non-negative integers <= 5 with their corresponding binary representations:
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
Among them, only integer 3 disobeys the rule (two consecutive ones) and the other 5 satisfy the rule. 

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

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

2⃣Чтобы проверить, существует ли 1 на позиции x (считая от младшего значащего бита), в текущем числе n, поступаем следующим образом. Сдвигаем двоичную 1 x−1 раз влево, чтобы получить число y, которое имеет 1 только на x-й позиции. Логическое И числа n и y даст результат 1 только если n содержит 1 на позиции x.

3⃣В конце подсчитываем и возвращаем количество чисел в диапазоне [0, n], не содержащих последовательных единиц.

😎 Решение:

class Solution {
    function findIntegers($num) {
        $count = 0;
        for ($i = 0; $i <= $num; $i++) {
            if ($this->check($i)) {
                $count++;
            }
        }
        return $count;
    }

    function check($n) {
        $i = 31;
        while ($i > 0) {
            if (($n & (1 << $i)) != 0 && ($n & (1 << ($i - 1))) != 0) {
                return false;
            }
            $i--;
        }
        return true;
    }
}

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

Задача: 401. Binary Watch
Сложность: easy

Бинарные часы имеют 4 светодиода сверху для представления часов (0-11) и 6 светодиодов снизу для представления минут (0-59). Каждый светодиод представляет ноль или единицу, при этом младший разряд находится справа.

Пример:

Input: turnedOn = 1
Output: ["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]

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

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

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

3⃣Форматирование результата:
Если комбинация часов и минут соответствует условию, отформатируйте их в виде строки "часы:минуты" и добавьте в список результатов.

😎 Решение:

class Solution {
    function readBinaryWatch($turnedOn) {
        $results = [];
        for ($h = 0; $h < 12; $h++) {
            for ($m = 0; $m < 60; $m++) {
                if (substr_count(decbin($h), '1') + substr_count(decbin($m), '1') == $turnedOn) {
                    $results[] = sprintf("%d:%02d", $h, $m);
                }
            }
        }
        return $results;
    }
}

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

Задача: 210. Course Schedule II
Сложность: medium

Всего есть numCourses курсов, которые вы должны пройти, пронумерованных от 0 до numCourses - 1. Вам дан массив prerequisites, где prerequisites[i] = [ai, bi] указывает на то, что вы должны сначала пройти курс bi, если хотите взять курс ai.
Например, пара [0, 1] указывает на то, что для прохождения курса 0 сначала нужно пройти курс 1.
Верните порядок курсов, которые вы должны пройти, чтобы завершить все курсы. Если существует несколько правильных ответов, верните любой из них. Если невозможно завершить все курсы, верните пустой массив.

Пример:

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Объяснение: Всего есть 4 курса, которые нужно пройти. Чтобы взять курс 3, вы должны завершить оба курса 1 и 2. Оба курса 1 и 2 должны быть взяты после того, как вы завершите курс 0.
Таким образом, один из правильных порядков курсов — [0,1,2,3]. Другой правильный порядок — [0,2,1,3].

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

1⃣Инициализация и построение графа:
Инициализируйте стек S, который будет содержать топологически отсортированный порядок курсов в нашем графе.
Постройте список смежности, используя пары ребер, указанные на входе. Важно отметить, что пара вида [a, b] указывает на то, что курс b должен быть пройден, чтобы взять курс a. Это подразумевает ребро вида b ➔ a. Учтите это при реализации алгоритма.

2⃣Запуск поиска в глубину (DFS):
Для каждого узла в нашем графе выполните поиск в глубину (DFS), если этот узел еще не был посещен во время DFS другого узла.
Предположим, что мы выполняем поиск в глубину для узла N. Рекурсивно обойдите всех соседей узла N, которые еще не были обработаны.

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

😎 Решение:

class Solution {
    const WHITE = 1;
    const GRAY = 2;
    const BLACK = 3;

    public function findOrder($numCourses, $prerequisites) {
        $isPossible = true;
        $color = array_fill(0, $numCourses, self::WHITE);
        $adjList = [];
        $topologicalOrder = [];

        foreach ($prerequisites as $relation) {
            list($dest, $src) = $relation;
            if (!isset($adjList[$src])) {
                $adjList[$src] = [];
            }
            $adjList[$src][] = $dest;
        }

        for ($i = 0; $i < $numCourses && $isPossible; $i++) {
            if ($color[$i] == self::WHITE) {
                $this->dfs($i, $color, $adjList, $isPossible, $topologicalOrder);
            }
        }

        if ($isPossible) {
            $order = array_reverse($topologicalOrder);
            return $order;
        } else {
            return [];
        }
    }

    private function dfs($node, &$color, &$adjList, &$isPossible, &$topologicalOrder) {
        if (!$isPossible) return;
        $color[$node] = self::GRAY;

        if (isset($adjList[$node])) {
            foreach ($adjList[$node] as $neighbor) {
                if ($color[$neighbor] == self::WHITE) {
                    $this->dfs($neighbor, $color, $adjList, $isPossible, $topologicalOrder);
                } else if ($color[$neighbor] == self::GRAY) {
                    $isPossible = false;
                }
            }
        }

        $color[$node] = self::BLACK;
        $topologicalOrder[] = $node;
    }
}

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

Задача: 1235. Maximum Profit in Job Scheduling
Сложность: hard

У нас есть n заданий, где каждое задание планируется выполнить от startTime[i] до endTime[i], получив прибыль profit[i]. Вам даны массивы startTime, endTime и profit, верните максимальную прибыль, которую вы можете получить, так чтобы в подмножестве не было двух заданий с перекрывающимся временным диапазоном. Если вы выберете задание, которое заканчивается в момент времени X, вы сможете начать другое задание, которое начинается в момент времени X.

Пример:

Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120

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

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

2⃣Использование динамического программирования с двоичным поиском:
Используем массив dp, где dp[i] будет хранить максимальную прибыль, которую можно получить, рассматривая первые i заданий.

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

😎 Решение:

function jobScheduling($startTime, $endTime, $profit) {
    $jobs = [];
    for ($i = 0; $i < count($startTime); $i++) {
        $jobs[] = [$endTime[$i], $startTime[$i], $profit[$i]];
    }
    usort($jobs, function($a, $b) {
        return $a[0] - $b[0];
    });

    $dp = [[0, 0]];

    foreach ($jobs as [$e, $s, $p]) {
        $i = 0;
        while ($i < count($dp) && $dp[$i][0] <= $s) $i++;
        $newProfit = $dp[$i - 1][1] + $p;
        if ($newProfit > $dp[count($dp) - 1][1]) {
            $dp[] = [$e, $newProfit];
        }
    }

    return $dp[count($dp) - 1][1];
}

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

Задача: 301. Remove Invalid Parentheses
Сложность: hard

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

Пример:

Input: s = "()())()"
Output: ["(())()","()()()"]

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

1⃣Инициализация:
Инициализируйте массив, который будет хранить все допустимые выражения.
Начните рекурсию с самой левой скобки в последовательности и двигайтесь вправо.
Определите состояние рекурсии переменной index, представляющей текущий обрабатываемый индекс в исходном выражении. Также используйте переменные left_count и right_count для отслеживания количества добавленных левых и правых скобок соответственно.

2⃣Обработка текущего символа:
Если текущий символ (S[i]) не является скобкой, добавьте его к окончательному решению для текущей рекурсии.
Если текущий символ является скобкой (S[i] == '(' или S[i] == ')'), у вас есть два варианта: либо отбросить этот символ как недопустимый, либо рассмотреть эту скобку как часть окончательного выражения.

3⃣Завершение рекурсии и проверка:
Когда все скобки в исходном выражении обработаны, проверьте, является ли текущее выражение допустимым, проверяя значения left_count и right_count (должны быть равны).
Если выражение допустимо, проверьте количество удалений (rem_count) и сравните его с минимальным количеством удалений, необходимых для получения допустимого выражения до сих пор.
Если текущее значение rem_count меньше, обновите глобальный минимум и добавьте новое выражение в массив допустимых выражений.

😎 Решение:

class Solution {
    private $validExpressions;
    private $minimumRemoved;

    function __construct() {
        $this->validExpressions = [];
        $this->minimumRemoved = PHP_INT_MAX;
    }

    private function reset() {
        $this->validExpressions = [];
        $this->minimumRemoved = PHP_INT_MAX;
    }

    private function recurse($s, $index, $leftCount, $rightCount, $expression, $removedCount) {
        if ($index === strlen($s)) {
            if ($leftCount === $rightCount) {
                if ($removedCount <= $this->minimumRemoved) {
                    $possibleAnswer = implode('', $expression);
                    if ($removedCount < $this->minimumRemoved) {
                        $this->validExpressions = [];
                        $this->minimumRemoved = $removedCount;
                    }
                    $this->validExpressions[$possibleAnswer] = true;
                }
            }
            return;
        }

        $currentCharacter = $s[$index];
        $length = count($expression);

        if ($currentCharacter !== '(' && $currentCharacter !== ')') {
            array_push($expression, $currentCharacter);
            $this->recurse($s, $index + 1, $leftCount, $rightCount, $expression, $removedCount);
            array_pop($expression);
        } else {
            $this->recurse($s, $index + 1, $leftCount, $rightCount, $expression, $removedCount + 1);
            array_push($expression, $currentCharacter);

            if ($currentCharacter === '(') {
                $this->recurse($s, $index + 1, $leftCount + 1, $rightCount, $expression, $removedCount);
            } else if ($rightCount < $leftCount) {
                $this->recurse($s, $index + 1, $leftCount, $rightCount + 1, $expression, $removedCount);
            }

            array_pop($expression);
        }
    }

    function removeInvalidParentheses($s) {
        $this->reset();
        $this->recurse($s, 0, 0, 0, [], 0);
        return array_keys($this->validExpressions);
    }
}

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

Задача: 725. Split Linked List in Parts
Сложность: medium

Учитывая голову односвязного списка и целое число k, разбейте связный список на k последовательных частей связного списка. Длина каждой части должна быть как можно более одинаковой: никакие две части не должны иметь размер, отличающийся более чем на единицу. Это может привести к тому, что некоторые части будут нулевыми. Части должны располагаться в порядке появления во входном списке, и части, появившиеся раньше, всегда должны иметь размер, больший или равный частям, появившимся позже. Возвращается массив из k частей.

Пример:

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

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

1⃣Определите общую длину связного списка.

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

3⃣Разделите список на части, присваивая каждую часть в массив результатов.

😎 Решение:

class ListNode {
    public $val = 0;
    public $next = null;
    function __construct($val = 0, $next = null) {
        $this->val = $val;
        $this->next = $next;
    }
}

function splitListToParts($root, $k) {
    $length = 0;
    $node = $root;
    while ($node != null) {
        $length++;
        $node = $node->next;
    }

    $partLength = intdiv($length, $k);
    $extraParts = $length % $k;

    $parts = array_fill(0, $k, null);
    $node = $root;
    for ($i = 0; $i < $k; $i++) {
        $partHead = $node;
        $partSize = $partLength + ($i < $extraParts ? 1 : 0);
        for ($j = 0; $j < $partSize - 1; $j++) {
            if ($node != null) {
                $node = $node->next;
            }
        }
        if ($node != null) {
            $nextPart = $node->next;
            $node->next = null;
            $node = $nextPart;
        }
        $parts[$i] = $partHead;
    }

    return $parts;
}

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

Задача: 295. Find Median from Data Stream
Сложность: hard

Медиана — это среднее значение в упорядоченном списке целых чисел. Если размер списка четный, то медианы нет, и медиана — это среднее арифметическое двух средних значений.
Например, для arr = [2, 3, 4] медиана равна 3.
Например, для arr = [2, 3] медиана равна (2 + 3) / 2 = 2.5.
Реализуйте класс MedianFinder:
MedianFinder() инициализирует объект MedianFinder.
void addNum(int num) добавляет целое число num из потока данных в структуру данных.
double findMedian() возвращает медиану всех элементов на данный момент. Ответы с точностью до 10^-5 от фактического ответа будут приниматься.

Пример:

Input
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
Output
[null, null, null, 1.5, null, 2.0]

Explanation
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

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

1⃣Храните числа в контейнере с возможностью изменения размера:
Создайте массив для хранения чисел.

2⃣Добавление нового числа:
Добавьте новое число в массив.

3⃣Вычисление и вывод медианы:
Отсортируйте массив.
Если размер массива нечетный, верните среднее значение массива.
Если размер массива четный, верните среднее арифметическое двух средних значений массива.

😎 Решение:

class MedianFinder {
    private $numbers;

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

    public function addNum($num) {
        $this->numbers[] = $num;
    }

    public function findMedian() {
        sort($this->numbers);
        $n = count($this->numbers);
        if ($n % 2 == 0) {
            return ($this->numbers[$n / 2 - 1] + $this->numbers[$n / 2]) / 2.0;
        } else {
            return $this->numbers[$n / 2];
        }
    }
}
?>

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

Задача: 395. Longest Substring with At Least K Repeating Characters
Сложность: medium

Дана строка s и целое число k, верните длину самой длинной подстроки строки s, такая что частота каждого символа в этой подстроке больше или равна k.
Если такой подстроки не существует, верните 0.

Пример:

Input: s = "aaabb", k = 3
Output: 3
Explanation: The longest substring is "aaa", as 'a' is repeated 3 times.

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

1⃣Генерируйте подстроки из строки s, начиная с индекса start и заканчивая индексом end. Используйте массив countMap для хранения частоты каждого символа в подстроке.

2⃣Метод isValid использует countMap для проверки, что каждый символ в подстроке встречается как минимум k раз. Если условие выполняется, текущая подстрока считается допустимой.

3⃣Отслеживайте максимальную длину допустимой подстроки, обновляя её, когда найдена более длинная подстрока, удовлетворяющая условиям. В конце возвращайте длину самой длинной подстроки.

😎 Решение:

function longestSubstring($s, $k) {
    if (strlen($s) == 0 || $k > strlen($s)) {
        return 0;
    }
    $result = 0;

    for ($start = 0; $start < strlen($s); $start++) {
        $countMap = array_fill(0, 26, 0);
        for ($end = $start; $end < strlen($s); $end++) {
            $countMap[ord($s[$end]) - ord('a')]++;
            if (isValid($countMap, $k)) {
                $result = max($result, $end - $start + 1);
            }
        }
    }
    return $result;
}

function isValid($countMap, $k) {
    $countLetters = 0;
    $countAtLeastK = 0;
    foreach ($countMap as $count) {
        if ($count > 0) $countLetters++;
        if ($count >= $k) $countAtLeastK++;
    }
    return $countLetters == $countAtLeastK;
}

echo longestSubstring("aaabb", 3); // Output: 3
echo "\n";
echo longestSubstring("ababbc", 2); // Output: 5

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

Задача: 74. Search a 2D Matrix
Сложность: medium

Вам дана матрица из целых чисел размером m на n с следующими двумя свойствами:

Каждая строка отсортирована в порядке неубывания.
Первое число каждой строки больше последнего числа предыдущей строки.
Дано целое число target. Верните true, если target присутствует в матрице, и false в противном случае.

Вы должны написать решение с временной сложностью O(log(m * n)).

Пример:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

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

1⃣Инициализируйте индексы слева и справа: left = 0 и right = m x n - 1.

2⃣Пока left <= right:
Выберите индекс посередине виртуального массива в качестве опорного индекса: pivot_idx = (left + right) / 2.

3⃣Индекс соответствует row = pivot_idx // n и col = pivot_idx % n в исходной матрице, и, следовательно, можно получить pivot_element. Этот элемент делит виртуальный массив на две части.
Сравните pivot_element и target, чтобы определить, в какой части нужно искать target.

😎 Решение:

function searchMatrix($matrix, $target) {
    $m = count($matrix);
    if ($m == 0) return false;
    $n = count($matrix[0]);
    $left = 0;
    $right = $m * $n - 1;

    while ($left <= $right) {
        $pivotIdx = intdiv($left + $right, 2);
        $pivotElement = $matrix[intdiv($pivotIdx, $n)][$pivotIdx % $n];
        if ($target == $pivotElement) {
            return true;
        } else {
            if ($target < $pivotElement) {
                $right = $pivotIdx - 1;
            } else {
                $left = $pivotIdx + 1;
            }
        }
    }
    return false;
}

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

Задача: 766. Toeplitz Matrix
Сложность: easy

Дана матрица размером m x n. Вернуть true, если матрица является Тёплицевой. В противном случае вернуть false.
Матрица является Тёплицевой, если все диагонали, идущие от верхнего левого к нижнему правому углу, содержат одинаковые элементы.

Пример:

Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
Output: true
Explanation:
In the above grid, the diagonals are:
"[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]".
In each diagonal all elements are the same, so the answer is True.

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

1⃣Что отличает две координаты (r1, c1) и (r2, c2) на одной диагонали? Оказывается, две координаты находятся на одной диагонали тогда и только тогда, когда r1 - c1 == r2 - c2.м

2⃣Это приводит к следующей идее: запоминайте значение этой диагонали как groups[r - c]. Если обнаружено несоответствие, то матрица не является Тёплицевой; в противном случае, она является таковой.

3⃣Таким образом, для каждой ячейки матрицы сохраняйте значение диагонали в словаре groups с ключом r - c. Проходите по всем ячейкам матрицы и проверяйте, совпадает ли текущее значение с сохранённым в groups. Если где-то обнаруживается несоответствие, верните false. Если все элементы соответствуют, верните true.

😎 Решение:

class Solution {
    function isToeplitzMatrix($matrix) {
        $groups = [];
        for ($r = 0; $r < count($matrix); ++$r) {
            for ($c = 0; $c < count($matrix[0]); ++$c) {
                if (!array_key_exists($r - $c, $groups))
                    $groups[$r - $c] = $matrix[$r][$c];
                else if ($groups[$r - $c] != $matrix[$r][$c])
                    return false;
            }
        }
        return true;
    }
}

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

Задача: 1041. Robot Bounded In Circle
Сложность: medium

На бесконечной плоскости робот изначально стоит в точке (0, 0) и обращен лицом на север. Обратите внимание, что: северное направление - это положительное направление оси y. южное направление - это отрицательное направление оси y. восточное направление - это положительное направление оси x. западное направление - это отрицательное направление оси x. робот может получить одну из трех команд: "G": идти прямо 1 единицу. "L": повернуть на 90 градусов влево (т.е, "R": повернуть на 90 градусов вправо (т. е. по часовой стрелке). Робот выполняет данные инструкции по порядку и повторяет их до бесконечности. Возвращается true тогда и только тогда, когда в плоскости существует окружность, такая, что робот никогда не покидает ее.

Пример:

Input: instructions = "GGLLGG"
Output: true

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

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

2⃣Изменение направления:
Робот может двигаться на север (0), восток (1), юг (2), или запад (3). Эти направления можно моделировать с помощью векторов (dx, dy): север (0, 1), восток (1, 0), юг (0, -1), запад (-1, 0).

3⃣Обработка команд:
Пройдите по всем командам и обновите позицию робота и направление, в котором он движется.
Проверка состояния робота:
После выполнения всех команд проверьте, вернулся ли робот в начальную точку (0, 0) или изменил направление. Если одно из этих условий выполнено, робот будет двигаться по замкнутой траектории.

😎 Решение:

function isRobotBounded($instructions) {
    $directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    $x = 0;
    $y = 0;
    $direction = 0;
    
    for ($i = 0; $i < strlen($instructions); $i++) {
        $instruction = $instructions[$i];
        if ($instruction == 'G') {
            $x += $directions[$direction][0];
            $y += $directions[$direction][1];
        } elseif ($instruction == 'L') {
            $direction = ($direction + 3) % 4;
        } elseif ($instruction == 'R') {
            $direction = ($direction + 1) % 4;
        }
    }
    
    return ($x == 0 && $y == 0) || $direction != 0;
}

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

Задача: 1318. Minimum Flips to Make a OR b Equal to c
Сложность: medium

Даны три положительных числа a, b и c. Верните минимальное количество переворотов, необходимых в некоторых битах a и b, чтобы сделать (a OR b == c) (побитовая операция OR). Операция переворота состоит из изменения любого отдельного бита с 1 на 0 или с 0 на 1 в их двоичном представлении.

Пример:

Input: a = 2, b = 6, c = 5
Output: 3
Explanation: After flips a = 1 , b = 4 , c = 5 such that (a OR b == c)

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

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

2⃣Итеративно обрабатывайте каждый бит двоичного представления чисел a, b и c одновременно:

Если (c & 1) == 0, обновите answer как answer += (a & 1) + (b & 1).
Если (c & 1) == 1, и если оба значения a & 1 и b & 1 равны 0, увеличьте answer на 1.

3⃣Сдвигайте все числа вправо с помощью a >>= 1, b >>= 1, c >>= 1. Если все числа равны 0, верните answer, в противном случае, повторите шаги 2 и 3.

😎 Решение:

class Solution {
    function minFlips($a, $b, $c) {
        $answer = 0;
        while ($a != 0 || $b != 0 || $c != 0) {
            if (($c & 1) == 1) {
                if (($a & 1) == 0 && ($b & 1) == 0) {
                    $answer++;
                }
            } else {
                $answer += ($a & 1) + ($b & 1);
            }
            $a >>= 1;
            $b >>= 1;
            $c >>= 1;
        }
        return $answer;
    }
}

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

Задача: 723. Candy Crush
Сложность: medium

Этот вопрос касается реализации базового алгоритма исключения для Candy Crush. Дан целочисленный массив board размером m x n, представляющий сетку конфет, где board[i][j] представляет тип конфеты. Значение board[i][j] == 0 означает, что ячейка пуста. Данная доска представляет собой состояние игры после хода игрока. Теперь необходимо вернуть доску в стабильное состояние, раздавив конфеты по следующим правилам: если три или более конфет одного типа находятся рядом по вертикали или горизонтали, раздавите их все одновременно - эти позиции станут пустыми. После одновременного раздавливания всех конфет, если на пустом месте доски есть конфеты, расположенные сверху, то эти конфеты будут падать, пока не ударятся о конфету или дно одновременно. Новые конфеты не будут падать за верхнюю границу. После выполнения описанных выше действий может остаться больше конфет, которые можно раздавить. Если конфет, которые можно раздавить, больше не существует (т. е. доска стабильна), верните текущую доску. Выполняйте описанные выше правила, пока доска не станет стабильной, затем верните стабильную доску.

Пример:

Input: board = [[110,5,112,113,114],[210,211,5,213,214],[310,311,3,313,314],[410,411,412,5,414],[5,1,512,3,3],[610,4,1,613,614],[710,1,2,713,714],[810,1,2,1,1],[1,1,2,2,2],[4,1,4,4,1014]]
Output: [[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[110,0,0,0,114],[210,0,0,0,214],[310,0,0,113,314],[410,0,0,213,414],[610,211,112,313,614],[710,311,412,613,714],[810,411,512,713,1014]]

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

1⃣Найдите все группы из трех или более одинаковых конфет, как в горизонтальном, так и в вертикальном направлениях, и отметьте их для удаления.

2⃣Удалите отмеченные конфеты, установив их значение в 0.

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

😎 Решение:

function candyCrush($board) {
    $m = count($board);
    $n = count($board[0]);
    $stable = false;

    while (!$stable) {
        $stable = true;
        $crush = array_fill(0, $m, array_fill(0, $n, false));

        for ($i = 0; $i < $m; $i++) {
            for ($j = 0; $j < $n - 2; $j++) {
                $v = abs($board[$i][$j]);
                if ($v != 0 && $v == abs($board[$i][$j + 1]) && $v == abs($board[$i][$j + 2])) {
                    $stable = false;
                    $crush[$i][$j] = $crush[$i][$j + 1] = $crush[$i][$j + 2] = true;
                }
            }
        }

        for ($i = 0; $i < $m - 2; $i++) {
            for ($j = 0; $j < $n; $j++) {
                $v = abs($board[$i][$j]);
                if ($v != 0 && $v == abs($board[$i + 1][$j]) && $v == abs($board[$i + 2][$j])) {
                    $stable = false;
                    $crush[$i][$j] = $crush[$i + 1][$j] = $crush[$i + 2][$j] = true;
                }
            }
        }

        for ($i = 0; $i < $m; $i++) {
            for ($j = 0; $j < $n; $j++) {
                if ($crush[$i][$j]) {
                    $board[$i][$j] = 0;
                }
            }
        }

        for ($j = 0; $j < $n; $j++) {
            $idx = $m - 1;
            for ($i = $m - 1; $i >= 0; $i--) {
                if ($board[$i][$j] != 0) {
                    $board[$idx][$j] = $board[$i][$j];
                    $idx--;
                }
            }
            for ($i = $idx; $i >= 0; $i--) {
                $board[$i][$j] = 0;
            }
        }
    }

    return $board;
}

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