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

Вам дан диапазон [lower, upper] и отсортированный массив уникальных целых чисел nums, где все элементы находятся в этом диапазоне.
Число x считается пропущенным, если оно находится в диапазоне [lower, upper] и его нет в массиве nums.
Верните кратчайший отсортированный список диапазонов, который точно покрывает все пропущенные числа. То есть ни один элемент из nums не включен в какой-либо из диапазонов, и каждое пропущенное число покрыто одним из диапазонов..

Пример:

Input: nums = [-1], lower = -1, upper = -1
Output: []
Explanation: There are no missing ranges since there are no missing numbers.

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

1⃣Инициализация и проверка начальных условий:
Создайте переменную n и инициализируйте её размером массива nums.
Создайте список missingRanges, который будет содержать решение задачи.
Если массив nums пуст, верните диапазон [lower, upper].
Проверьте, совпадает ли первый элемент массива с lower. Если lower < nums[0], добавьте в missingRanges диапазон [lower, nums[0] - 1].

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

3⃣Проверка и добавление последнего пропущенного диапазона:
Проверьте, совпадает ли последний элемент массива с upper. Если nums[n - 1] < upper, добавьте в missingRanges диапазон [nums[n - 1] + 1, upper].

😎 Решение:

class Solution {
    function findMissingRanges($nums, $lower, $upper) {
        $n = count($nums);
        $missingRanges = [];
        
        if ($n == 0) {
            array_push($missingRanges, [$lower, $upper]);
            return $missingRanges;
        }
        if ($lower < $nums[0]) {
            array_push($missingRanges, [$lower, $nums[0] - 1]);
        }
        for ($i = 0; $i < $n - 1; $i++) {
            if ($nums[$i + 1] - $nums[$i] > 1) {
                array_push($missingRanges, [$nums[$i] + 1, $nums[$i + 1] - 1]);
            }
        }
        if ($upper > $nums[$n - 1]) {
            array_push($missingRanges, [$nums[$n - 1] + 1, $upper]);
        }
        
        return $missingRanges;
    }
}

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

Задача: 527. Word Abbreviation
Сложность: hard

Дано массив уникальных строк 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);
    }
}

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

Задача: 972. Equal Rational Numbers
Сложность: hard

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

Рациональное число может быть представлено с использованием до трех частей: <ЦелаяЧасть>, <НеповторяющаясяЧасть> и <ПовторяющаясяЧасть>. Число будет представлено одним из следующих трех способов:

<ЦелаяЧасть>
Например, 12, 0 и 123.
<ЦелаяЧасть><.><НеповторяющаясяЧасть>
Например, 0.5, 1., 2.12 и 123.0001.
<ЦелаяЧасть><.><НеповторяющаясяЧасть><(><ПовторяющаясяЧасть><)>
Например, 0.1(6), 1.(9), 123.00(1212).
Повторяющаяся часть десятичного разложения обозначается в круглых скобках. Например:

1/6 = 0.16666666... = 0.1(6) = 0.1666(6) = 0.166(66).

Пример:

Input: s = "0.(52)", t = "0.5(25)"
Output: true
Explanation: Because "0.(52)" represents 0.52525252..., and "0.5(25)" represents 0.52525252525..... , the strings represent the same number.

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

1⃣Преобразование дроби. Определите и изолируйте повторяющуюся часть дроби. Преобразуйте строку, представляющую число, в выражение вида S=x/(10^k-1), где x — повторяющаяся часть, а k — её длина.

2⃣Вычисление геометрической суммы. Преобразуйте повторяющуюся часть в сумму вида S=x*(r/(1-r)), где r = 10^(-k). Найдите значение дроби для повторяющейся части, используя формулу геометрической прогрессии.

3⃣Обработка неповторяющейся части. Определите значение неповторяющейся части дроби как обычное число. Объедините результаты для повторяющейся и неповторяющейся частей для получения итогового значения.

😎 Решение:

class Solution {
    function isRationalEqual($S, $T) {
        $f1 = $this->convert($S);
        $f2 = $this->convert($T);
        return $f1->n == $f2->n && $f1->d == $f2->d;
    }

    function convert($S) {
        $state = 0;
        $ans = new Fraction(0, 1);
        $decimal_size = 0;

        $parts = preg_split('/[.()]/', $S);

        foreach ($parts as $part) {
            $state++;
            if ($part === "") continue;
            $x = intval($part);
            $sz = strlen($part);

            if ($state == 1) {
                $ans->iadd(new Fraction($x, 1));
            } elseif ($state == 2) {
                $ans->iadd(new Fraction($x, pow(10, $sz)));
                $decimal_size = $sz;
            } else {
                $denom = pow(10, $decimal_size);
                $denom *= pow(10, $sz) - 1;
                $ans->iadd(new Fraction($x, $denom));
            }
        }
        return $ans;
    }
}

class Fraction {
    public $n, $d;

    function __construct($n, $d) {
        $g = $this->gcd($n, $d);
        $this->n = $n / $g;
        $this->d = $d / $g;
    }

