Задача: 161. One Edit Distance
Сложность: medium

Даны две строки s и t. Верните true, если они отличаются ровно на одну операцию редактирования, иначе верните false.
Строка s считается отличающейся на одну операцию редактирования от строки t, если можно:
- Вставить ровно один символ в строку s, чтобы получить t.
- Удалить ровно один символ из строки s, чтобы получить t.
- Заменить ровно один символ в строке s на другой символ, чтобы получить t.

Пример:

Input: s = "ab", t = "acb"
Output: true
Explanation: We can insert 'c' into s to get t.

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

1⃣Проверка длины строк:
Убедитесь, что строка s короче строки t. Если это не так, поменяйте их местами и повторите проверку.
Если разница в длине между s и t больше 1, то строки невозможно привести к равенству одной операцией редактирования, верните false.

2⃣Сравнение строк посимвольно:
Проходите по строке s и сравнивайте каждый символ с соответствующим символом в строке t.
Если находите различающийся символ:
Если длины строк равны (ns == nt), проверьте, равны ли подстроки после текущего символа для обеих строк (s.substr(i + 1) == t.substr(i + 1)). Если равны, возвращайте true, иначе false.
Если длины строк различаются, проверьте, равна ли подстрока s начиная с текущего символа подстроке t начиная с следующего символа (s.substr(i) == t.substr(i + 1)). Если равны, возвращайте true, иначе false

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

😎 Решение:

class Solution {
    function isOneEditDistance($s, $t) {
        $ns = strlen($s);
        $nt = strlen($t);
        if ($ns > $nt) return $this->isOneEditDistance($t, $s);
        if ($nt - $ns > 1) return false;

        for ($i = 0; $i < $ns; $i++) {
            if ($s[$i] != $t[$i]) {
                if ($ns == $nt) return substr($s, $i + 1) == substr($t, $i + 1);
                else return substr($s, $i) == substr($t, $i + 1);
            }
        }
        return $ns + 1 == $nt;
    }
}

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

Задача: 238. Product of Array Except Self
Сложность: medium

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

Пример:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

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

1⃣Инициализация массивов L и R: Инициализируйте два пустых массива L и R. Массив L будет содержать произведение всех чисел слева от i, а массив R будет содержать произведение всех чисел справа от i. Заполните массив L, установив L[0] равным 1, а для остальных элементов используйте формулу L[i] = L[i-1] * nums[i-1]. Заполните массив R, установив R[length-1] равным 1, а для остальных элементов используйте формулу R[i] = R[i+1] * nums[i+1].

2⃣Заполнение массивов L и R: Пройдите два цикла для заполнения массивов L и R. В первом цикле заполните массив L, начиная с L[0] и двигаясь вправо. Во втором цикле заполните массив R, начиная с R[length-1] и двигаясь влево.

3⃣Формирование результата: Пройдите по исходному массиву и для каждого элемента i вычислите произведение всех элементов, кроме nums[i], используя L[i] * R[i]. Сохраните результат в массиве answer и верните его.

😎 Решение:

class Solution {
    function productExceptSelf($nums) {
        $length = count($nums);
        $L = array_fill(0, $length, 1);
        $R = array_fill(0, $length, 1);
        $answer = array_fill(0, $length, 1);

        for ($i = 1; $i < $length; $i++) {
            $L[$i] = $nums[$i - 1] * $L[$i - 1];
        }

        for ($i = $length - 2; $i >= 0; $i--) {
            $R[$i] = $nums[$i + 1] * $R[$i + 1];
        }

        for ($i = 0; $i < $length; $i++) {
            $answer[$i] = $L[$i] * $R[$i];
        }

        return $answer;
    }
}

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

Задача: 715. Range Module
Сложность: hard

