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

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

Пример:

Input: n = 6
Output: true

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

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

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

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

😎 Решение:

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

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

    return $rotatedStr !== $nStr;
}

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

        return $A;
    }
}

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

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

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

Пример:

Input: s = "*"
Output: 9

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

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

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

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

😎 Решение:

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

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

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

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

Задача: 1243. Array Transformation
Сложность: easy

Если задан исходный массив arr, то каждый день вы создаете новый массив, используя массив предыдущего дня. В i-й день вы выполняете следующие операции над массивом дня i-1, чтобы получить массив дня i: если элемент меньше своего левого и правого соседа, то этот элемент увеличивается. Если элемент больше своего левого и правого соседа, то этот элемент уменьшается. Первый и последний элементы никогда не меняются. Через несколько дней массив не меняется. Верните этот окончательный массив.

Пример:

Input: arr = [6,2,3,4]
Output: [6,3,3,4]

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

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

2⃣Для каждого элемента массива проверяем, изменяется ли он в зависимости от его левого и правого соседей.
Если элемент меньше своего левого и правого соседей, увеличиваем его.
Если элемент больше своего левого и правого соседей, уменьшаем его.

3⃣Первый и последний элементы массива остаются неизменными.

😎 Решение:

function transformArray($arr) {
    do {
        $changed = false;
        $newArr = $arr;
        for ($i = 1; $i < count($arr) - 1; $i++) {
            if ($arr[$i] < $arr[$i - 1] && $arr[$i] < $arr[$i + 1]) {
                $newArr[$i]++;
                $changed = true;
            } else if ($arr[$i] > $arr[$i - 1] && $arr[$i] > $arr[$i + 1]) {
                $newArr[$i]--;
                $changed = true;
            }
        }
        $arr = $newArr;
    } while ($changed);
    return $arr;
}

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

Задача: 410. Split Array Largest Sum
Сложность: easy

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

Пример:

Input: nums = [7,2,5,10,8], k = 2
Output: 18

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

1⃣Определите границы для бинарного поиска: минимальная сумма равна максимальному элементу массива, максимальная сумма равна сумме всех элементов массива.

2⃣Выполните бинарный поиск по этим границам. Для каждой средней суммы проверьте, можно ли разбить массив на k подмассивов, чтобы максимальная сумма подмассива не превышала эту среднюю сумму.

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

😎 Решение:

function splitArray($nums, $k) {
    $left = max($nums);
    $right = array_sum($nums);
    while ($left < $right) {
        $mid = intdiv($left + $right, 2);
        if (canSplit($nums, $k, $mid)) {
            $right = $mid;
        } else {
            $left = $mid + 1;
        }
    }
    return $left;
}

function canSplit($nums, $k, $maxSum) {
    $currentSum = 0;
    $subarrays = 1;
    foreach ($nums as $num) {
        if ($currentSum + $num > $maxSum) {
            $currentSum = $num;
            $subarrays++;
            if ($subarrays > $k) {
                return false;
            }
        } else {
            $currentSum += $num;
        }
    }
    return true;
}

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

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

В инопланетном языке, как ни странно, тоже используются английские строчные буквы, но, возможно, в другом порядке. Порядок алфавита - это некоторая перестановка строчных букв. Учитывая последовательность слов, написанных на инопланетном языке, и порядок алфавита, верните true тогда и только тогда, когда данные слова отсортированы лексикографически на этом инопланетном языке.

Пример:

Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
Output: true

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

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

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

3⃣Если все слова отсортированы правильно, вернуть true.

😎 Решение:

function isAlienSorted($words, $order) {
    $orderMap = array_flip(str_split($order));
    
    for ($i = 0; $i < count($words) - 1; $i++) {
        if (!compare($words[$i], $words[$i + 1], $orderMap)) {
            return false;
        }
    }
    return true;
}

function compare($word1, $word2, $orderMap) {
    $minLength = min(strlen($word1), strlen($word2));
    for ($i = 0; $i < $minLength; $i++) {
        if ($orderMap[$word1[$i]] < $orderMap[$word2[$i]]) {
            return true;
        } elseif ($orderMap[$word1[$i]] > $orderMap[$word2[$i]]) {
            return false;
        }
    }
    return strlen($word1) <= strlen($word2);
}

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

Задача: 750. Number Of Corner Rectangles
Сложность: medium

Дан указатель на начало односвязного списка и два целых числа left и right, где left <= right. Необходимо перевернуть узлы списка, начиная с позиции left и заканчивая позицией right, и вернуть измененный список.

Пример:

Input: grid = [[1,0,0,1,0],[0,0,1,0,1],[0,0,0,1,0],[1,0,1,0,1]]
Output: 1

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

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

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

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