    function iadd($other) {
        $numerator = $this->n * $other->d + $this->d * $other->n;
        $denominator = $this->d * $other->d;
        $g = $this->gcd($numerator, $denominator);
        $this->n = $numerator / $g;
        $this->d = $denominator / $g;
    }

    function gcd($x, $y) {
        return $x != 0 ? $this->gcd($y % $x, $x) : $y;
    }
}

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

Задача: 414. Third Maximum Number
Сложность: easy

Если задан целочисленный массив nums, верните третье максимальное число в этом массиве. Если третьего максимального числа не существует, верните максимальное число.

Пример:

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

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

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

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

3⃣Если третье максимальное число существует, верните его. В противном случае, верните первое максимальное число.

😎 Решение:

function thirdMax($nums) {
    $first = null;
    $second = null;
    $third = null;
    
    foreach ($nums as $num) {
        if ($num === $first || $num === $second || $num === $third) {
            continue;
        }
        if ($first === null || $num > $first) {
            $third = $second;
            $second = $first;
            $first = $num;
        } elseif ($second === null || $num > $second) {
            $third = $second;
            $second = $num;
        } elseif ($third === null || $num > $third) {
            $third = $num;
        }
    }
    
    return $third !== null ? $third : $first;
}

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

Задача: 226. Invert Binary Tree
Сложность: easy

Дан корень бинарного дерева, инвертируйте дерево и верните его корень.

Пример:

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

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

1⃣Рекурсивная инверсия поддеревьев:
Если текущий узел (root) пустой, возвращаем null.
Рекурсивно инвертируем правое поддерево и сохраняем результат в переменную right.
Рекурсивно инвертируем левое поддерево и сохраняем результат в переменную left.

2⃣Обмен поддеревьев:
Устанавливаем левое поддерево текущего узла равным правому поддереву.
Устанавливаем правое поддерево текущего узла равным левому поддереву.

3⃣Возврат корня:
Возвращаем текущий узел (root) как новый корень инвертированного дерева.

😎 Решение:

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

class Solution {
    public function invertTree($root) {
        if ($root === null) {
            return null;
        }
        $right = $this->invertTree($root->right);
        $left = $this->invertTree($root->left);
        $root->left = $right;
        $root->right = $left;
        return $root;
    }
}

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

Задача №18. 4Sum
Сложность: medium

Учитывая массив nums из n целых чисел, верните массив всех уникальных четверок [nums[a], nums[b], nums[c], nums[d]] таких, что:
- 0 <= a, b, c, d < n,
- a, b, c и d различны,
- nums[a] + nums[b] + nums[c] + nums[d] == target.
Вы можете вернуть ответ в любом порядке.

Пример:

Input: nums = [1,0,-1,0,-2,2], target = 0  
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

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

1⃣Отсортировать массив для удобного поиска.

2⃣Использовать рекурсивную функцию kSum для поиска всех k-элементных комбинаций.

3⃣Для k = 2 использовать метод двух указателей twoSum.

😎 Решение:

class Solution { 
 
    function fourSum($nums, $target) { 
        sort($nums); 
        return $this->kSum($nums, $target, 4); 
    } 
 
    function kSum($nums, $target, $k) { 
        $res = []; 
 
        if (!count($nums)) { 
            return $res; 
        } 
 
        $averageValue = $target / $k; 
        if ($averageValue < $nums[0] || $nums[count($nums)-1] < $averageValue) { 
            return $res; 
        } 
 
        if ($k == 2) { 
            return $this->twoSum($nums, $target); 
        } 
 
        for ($i = 0; $i < count($nums); $i++) { 
            if ($i == 0 || $nums[$i - 1] != $nums[$i]) { 
                $kSum = $this->kSum(array_slice($nums, $i+1), $target - $nums[$i], $k - 1); 
                foreach ($kSum as $item) { 
                    $res[] = array_merge([$nums[$i]], $item); 
                } 
            } 
        } 
        return $res; 
    } 
 
    function twoSum($nums, $target) { 
        $res = []; 
        $lo = 0; 
        $hi = count($nums) - 1; 
 
        while ($lo < $hi) { 
            $currSum = $nums[$lo] + $nums[$hi]; 
            if ($currSum < $target || ($lo > 0 && $nums[$lo] == $nums[$lo - 1])) { 
                $lo++; 
            } elseif ($currSum > $target || ($hi < count($nums) - 1 && $nums[$hi] == $nums[$hi + 1])) { 
                $hi--; 
            } else { 
                $res[] = [$nums[$lo], $nums[$hi]]; 
                $lo++; 
                $hi--; 
            } 
        } 
        return $res; 
    } 
}

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

Задача: 591. Tag Validator
Сложность: hard