Модуль Range - это модуль, который отслеживает диапазоны чисел. Создайте структуру данных для отслеживания диапазонов, представленных в виде полуоткрытых интервалов, и запросов к ним. Полуоткрытый интервал [left, right) обозначает все вещественные числа x, где left <= x < right. Реализуйте класс RangeModule: RangeModule() Инициализирует объект структуры данных. void addRange(int left, int right) Добавляет полуоткрытый интервал [left, right), отслеживая каждое вещественное число в этом интервале. Добавление интервала, который частично перекрывает отслеживаемые в данный момент числа, должно добавить все числа в интервале [left, right), которые еще не отслеживаются. boolean queryRange(int left, int right) Возвращает true, если каждое действительное число в интервале [left, right) отслеживается в данный момент, и false в противном случае. void removeRange(int left, int right) Прекращает отслеживание каждого действительного числа, отслеживаемого в данный момент в полуоткрытом интервале [left, right).

Пример:

Input
["RangeModule", "addRange", "removeRange", "queryRange", "queryRange", "queryRange"]
[[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]]
Output
[null, null, null, true, false, true]

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

1⃣Инициализируйте класс RangeModule с пустым списком диапазонов.

2⃣Для метода addRange(left, right) добавьте новый диапазон, объединяя его с существующими перекрывающимися диапазонами. Для метода queryRange(left, right) проверьте, полностью ли данный диапазон содержится в отслеживаемых диапазонах.

3⃣Для метода removeRange(left, right) удалите указанный диапазон, разбивая существующие диапазоны на соответствующие части.

😎 Решение:

class RangeModule {

    private $ranges;

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

    function addRange($left, $right) {
        $newRanges = [];
        $i = 0;
        while ($i < count($this->ranges) && $this->ranges[$i][1] < $left) {
            $newRanges[] = $this->ranges[$i];
            $i++;
        }
        while ($i < count($this->ranges) && $this->ranges[$i][0] <= $right) {
            $left = min($left, $this->ranges[$i][0]);
            $right = max($right, $this->ranges[$i][1]);
            $i++;
        }
        $newRanges[] = [$left, $right];
        while ($i < count($this->ranges)) {
            $newRanges[] = $this->ranges[$i];
            $i++;
        }
        $this->ranges = $newRanges;
    }

    function queryRange($left, $right) {
        foreach ($this->ranges as $range) {
            if ($range[0] <= $left && $right <= $range[1]) {
                return true;
            }
        }
        return false;
    }

    function removeRange($left, $right) {
        $newRanges = [];
        foreach ($this->ranges as $range) {
            if ($range[0] < $left) {
                $newRanges[] = [$range[0], min($range[1], $left)];
            }
            if ($right < $range[1]) {
                $newRanges[] = [max($range[0], $right), $range[1]];
            }
        }
        $this->ranges = $newRanges;
    }
}

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

Задача: 642. Design Search Autocomplete System
Сложность: hard

Разработайте свою реализацию круговой двусторонней очереди (deque). Реализуйте класс MyCircularDeque: MyCircularDeque(int k) Инициализирует deque с максимальным размером k. boolean insertFront() Добавляет элемент в переднюю часть Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean insertLast() Добавляет элемент в заднюю часть Deque. Возвращает true, если операция выполнена успешно, или false в противном случае. boolean deleteFront() Удаляет элемент из передней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean deleteLast() Удаляет элемент из задней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. int getFront() Возвращает передний элемент из Deque. Возвращает -1, если Deque пуст. int getRear() Возвращает последний элемент из Deque. Возвращает -1, если Deque пуст. boolean isEmpty() Возвращает true, если Deque пуст, или false в противном случае. boolean isFull() Возвращает true, если Deque полон, или false в противном случае.

Пример:

Input
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 2, true, true, true, 4]

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

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

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

3⃣Операции удаления
Реализуйте методы удаления элементов из передней и задней частей очереди с учетом кольцевой структуры и методы для получения переднего и заднего элементов очереди.

😎 Решение:

class TrieNode {
    public $children;
    public $count;

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

class AutocompleteSystem {
    private $root;
    private $prefix;

    function __construct($sentences, $times) {
        $this->root = new TrieNode();
        $this->prefix = "";
        for ($i = 0; $i < count($sentences); $i++) {
            $this->add($sentences[$i], $times[$i]);
        }
    }

