#medium
Задача: 237. Delete Node in a Linked List

Дан односвязный список с головой head, и требуется удалить узел node в этом списке.

Вам дан узел node, который нужно удалить. У вас нет доступа к первому узлу head.

Все значения в односвязном списке уникальны, и гарантируется, что данный узел node не является последним узлом в списке.

Удалите данный узел. Обратите внимание, что под удалением узла мы не подразумеваем его удаление из памяти. Мы имеем в виду:

- Значение данного узла не должно существовать в односвязном списке.
- Количество узлов в односвязном списке должно уменьшиться на один.
- Все значения перед узлом должны оставаться в том же порядке.
- Все значения после узла должны оставаться в том же порядке.

Пример:

Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.

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

1⃣Копирование данных: Скопируйте значение из следующего узла (node.next) в текущий узел (node). Таким образом, текущий узел будет иметь значение, которое было в следующем узле.

2⃣Обновление указателя: Обновите указатель next текущего узла, чтобы он ссылался на узел, следующий за узлом node.next. Это effectively удалит следующий узел из списка.

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

😎 Решение:

class Solution {
    function deleteNode($node) {
        $node->val = $node->next->val;
        $node->next = $node->next->next;
    }
}

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

#medium
Задача: 526. Beautiful Arrangement

Предположим, у вас есть n целых чисел, пронумерованных от 1 до n. Перестановка этих n целых чисел perm (нумерация с 1) считается красивой, если для каждого i (1 <= i <= n) выполняется одно из следующих условий:
perm[i] делится на i.
i делится на perm[i].
Дано целое число n, верните количество красивых перестановок, которые вы можете создать.

Пример:

Input: n = 2
Output: 2
Explanation: 
The first beautiful arrangement is [1,2]:
    - perm[1] = 1 is divisible by i = 1
    - perm[2] = 2 is divisible by i = 2
The second beautiful arrangement is [2,1]:
    - perm[1] = 2 is divisible by i = 1
    - i = 2 is divisible by perm[2] = 1

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

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

2⃣ Рекурсивное создание перестановок и проверка условий:
Напишите рекурсивную функцию для создания всех возможных перестановок массива, начиная с текущей позиции l.
На каждом шаге перестановки проверяйте, удовлетворяет ли текущий элемент условиям делимости. Если условие выполняется, продолжайте создание перестановок рекурсивно для следующей позиции.

3⃣ Возврат результата:
В основной функции вызовите рекурсивную функцию с начальной позицией 0 и верните значение счетчика красивых перестановок.

😎 Решение:

class Solution {
    private $count = 0;
    
    function countArrangement($N) {
        $nums = range(1, $N);
        $this->permute($nums, 0);
        return $this->count;
    }
    
    private function permute(&$nums, $l) {
        if ($l == count($nums)) {
            $this->count++;
        }
        for ($i = $l; $i < count($nums); $i++) {
            $this->swap($nums, $i, $l);
            if ($nums[$l] % ($l + 1) == 0 || ($l + 1) % $nums[$l] == 0) {
                $this->permute($nums, $l + 1);
            }
            $this->swap($nums, $i, $l);
        }
    }
    
    private function swap(&$nums, $x, $y) {
        $temp = $nums[$x];
        $nums[$x] = $nums[$y];
        $nums[$y] = $temp;
    }
}

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

#medium
Задача: 238. Product of Array Except Self

Дан массив целых чисел 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;
    }
}

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

#hard
Задача: 527. Word Abbreviation

Дано массив уникальных строк words, верните минимально возможные сокращения для каждого слова.

Правила сокращения строки следующие:
Первоначальное сокращение для каждого слова: первый символ, затем количество символов между первым и последним символом, затем последний символ.
Если более одного слова имеют одинаковое сокращение, выполните следующее:
Увеличьте префикс (символы в первой части) каждого из их сокращений на 1.
Например, начнем с слов ["abcdef", "abndef"], оба изначально сокращены как "a4f". Последовательность операций будет следующей: ["a4f", "a4f"] -> ["ab3f", "ab3f"] -> ["abc2f", "abn2f"].
Эта операция повторяется до тех пор, пока каждое сокращение не станет уникальным.
В конце, если сокращение не сделало слово короче, оставьте его в исходном виде.

