#medium
Задача: 621. Task Scheduler

Вам дан массив задач процессора, каждая из которых представлена буквами от A до Z, и время охлаждения, n. Каждый цикл или интервал позволяет завершить одну задачу. Задачи могут быть выполнены в любом порядке, но есть ограничение: одинаковые задачи должны быть разделены не менее чем n интервалами из-за времени охлаждения. Верните минимальное количество интервалов, необходимое для выполнения всех задач.

Пример:

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8

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

1⃣Подсчитайте количество каждой задачи и найдите максимальное количество вхождений (maxFreq).

2⃣Вычислите количество интервалов, необходимых для задач с maxFreq: (maxFreq - 1) * (n + 1) + countMaxFreq, где countMaxFreq - количество задач, имеющих maxFreq.

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

😎 Решение:

function leastInterval($tasks, $n) {
    $taskCounts = array_count_values($tasks);
    $maxFreq = max($taskCounts);
    $countMaxFreq = count(array_filter($taskCounts, function($count) use ($maxFreq) {
        return $count == $maxFreq;
    }));
    
    return max(count($tasks), ($maxFreq - 1) * ($n + 1) + $countMaxFreq);
}

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

#medium
Задача: 622. Design Circular Queue

Разработайте свою реализацию круговой очереди. Круговая очередь - это линейная структура данных, в которой операции выполняются по принципу FIFO (First In First Out), а последняя позиция соединяется с первой, образуя круг. Одно из преимуществ круговой очереди заключается в том, что мы можем использовать пространство перед очередью. В обычной очереди, когда очередь становится полной, мы не можем вставить следующий элемент, даже если перед очередью есть свободное место. Но с помощью круговой очереди мы можем использовать пространство для хранения новых значений. Реализация класса MyCircularQueue: MyCircularQueue(k) Инициализирует объект с размером очереди k. int Front() Получает первый элемент из очереди. Если очередь пуста, возвращается -1. int Rear() Получает последний элемент из очереди. Если очередь пуста, возвращается -1. boolean enQueue(int value) Вставляет элемент в циклическую очередь. Возвращает true, если операция прошла успешно. boolean deQueue() Удаляет элемент из круговой очереди. Возвращает true, если операция выполнена успешно. boolean isEmpty() Проверяет, пуста ли круговая очередь. boolean isFull() Проверяет, заполнена ли круговая очередь. Вы должны решить проблему без использования встроенной структуры данных очереди в вашем языке программирования.

Пример:

Input
["MyCircularQueue", "enQueue", "enQueue", "enQueue", "enQueue", "Rear", "isFull", "deQueue", "enQueue", "Rear"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 3, true, true, true, 4]

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

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

2⃣Реализуйте методы enQueue и deQueue для вставки и удаления элементов, обновляя указатели по круговому принципу.

3⃣Реализуйте методы Front, Rear, isEmpty и isFull для доступа к элементам и проверки состояния очереди.

😎 Решение:

class MyCircularQueue {
    private $queue;
    private $front;
    private $rear;
    private $size;
    private $capacity;

    function __construct($k) {
        $this->queue = array_fill(0, $k, -1);
        $this->front = 0;
        $this->rear = -1;
        $this->size = 0;
        $this->capacity = $k;
    }
    
    function enQueue($value) {
        if ($this->isFull()) {
            return false;
        }
        $this->rear = ($this->rear + 1) % $this->capacity;
        $this->queue[$this->rear] = $value;
        $this->size++;
        return true;
    }
    
    function deQueue() {
        if ($this->isEmpty()) {
            return false;
        }
        $this->front = ($this->front + 1) % $this->capacity;
        $this->size--;
        return true;
    }
    
    function Front() {
        return $this->isEmpty() ? -1 : $this->queue[$this->front];
    }
    
    function Rear() {
        return $this->isEmpty() ? -1 : $this->queue[$this->rear];
    }
    
    function isEmpty() {
        return $this->size == 0;
    }
    
    function isFull() {
        return $this->size == $this->capacity;
    }
}

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

#medium
Задача: 623. Add One Row to Tree