    private function add($sentence, $count) {
        $node = $this->root;
        for ($i = 0; $i < strlen($sentence); $i++) {
            $char = $sentence[$i];
            if (!isset($node->children[$char])) {
                $node->children[$char] = new TrieNode();
            }
            $node = $node->children[$char];
            if (!isset($node->count[$sentence])) {
                $node->count[$sentence] = 0;
            }
            $node->count[$sentence] += $count;
        }
    }

    function input($c) {
        if ($c == '#') {
            $this->add($this->prefix, 1);
            $this->prefix = "";
            return [];
        }

        $this->prefix .= $c;
        $node = $this->root;
        for ($i = 0; $i < strlen($this->prefix); $i++) {
            $char = $this->prefix[$i];
            if (!isset($node->children[$char])) {
                return [];
            }
            $node = $node->children[$char];
        }

        $pq = [];
        foreach ($node->count as $sentence => $count) {
            $pq[] = [$sentence, $count];
        }

        usort($pq, function($a, $b) {
            if ($a[1] == $b[1]) {
                return strcmp($a[0], $b[0]);
            }
            return $b[1] - $a[1];
        });

        $result = [];
        for ($i = 0; $i < min(3, count($pq)); $i++) {
            $result[] = $pq[$i][0];
        }

        return $result;
    }
}

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

Задача: 376. Wiggle Subsequence
Сложность: easy

Колеблющаяся последовательность — это последовательность, в которой разности между последовательными числами строго чередуются между положительными и отрицательными. Первая разность (если она существует) может быть как положительной, так и отрицательной. Последовательность с одним элементом и последовательность с двумя неравными элементами тривиально являются колеблющимися последовательностями.
Например, [1, 7, 4, 9, 2, 5] — это колеблющаяся последовательность, потому что разности (6, -3, 5, -7, 3) чередуются между положительными и отрицательными.
В отличие от нее, [1, 4, 7, 2, 5] и [1, 7, 4, 5, 5] не являются колеблющимися последовательностями. Первая не является, потому что первые две разности положительные, а вторая не является, потому что последняя разность равна нулю.
Подпоследовательность получается путем удаления некоторых элементов (возможно, нуля) из исходной последовательности с сохранением оставшихся элементов в их первоначальном порядке.

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

Пример:

Input: nums = [1,7,4,9,2,5]
Output: 6
Explanation: The entire sequence is a wiggle sequence with differences (6, -3, 5, -7, 3).

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

1⃣Для понимания этого подхода создайте два массива для динамического программирования, названных up и down. Эти массивы будут хранить длины наибольших колеблющихся подпоследовательностей, заканчивающихся соответственно восходящим или нисходящим колебанием.

2⃣up[i] относится к длине самой длинной колеблющейся подпоследовательности на данный момент, если рассматривать i-й элемент как последний элемент последовательности, заканчивающейся восходящим колебанием. Аналогично, down[i] относится к длине самой длинной колеблющейся подпоследовательности, если рассматривать i-й элемент как последний элемент последовательности, заканчивающейся нисходящим колебанием.

3⃣up[i] обновляется каждый раз, когда мы находим восходящее колебание, заканчивающееся на i-м элементе. Чтобы найти up[i], необходимо учесть максимальное значение всех предыдущих подпоследовательностей, заканчивающихся нисходящим колебанием, т.е. down[j], для каждого j<i и nums[i]>nums[j]. Аналогично, down[i] обновляется при нахождении нисходящего колебания.

😎 Решение:

class Solution {
    public function islandPerimeter($grid) {
        $rows = count($grid);
        $cols = count($grid[0]);
        
        $result = 0;
        
        for ($r = 0; $r < $rows; $r++) {
            for ($c = 0; $c < $cols; $c++) {
                if ($grid[$r][$c] == 1) {
                    $up = ($r == 0) ? 0 : $grid[$r-1][$c];
                    $left = ($c == 0) ? 0 : $grid[$r][$c-1];
                    $down = ($r == $rows-1) ? 0 : $grid[$r+1][$c];
                    $right = ($c == $cols-1) ? 0 : $grid[$r][$c+1];
                    
                    $result += 4 - ($up + $left + $right + $down);
                }
            }
        }
        
        return $result;
    }
}

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

Задача: 998. Maximum Binary Tree II
Сложность: medium

Максимальное дерево - это дерево, в котором каждый узел имеет значение большее, чем любое другое значение в его поддереве. Вам дан корень максимального двоичного дерева и целое число val. Как и в предыдущей задаче, данное дерево было построено из списка a (root = Construct(a)) рекурсивно с помощью следующей процедуры Construct(a): Если a пусто, верните null.
В противном случае пусть a[i] - наибольший элемент a. Создайте корневой узел со значением a[i]. Левым ребенком root будет Construct([a[0], a[1], ..., a[i - 1]]). Правым ребенком root будет Construct([a[i + 1], a[i + 2], ..., a[a.length])...., a[a.length - 1]]). Возвращаем root. Обратите внимание, что нам не было дано непосредственно a, а только корневой узел root = Construct(a). Предположим, что b - это копия a с добавленным к ней значением val. Гарантируется, что b имеет уникальные значения. Возвращаем Construct(b).