Дана строка, представляющая фрагмент кода, реализуйте валидатор тегов для разбора кода и определения его корректности.
Фрагмент кода считается корректным, если соблюдаются все следующие правила:
Код должен быть заключен в корректный закрытый тег. В противном случае код некорректен.
Закрытый тег (не обязательно корректный) имеет точно следующий формат: <TAG_NAME>TAG_CONTENT</TAG_NAME>. Среди них <TAG_NAME> — это начальный тег, а </TAG_NAME> — конечный тег. TAG_NAME в начальном и конечном тегах должен быть одинаковым. Закрытый тег корректен, если и только если TAG_NAME и TAG_CONTENT корректны.
Корректное TAG_NAME содержит только заглавные буквы и имеет длину в диапазоне [1, 9]. В противном случае TAG_NAME некорректен.
Корректное TAG_CONTENT может содержать другие корректные закрытые теги, cdata и любые символы (см. примечание 1), КРОМЕ неподходящих <, неподходящих начальных и конечных тегов, и неподходящих или закрытых тегов с некорректным TAG_NAME. В противном случае TAG_CONTENT некорректен.
Начальный тег неподходящий, если нет конечного тега с тем же TAG_NAME, и наоборот. Однако нужно также учитывать проблему несбалансированных тегов, когда они вложены.
< неподходящий, если не удается найти последующий >. И когда вы находите < или </, все последующие символы до следующего > должны быть разобраны как TAG_NAME (не обязательно корректный).
cdata имеет следующий формат: <![CDATA[CDATA_CONTENT]]>. Диапазон CDATA_CONTENT определяется как символы между <![CDATA[ и первым последующим ]]>.
CDATA_CONTENT может содержать любые символы. Функция cdata заключается в том, чтобы запретить валидатору разбирать CDATA_CONTENT, поэтому даже если в нем есть символы, которые могут быть разобраны как тег (корректный или некорректный), вы должны рассматривать их как обычные символы.

Пример:

Input: code = "<DIV>This is the first line <![CDATA[<div>]]></DIV>"
Output: true

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

1⃣Инициализируйте стек для отслеживания открытых тегов и флаг для определения наличия тегов. Используйте регулярное выражение для проверки корректности TAG_NAME, TAG_CONTENT и CDATA.

2⃣Пройдитесь по строке, проверяя каждый символ. Если встретите <, определите тип тега (начальный, конечный или CDATA). Обновите стек и индексы в зависимости от найденного типа.

3⃣В конце проверьте, что стек пуст (все теги корректно закрыты) и верните результат.

😎 Решение:

class Solution {
    private $stack = [];
    private $containsTag = false;

    private function isValidTagName($s, $ending) {
        if ($ending) {
            if (!empty($this->stack) && end($this->stack) === $s) {
                array_pop($this->stack);
            } else {
                return false;
            }
        } else {
            $this->containsTag = true;
            $this->stack[] = $s;
        }
        return true;
    }

    public function isValid($code) {
        $regex = "/<[A-Z]{0,9}>([^<]*(<((\/?[A-Z]{1,9}>)|(!\[CDATA\[.*?\]\]>)))?)*/";
        if (!preg_match($regex, $code)) {
            return false;
        }

        $i = 0;
        while ($i < strlen($code)) {
            $ending = false;
            if (empty($this->stack) && $this->containsTag) {
                return false;
            }
            if ($code[$i] === '<') {
                if ($code[$i + 1] === '!') {
                    $i = strpos($code, "]]>", $i + 1);
                    if ($i === false) {
                        return false;
                    }
                    continue;
                }
                if ($code[$i + 1] === '/') {
                    $i++;
                    $ending = true;
                }
                $closeIndex = strpos($code, '>', $i + 1);
                if ($closeIndex === false || !$this->isValidTagName(substr($code, $i + 1, $closeIndex - $i - 1), $ending)) {
                    return false;
                }
                $i = $closeIndex;
            }
            $i++;
        }
        return empty($this->stack);
    }
}

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

Задача: 851. Loud and Rich
Сложность: medium

Есть группа из n человек, пронумерованных от 0 до n - 1, где у каждого человека разное количество денег и разный уровень спокойствия.

Вам дан массив richer, где richer[i] = [ai, bi] указывает на то, что ai имеет больше денег, чем bi, и целочисленный массив quiet, где quiet[i] — это уровень спокойствия i-го человека. Все данные в richer логически корректны (т.е. данные не приведут к ситуации, где x богаче y и y богаче x одновременно).

Верните целочисленный массив answer, где answer[x] = y, если y — это самый спокойный человек (то есть человек y с наименьшим значением quiet[y]) среди всех людей, которые однозначно имеют столько же или больше денег, чем человек x.

Пример:

Input: richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1,7,0]
Output: [5,5,2,5,4,5,6,7]
Explanation: 
answer[0] = 5.
Person 5 has more money than 3, which has more money than 1, which has more money than 0.
The only person who is quieter (has lower quiet[x]) is person 7, but it is not clear if they have more money than person 0.
answer[7] = 7.
Among all people that definitely have equal to or more money than person 7 (which could be persons 3, 4, 5, 6, or 7), the person who is the quietest (has lower quiet[x]) is person 7.
The other answers can be filled out with similar reasoning.

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