Учитывая корень бинарного дерева и два целых числа val и depth, добавьте ряд узлов со значением val на заданную глубину depth. Обратите внимание, что корневой узел находится на глубине 1. Правило добавления таково: учитывая целое число depth, для каждого ненулевого узла дерева cur на глубине depth - 1 создайте два узла дерева со значением val в качестве левого поддерева корня cur и правого поддерева корня.
Оригинальное левое поддерево cur должно быть левым поддеревом нового корня левого поддерева. Оригинальное правое поддерево cur должно быть правым поддеревом нового корня правого поддерева. Если глубина == 1, то есть глубина - 1 вообще не существует, создайте узел дерева со значением val как новый корень всего оригинального дерева, а оригинальное дерево - левое поддерево нового корня.

Пример:

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

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

1⃣Если depth равна 1, создайте новый корень со значением val и сделайте текущий корень левым поддеревом нового корня.

2⃣Используйте обход в ширину (BFS) для поиска всех узлов на глубине depth - 1.

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

😎 Решение:

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

function addOneRow($root, $val, $depth) {
    if ($depth == 1) {
        return new TreeNode($val, $root);
    }
    
    $queue = [$root];
    $currentDepth = 1;
    
    while (!empty($queue)) {
        if ($currentDepth == $depth - 1) {
            foreach ($queue as $node) {
                $node->left = new TreeNode($val, $node->left);
                $node->right = new TreeNode($val, null, $node->right);
            }
            break;
        }
        $currentDepth++;
        $nextQueue = [];
        foreach ($queue as $node) {
            if ($node->left !== null) {
                $nextQueue[] = $node->left;
            }
            if ($node->right !== null) {
                $nextQueue[] = $node->right;
            }
        }
        $queue = $nextQueue;
    }
    
    return $root;
}

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

#medium
Задача: 624. Maximum Distance in Arrays

Вам дано m массивов, где каждый массив отсортирован по возрастанию. Вы можете взять два целых числа из двух разных массивов (каждый массив выбирает одно) и вычислить расстояние. Мы определяем расстояние между двумя целыми числами a и b как их абсолютную разность |a - b|. Верните максимальное расстояние.

Пример:

Input: arrays = [[1,2,3],[4,5],[1,2,3]]
Output: 4

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

1⃣Найдите минимальный элемент из всех первых элементов массивов и максимальный элемент из всех последних элементов массивов.

2⃣Рассчитайте максимальное расстояние между минимальным и максимальным элементами.

3⃣Верните это максимальное расстояние.

😎 Решение:

function maxDistance($arrays) {
    $minElement = $arrays[0][0];
    $maxElement = end($arrays[0]);
    $maxDistance = 0;
    
    for ($i = 1; $i < count($arrays); $i++) {
        $array = $arrays[$i];
        $maxDistance = max($maxDistance, abs(end($array) - $minElement), abs($maxElement - $array[0]));
        $minElement = min($minElement, $array[0]);
        $maxElement = max($maxElement, end($array));
    }
    
    return $maxDistance;
}

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

#medium
Задача: 625. Minimum Factorization

Если задано целое положительное число num, верните наименьшее целое положительное число x, умножение каждого разряда которого равно num. Если ответа нет или ответ не помещается в 32-битное знаковое целое число, возвращается 0.

Пример:

Input: num = 48
Output: 68

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

1⃣Если num равно 1, верните 1. Инициализируйте массив для хранения множителей.

2⃣Разделите num на множители от 9 до 2, пока num больше 1. Если в процессе остаются множители больше 9, верните 0.

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

😎 Решение:

function smallestFactorization($num) {
    if ($num == 1) {
        return 1;
    }
    
    $factors = [];
    
    for ($i = 9; $i >= 2; $i--) {
        while ($num % $i == 0) {
            $factors[] = $i;
            $num /= $i;
        }
    }
    
    if ($num > 1) {
        return 0;
    }
    
    $result = 0;
    foreach (array_reverse($factors) as $factor) {
        $result = $result * 10 + $factor;
        if ($result > PHP_INT_MAX) {
            return 0;
        }
    }
    
    return $result;
}

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

#medium
Задача: 628. Maximum Product of Three Numbers

Задав целочисленный массив nums, найдите три числа, произведение которых максимально, и верните максимальное произведение.

Пример:

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

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

1⃣Отсортируйте массив nums.

2⃣Найдите два возможных максимальных произведения: Произведение трех наибольших элементов массива. Произведение двух наименьших (отрицательных) и одного наибольшего элемента массива.

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

😎 Решение:

function maximumProduct($nums) {
    sort($nums);
    $n = count($nums);
    $max1 = $nums[$n - 1] * $nums[$n - 2] * $nums[$n - 3];
    $max2 = $nums[0] * $nums[1] * $nums[$n - 1];
    return max($max1, $max2);
}

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