Пример:

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

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

1⃣Поиск места вставки:
Итерируйте через дерево, начиная с корня. Найдите место для вставки нового значения val так, чтобы дерево оставалось максимальным деревом. Если значение val больше, чем значение текущего узла, создайте новый узел с val и сделайте текущий узел его левым ребенком.

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

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

class Solution {
    function insertIntoMaxTree($root, $val) {
        if ($root == null || $val > $root->val) {
            return new TreeNode($val, $root, null);
        }
        $root->right = $this->insertIntoMaxTree($root->right, $val);
        return $root;
    }
}

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

Задача: 364. Nested List Weight Sum II
Сложность: medium

Вам дан вложенный список целых чисел nestedList. Каждый элемент является либо целым числом, либо списком, элементы которого также могут быть целыми числами или другими списками.
Глубина целого числа — это количество списков, внутри которых оно находится. Например, вложенный список [1,[2,2],[[3],2],1] имеет значение каждого целого числа, установленное равным его глубине. Пусть maxDepth будет максимальной глубиной любого целого числа.
Вес целого числа определяется как maxDepth - (глубина целого числа) + 1.
Верните сумму каждого целого числа в nestedList, умноженную на его вес.

Пример:

Input: nestedList = [[1,1],2,[1,1]]
Output: 8
Explanation: Four 1's with a weight of 1, one 2 with a weight of 2.
1*1 + 1*1 + 2*2 + 1*1 + 1*1 = 8

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

1⃣Инициализировать первый уровень BFS-дерева, добавив все элементы из входного nestedList в очередь.

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

3⃣Когда очередь станет пустой, вернуть значение (maxDepth + 1) * sumOfElements - sumOfProducts.

😎 Решение:

class Solution {
    function depthSumInverse($nestedList) {
        $queue = $nestedList;
        $depth = 1;
        $maxDepth = 0;
        $sumOfElements = 0;
        $sumOfProducts = 0;

        while (!empty($queue)) {
            $size = count($queue);
            $maxDepth = max($maxDepth, $depth);

            for ($i = 0; $i < $size; $i++) {
                $nested = array_shift($queue);

                if ($nested->isInteger()) {
                    $value = $nested->getInteger();
                    $sumOfElements += $value;
                    $sumOfProducts += $value * $depth;
                } else {
                    $queue = array_merge($queue, $nested->getList());
                }
            }
            $depth++;
        }
        return ($maxDepth + 1) * $sumOfElements - $sumOfProducts;
    }
}

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

Задача: 1160. Find Words That Can Be Formed by Characters
Сложность: easy

Вам дан массив строк words и строка chars.

Строка считается хорошей, если она может быть составлена из символов chars (каждый символ может быть использован только один раз).

Верните сумму длин всех хороших строк в words.

Пример:

Input: words = ["cat","bt","hat","tree"], chars = "atach"
Output: 6
Explanation: The strings that can be formed are "cat" and "hat" so the answer is 3 + 3 = 6.

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

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

2⃣Итерируйте по каждому слову в words. Создайте хеш-таблицу wordCount, которая будет записывать частоту каждого символа в слове. Установите good = true. Итерируйте по каждому ключу c в wordCount. Пусть freq = wordCount[c]. Если counts[c] < freq, установите good = false и прервите цикл.

3⃣Если good = true, добавьте длину слова к ans. Верните ans.

😎 Решение:

class Solution {
    function countCharacters($words, $chars) {
        $counts = array_count_values(str_split($chars));
        
        $ans = 0;
        foreach ($words as $word) {
            $wordCount = array_count_values(str_split($word));
            $good = true;
            foreach ($wordCount as $c => $freq) {
                if (!isset($counts[$c]) || $counts[$c] < $freq) {
                    $good = false;
                    break;
                }
            }
            
            if ($good) {
                $ans += strlen($word);
            }
        }
        
        return $ans;
    }
}

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

Задача: 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree
Сложность: easy

Даны два бинарных дерева: original и cloned, а также ссылка на узел target в оригинальном дереве.

Дерево cloned является копией оригинального дерева.

Верните ссылку на тот же узел в дереве cloned.

Обратите внимание, что вам не разрешается изменять какое-либо из двух деревьев или узел target, и ответ должен быть ссылкой на узел в дереве cloned.

Пример:

Input: tree = [7,4,3,null,null,6,19], target = 3
Output: 3
Explanation: In all examples the original and cloned trees are shown. The target node is a green node from the original tree. The answer is the yellow node from the cloned tree.

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

1⃣Добавьте корень в очередь.

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

3⃣Верните ссылку на найденный целевой узел.

😎 Решение:

class Solution {
    function getTargetCopy($original, $cloned, $target) {
        $queue_o = [$original];
        $queue_c = [$cloned];
        
        while (!empty($queue_o)) {
            $node_o = array_shift($queue_o);
            $node_c = array_shift($queue_c);
            
            if ($node_o === $target) {
                return $node_c;
            }
            
            if ($node_o->left !== null) {
                $queue_o[] = $node_o->left;
                $queue_c[] = $node_c->left;
            }
            if ($node_o->right !== null) {
                $queue_o[] = $node_o->right;
                $queue_c[] = $node_c->right;
            }
        }
        return null;
    }
}

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

Задача: 530. Minimum Absolute Difference in BST
Сложность: easy

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

Пример:

Input: root = [4,2,6,1,3]
Output: 1

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

1⃣Обход дерева в порядке возрастания (инфиксный обход):
Создайте список inorderNodes для хранения значений узлов.
Выполните инфиксный обход дерева, добавляя значения узлов в список.

2⃣Нахождение минимальной разницы:
Создайте переменную minDifference и инициализируйте её бесконечностью.
Пройдите по списку inorderNodes, начиная с индекса 1, и найдите минимальную абсолютную разницу между последовательными элементами.

3⃣Возврат результата:
Верните minDifference.

😎 Решение:

class Solution {
    private $inorderNodes = [];

    function getMinimumDifference($root) {
        $this->inorderTraversal($root);
        $minDifference = PHP_INT_MAX;
        for ($i = 1; $i < count($this->inorderNodes); $i++) {
            $minDifference = min($minDifference, $this->inorderNodes[$i] - $this->inorderNodes[$i - 1]);
        }
        return $minDifference;
    }

    private function inorderTraversal($node) {
        if ($node === null) return;
        $this->inorderTraversal($node->left);
        $this->inorderNodes[] = $node->val;
        $this->inorderTraversal($node->right);
    }
}

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

Задача: 1267. Count Servers that Communicate
Сложность: medium