1⃣Постройте граф, описанный выше, и пусть dfs(person) будет самым спокойным человеком в поддереве person. Обратите внимание, что из-за логической последовательности утверждений граф должен быть DAG — ориентированным графом без циклов.

2⃣Теперь dfs(person) — это либо сам person, либо min(dfs(child) для каждого child из person). То есть, самый спокойный человек в поддереве — это либо сам person, либо самый спокойный человек в каком-то поддереве потомка person.

3⃣Мы можем кэшировать значения dfs(person) в answer[person], выполняя обход графа в пост-обходе. Таким образом, мы не повторяем работу. Этот метод уменьшает квадратичное время выполнения алгоритма до линейного.

😎 Решение:

class Solution {
    private $graph;
    private $answer;
    private $quiet;

    function loudAndRich($richer, $quiet) {
        $N = count($quiet);
        $this->graph = array_fill(0, $N, []);
        $this->answer = array_fill(0, $N, -1);
        $this->quiet = $quiet;

        foreach ($richer as $edge) {
            $this->graph[$edge[1]][] = $edge[0];
        }

        for ($node = 0; $node < $N; ++$node) {
            $this->dfs($node);
        }

        return $this->answer;
    }

    function dfs($node) {
        if ($this->answer[$node] == -1) {
            $this->answer[$node] = $node;
            foreach ($this->graph[$node] as $child) {
                $cand = $this->dfs($child);
                if ($this->quiet[$cand] < $this->quiet[$this->answer[$node]]) {
                    $this->answer[$node] = $cand;
                }
            }
        }
        return $this->answer[$node];
    }
}

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

Задача: 1182. Shortest Distance to Target Color
Сложность: medium

Дан массив colors, содержащий три цвета: 1, 2 и 3.

Также даны несколько запросов. Каждый запрос состоит из двух целых чисел i и c. Верните наименьшее расстояние между заданным индексом i и целевым цветом c. Если решения нет, верните -1.

Пример:

Input: colors = [1,1,2,1,3,2,2,3,3], queries = [[1,3],[2,2],[6,1]]
Output: [3,0,3]
Explanation: 
The nearest 3 from index 1 is at index 4 (3 steps away).
The nearest 2 from index 2 is at index 2 itself (0 steps away).
The nearest 1 from index 6 is at index 3 (3 steps away).

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

1⃣Инициализируйте хэш-таблицу для отображения каждого цвета в список индексов. Итерируйте по массиву colors и добавляйте каждый индекс в соответствующий список хэш-таблицы.

2⃣Для каждого запроса, содержащего i и c, если c не является одним из ключей в хэш-таблице, то colors не содержит c, поэтому верните -1. Иначе, найдите позицию i в соответствующем списке индексов indexList для поддержания упорядоченного порядка.

3⃣Если i меньше всех элементов в indexList, то i - indexList[0] является кратчайшим расстоянием. Если i больше всех элементов в indexList, то indexList[indexList.size() - 1] - i является кратчайшим расстоянием. Иначе, ближайшее появление c к i либо на индексе вставки, либо перед ним, поэтому рассчитайте расстояние от i до каждого из них и верните наименьшее.

😎 Решение:

class Solution {
    function shortestDistanceColor($colors, $queries) {
        $queryResults = [];
        $hashmap = [];

        foreach ($colors as $i => $color) {
            if (!isset($hashmap[$color])) {
                $hashmap[$color] = [];
            }
            $hashmap[$color][] = $i;
        }

        foreach ($queries as $query) {
            list($target, $color) = $query;
            if (!isset($hashmap[$color])) {
                $queryResults[] = -1;
                continue;
            }

            $indexList = $hashmap[$color];
            $insert = $this->binarySearch($indexList, $target);

            if ($insert < 0) {
                $insert = -$insert - 1;
            }

            if ($insert == 0) {
                $queryResults[] = $indexList[$insert] - $target;
            } elseif ($insert == count($indexList)) {
                $queryResults[] = $target - $indexList[$insert - 1];
            } else {
                $leftNearest = $target - $indexList[$insert - 1];
                $rightNearest = $indexList[$insert] - $target;
                $queryResults[] = min($leftNearest, $rightNearest);
            }
        }
        return $queryResults;
    }

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

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

Задача: 1014. Best Sightseeing Pair
Сложность: medium

Вам дан целочисленный массив values, в котором values[i] представляет собой значение i-й достопримечательности. Две достопримечательности i и j имеют расстояние j - i между собой. Оценка пары (i < j) достопримечательностей равна values[i] + values[j] + i - j: сумма значений достопримечательностей минус расстояние между ними. Возвращается максимальная оценка пары достопримечательностей.

Пример:

Input: values = [8,1,5,2,6]
Output: 11

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

1⃣Инициализация переменных:
Инициализируйте переменную max_score для хранения максимальной оценки пары.
Инициализируйте переменную max_i_plus_value для хранения максимального значения выражения values[i] + i при проходе по массиву.

2⃣Проход по массиву:
Пройдитесь по массиву начиная с первого элемента и для каждого элемента values[j] вычислите текущую оценку пары как values[j] - j + max_i_plus_value.
Обновите значение max_score, если текущая оценка больше.
Обновите значение max_i_plus_value, если текущий элемент values[j] + j больше предыдущего max_i_plus_value.

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

😎 Решение:

class Solution {
    function maxScoreSightseeingPair($values) {
        $maxScore = 0;
        $maxIPlusValue = $values[0];
        
        for ($j = 1; $j < count($values); $j++) {
            $maxScore = max($maxScore, $maxIPlusValue + $values[$j] - $j);
            $maxIPlusValue = max($maxIPlusValue, $values[$j] + $j);
        }
        
        return $maxScore;
    }
}

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

Задача: 592. Fraction Addition and Subtraction
Сложность: medium

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

Пример:

Input: expression = "-1/2+1/2+1/3"
Output: "1/3"

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

1⃣Начните сканирование строки и разделите её на части, содержащие числители и знаменатели, с учетом знаков.

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

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

😎 Решение:

class Solution {
    function fractionAddition($expression) {
        $sign = [];
        if ($expression[0] !== '-') $sign[] = '+';
        for ($i = 0; $i < strlen($expression); $i++) {
            if ($expression[$i] == '+' || $expression[$i] == '-') {
                $sign[] = $expression[$i];
            }
        }

        $fractions = preg_split('/(?=[+-])/', $expression);
        $prev_num = 0;
        $prev_den = 1;
        $i = 0;

        foreach ($fractions as $sub) {
            if ($sub == "") continue;
            list($num, $den) = sscanf($sub, '%d/%d');
            $g = abs($this->gcd($prev_den, $den));
            if ($sign[$i++] == '+') $prev_num = $prev_num * $den / $g + $num * $prev_den / $g;
            else $prev_num = $prev_num * $den / $g - $num * $prev_den / $g;
            $prev_den = $prev_den * $den / $g;
            $g = abs($this->gcd($prev_den, $prev_num));
            $prev_num /= $g;
            $prev_den /= $g;
        }

        return "$prev_num/$prev_den";
    }

    private function gcd($a, $b) {
        while ($b != 0) {
            $t = $b;
            $b = $a % $b;
            $a = $t;
        }
        return $a;
    }
}

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

Задача: 1473. Paint House III
Сложность: hard

Есть ряд из m домов в маленьком городе, каждый дом должен быть покрашен одним из n цветов (обозначены от 1 до n), некоторые дома, которые были покрашены прошлым летом, не должны быть перекрашены.

Соседство — это максимальная группа непрерывных домов, которые покрашены в один и тот же цвет.

Например: дома = [1,2,2,3,3,2,1,1] содержат 5 соседств [{1}, {2,2}, {3,3}, {2}, {1,1}].
Дан массив домов, матрица m x n стоимости и целое число target, где:
houses[i]: цвет дома i, и 0, если дом ещё не покрашен.
cost[i][j]: стоимость покраски дома i в цвет j + 1.
Верните минимальную стоимость покраски всех оставшихся домов таким образом, чтобы было ровно target соседств. Если это невозможно, верните -1.

Пример:

Input: houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
Output: 9
Explanation: Paint houses of this way [1,2,2,1,1]
This array contains target = 3 neighborhoods, [{1}, {2,2}, {1,1}].
Cost of paint all houses (1 + 1 + 1 + 1 + 5) = 9.

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

1⃣Инициализация и базовые случаи:
Создайте класс Solution и массив memo для мемоизации результатов. Установите MAX_COST как максимально возможную стоимость плюс 1.
Создайте метод findMinCost, который проверяет базовые случаи:
- если все дома пройдены, возвращайте 0, если количество соседств равно target, иначе возвращайте MAX_COST.
- если количество соседств больше target, возвращайте MAX_COST.
Если результат уже вычислен, возвращайте его из memo.

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

3⃣Метод minCost:
Запустите метод findMinCost с начальными параметрами и верните результат. Если результат равен MAX_COST, верните -1.

😎 Решение:

class Solution {
    private $MAX_COST = 1000001;
    private $memo = [];
    
    private function findMinCost($houses, $cost, $targetCount, $currIndex, $neighborhoodCount, $prevHouseColor) {
        if ($currIndex == count($houses)) {
            return $neighborhoodCount == $targetCount ? 0 : $this->MAX_COST;
        }

        if ($neighborhoodCount > $targetCount) {
            return $this->MAX_COST;
        }

        $key = "$currIndex,$neighborhoodCount,$prevHouseColor";
        if (isset($this->memo[$key])) {
            return $this->memo[$key];
        }

        $minCost = $this->MAX_COST;

        if ($houses[$currIndex] != 0) {
            $newNeighborhoodCount = $neighborhoodCount + ($houses[$currIndex] != $prevHouseColor ? 1 : 0);
            $minCost = $this->findMinCost($houses, $cost, $targetCount, $currIndex + 1, $newNeighborhoodCount, $houses[$currIndex]);
        } else {
            for ($color = 1; $color <= count($cost[0]); $color++) {
                $newNeighborhoodCount = $neighborhoodCount + ($color != $prevHouseColor ? 1 : 0);
                $currCost = $cost[$currIndex][$color - 1] + $this->findMinCost($houses, $cost, $targetCount, $currIndex + 1, $newNeighborhoodCount, $color);
                $minCost = min($minCost, $currCost);
            }
        }

        $this->memo[$key] = $minCost;
        return $minCost;
    }
    