😎 Решение:

function countCornerRectangles($grid) {
    $count = 0;
    for ($i = 0; $i < count($grid); $i++) {
        for ($j = $i + 1; $j < count($grid); $j++) {
            $numPairs = 0;
            for ($k = 0; $k < count($grid[0]); $k++) {
                if ($grid[$i][$k] == 1 && $grid[$j][$k] == 1) {
                    $numPairs++;
                }
            }
            if ($numPairs > 1) {
                $count += $numPairs * ($numPairs - 1) / 2;
            }
        }
    }
    return $count;
}

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

Задача: 1034. Coloring A Border
Сложность: medium

Вам дана целочисленная матричная сетка m x n и три целых числа row, col и color. Каждое значение в сетке представляет собой цвет квадрата сетки в данном месте. Два квадрата называются смежными, если они находятся рядом друг с другом в любом из 4 направлений. Два квадрата принадлежат одному связанному компоненту, если они имеют одинаковый цвет и являются смежными.

Граница связанного компонента - это все квадраты в связанном компоненте, которые либо смежны (по крайней мере) с квадратом, не входящим в компонент, либо находятся на границе сетки (в первой или последней строке или столбце). Вы должны окрасить границу связанного компонента, содержащего квадрат grid[row][col], в цвет. Верните конечную сетку.

Пример:

Input: grid = [[1,1],[1,2]], row = 0, col = 0, color = 3
Output: [[3,3],[3,2]]

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

1⃣Поиск связанного компонента:
Используйте поиск в глубину (DFS) или поиск в ширину (BFS), чтобы найти все клетки, принадлежащие связанному компоненту, содержащему клетку grid[row][col].
Запомните все клетки, которые принадлежат этому компоненту.

2⃣Определение границ компонента:
Для каждой клетки в связанном компоненте проверьте, является ли она границей. Клетка является границей, если она находится на краю сетки или если хотя бы одна из её соседних клеток не принадлежит связанному компоненту или имеет другой цвет.

3⃣Окрашивание границы:
Измените цвет всех клеток, являющихся границами, на заданный цвет.

😎 Решение:

function colorBorder($grid, $row, $col, $color) {
    $m = count($grid);
    $n = count($grid[0]);
    $originalColor = $grid[$row][$col];
    $visited = array_fill(0, $m, array_fill(0, $n, false));
    $borders = [];

    function dfs($r, $c, $m, $n, $originalColor, &$grid, &$visited, &$borders) {
        $visited[$r][$c] = true;
        $isBorder = false;
        foreach ([[-1, 0], [1, 0], [0, -1], [0, 1]] as [$dr, $dc]) {
            $nr = $r + $dr;
            $nc = $c + $dc;
            if ($nr >= 0 && $nr < $m && $nc >= 0 && $nc < $n) {
                if (!$visited[$nr][$nc]) {
                    if ($grid[$nr][$nc] == $originalColor) {
                        dfs($nr, $nc, $m, $n, $originalColor, $grid, $visited, $borders);
                    } else {
                        $isBorder = true;
                    }
                }
            } else {
                $isBorder = true;
            }
        }
        if ($isBorder || $r == 0 || $r == $m - 1 || $c == 0 || $c == $n - 1) {
            $borders[] = [$r, $c];
        }
    }

    dfs($row, $col, $m, $n, $originalColor, $grid, $visited, $borders);
    foreach ($borders as [$r, $c]) {
        $grid[$r][$c] = $color;
    }

    return $grid;
}

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

Задача: 326. Power of Three
Сложность: easy

Дано целое число n. Верните true, если оно является степенью тройки, иначе верните false.
Целое число n является степенью тройки, если существует целое число x такое, что n == 3^x.

Пример:

Input: n = 27
Output: true
Explanation: 27 = 3^3

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

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

2⃣Цикл деления на 3
Пока n делится на 3 без остатка, делите n на 3. Повторяйте этот процесс до тех пор, пока n делится на 3.

3⃣Проверка конечного значения
Если после всех делений значение n стало равно 1, значит исходное число является степенью тройки, вернуть true. В противном случае вернуть false.

😎 Решение:

class Solution {
    function isPowerOfThree($n) {
        if ($n <= 0) return false;
        while ($n % 3 == 0) {
            $n /= 3;
        }
        return $n == 1;
    }
}

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

Задача: 179. Largest Number
Сложность: medium

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

Пример:

Input: nums = [10,2]
Output: "210"

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

1⃣Преобразование и сортировка: Преобразовать каждое число в строку и отсортировать массив строк с использованием специального компаратора, который для двух строк 𝑎 и b сравнивает результаты конкатенации 𝑎+𝑏 и 𝑏+𝑎.