На двумерной плоскости имеется n точек с целочисленными координатами points[i] = [xi, yi]. Верните минимальное время в секундах для посещения всех точек в порядке, заданном точками. Вы можете перемещаться по следующим правилам: за 1 секунду вы можете либо: переместиться по вертикали на одну единицу, по горизонтали на одну единицу, либо по диагонали sqrt(2) единиц (другими словами, переместиться на одну единицу по вертикали и на одну единицу по горизонтали за 1 секунду). Вы должны посетить точки в том же порядке, в котором они появляются в массиве. Вы можете проходить через точки, которые появляются позже в порядке, но они не считаются за посещение.

Пример:

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

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

1⃣Подсчитайте количество серверов в каждой строке и каждом столбце.

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

3⃣Подсчитайте и верните количество взаимодействующих серверов.

😎 Решение:

class Solution {
    function countServers($grid) {
        $rows = array_fill(0, count($grid), 0);
        $cols = array_fill(0, count($grid[0]), 0);

        for ($i = 0; $i < count($grid); $i++) {
            for ($j = 0; $j < count($grid[0]); $j++) {
                if ($grid[$i][$j] == 1) {
                    $rows[$i]++;
                    $cols[$j]++;
                }
            }
        }

        $count = 0;
        for ($i = 0; $i < count($grid); $i++) {
            for ($j = 0; $j < count($grid[0]); $j++) {
                if ($grid[$i][$j] == 1 && ($rows[$i] > 1 || $cols[$j] > 1)) {
                    $count++;
                }
            }
        }

        return $count;
    }
}

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

#hard
Задача: 827. Making A Large Island

Вам дан n x n бинарный матрица grid. Вам разрешено изменить не более одного 0 на 1.

Верните размер самого большого острова в grid после выполнения этой операции.

Остров — это группа 1, соединенных в 4 направлениях.

Пример:

Input: grid = [[1,1],[1,0]]
Output: 4
Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.

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

1⃣Пройдите по матрице и пометьте каждую группу, используя уникальный индекс, и запомните её размер.

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

3⃣Возвращайте максимальный размер острова, учитывая как уже существующие острова, так и потенциальные, образованные после изменения 0 на 1.

😎 Решение:

class Solution {
    private $dr = [-1, 0, 1, 0];
    private $dc = [0, -1, 0, 1];
    private $grid;
    private $N;

    function largestIsland($grid) {
        $this->grid = $grid;
        $this->N = count($grid);
        
        $index = 2;
        $area = array_fill(0, $this->N * $this->N + 2, 0);
        for ($r = 0; $r < $this->N; ++$r) {
            for ($c = 0; $c < $this->N; ++$c) {
                if ($grid[$r][$c] == 1) {
                    $area[$index] = $this->dfs($r, $c, $index);
                    ++$index;
                }
            }
        }
        
        $ans = max($area);
        for ($r = 0; $r < $this->N; ++$r) {
            for ($c = 0; $c < $this->N; ++$c) {
                if ($grid[$r][$c] == 0) {
                    $seen = [];
                    foreach ($this->neighbors($r, $c) as $move) {
                        if ($grid[$move[0]][$move[1]] > 1) {
                            $seen[$grid[$move[0]][$move[1]]] = true;
                        }
                    }
                    $bns = 1;
                    foreach (array_keys($seen) as $i) {
                        $bns += $area[$i];
                    }
                    $ans = max($ans, $bns);
                }
            }
        }
        
        return $ans;
    }

    function dfs($r, $c, $index) {
        $ans = 1;
        $this->grid[$r][$c] = $index;
        foreach ($this->neighbors($r, $c) as $move) {
            if ($this->grid[$move[0]][$move[1]] == 1) {
                $this->grid[$move[0]][$move[1]] = $index;
                $ans += $this->dfs($move[0], $move[1], $index);
            }
        }
        return $ans;
    }

