Задача: 755. Pour Water
Сложность: medium

Вам дана карта высот, представленная в виде целочисленного массива heights, где heights[i] - высота местности в точке i. Ширина в каждой точке равна 1. Вам также даны два целых числа volume и k. Единицы объема воды будут падать в точке k. Вода сначала падает в точке k и упирается в самую высокую местность или воду в этой точке. Затем она течет по следующим правилам: если капля в конечном итоге упадет, двигаясь влево, то двигайтесь влево. Иначе, если капля в конечном итоге упадет, двигаясь вправо, то двигайтесь вправо. Иначе поднимайтесь в текущее положение. Здесь "в конечном итоге упадет" означает, что капля в конечном итоге окажется на более низком уровне, если она будет двигаться в этом направлении. Кроме того, уровень означает высоту местности плюс вода в этом столбе. Мы можем предположить, что на двух сторонах, выходящих за пределы массива, есть бесконечно высокая местность. Также не может быть частичного равномерного распределения воды более чем на один блок сетки, и каждая единица воды должна находиться ровно в одном блоке.

Пример:

Input: heights = [2,1,1,2,1,2,2], volume = 4, k = 3
Output: [2,2,2,3,2,2,2]

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

1⃣Инициализируйте цикл для добавления объема воды.

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

3⃣Повторите шаг 2, пока не будет добавлен весь объем воды.

😎 Решение:

function pourWater($heights, $volume, $k) {
    for ($v = 0; $v < $volume; $v++) {
        $dropIndex = $k;
        foreach ([-1, 1] as $d) {
            $i = $k;
            while ($i + $d >= 0 && $i + $d < count($heights) && $heights[$i + $d] <= $heights[$i]) {
                if ($heights[$i + $d] < $heights[$i]) {
                    $dropIndex = $i + $d;
                }
                $i += $d;
            }
            if ($dropIndex != $k) {
                break;
            }
        }
        $heights[$dropIndex]++;
    }
    return $heights;
}

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

Задача: 604. Design Compressed String Iterator
Сложность: Easy

Разработайте и реализуйте структуру данных для итератора сжатой строки. Данная сжатая строка будет в виде каждой буквы, за которой следует положительное целое число, представляющее количество этой буквы в оригинальной несжатой строке.
Реализуйте класс StringIterator:
- next(): Возвращает следующий символ, если в оригинальной строке еще остались несжатые символы, в противном случае возвращает пробел.
- hasNext(): Возвращает true, если в оригинальной строке остались символы, которые нужно распаковать, в противном случае возвращает false.

Пример:

Input
["StringIterator", "next", "next", "next", "next", "next", "next", "hasNext", "next", "hasNext"]
[["L1e2t1C1o1d1e1"], [], [], [], [], [], [], [], [], []]
Output
[null, "L", "e", "e", "t", "C", "o", true, "d", true]

Explanation
StringIterator stringIterator = new StringIterator("L1e2t1C1o1d1e1");
stringIterator.next(); // return "L"
stringIterator.next(); // return "e"
stringIterator.next(); // return "e"
stringIterator.next(); // return "t"
stringIterator.next(); // return "C"
stringIterator.next(); // return "o"
stringIterator.hasNext(); // return True
stringIterator.next(); // return "d"
stringIterator.hasNext(); // return True

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

1⃣Предварительная обработка
Мы заранее создаем несжатую строку. Для этого проходим по данному сжатому строковому представлению и добавляем несжатые буквы для каждой сжатой буквы в результирующий строковый строитель res. Чтобы найти количество несжатых букв, мы проходим по данному сжатому строковому представлению. Когда находим букву, определяем следующее за ней число, используя десятичную арифметику. Таким образом, получаем два элемента (букву и количество), необходимые для формирования текущего фрагмента несжатой строки.

2⃣Операция next()
Начинаем с проверки, есть ли еще несжатые буквы в строке. Если нет, hasNext() возвращает False, а next() возвращает пробел (' '). В противном случае возвращаем букву, на которую указывает ptr, указывающий на следующую букву для возврата. Перед возвратом буквы также обновляем ptr, чтобы указывать на следующую букву в res.

3⃣Операция hasNext()
Если указатель ptr выходит за пределы массива res, это указывает на то, что больше несжатых букв нет. В этом случае возвращаем False. В противном случае возвращаем True.

😎 Решение:

class StringIterator {
    private $res = [];
    private $ptr = 0;

    public function __construct($s) {
        $i = 0;
        while ($i < strlen($s)) {
            $ch = $s[$i++];
            $num = 0;
            while ($i < strlen($s) && is_numeric($s[$i])) {
                $num = $num * 10 + intval($s[$i]);
                $i++;
            }
            for ($j = 0; $j < $num; $j++) {
                $this->res[] = $ch;
            }
        }
    }

    public function next() {
        return $this->hasNext() ? $this->res[$this->ptr++] : ' ';
    }

    public function hasNext() {
        return $this->ptr < count($this->res);
    }
}

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

Задача: 462. Minimum Moves to Equal Array Elements II
Сложность: medium

Дан массив целых чисел nums размера n, вернуть минимальное количество ходов, необходимых для того, чтобы сделать все элементы массива равными.
В одном ходе вы можете увеличить или уменьшить элемент массива на 1.
Тестовые случаи составлены так, что ответ поместится в 32-битное целое число.

Пример:

Input: nums = [1,2,3]
Output: 2
Explanation:
Only two moves are needed (remember each move increments or decrements one element):
[1,2,3]  =>  [2,2,3]  =>  [2,2,2]

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

1⃣Найти минимальный и максимальный элементы в массиве. Пусть k будет числом, к которому должны быть приведены все элементы массива.

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

3⃣Определить минимальное количество ходов среди всех возможных k, что и будет конечным результатом.

😎 Решение:

class Solution {
    public function minMoves2($nums) {
        $ans = PHP_INT_MAX;
        $minval = min($nums);
        $maxval = max($nums);
        for ($i = $minval; $i <= $maxval; $i++) {
            $sum = 0;
            foreach ($nums as $num) {
                $sum += abs($num - $i);
            }
            $ans = min($ans, $sum);
        }
        return (int) $ans;
    }
}

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

Задача: 741. Cherry Pickup
Сложность: hard

Вам дана сетка n x n, представляющая поле вишен. Каждая клетка - одно из трех возможных целых чисел. 0 означает, что клетка пуста, и вы можете пройти через нее, 1 означает, что клетка содержит вишню, которую вы можете сорвать и пройти через нее, или -1 означает, что клетка содержит шип, который преграждает вам путь. Верните максимальное количество вишен, которое вы можете собрать, следуя следующим правилам: Начиная с позиции (0, 0) и достигая (n - 1, n - 1) путем перемещения вправо или вниз через допустимые клетки пути (клетки со значением 0 или 1).
После достижения (n - 1, n - 1) вернитесь в (0, 0), двигаясь влево или вверх по клеткам с действительными путями. Проходя через клетку пути, содержащую вишню, вы поднимаете ее, и клетка становится пустой клеткой 0. Если между (0, 0) и (n - 1, n - 1) нет действительного пути, то вишни собрать нельзя.

Пример:

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

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

1⃣Используйте динамическое программирование для подсчета максимального количества вишен, которые можно собрать при движении от (0, 0) до (n - 1, n - 1).

2⃣Примените еще один проход с использованием динамического программирования для движения обратно от (n - 1, n - 1) до (0, 0), чтобы учитывать вишни, собранные на обратном пути.

3⃣Объедините результаты двух проходов, чтобы найти максимальное количество вишен, которые можно собрать.

😎 Решение:

function cherryPickup($grid) {
    $n = count($grid);
    $dp = array_fill(0, $n, array_fill(0, $n, array_fill(0, 2 * $n - 1, -INF)));
    $dp[0][0][0] = $grid[0][0];

    for ($k = 1; $k < 2 * $n - 1; $k++) {
        for ($i1 = max(0, $k - $n + 1); $i1 <= min($n - 1, $k); $i1++) {
            for ($i2 = max(0, $k - $n + 1); $i2 <= min($n - 1, $k); $i2++) {
                $j1 = $k - $i1;
                $j2 = $k - $i2;
                if ($j1 < $n && $j2 < $n && $grid[$i1][$j1] != -1 && $grid[$i2][$j2] != -1) {
                    $maxCherries = -INF;
                    if ($i1 > 0 && $i2 > 0) $maxCherries = max($maxCherries, $dp[$i1 - 1][$i2 - 1][$k - 1]);
                    if ($i1 > 0) $maxCherries = max($maxCherries, $dp[$i1 - 1][$i2][$k - 1]);
                    if ($i2 > 0) $maxCherries = max($maxCherries, $dp[$i1][$i2 - 1][$k - 1]);
                    $maxCherries = max($maxCherries, $dp[$i1][$i2][$k - 1]);
                    if ($maxCherries != -INF) {
                        $dp[$i1][$i2][$k] = $maxCherries + $grid[$i1][$j1];
                        if ($i1 != $i2) $dp[$i1][$i2][$k] += $grid[$i2][$j2];
                    }
                }
            }
        }
    }

    return max(0, $dp[$n - 1][$n - 1][2 * $n - 1]);
}

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

Задача: 989. Add to Array-Form of Integer
Сложность: easy

Массивная форма целого числа num - это массив, представляющий его цифры в порядке слева направо.

Например, для num = 1321, массивная форма - это [1, 3, 2, 1].
Дано num в массивной форме целого числа и целое число k, верните массивную форму числа num + k.

Пример:

Input: num = [1,2,0,0], k = 34
Output: [1,2,3,4]
Explanation: 1200 + 34 = 1234

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

1⃣Инициализация переменных:
Преобразуйте число k в массив его цифр и переверните оба массива (массив num и массив цифр k).
Завести переменную carry для хранения переноса и инициализировать ее нулем.
Создать пустой массив result для хранения результата.

2⃣Сложение массивов:
Пройдите по элементам массивов num и цифр k, начиная с их конца, сложите соответствующие цифры вместе с переносом (carry).
Если сумма больше 9, сохраните последнюю цифру в текущей позиции результата, а carry установите в 1.
Если сумма меньше 10, установите carry в 0.
Добавьте результат текущего сложения в массив result

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

😎 Решение:

class Solution {
    function addToArrayForm($num, $k) {
        $result = [];
        $n = count($num);
        for ($i = $n - 1; $i >= 0; $i--) {
            $k += $num[$i];
            array_unshift($result, $k % 10);
            $k = intdiv($k, 10);
        }
        while ($k > 0) {
            array_unshift($result, $k % 10);
            $k = intdiv($k, 10);
        }
        return $result;
    }
}

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

Задача: 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);
        }
    }
}

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