Пример:

Input: words = ["like","god","internal","me","internet","interval","intension","face","intrusion"]
Output: ["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"]

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

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

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

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

😎 Решение:

class Solution {
    /**
     * @param String[] $words
     * @return String[]
     */
    function wordsAbbreviation($words) {
        $n = count($words);
        $ans = array_fill(0, $n, "");
        $prefix = array_fill(0, $n, 0);

        for ($i = 0; $i < $n; ++$i) {
            $ans[$i] = $this->abbrev($words[$i], 0);
        }

        for ($i = 0; $i < $n; ++$i) {
            while (true) {
                $dupes = [];
                for ($j = $i + 1; $j < $n; ++$j) {
                    if ($ans[$i] == $ans[$j]) {
                        $dupes[] = $j;
                    }
                }

                if (empty($dupes)) break;
                $dupes[] = $i;
                foreach ($dupes as $k) {
                    $ans[$k] = $this->abbrev($words[$k], ++$prefix[$k]);
                }
            }
        }

        return $ans;
    }

    function abbrev($word, $i) {
        $n = strlen($word);
        if ($n - $i <= 3) return $word;
        return substr($word, 0, $i + 1) . ($n - $i - 2) . substr($word, -1);
    }
}

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

#hard
Задача: 239. Sliding Window Maximum

Вам дан массив целых чисел nums. Существует скользящее окно размера k, которое перемещается с самого левого конца массива до самого правого. Вы можете видеть только k чисел в окне. Каждый раз скользящее окно перемещается вправо на одну позицию.

Верните максимальные значения скользящего окна.

Пример:

Input: nums = [1], k = 1
Output: [1]

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

1⃣Инициализация и заполнение первой части окна:
Создайте двустороннюю очередь dq для хранения индексов элементов и список res для хранения результатов.
Пройдите по первым k элементам массива nums (от i = 0 до k - 1). Для каждого элемента:
Удалите из dq все элементы, которые меньше или равны текущему элементу nums[i].
Добавьте текущий индекс i в конец dq.
Добавьте в res максимальный элемент первого окна, который находится в nums[dq[0]].

2⃣Сканирование оставшейся части массива:
Пройдите по оставшимся элементам массива nums (от i = k до n - 1). Для каждого элемента:
Если индекс элемента на передней части dq равен i - k, удалите этот элемент из dq, так как он выходит за пределы текущего окна.
Удалите из dq все элементы, которые меньше или равны текущему элементу nums[i].
Добавьте текущий индекс i в конец dq.
Добавьте в res максимальный элемент текущего окна, который находится в nums[dq[0]].

3⃣Возвращение результата:
Верните список res, содержащий максимальные элементы для каждого скользящего окна.

😎 Решение:

class Solution {
    function maxSlidingWindow($nums, $k) {
        $dq = [];
        $res = [];

        for ($i = 0; $i < $k; $i++) {
            while (!empty($dq) && $nums[$i] >= $nums[end($dq)]) {
                array_pop($dq);
            }
            $dq[] = $i;
        }
        $res[] = $nums[$dq[0]];

        for ($i = $k; $i < count($nums); $i++) {
            if ($dq[0] == $i - $k) {
                array_shift($dq);
            }
            while (!empty($dq) && $nums[$i] >= $nums[end($dq)]) {
                array_pop($dq);
            }
            $dq[] = $i;
            $res[] = $nums[$dq[0]];
        }

        return $res;
    }
}

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

#medium
Задача: 528. Random Pick with Weight

Вам дан массив положительных целых чисел w, где w[i] описывает вес индекса i.
Вам нужно реализовать функцию pickIndex(), которая случайным образом выбирает индекс в диапазоне [0, w.length - 1] (включительно) и возвращает его. Вероятность выбора индекса i равна w[i] / sum(w).

Например, если w = [1, 3], вероятность выбора индекса 0 составляет 1 / (1 + 3) = 0.25 (т.е. 25%), а вероятность выбора индекса 1 составляет 3 / (1 + 3) = 0.75 (т.е. 75%).

Пример:

Input
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
Output
[null,1,1,1,1,0]