    public function minCost($houses, $cost, $m, $n, $target) {
        $answer = $this->findMinCost($houses, $cost, $target, 0, 0, 0);
        return $answer == $this->MAX_COST ? -1 : $answer;
    }
}

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

Задача: 277. Find the Celebrity
Сложность: medium

Предположим, вы находитесь на вечеринке с n людьми, обозначенными от 0 до n - 1, и среди них может быть один знаменитость. Определение знаменитости: все остальные n - 1 человек знают знаменитость, но знаменитость не знает никого из них.
Теперь вы хотите выяснить, кто является знаменитостью, или убедиться, что ее нет. Вам разрешено задавать вопросы типа: "Привет, A. Ты знаешь B?", чтобы получить информацию о том, знает ли A B. Вам нужно найти знаменитость (или убедиться, что ее нет), задав как можно меньше вопросов (в асимптотическом смысле).
Вам предоставлена вспомогательная функция bool knows(a, b), которая сообщает, знает ли a b. Реализуйте функцию int findCelebrity(n). На вечеринке будет ровно одна знаменитость, если она есть.
Верните метку знаменитости, если она есть на вечеринке. Если знаменитости нет, верните -1.

Пример:

Input: graph = [[1,1,0],[0,1,0],[1,1,1]]
Output: 1
Explanation: There are three persons labeled with 0, 1 and 2. graph[i][j] = 1 means person i knows person j, otherwise graph[i][j] = 0 means person i does not know person j. The celebrity is the person labeled as 1 because both 0 and 2 know him but 1 does not know anybody.

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

1⃣Найти потенциального кандидата на знаменитость:
Использовать один проход через всех людей, чтобы определить возможного кандидата.
Если человек a знает человека b, то a не может быть знаменитостью, и переключаем кандидата на b.

2⃣Реализовать функцию isCelebrity(candidate):
Проверить, знает ли кандидат кого-либо из людей (исключая самих себя).
Проверить, знают ли все остальные кандидата (исключая самого кандидата).
Если кандидат знает кого-то, или кто-то не знает кандидата, то кандидат не является знаменитостью.

3⃣Возвращение результата:
Если кандидат проходит все проверки в isCelebrity(candidate), вернуть его метку.
В противном случае вернуть -1.

😎 Решение:

class Solution {
    private $n;
    private $cache = [];

    function findCelebrity($n) {
        $this->n = $n;
        $celebrityCandidate = 0;
        for ($i = 1; $i < $n; $i++) {
            if ($this->cachedKnows($celebrityCandidate, $i)) {
                $celebrityCandidate = $i;
            }
        }
        return $this->isCelebrity($celebrityCandidate) ? $celebrityCandidate : -1;
    }

    private function isCelebrity($i) {
        for ($j = 0; $j < $this->n; $j++) {
            if ($i == $j) continue;
            if ($this->cachedKnows($i, $j) || !$this->cachedKnows($j, $i)) {
                return false;
            }
        }
        return true;
    }

    private function cachedKnows($a, $b) {
        $key = "$a,$b";
        if (!isset($this->cache[$key])) {
            $this->cache[$key] = knows($a, $b);
        }
        return $this->cache[$key];
    }
}

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

Задача: 991. Broken Calculator
Сложность: medium

Имеется неисправный калькулятор, на экране которого изначально отображается целое число startValue. За одну операцию можно:

Умножить число на экране на 2, или
Вычесть 1 из числа на экране.
Даны два целых числа startValue и target. Верните минимальное количество операций, необходимых для отображения target на калькуляторе.

Пример:

Input: startValue = 2, target = 3
Output: 2
Explanation: Use double operation and then decrement operation {2 -> 4 -> 3}.

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

1⃣Обратный путь:
Если target больше startValue, то попытайтесь уменьшить target, чтобы привести его к startValue.
Если target четный, разделите его на 2, иначе прибавьте 1.

2⃣Подсчет операций:
Повторяйте шаги, пока target не станет меньше или равен startValue.
После этого вычитайте из startValue оставшееся значение target.

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

😎 Решение:

class Solution {
    function brokenCalc($startValue, $target) {
        $operations = 0;
        
        while ($target > $startValue) {
            $operations++;
            if ($target % 2 == 0) {
                $target /= 2;
            } else {
                $target += 1;
            }
        }
        
        return $operations + ($startValue - $target);
    }
}

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

Задача: 513. Find Bottom Left Tree Value
Сложность: medium

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

Пример:

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

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

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

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

3⃣Проверьте, превышает ли текущая глубина глобальную переменную maxDepth. Если да, это значит, что мы нашли новый уровень. Установите maxDepth в значение текущей глубины. Установите bottomLeftValue в значение текущего узла. Рекурсивно вызовите dfs для левого поддерева текущего узла, увеличив глубину на один. Рекурсивно вызовите dfs для правого поддерева текущего узла, увеличив глубину на один. Вызовите dfs с корнем и начальной глубиной 0. Верните bottomLeftValue.

😎 Решение:

class Solution {
    private $maxDepth = -1;
    private $bottomLeftValue = 0;
    
