Сложность: medium
Вам дан вложенный список целых чисел nestedList. Каждый элемент либо целое число, либо список, элементы которого также могут быть целыми числами или другими списками.
Глубина целого числа — это количество списков, в которых оно находится. Например, вложенный список [1,[2,2],[[3],2],1] имеет значения каждого целого числа, установленные в его глубину.
Верните сумму каждого целого числа в nestedList, умноженного на его глубину.
Пример:
Input: nestedList = [1,[4,[6]]]
Output: 27
Explanation: One 1 at depth 1, one 4 at depth 2, and one 6 at depth 3. 1*1 + 4*2 + 6*3 = 27.
👨💻 Алгоритм:
1⃣ Инициализация и вызов рекурсивной функции:
Создайте основную функцию, которая принимает вложенный список и вызывает вспомогательную рекурсивную функцию с начальной глубиной 1.
2⃣ Рекурсивное исследование списка:
В вспомогательной функции пройдите по каждому элементу списка. Если элемент является целым числом, добавьте его значение, умноженное на текущую глубину, к общей сумме. Если элемент является списком, вызовите вспомогательную функцию рекурсивно с увеличенной глубиной.
3⃣ Возврат результата:
Возвращайте общую сумму на каждом уровне рекурсии. Основная функция возвращает итоговую сумму.
😎 Решение:
class Solution {
function depthSum($nestedList) {
return $this->dfs($nestedList, 1);
}
private function dfs($list, $depth) {
$total = 0;
foreach ($list as $nested) {
if ($nested->isInteger()) {
$total += $nested->getInteger() * $depth;
} else {
$total += $this->dfs($nested->getList(), $depth + 1);
}
}
return $total;
}
}Ставь 👍 и забирай 📚 Базу знаний