Explanation
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // return 1. It is returning the second element (index = 1) that has a probability of 3/4.
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 0. It is returning the first element (index = 0) that has a probability of 1/4.

Since this is a randomization problem, multiple answers are allowed.
All of the following outputs can be considered correct:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
......
and so on.

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

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

2⃣ Генерация случайного числа и выбор индекса:
В функции pickIndex() сгенерируйте случайное число в диапазоне от 0 до общей суммы весов totalSum.
Используйте линейный поиск, чтобы найти первый индекс в prefixSums, который больше или равен сгенерированному числу.

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

😎 Решение:

class Solution {
    private $prefixSums;
    private $totalSum;

    /**
     * @param Integer[] $w
     */
    function __construct($w) {
        $this->prefixSums = array_fill(0, count($w), 0);
        $prefixSum = 0;
        for ($i = 0; $i < count($w); $i++) {
            $prefixSum += $w[$i];
            $this->prefixSums[$i] = $prefixSum;
        }
        $this->totalSum = $prefixSum;
    }

    /**
     * @return Integer
     */
    function pickIndex() {
        $target = $this->totalSum * (mt_rand() / mt_getrandmax());
        for ($i = 0; $i < count($this->prefixSums); $i++) {
            if ($target < $this->prefixSums[$i]) {
                return $i;
            }
        }
        return count($this->prefixSums) - 1;
    }
}

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

#medium
Задача: 538. Convert BST to Greater Tree

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

Напоминаем, что бинарное дерево поиска — это дерево, удовлетворяющее следующим условиям:

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

Пример:

Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

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

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

2⃣Посещаем текущий узел, обновляем его значение и общую сумму.

3⃣Рекурсивно обрабатываем левое поддерево.

😎 Решение:

class Solution {
    private $sum = 0;

    public function convertBST($root) {
        if ($root !== null) {
            $this->convertBST($root->right);
            $this->sum += $root->val;
            $root->val = $this->sum;
            $this->convertBST($root->left);
        }
        return $root;
    }
}

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

#easy
Задача: 530. Minimum Absolute Difference in BST

Дано корень бинарного дерева поиска (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);
    }
}

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

#medium
Задача: 540. Single Element in a Sorted Array

Дан отсортированный массив, состоящий только из целых чисел, где каждый элемент встречается ровно дважды, кроме одного элемента, который встречается ровно один раз.

Верните единственный элемент, который встречается только один раз.

Ваше решение должно работать за время O(log n) и использовать O(1) памяти.

Пример:

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

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

1⃣Начиная с первого элемента, итерируемся через каждый второй элемент, проверяя, является ли следующий элемент таким же, как текущий. Если нет, то текущий элемент — это искомый элемент.

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

3⃣Возвращаем найденный элемент.

😎 Решение:

class Solution {
    function singleNonDuplicate($nums) {
        for ($i = 0; $i < count($nums) - 1; $i += 2) {
            if ($nums[$i] != $nums[$i + 1]) {
                return $nums[$i];
            }
        }
        return $nums[count($nums) - 1];
    }
}

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

#easy
Задача: 541. Reverse String II

Дана строка s и целое число k, переверните первые k символов для каждых 2k символов, начиная с начала строки.

Если осталось меньше k символов, переверните все. Если осталось меньше 2k, но больше или равно k символов, переверните первые k символов и оставьте остальные как есть.

Пример:

Input: s = "abcdefg", k = 2
Output: "bacdfeg"

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

1⃣Разворачиваем каждый блок из 2k символов непосредственно. Каждый блок начинается с кратного 2k: например, 0, 2k, 4k, 6k и так далее.

2⃣Будьте внимательны, если символов недостаточно, блок может не быть перевернут.

3⃣Для разворота блока символов с позиции i до j, меняем местами символы на позициях i++ и j--.

😎 Решение:

class Solution {
    function reverseStr($s, $k) {
        $a = str_split($s);
        for ($start = 0; $start < count($a); $start += 2 * $k) {
            $i = $start;
            $j = min($start + $k - 1, count($a) - 1);
            while ($i < $j) {
                $tmp = $a[$i];
                $a[$i++] = $a[$j];
                $a[$j--] = $tmp;
            }
        }
        return implode('', $a);
    }
}

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