#hard
Задача: 629. K Inverse Pairs Array

Для целочисленного массива nums инверсная пара - это пара целых чисел [i, j], где 0 <= i < j < nums.length и nums[i] > nums[j]. Учитывая два целых числа n и k, верните количество различных массивов, состоящих из чисел от 1 до n, в которых существует ровно k инверсных пар. Поскольку ответ может быть огромным, верните его по модулю 109 + 7.

Пример:

Input: n = 3, k = 0
Output: 1

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

1⃣Инициализация
Создайте двумерный массив dp размером [n+1][k+1] и установите начальное значение dp[0][0] = 1. Остальные значения установите в 0.

2⃣Заполнение DP-таблицы
Используйте два вложенных цикла для заполнения таблицы DP. Внешний цикл перебирает длину массива i от 1 до n, а внутренний цикл перебирает количество инверсий j от 0 до k. Если j == 0, то dp[i][j] = 1. В противном случае обновляйте dp[i][j] с учетом всех возможных позиций вставки нового элемента в массив длины i-1.

3⃣Возвращение результата
Результатом будет значение dp[n][k].

😎 Решение:

function kInversePairs($n, $k) {
    $MOD = 1000000007;
    $dp = array_fill(0, $n + 1, array_fill(0, $k + 1, 0));
    $dp[0][0] = 1;

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

    return $dp[$n][$k];
}

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

#hard
Задача: 630. Course Schedule III

Имеется n различных онлайн-курсов, пронумерованных от 1 до n. Вам дан массив courses, где courses[i] = [durationi, lastDayi] указывает, что i-й курс должен быть пройден непрерывно в течениеi дней и должен быть закончен до или в lastDayi. Вы начинаете в 1-й день и не можете проходить два или более курсов одновременно. Верните максимальное количество курсов, которые вы можете пройти.

Пример:

Input: courses = [[100,200],[200,1300],[1000,1250],[2000,3200]]
Output: 3

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

1⃣Сортировка курсов
Отсортируйте курсы по их конечным датам (lastDay). Это позволяет проходить курсы как можно ближе к их крайним срокам.

2⃣Проход по курсам
Используйте приоритетную очередь (max-heap) для отслеживания продолжительности пройденных курсов.

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

😎 Решение:

function scheduleCourse($courses) {
    usort($courses, function($a, $b) {
        return $a[1] - $b[1];
    });

    $totalTime = 0;
    $maxHeap = new SplPriorityQueue();
    $maxHeap->setExtractFlags(SplPriorityQueue::EXTR_DATA);

    foreach ($courses as $course) {
        $duration = $course[0];
        $lastDay = $course[1];
        $maxHeap->insert($duration, -$duration);
        $totalTime += $duration;

        if ($totalTime > $lastDay) {
            $totalTime -= $maxHeap->extract();
        }
    }

    return iterator_count($maxHeap);
}

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

#easy
Задача: 434. Number of Segments in a String

Дана строка s, верните количество сегментов в строке.

Сегмент определяется как непрерывная последовательность символов, отличных от пробелов.

Пример:

Input: s = "Hello, my name is John"
Output: 5
Explanation: The five segments are ["Hello,", "my", "name", "is", "John"]

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

1⃣Инициализируйте счетчик сегментов segment_count равным 0.

2⃣Итеративно пройдитесь по строке s. Для каждого индекса i проверьте, начинается ли на этом индексе сегмент: Если символ s[i] не является пробелом, и (либо это первый символ строки, либо предыдущий символ s[i-1] является пробелом), увеличьте segment_count.

3⃣Верните segment_count.

😎 Решение:

class Solution {
    function countSegments($s) {
        $segmentCount = 0;

        for ($i = 0; $i < strlen($s); $i++) {
            if (($i == 0 || $s[$i - 1] == ' ') && $s[$i] != ' ') {
                $segmentCount++;
            }
        }

        return $segmentCount;
    }
}

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

#hard
Задача: 354. Russian Doll Envelopes

Вам дан двумерный массив целых чисел envelopes, где envelopes[i] = [wi, hi] представляет ширину и высоту конверта.

Один конверт может поместиться в другой, если и только если ширина и высота одного конверта больше ширины и высоты другого конверта.
Верните максимальное количество конвертов, которые вы можете вложить друг в друга (т.е. поместить один в другой).