    function findBottomLeftValue($root) {
        $this->dfs($root, 0);
        return $this->bottomLeftValue;
    }
    
    private function dfs($current, $depth) {
        if ($current == null) return;
        
        if ($depth > $this->maxDepth) {
            $this->maxDepth = $depth;
            $this->bottomLeftValue = $current->val;
        }
        
        $this->dfs($current->left, $depth + 1);
        $this->dfs($current->right, $depth + 1);
    }
}

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

Задача: 965. Univalued Binary Tree
Сложность: easy

Бинарное дерево является одноценным, если каждый узел в дереве имеет одинаковое значение.

Дан корень бинарного дерева, верните true, если данное дерево является одноценным, или false в противном случае.

Пример:

Input: root = [1,1,1,1,1,null,1]
Output: true

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

1⃣Выполните обход дерева в глубину (DFS), чтобы собрать все значения узлов в список.

2⃣Проверьте, что все значения в списке одинаковы.

3⃣Если все значения одинаковы, верните true, иначе верните false.

😎 Решение:

class Solution {
    private $vals;
    
    function isUnivalTree($root) {
        $this->vals = [];
        $this->dfs($root);
        foreach ($this->vals as $v) {
            if ($v != $this->vals[0]) {
                return false;
            }
        }
        return true;
    }

    function dfs($node) {
        if ($node != null) {
            $this->vals[] = $node->val;
            $this->dfs($node->left);
            $this->dfs($node->right);
        }
    }
}

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

Задача: 1101. The Earliest Moment When Everyone Become Friends
Сложность: medium

В социальной группе есть n человек, пронумерованных от 0 до n - 1. Вам дан массив logs, где logs[i] = [timestampi, xi, yi] указывает, что xi и yi станут друзьями в момент времени timestampi.

Дружба является симметричной. Это означает, что если a является другом b, то b является другом a. Также человек a знаком с человеком b, если a является другом b или a является другом кого-то, кто знаком с b.

Верните самое раннее время, когда каждый человек стал знаком с каждым другим человеком. Если такого времени не существует, верните -1.

Пример:

Input: logs = [[0,2,0],[1,0,1],[3,0,3],[4,1,2],[7,3,1]], n = 4
Output: 3
Explanation: At timestamp = 3, all the persons (i.e., 0, 1, 2, and 3) become friends.

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

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

2⃣Пройдитесь по отсортированным логам, применяя структуру данных "Объединение-Поиск":
Для каждого лога объедините двух участников, упомянутых в логе, с помощью функции union(a, b).
Каждое объединение добавляет новые связи между участниками.

3⃣Следите за количеством групп:
Изначально каждый участник рассматривается как отдельная группа.
Количество групп уменьшается с каждым полезным объединением.
Момент, когда количество групп уменьшается до одной, является самым ранним моментом, когда все участники становятся связанными (друзьями). Верните этот момент времени.
Если такого момента не существует, верните -1.

😎 Решение:

class UnionFind {
    private $parent;
    private $rank;

    public function __construct($n) {
        $this->parent = range(0, $n - 1);
        $this->rank = array_fill(0, $n, 1);
    }

    public function find($x) {
        if ($this->parent[$x] != $x) {
            $this->parent[$x] = $this->find($this->parent[$x]);
        }
        return $this->parent[$x];
    }