#medium
Задача: 531. Lonely Pixel I

Дано изображение размером m x n, состоящее из чёрных ('B') и белых ('W') пикселей. Верните количество чёрных одиночных пикселей.

Чёрный одиночный пиксель — это символ 'B', расположенный в такой позиции, где в той же строке и в том же столбце нет других чёрных пикселей.

Пример:

Input: picture = [["W","W","B"],["W","B","W"],["B","W","W"]]
Output: 3
Explanation: All the three 'B's are black lonely pixels.

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

1⃣ Подсчёт количества чёрных пикселей в строках и столбцах:
Пройдите по всей матрице picture, для каждой чёрной клетки (x, y) увеличивайте rowCount[x] и colCount[y] на 1.

2⃣ Поиск одиночных чёрных пикселей:
Снова пройдите по всей матрице и для каждой чёрной клетки (x, y) проверьте значения rowCount[x] и colCount[y]. Если оба значения равны 1, увеличьте переменную answer на 1.

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

😎 Решение:

class Solution {
    function findLonelyPixel($picture) {
        $n = count($picture);
        $m = count($picture[0]);
        
        $rowCount = array_fill(0, $n, 0);
        $columnCount = array_fill(0, $m, 0);
        
        for ($i = 0; $i < $n; $i++) {
            for ($j = 0; $j < $m; $j++) {
                if ($picture[$i][$j] == 'B') {
                    $rowCount[$i]++;
                    $columnCount[$j]++;
                }
            }
        }
        
        $answer = 0;
        for ($i = 0; $i < $n; $i++) {
            for ($j = 0; $j < $m; $j++) {
                if ($picture[$i][$j] == 'B' && $rowCount[$i] == 1 && $columnCount[$j] == 1) {
                    $answer++;
                }
            }
        }
        
        return $answer;
    }
}

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

#medium
Задача: 532. K-diff Pairs in an Array

Дан массив целых чисел nums и целое число k. Верните количество уникальных пар с разницей k в массиве.

Пара с разницей k — это пара целых чисел (nums[i], nums[j]), для которой выполняются следующие условия:
0 <= i, j < nums.length
i != j
|nums[i] - nums[j]| == k
Обратите внимание, что |val| обозначает абсолютное значение val.

Пример:

Input: nums = [3,1,4,1,5], k = 2
Output: 2
Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
Although we have two 1s in the input, we should only return the number of unique pairs.

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

1⃣ Создайте частотный хэш-словарь для подсчета количества каждого уникального числа в массиве nums.

2⃣ Для каждого ключа в хэш-словаре проверьте, можно ли найти пару, удовлетворяющую условиям:
Если k > 0, проверьте, существует ли ключ, равный x + k.
Если k == 0, проверьте, есть ли более одного вхождения x.

3⃣ Увеличьте счётчик результатов, если условие выполняется.

😎 Решение:

class Solution {
    function findPairs($nums, $k) {
        $counter = [];
        foreach ($nums as $num) {
            if (!isset($counter[$num])) {
                $counter[$num] = 0;
            }
            $counter[$num]++;
        }
        
        $result = 0;
        foreach ($counter as $x => $val) {
            if ($k > 0) {
                if (isset($counter[$x + $k])) {
                    $result++;
                }
            } else if ($k == 0 && $val > 1) {
                $result++;
            }
        }
        
        return $result;
    }
}

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

#hard
Задача: 302. Smallest Rectangle Enclosing Black Pixels

Вам дана бинарная матрица размером m x n, где 0 представляет собой белый пиксель, а 1 представляет собой черный пиксель.
Черные пиксели соединены (то есть существует только одна черная область). Пиксели соединены по горизонтали и вертикали.
Даны два целых числа x и y, которые представляют местоположение одного из черных пикселей. Верните площадь наименьшего (выравненного по осям) прямоугольника, который охватывает все черные пиксели.
Вы должны написать алгоритм со сложностью менее O(mn).

Пример:

Input: image = [["0","0","1","0"],["0","1","1","0"],["0","1","0","0"]], x = 0, y = 2
Output: 6

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