    function neighbors($r, $c) {
        $ans = [];
        for ($k = 0; $k < 4; ++$k) {
            $nr = $r + $this->dr[$k];
            $nc = $c + $this->dc[$k];
            if ($nr >= 0 && $nr < $this->N && $nc >= 0 && $nc < $this->N) {
                $ans[] = [$nr, $nc];
            }
        }
        return $ans;
    }

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

Сложность: hard
Задача: 1274. Number of Ships in a Rectangle


(Эта задача является интерактивной.) Каждый корабль находится в целочисленной точке моря, представленной картезианской плоскостью, и каждая целочисленная точка может содержать не более 1 корабля. У вас есть функция Sea.hasShips(topRight, bottomLeft), которая принимает две точки в качестве аргументов и возвращает true, если в прямоугольнике, представленном этими двумя точками, есть хотя бы один корабль, включая на границе. Учитывая две точки: правый верхний и левый нижний углы прямоугольника, верните количество кораблей в этом прямоугольнике. Гарантируется, что в прямоугольнике находится не более 10 кораблей. Решения, содержащие более 400 обращений к hasShips, будут оцениваться как "Неправильный ответ". Кроме того, любые решения, пытающиеся обойти судью, приведут к дисквалификации.

Пример:

Input: 
ships = [[1,1],[2,2],[3,3],[5,5]], topRight = [4,4], bottomLeft = [0,0]
Output: 3

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

1⃣Разделите текущий прямоугольник на четыре меньших прямоугольника

2⃣Рекурсивно проверьте наличие кораблей в каждом из четырех подпрямоугольников, используя функцию hasShips

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

😎 Решение:

class Solution {
    function countShips($sea, $topRight, $bottomLeft) {
        if (!$sea->hasShips($topRight, $bottomLeft)) {
            return 0;
        }
        if ($topRight->x == $bottomLeft->x && $topRight->y == $bottomLeft->y) {
            return 1;
        }
        $midX = intdiv($topRight->x + $bottomLeft->x, 2);
        $midY = intdiv($topRight->y + $bottomLeft->y, 2);
        return $this->countShips($sea, new Point($midX, $midY), $bottomLeft) +
               $this->countShips($sea, $topRight, new Point($midX + 1, $midY + 1)) +
               $this->countShips($sea, new Point($midX, $topRight->y), new Point($bottomLeft->x, $midY + 1)) +
               $this->countShips($sea, new Point($topRight->x, $midY), new Point($midX + 1, $bottomLeft->y));
    }
}

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

Задача: 956. Tallest Billboard
Сложность: hard

Вы устанавливаете рекламный щит и хотите, чтобы он имел наибольшую высоту. У рекламного щита будет две стальные опоры, по одной с каждой стороны. Каждая стальная опора должна быть одинаковой высоты. Вам дается набор стержней, которые можно сварить вместе. Например, если у вас есть стержни длиной 1, 2 и 3, вы можете сварить их вместе, чтобы получилась опора длиной 6. Верните наибольшую возможную высоту вашей рекламной установки. Если вы не можете установить рекламный щит, верните 0.

Пример:

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

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

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

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

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

😎 Решение:

function minDeletionSize($strs) {
    $n = count($strs);
    $m = strlen($strs[0]);
    $deleteCount = array_fill(0, $m, false);
    
    function isSorted($strs, $deleteCount) {
        $n = count($strs);
        $m = count($deleteCount);
        for ($i = 0; $i < $n - 1; $i++) {
            for ($j = 0; $j < $m; $j++) {
                if ($deleteCount[$j]) continue;
                if ($strs[$i][$j] > $strs[$i + 1][$j]) return false;
                if ($strs[$i][$j] < $strs[$i + 1][$j]) break;
            }
        }
        return true;
    }
    
    while (!isSorted($strs, $deleteCount)) {
        for ($j = 0; $j < $m; $j++) {
            if ($deleteCount[$j]) continue;
            for ($i = 0; $i < $n - 1; $i++) {
                if ($strs[$i][$j] > $strs[$i + 1][$j]) {
                    $deleteCount[$j] = true;
                    break;
                }
            }
            if ($deleteCount[$j]) break;
        }
    }
    
    return array_sum($deleteCount);
}

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

Задача: 909. Snakes and Ladders
Сложность: medium

Вам дана доска с целочисленной матрицей n x n, клетки которой помечены метками от 1 до n2 в стиле Бустрофедона, начиная с левого нижнего края доски (т.е. board[n - 1][0]) и чередуя направление в каждой строке. Вы начинаете на клетке 1 доски. В каждый ход, начиная с клетки curr, вы делаете следующее: выбираете клетку назначения next с меткой в диапазоне [curr + 1, min(curr + 6, n2)]. Этот выбор имитирует результат стандартного броска 6-гранного кубика: то есть всегда существует не более 6 мест назначения, независимо от размера доски. Если next имеет змейку или лестницу, вы должны двигаться к месту назначения этой змейки или лестницы. В противном случае вы переходите на следующий. Игра заканчивается, когда вы достигаете клетки n2. Клетка доски в строке r и столбце c имеет змейку или лестницу, если board[r][c] != -1. Местом назначения этой змейки или лестницы является доска[r][c]. В клетках 1 и n2 нет змейки или лестницы. Обратите внимание, что вы можете взять змейку или лестницу не более одного раза за ход. Если конечный пункт змейки или лестницы является началом другой змейки или лестницы, вы не ходите по последующей змейке или лестнице. Например, предположим, что доска имеет вид [[-1,4],[-1,3]], и на первом ходу ваш конечный квадрат - 2. Вы ходите по лестнице до квадрата 3, но не ходите по последующей лестнице до 4. Верните наименьшее количество ходов, необходимое для достижения квадрата n2. Если достичь квадрата невозможно, верните -1.

Пример:

Input: board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]]
Output: 4

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

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