Примечание: Вы не можете поворачивать конверт.

Пример:

Input: envelopes = [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

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

1⃣Отсортируйте массив конвертов по возрастанию по первой размерности (ширине) и по убыванию по второй размерности (высоте).

2⃣Извлеките вторую размерность (высоты) отсортированного массива.

3⃣Найдите длину наибольшей возрастающей подпоследовательности в массиве высот.

😎 Решение:

class Solution {
    function lengthOfLIS($nums) {
        $dp = [];
        foreach ($nums as $num) {
            $i = $this->binarySearch($dp, $num);
            if ($i < 0) $i = -($i + 1);
            $dp[$i] = $num;
        }
        return count($dp);
    }

    function binarySearch($arr, $target) {
        $left = 0;
        $right = count($arr);
        while ($left < $right) {
            $mid = intdiv($left + $right, 2);
            if ($arr[$mid] < $target) {
                $left = $mid + 1;
            } else {
                $right = $mid;
            }
        }
        return ($left < count($arr) && $arr[$left] == $target) ? $left : -($left + 1);
    }

    function maxEnvelopes($envelopes) {
        usort($envelopes, function($a, $b) {
            return $a[0] == $b[0] ? $b[1] - $a[1] : $a[0] - $b[0];
        });
        $secondDim = array_map(function($envelope) {
            return $envelope[1];
        }, $envelopes);
        return $this->lengthOfLIS($secondDim);
    }
}

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

#hard
Задача: 631. Design Excel Sum Formula

Разработайте базовую функцию Excel и реализуйте функцию формулы суммы. Реализуйте класс Excel: Excel(int height, char width) Инициализирует объект с высотой и шириной листа. Лист представляет собой целочисленную матрицу размером height x width с индексом строки в диапазоне [1, height] и индексом столбца в диапазоне ['A', width]. Все значения должны быть нулевыми изначально. void set(int row, char column, int val) Изменяет значение в mat[row][column] на val. int get(int row, char column) Возвращает значение в mat[row][column]. int sum(int row, char column, List<String> numbers) Устанавливает значение в mat[row][column] как сумму ячеек, представленных числами, и возвращает значение в mat[row][column]. Эта формула суммы должна существовать до тех пор, пока эта ячейка не будет перекрыта другим значением или другой формулой суммы. numbers[i] могут иметь формат: "ColRow", который представляет одну ячейку. Например, "F7" представляет ячейку mat[7]['F']. "ColRow1:ColRow2", который представляет диапазон ячеек. Диапазон всегда будет прямоугольником, где "ColRow1" представляет позицию левой верхней ячейки, а "ColRow2" - позицию правой нижней ячейки.
Например, "B3:F7" представляет ячейки mat[i][j] для 3 <= i <= 7 и 'B' <= j <= 'F'. Примечание: Можно предположить, что не будет никаких ссылок на круговую сумму. Например, mat[1]['A'] == sum(1, "B") и mat[1]['B'] == sum(1, "A").

Пример:

Input
["Excel", "set", "sum", "set", "get"]
[[3, "C"], [1, "A", 2], [3, "C", ["A1", "A1:B2"]], [2, "B", 2], [3, "C"]]
Output
[null, null, 4, null, 6]

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

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

2⃣Метод установки значений
Реализуйте метод set, который будет изменять значение ячейки в матрице.

3⃣Метод вычисления суммы
Реализуйте метод sum, который будет вычислять сумму значений ячеек, указанных в списке numbers. Метод должен поддерживать как одиночные ячейки, так и диапазоны ячеек.

😎 Решение:

class Excel {
    private $mat;
    private $formulas;

    public function __construct($height, $width) {
        $this->mat = array_fill(0, $height, array_fill(0, ord($width) - ord('A') + 1, 0));
        $this->formulas = [];
    }

    public function set($row, $column, $val) {
        $this->mat[$row - 1][ord($column) - ord('A')] = $val;
        unset($this->formulas["$row$column"]);
    }

    public function get($row, $column) {
        $key = "$row$column";
        if (isset($this->formulas[$key])) {
            return $this->evaluateFormula($key);
        }
        return $this->mat[$row - 1][ord($column) - ord('A')];
    }

    public function sum($row, $column, $numbers) {
        $key = "$row$column";
        $this->formulas[$key] = $numbers;
        return $this->evaluateFormula($key);
    }

    private function evaluateFormula($key) {
        $numbers = $this->formulas[$key];
        $total = 0;
        foreach ($numbers as $number) {
            if (strpos($number, ':') !== false) {
                list($start, $end) = explode(':', $number);
                $startRow = (int)substr($start, 1);
                $startCol = $start[0];
                $endRow = (int)substr($end, 1);
                $endCol = $end[0];
                for ($r = $startRow; $r <= $endRow; $r++) {
                    for ($c = ord($startCol); $c <= ord($endCol); $c++) {
                        $total += $this->get($r, chr($c));
                    }
                }
            } else {
                $r = (int)substr($number, 1);
                $c = $number[0];
                $total += $this->get($r, $c);
            }
        }
        return $total;
    }
}

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

#medium
Задача: 435. Non-overlapping Intervals

Дан массив интервалов intervals, где intervals[i] = [starti, endi]. Верните минимальное количество интервалов, которые нужно удалить, чтобы остальные интервалы не пересекались.

Пример:

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.

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

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

2⃣Инициализируйте переменную ответа ans = 0 и целое число k для представления самого последнего времени окончания. k следует инициализировать небольшим значением, например, INT_MIN.

3⃣Итеративно пройдитесь по интервалам. Для каждого интервала: Если время начала больше или равно k, обновите k до времени окончания текущего интервала. В противном случае увеличьте ans. Верните ans.

😎 Решение:

class Solution {
    function eraseOverlapIntervals($intervals) {
        usort($intervals, function($a, $b) {
            return $a[1] - $b[1];
        });
        $ans = 0;
        $k = -INF;
        
        foreach ($intervals as $interval) {
            list($x, $y) = $interval;
            if ($x >= $k) {
                $k = $y;
            } else {
                $ans++;
            }
        }
        
        return $ans;
    }
}

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

#hard
Задача: 358. Rearrange String k Distance Apart

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

Пример:

Input: s = "aabbcc", k = 3
Output: "abcabc"
Explanation: The same letters are at least a distance of 3 from each other.

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

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

2⃣Разделите символы на группы по частоте и создайте сегменты для размещения символов.

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

😎 Решение:

class Solution {
    function rearrangeString($s, $k) {
        $freqs = [];
        $maxFreq = 0;

        for ($i = 0; $i < strlen($s); $i++) {
            $char = $s[$i];
            if (!isset($freqs[$char])) {
                $freqs[$char] = 0;
            }
            $freqs[$char]++;
            $maxFreq = max($maxFreq, $freqs[$char]);
        }

        $mostChars = [];
        $secondChars = [];

        foreach ($freqs as $char => $freq) {
            if ($freq == $maxFreq) {
                $mostChars[] = $char;
            } else if ($freq == $maxFreq - 1) {
                $secondChars[] = $char;
            }
        }

        $segments = array_fill(0, $maxFreq, "");

        for ($i = 0; $i < $maxFreq; $i++) {
            foreach ($mostChars as $char) {
                $segments[$i] .= $char;
            }
            if ($i < $maxFreq - 1) {
                foreach ($secondChars as $char) {
                    $segments[$i] .= $char;
                }
            }
        }

        $segmentId = 0;

        foreach ($freqs as $char => $freq) {
            if (in_array($char, $mostChars) || in_array($char, $secondChars)) {
                continue;
            }

            for ($j = 0; $j < $freq; $j++) {
                $segments[$segmentId] .= $char;
                $segmentId = ($segmentId + 1) % ($maxFreq - 1);
            }
        }

        for ($i = 0; $i < $maxFreq - 1; $i++) {
            if (strlen($segments[$i]) < $k) {
                return "";
            }
        }

        return implode("", $segments);
    }
}

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

#easy
Задача: 559. Maximum Depth of N-ary Tree

Дано n-арное дерево, найдите его максимальную глубину.

Максимальная глубина - это количество узлов вдоль самого длинного пути от корневого узла до самого дальнего листового узла.

Сериализация ввода n-арного дерева представлена в порядке уровня, каждая группа дочерних узлов разделена значением null (см. примеры).

Пример:

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

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

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

2⃣Здесь мы демонстрируем пример с использованием стратегии поиска в глубину (DFS - Depth First Search).

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

😎 Решение:

class Solution {
    function maxDepth($root) {
        if ($root === null) {
            return 0;
        } else if (empty($root->children)) {
            return 1;
        } else {
            $heights = array_map(array($this, 'maxDepth'), $root->children);
            return max($heights) + 1;
        }
    }
}

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

Задача: 560. Subarray Sum Equals K

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

Подмассив - это непрерывная непустая последовательность элементов внутри массива.

Пример:

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

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

1⃣Самый простой метод - рассмотреть каждый возможный подмассив данного массива nums.

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

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

😎 Решение:

class Solution {
    function subarraySum($nums, $k) {
        $count = 0;
        for ($start = 0; $start < count($nums); $start++) {
            for ($end = $start + 1; $end <= count($nums); $end++) {
                $sum = 0;
                for ($i = $start; $i < $end; $i++) {
                    $sum += $nums[$i];
                }
                if ($sum == $k) {
                    $count++;
                }
            }
        }
        return $count;
    }
}

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

📊 Реклама в сети телеграм каналов easyoffer
✈️ Для заказа пишите @easyoffer_adv

easyoffer
Backend

Python | Вопросы
Python | Удалёнка
Python | LeetCode
Python | Тесты

Frontend | Вопросы
Frontend | Удалёнка
JavaScript | LeetCode
Frontend | Тесты

Java | Вопросы
Java | Удалёнка
Java | LeetCode
Java | Тесты

Тестировщик | Вопросы
Тестировщик | Удалёнка
Тестировщик | Тесты

Data Science | Вопросы
Data Science | Удалёнка
Data Science | Тесты

C# | Вопросы
C# | Удалёнка
C# | LeetCode
C# | Тесты

C/C++ | Вопросы
C/C++ | Удалёнка
C/C++ | LeetCode
C/C++ | Тесты

Golang | Вопросы
Golang | Удалёнка
Golang | LeetCode
Golang | Тесты

DevOps | Вопросы
DevOps | Удалёнка
DevOps | Тесты

PHP | Вопросы
PHP | Удалёнка
PHP | LeetCode
PHP | Тесты

Kotlin | Вопросы
Kotlin | Удалёнка
Kotlin | LeetCode
Kotlin | Тесты

Swift | Вопросы
Swift | Удалёнка
Swift | LeetCode
Swift | Тесты

📊 Реклама в сети телеграм каналов easyoffer
✈️ Для заказа пишите @easyoffer_adv

#easy
Задача: 561. Array Partition

Дан массив целых чисел nums из 2n элементов. Разделите эти числа на n пар (a1, b1), (a2, b2), ..., (an, bn) так, чтобы сумма min(ai, bi) для всех i была максимальной. Верните максимальную сумму.

Пример:

Input: nums = [1,4,3,2]
Output: 4
Explanation: All possible pairings (ignoring the ordering of elements) are:
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
So the maximum possible sum is 4.

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

1⃣Отсортируйте массив nums в неубывающем порядке.

2⃣Итерируйте через массив, выбирая каждый второй элемент (начиная с первого).

3⃣Суммируйте выбранные элементы и верните эту сумму.

😎 Решение:

class Solution {
    function arrayPairSum($nums) {
        sort($nums);
        $sum = 0;
        for ($i = 0; $i < count($nums); $i += 2) {
            $sum += $nums[$i];
        }
        return $sum;
    }
}

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

#medium
Задача: 562. Longest Line of Consecutive One in Matrix

Дана бинарная матрица размера m x n. Вернуть длину самой длинной последовательной линии из единиц в матрице.

Линия может быть горизонтальной, вертикальной, диагональной или анти-диагональной.

Пример:

Input: mat = [[0,1,1,0],[0,1,1,0],[0,0,0,1]]
Output: 3

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

1⃣Создайте 3 матрицы для хранения текущей длины последовательных единиц: horizontal, vertical, diagonal и anti_diagonal.

2⃣Итерируйте через каждый элемент матрицы: Если элемент равен 1, обновите соответствующие значения в матрицах horizontal, vertical, diagonal и anti_diagonal. Обновите максимальную длину последовательной линии.

3⃣Верните максимальную длину.

😎 Решение:

class Solution {
    function longestLine($mat) {
        if (empty($mat) || empty($mat[0])) {
            return 0;
        }
        
        $m = count($mat);
        $n = count($mat[0]);
        $maxLength = 0;
        
        $horizontal = array_fill(0, $m, array_fill(0, $n, 0));
        $vertical = array_fill(0, $m, array_fill(0, $n, 0));
        $diagonal = array_fill(0, $m, array_fill(0, $n, 0));
        $antiDiagonal = array_fill(0, $m, array_fill(0, $n, 0));
        
        for ($i = 0; $i < $m; $i++) {
            for ($j = 0; $j < $n; $j++) {
                if ($mat[$i][$j] == 1) {
                    $horizontal[$i][$j] = ($j > 0 ? $horizontal[$i][$j-1] : 0) + 1;
                    $vertical[$i][$j] = ($i > 0 ? $vertical[$i-1][$j] : 0) + 1;
                    $diagonal[$i][$j] = ($i > 0 && $j > 0 ? $diagonal[$i-1][$j-1] : 0) + 1;
                    $antiDiagonal[$i][$j] = ($i > 0 && $j < $n - 1 ? $antiDiagonal[$i-1][$j+1] : 0) + 1;
                    
                    $maxLength = max($maxLength, $horizontal[$i][$j], $vertical[$i][$j], $diagonal[$i][$j], $antiDiagonal[$i][$j]);
                }
            }
        }
        
        return $maxLength;
    }
}

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

#easy
Задача: 563. Binary Tree Tilt

Дано корневое значение бинарного дерева. Вернуть сумму значений наклонов всех узлов дерева.

Наклон узла дерева - это абсолютная разница между суммой всех значений узлов левого поддерева и всех значений узлов правого поддерева. Если у узла нет левого потомка, то сумма значений узлов левого поддерева считается равной 0. То же правило применяется, если у узла нет правого потомка.

Пример:

Input: root = [1,2,3]
Output: 1
Explanation: 
Tilt of node 2 : |0-0| = 0 (no children)
Tilt of node 3 : |0-0| = 0 (no children)
Tilt of node 1 : |2-3| = 1 (left subtree is just left child, so sum is 2; right subtree is just right child, so sum is 3)
Sum of every tilt : 0 + 0 + 1 = 1

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

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

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

3⃣Верните общую сумму наклонов всех узлов.

😎 Решение:

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

class Solution {
    private $totalTilt = 0;
    
    function findTilt($root) {
        $this->sumAndTilt($root);
        return $this->totalTilt;
    }
    
    private function sumAndTilt($node) {
        if ($node === null) {
            return 0;
        }
        $leftSum = $this->sumAndTilt($node->left);
        $rightSum = $this->sumAndTilt($node->right);
        $nodeTilt = abs($leftSum - $rightSum);
        $this->totalTilt += $nodeTilt;
        return $node->val + $leftSum + $rightSum;
    }
}

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

#medium
Задача: 565. Array Nesting

Дан массив целых чисел nums длиной n, где nums является перестановкой чисел в диапазоне [0, n - 1].

Вы должны построить множество s[k] = {nums[k], nums[nums[k]], nums[nums[nums[k]]], ...} при соблюдении следующего правила:

Первый элемент в s[k] начинается с выбора элемента nums[k] с индексом k.
Следующий элемент в s[k] должен быть nums[nums[k]], затем nums[nums[nums[k]]], и так далее.
Мы прекращаем добавлять элементы непосредственно перед тем, как в s[k] появится дубликат.

Верните длину самого длинного множества s[k].

Пример:

Input: nums = [5,4,0,3,1,6,2]
Output: 4
Explanation: 
nums[0] = 5, nums[1] = 4, nums[2] = 0, nums[3] = 3, nums[4] = 1, nums[5] = 6, nums[6] = 2.
One of the longest sets s[k]:
s[0] = {nums[0], nums[5], nums[6], nums[2]} = {5, 6, 2, 0}

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

1⃣Создайте массив для отслеживания посещенных элементов.

2⃣Для каждого элемента в nums, если он не посещен, начните формирование множества s[k], последовательно переходя по элементам, пока не встретится уже посещенный элемент.

3⃣Обновите максимальную длину найденного множества.

😎 Решение:

class Solution {
    function arrayNesting($nums) {
        $visited = array_fill(0, count($nums), false);
        $maxLength = 0;
        
        for ($i = 0; $i < count($nums); $i++) {
            if (!$visited[$i]) {
                $start = $i;
                $count = 0;
                while (!$visited[$start]) {
                    $visited[$start] = true;
                    $start = $nums[$start];
                    $count++;
                }
                $maxLength = max($maxLength, $count);
            }
        }
        
        return $maxLength;
    }
}

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