1⃣Инициализация границ прямоугольника: Инициализируйте переменные left, right, top и bottom. left и top задаются значениями координат (x, y), right и bottom - значениями x + 1 и y + 1 соответственно.

2⃣Обход всех пикселей: Пройдите по всем координатам (x, y) матрицы. Если текущий пиксель является черным (image[x][y] == 1), обновите границы прямоугольника:
left = min(left, x)
right = max(right, x + 1)
top = min(top, y)
bottom = max(bottom, y + 1)

3⃣Вычисление и возврат площади: После завершения обхода матрицы, верните площадь прямоугольника, используя формулу (right - left) * (bottom - top).

😎 Решение:

class Solution {
    function minArea($image, $x, $y) {
        $m = count($image);
        $n = count($image[0]);
        $left = $this->searchColumns($image, 0, $y, 0, $m, true);
        $right = $this->searchColumns($image, $y + 1, $n, 0, $m, false);
        $top = $this->searchRows($image, 0, $x, $left, $right, true);
        $bottom = $this->searchRows($image, $x + 1, $m, $left, $right, false);
        return ($right - $left) * ($bottom - $top);
    }

    private function searchColumns($image, $i, $j, $top, $bottom, $opt) {
        while ($i != $j) {
            $k = (int)(($i + $j) / 2);
            $t = $top;
            while ($t < $bottom && $image[$t][$k] == '0') $t++;
            if (($t < $bottom) == $opt) {
                $j = $k;
            } else {
                $i = $k + 1;
            }
        }
        return $i;
    }

    private function searchRows($image, $i, $j, $left, $right, $opt) {
        while ($i != $j) {
            $k = (int)(($i + $j) / 2);
            $l = $left;
            while ($l < $right && $image[$k][$l] == '0') $l++;
            if (($l < $right) == $opt) {
                $j = $k;
            } else {
                $i = $k + 1;
            }
        }
        return $i;
    }
}

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

#medium
Задача: 535. Encode and Decode TinyURL

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

Реализуйте класс Solution:
Solution() Инициализирует объект системы.
String encode(String longUrl) Возвращает короткий URL для данного longUrl.
String decode(String shortUrl) Возвращает исходный длинный URL для данного shortUrl. Гарантируется, что данный shortUrl был закодирован тем же объектом.

Пример:

Input: url = "https://leetcode.com/problems/design-tinyurl"
Output: "https://leetcode.com/problems/design-tinyurl"

Explanation:
Solution obj = new Solution();
string tiny = obj.encode(url); // returns the encoded tiny url.
string ans = obj.decode(tiny); // returns the original url after decoding it.

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

1⃣ Инициализация:
Создайте строку, содержащую все возможные символы (цифры и буквы), которые могут быть использованы для генерации кода.
Создайте хэш-таблицу для хранения соответствий коротких и длинных URL-адресов.
Создайте объект для генерации случайных чисел.

2⃣ Кодирование:
Сгенерируйте случайный 6-символьный код.
Если такой код уже существует в хэш-таблице, повторите генерацию.
Сохраните соответствие длинного URL и сгенерированного кода в хэш-таблице.
Верните полный короткий URL.

3⃣ Декодирование:
Удалите префикс короткого URL, чтобы получить код.
Используйте код для поиска длинного URL в хэш-таблице.
Верните длинный URL.

😎 Решение:

class Codec {
    private $alphabet = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ';
    private $map = [];

    private function getRand() {
        $result = '';
        for ($i = 0; $i < 6; $i++) {
            $result .= $this->alphabet[random_int(0, 61)];
        }
        return $result;
    }

    public function encode($longUrl) {
        $key = $this->getRand();
        while (array_key_exists($key, $this->map)) {
            $key = $this->getRand();
        }
        $this->map[$key] = $longUrl;
        return 'https://tinyurl.com/' . $key;
    }

    public function decode($shortUrl) {
        $key = str_replace('https://tinyurl.com/', '', $shortUrl);
        return $this->map[$key];
    }
}

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

#medium
Задача: 536. Construct Binary Tree from String

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

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

Вы всегда начинаете строить левый дочерний узел родителя сначала, если он существует.

Пример:

Input: s = "4(2(3)(1))(6(5))"
Output: [4,2,6,3,1,5]

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

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