2⃣Использовать BFS (поиск в ширину) для минимизации количества ходов до клетки n2.
В каждом ходе проверять клетки от curr + 1 до min(curr + 6, n2) и перемещаться по змейкам и лестницам, если они существуют.

3⃣Если достижение клетки n2 невозможно, вернуть -1.

😎 Решение:

function snakesAndLadders($board) {
    $n = count($board);
    
    $getPos = function($x) use ($n) {
        $quot = intdiv($x - 1, $n);
        $rem = ($x - 1) % $n;
        $row = $n - 1 - $quot;
        $col = $row % 2 != $n % 2 ? $rem : $n - 1 - $rem;
        return [$row, $col];
    };
    
    $visited = [];
    $queue = [[1, 0]];  // [current position, steps]
    
    while ($queue) {
        list($pos, $steps) = array_shift($queue);
        for ($i = 1; $i <= 6; $i++) {
            $nextPos = $pos + $i;
            if ($nextPos > $n * $n) continue;
            list($r, $c) = $getPos($nextPos);
            if ($board[$r][$c] != -1) {
                $nextPos = $board[$r][$c];
            }
            if ($nextPos == $n * $n) {
                return $steps + 1;
            }
            if (!in_array($nextPos, $visited)) {
                $visited[] = $nextPos;
                $queue[] = [$nextPos, $steps + 1];
            }
        }
    }
    return -1;
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

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

Задача: 917. Reverse Only Letters4
Сложность: easy

Задав строку s, переверните ее в соответствии со следующими правилами: все символы, не являющиеся английскими буквами, остаются в той же позиции. Все английские буквы (строчные или прописные) должны быть перевернуты. Верните s после перевертывания.

Пример:

Input: s = "ab-cd"
Output: "dc-ba"

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

1⃣Создать массив для хранения только английских букв из строки s.

2⃣Перевернуть массив с английскими буквами.
Пройти по строке s и заменить каждую английскую букву на соответствующую из перевернутого массива.

3⃣Вернуть результат.

😎 Решение:

function reverseOnlyLetters($s) {
    $letters = [];
    for ($i = 0; $i < strlen($s); $i++) {
        if (ctype_alpha($s[$i])) {
            $letters[] = $s[$i];
        }
    }
    $letters = array_reverse($letters);
    $result = '';
    $idx = 0;
    for ($i = 0; $i < strlen($s); $i++) {
        if (ctype_alpha($s[$i])) {
            $result .= $letters[$idx++];
        } else {
            $result .= $s[$i];
        }
    }
    return $result;
}

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