    public function union($x, $y) {
        $rootX = $this->find($x);
        $rootY = $this->find($y);
        
        if ($rootX != $rootY) {
            if ($this->rank[$rootX] > $this->rank[$rootY]) {
                $this->parent[$rootY] = $rootX;
            } else if ($this->rank[$rootX] < $this->rank[$rootY]) {
                $this->parent[$rootX] = $rootY;
            } else {
                $this->parent[$rootY] = $rootX;
                $this->rank[$rootX]++;
            }
            return true;
        }
        return false;
    }
}

class Solution {
    function earliestAcq($logs, $n) {
        usort($logs, function($a, $b) {
            return $a[0] - $b[0];
        });
        $uf = new UnionFind($n);
        $groupCount = $n;
        
        foreach ($logs as $log) {
            $timestamp = $log[0];
            $friendA = $log[1];
            $friendB = $log[2];
            if ($uf->union($friendA, $friendB)) {
                $groupCount--;
            }
            if ($groupCount == 1) {
                return $timestamp;
            }
        }
        
        return -1;
    }
}

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

Задача: 1506. Find Root of N-Ary Tree
Сложность: medium

Вам даны все узлы N-арного дерева в виде массива объектов Node, где каждый узел имеет уникальное значение.

Верните корень N-арного дерева.

Пример:

Input: tree = [1,null,3,2,4,null,5,6]
Output: [1,null,3,2,4,null,5,6]
Explanation: The tree from the input data is shown above.
The driver code creates the tree and gives findRoot the Node objects in an arbitrary order.
For example, the passed array could be [Node(5),Node(4),Node(3),Node(6),Node(2),Node(1)] or [Node(2),Node(6),Node(1),Node(3),Node(5),Node(4)].
The findRoot function should return the root Node(1), and the driver code will serialize it and compare with the input data.
The input data and serialized Node(1) are the same, so the test passes.

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

1⃣Используйте хэшсет (named as seen) для отслеживания всех посещенных дочерних узлов. В конечном итоге корневой узел не будет в этом множестве.

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

3⃣Посетите список еще раз. На этот раз у нас будут все дочерние узлы в хэшсете. Как только вы наткнетесь на узел, который не находится в хэшсете, это и будет корневой узел, который мы ищем.

😎 Решение:

class Solution {
    function findRoot($tree) {
        $seen = [];

        foreach ($tree as $node) {
            foreach ($node->children as $child) {
                $seen[$child->val] = true;
            }
        }

        foreach ($tree as $node) {
            if (!isset($seen[$node->val])) {
                return $node;
            }
        }

        return null;
    }
}

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

Задача: 641. Design Circular Deque
Сложность: medium

Разработайте свою реализацию круговой двусторонней очереди (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 MyCircularDeque {
    private $deque;
    private $front;
    private $rear;
    private $size;
    private $capacity;

    function __construct($k) {
        $this->capacity = $k;
        $this->deque = array_fill(0, $k, 0);
        $this->front = 0;
        $this->rear = 0;
        $this->size = 0;
    }

    function insertFront($value) {
        if ($this->isFull()) return false;
        $this->front = ($this->front - 1 + $this->capacity) % $this->capacity;
        $this->deque[$this->front] = $value;
        $this->size++;
        return true;
    }

    function insertLast($value) {
        if ($this->isFull()) return false;
        $this->deque[$this->rear] = $value;
        $this->rear = ($this->rear + 1) % $this->capacity;
        $this->size++;
        return true;
    }

    function deleteFront() {
        if ($this->isEmpty()) return false;
        $this->front = ($this->front + 1) % $this->capacity;
        $this->size--;
        return true;
    }

    function deleteLast() {
        if ($this->isEmpty()) return false;
        $this->rear = ($this->rear - 1 + $this->capacity) % $this->capacity;
        $this->size--;
        return true;
    }

    function getFront() {
        if ($this->isEmpty()) return -1;
        return $this->deque[$this->front];
    }

    function getRear() {
        if ($this->isEmpty()) return -1;
        return $this->deque[($this->rear - 1 + $this->capacity) % $this->capacity];
    }

    function isEmpty() {
        return $this->size == 0;
    }

    function isFull() {
        return $this->size == $this->capacity;
    }
}

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

Задача: 903. Valid Permutations for DI Sequence
Сложность: hard

Вам дана строка s длины n, где s[i] либо: 'D' означает убывание, либо 'I' означает возрастание. Перестановка perm из n + 1 целых чисел всех целых чисел в диапазоне [0, n] называется допустимой, если для всех допустимых i: если s[i] == 'D', то perm[i] > perm[i + 1], а если s[i] == 'I', то perm[i] < perm[i + 1]. Верните количество допустимых перестановок perm. Поскольку ответ может быть большим, верните его по модулю 109 + 7.

Пример:

Input: s = "DID"
Output: 5

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

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

2⃣Заполнить массив dp, учитывая условия возрастания и убывания из строки s.

3⃣Вернуть сумму dp[n][j] для всех j, что даст количество допустимых перестановок длины n + 1.

😎 Решение:

function numPermsDISequence($s) {
    $MOD = 1000000007;
    $n = strlen($s);
    $dp = array_fill(0, $n + 1, array_fill(0, $n + 1, 0));
    $dp[0][0] = 1;

    for ($i = 1; $i <= $n; $i++) {
        for ($j = 0; $j <= $i; $j++) {
            if ($s[$i - 1] == 'D') {
                for ($k = $j; $k < $i; $k++) {
                    $dp[$i][$j] = ($dp[$i][$j] + $dp[$i - 1][$k]) % $MOD;
                }
            } else {
                for ($k = 0; $k < $j; $k++) {
                    $dp[$i][$j] = ($dp[$i][$j] + $dp[$i - 1][$k]) % $MOD;
                }
            }
        }
    }

    $result = 0;
    for ($j = 0; $j <= $n; $j++) {
        $result = ($result + $dp[$n][$j]) % $MOD;
    }

    return $result;
}

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