2⃣ Построение поддерева:
Определите рекурсивную функцию str2treeInternal, которая принимает строку и текущий индекс в качестве входных данных и возвращает пару: узел TreeNode и следующий индекс для обработки.
Внутри функции извлеките значение для корневого узла текущего поддерева, создайте узел, а затем рекурсивно постройте левое и правое поддеревья, если они существуют.

3⃣ Основная функция:
Определите основную функцию str2tree, которая вызывает рекурсивную функцию str2treeInternal и возвращает построенное дерево.

😎 Решение:

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 str2tree($s) {
        list($root, $_) = $this->str2treeInternal($s, 0);
        return $root;
    }

    private function getNumber($s, $index) {
        $isNegative = false;
        if ($s[$index] == '-') {
            $isNegative = true;
            $index++;
        }
        $number = 0;
        while ($index < strlen($s) && is_numeric($s[$index])) {
            $number = $number * 10 + intval($s[$index]);
            $index++;
        }
        return [$isNegative ? -$number : $number, $index];
    }

    private function str2treeInternal($s, $index) {
        if ($index == strlen($s)) return [null, $index];

        list($value, $newIndex) = $this->getNumber($s, $index);
        $node = new TreeNode($value);

        if ($newIndex < strlen($s) && $s[$newIndex] == '(') {
            list($node->left, $newIndex) = $this->str2treeInternal($s, $newIndex + 1);
        }

        if ($newIndex < strlen($s) && $s[$newIndex] == '(') {
            list($node->right, $newIndex) = $this->str2treeInternal($s, $newIndex + 1);
        }

        if ($newIndex < strlen($s) && $s[$newIndex] == ')') {
            $newIndex++;
        }

        return [$node, $newIndex];
    }
}

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

#easy
Задача: 303. Range Sum Query - Immutable

Дан целочисленный массив nums. Обработайте несколько запросов следующего типа:
Вычислите сумму элементов массива nums между индексами left и right включительно, где left <= right.
Реализуйте класс NumArray:
- NumArray(int[] nums) Инициализирует объект с целочисленным массивом nums.
- int sumRange(int left, int right) Возвращает сумму элементов массива nums между индексами left и right включительно (т.е. nums[left] + nums[left + 1] + ... + nums[right]).

Пример:

Input
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
Output
[null, 1, -1, -3]

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

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

2⃣Предварительное вычисление сумм:
Заполните массив sum, где каждый элемент sum[i + 1] является суммой всех предыдущих элементов массива nums до индекса i включительно.

3⃣Вычисление диапазонной суммы:
Для каждого запроса суммы элементов между индексами left и right используйте разницу между sum[right + 1] и sum[left], чтобы быстро получить результат.

😎 Решение:

class NumArray {
    private $sum;

    function __construct($nums) {
        $this->sum = array_fill(0, count($nums) + 1, 0);
        for ($i = 0; $i < count($nums); $i++) {
            $this->sum[$i + 1] = $this->sum[$i] + $nums[$i];
        }
    }

    function sumRange($i, $j) {
        return $this->sum[$j + 1] - $this->sum[$i];
    }
}

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

#medium
Задача: 537. Complex Number Multiplication

Комплексное число можно представить в виде строки в формате "real+imaginaryi", где:
real — это действительная часть и является целым числом в диапазоне [-100, 100].
imaginary — это мнимая часть и является целым числом в диапазоне [-100, 100].
i^2 == -1.
Даны два комплексных числа num1 и num2 в виде строк, верните строку комплексного числа, представляющую их произведение.

Пример:

Input: num1 = "1+1i", num2 = "1+1i"
Output: "0+2i"
Explanation: (1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i, and you need convert it to the form of 0+2i.

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

1⃣ Извлечение реальной и мнимой частей:
Разделите строки a и b на реальные и мнимые части, используя символы '+' и 'i'.

2⃣ Вычисление произведения:
Переведите извлечённые части в целые числа.
Используйте формулу для умножения комплексных чисел: (a+ib)×(x+iy)=ax−by+i(bx+ay).

3⃣ Формирование строки результата:
Создайте строку в требуемом формате с реальной и мнимой частями произведения и верните её.

😎 Решение:

class Solution {
    function complexNumberMultiply($a, $b) {
        list($a_real, $a_img) = explode('+', str_replace('i', '', $a));
        list($b_real, $b_img) = explode('+', str_replace('i', '', $b));
        $realPart = $a_real * $b_real - $a_img * $b_img;
        $imaginaryPart = $a_real * $b_img + $a_img * $b_real;
        return $realPart . "+" . $imaginaryPart . "i";
    }
}

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

#medium
Задача: 583. Delete Operation for Two Strings

Даны две строки word1 и word2, вернуть минимальное количество шагов, необходимых для того, чтобы сделать word1 и word2 одинаковыми.

На одном шаге можно удалить ровно один символ в любой строке.

Пример:

Input: word1 = "sea", word2 = "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

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

1⃣ Инициализация массива:
Создайте одномерный массив dp для хранения минимального количества удалений, необходимых для уравнивания строк word1 и word2.

2⃣ Заполнение массива:
Используйте временный массив temp для обновления значений dp, представляющих текущую строку. Обновите temp с использованием значений dp предыдущей строки.

3⃣ Обновление и результат:
Скопируйте временный массив temp обратно в dp после обработки каждой строки. В конце верните значение из dp, представляющее минимальное количество удалений.

😎 Решение:

class Solution {
    function minDistance($word1, $word2) {
        $m = strlen($word1);
        $n = strlen($word2);
        $dp = array_fill(0, $n + 1, 0);

        for ($i = 0; $i <= $m; $i++) {
            $temp = array_fill(0, $n + 1, 0);
            for ($j = 0; $j <= $n; $j++) {
                if ($i == 0 || $j == 0) {
                    $temp[$j] = $i + $j;
                } else if ($word1[$i - 1] == $word2[$j - 1]) {
                    $temp[$j] = $dp[$j - 1];
                } else {
                    $temp[$j] = 1 + min($dp[$j], $temp[$j - 1]);
                }
            }
            $dp = $temp;
        }

        return $dp[$n];
    }
}

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

#hard
Задача: 587. Erect the Fence

Вам дан массив 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);
    }
}

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

#medium
Задача: 304. Range Sum Query 2D - Immutable

Дана двумерная матрица matrix. Обработайте несколько запросов следующего типа:
Вычислите сумму элементов матрицы внутри прямоугольника, определенного его верхним левым углом (row1, col1) и нижним правым углом (row2, col2).
Реализуйте класс NumMatrix:
- NumMatrix(int[][] matrix) Инициализирует объект целочисленной матрицей matrix.- int sumRegion(int row1, int col1, int row2, int col2) Возвращает сумму элементов матрицы внутри прямоугольника, определенного его верхним левым углом (row1, col1) и нижним правым углом (row2, col2).
Необходимо разработать алгоритм, где метод sumRegion работает за O(1) по времени.

Пример:

Input
["NumMatrix", "sumRegion", "sumRegion", "sumRegion"]
[[[[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]], [2, 1, 4, 3], [1, 1, 2, 2], [1, 2, 2, 4]]

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

1⃣Инициализация:
Создайте двумерный массив sums размером (m + 1) x (n + 1), где m и n — размеры исходной матрицы matrix. Заполните этот массив нулями.

2⃣Предварительное вычисление сумм:
Заполните массив sums, где каждый элемент sums[i][j] будет содержать сумму всех элементов матрицы от начала до позиции (i-1, j-1) включительно.

3⃣Вычисление диапазонной суммы:
Для каждого запроса суммы элементов внутри прямоугольника, определенного его углами (row1, col1) и (row2, col2), используйте предварительно вычисленный массив sums для получения результата за O(1) времени.

😎 Решение:

class NumMatrix {
    private $dp;

    function __construct($matrix) {
        if (count($matrix) == 0 || count($matrix[0]) == 0) return;
        $m = count($matrix);
        $n = count($matrix[0]);
        $this->dp = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));
        for ($r = 0; $r < $m; $r++) {
            for ($c = 0; $c < $n; $c++) {
                $this->dp[$r + 1][$c + 1] = $this->dp[$r + 1][$c] + $this->dp[$r][$c + 1] + $matrix[$r][$c] - $this->dp[$

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