2⃣Проверка на нули: Если после сортировки первый элемент массива равен "0", вернуть "0", так как все числа в массиве нули.

3⃣Формирование результата: Конкатенировать отсортированные строки для формирования наибольшего числа и вернуть это число в виде строки.

😎 Решение:

class Solution {
    function largestNumber($nums) {
        $strNums = array_map('strval', $nums);
        usort($strNums, function($a, $b) {
            return strcmp($b . $a, $a . $b);
        });
        if ($strNums[0] === "0") {
            return "0";
        }
        return implode('', $strNums);
    }
}

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

Задача: 70. Climbing Stairs
Сложность: easy

Ты поднимаешься по лестнице. Чтобы добраться до вершины, нужно преодолеть n ступенек.
Каждый раз ты можешь подняться на 1 или 2 ступеньки. Сколькими различными способами ты можешь добраться до вершины?

Пример:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

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

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

2⃣На каждом шаге мы вызываем функцию climbStairs для шага 1 и шага 2, и возвращаем сумму возвращаемых значений обеих функций.

3⃣Формула вызова функции: climbStairs(i, n) = climbStairs(i+1, n) + climbStairs(i+2, n), где i определяет текущий шаг, а n — целевой шаг.

😎 Решение:

function climbStairs($n) {
    return climb_Stairs(0, $n);
}

function climb_Stairs($i, $n) {
    if ($i > $n) {
        return 0;
    }
    if ($i == $n) {
        return 1;
    }
    return climb_Stairs($i + 1, $n) + climb_Stairs($i + 2, $n);
}

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

Задача: 936. Stamping The Sequence
Сложность: hard

Вам даны две строки stamp и target. Изначально имеется строка s длины target.length со всеми s[i] == '?'. За один ход вы можете поместить штамп над s и заменить каждую букву в s на соответствующую букву из штампа. Например, если штамп = "abc" и target = "abcba", то s изначально будет "?????". За один ход вы можете: поместить штамп в индекс 0 s, чтобы получить "abc??", поместить штамп в индекс 1 s, чтобы получить "?abc?", или поместить штамп в индекс 2 s, чтобы получить "??abc". Обратите внимание, что штамп должен полностью находиться в границах s, чтобы штамповать (то есть вы не можете поместить штамп в индекс 3 s). Мы хотим преобразовать s в цель, используя не более 10 * target.length ходов. Верните массив индекса самой левой буквы, которая штампуется на каждом ходу. Если мы не можем получить цель из s за 10 * target.length оборотов, верните пустой массив

Пример:

Input: stamp = "abc", target = "ababc"
Output: [0,2]

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

1⃣Инициализировать переменные:
s как массив символов '?', длиной target.length.
res как список для хранения результатов.
done как массив булевых значений для отслеживания того, какие позиции уже штампованы.
target как массив символов для удобства.

2⃣Использовать функцию canStamp для проверки, можно ли штамповать stamp в target начиная с индекса i.
Использовать функцию doStamp для штампования stamp в target начиная с индекса i.
Повторять шаги, пока штампы возможны или достигнут максимум ходов (10 * target.length):
Перебрать все возможные начальные позиции для штампа.
Проверить, можно ли штамповать в текущей позиции.
Если можно, штамповать и добавить индекс в res.

3⃣Если все символы в s соответствуют символам в target, вернуть массив res в обратном порядке. Иначе, вернуть пустой массив.

😎 Решение:

function movesToStamp($stamp, $target) {
    $s = str_split($stamp);
    $t = str_split($target);
    $m = count($s);
    $n = count($t);
    $res = [];
    $done = array_fill(0, $n, false);
    
    $canStamp = function($i) use ($s, $t, $m) {
        for ($j = 0; $j < $m; $j++) {
            if ($t[$i + $j] !== '?' && $t[$i + $j] !== $s[$j]) {
                return false;
            }
        }
        return true;
    };
    
    $doStamp = function($i) use (&$t, &$res, &$done, $m) {
        for ($j = 0; $j < $m; $j++) {
            $t[$i + $j] = '?';
        }
        $res[] = $i;
        $done[$i] = true;
    };
    
    $changed = true;
    while ($changed) {
        $changed = false;
        for ($i = 0; $i <= $n - $m; $i++) {
            if (!$done[$i] && $canStamp($i)) {
                $doStamp($i);
                $changed = true;
            }
        }
    }
    
    foreach ($t as $c) {
        if ($c !== '?') {
            return [];
        }
    }
    
    return array_reverse($res);
}

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