Сложность: 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 {
public:
int depthSum(vector<NestedInteger>& nestedList) {
return dfs(nestedList, 1);
}
private:
int dfs(const vector<NestedInteger>& list, int depth) {
int total = 0;
for (const auto& nested : list) {
if (nested.isInteger()) {
total += nested.getInteger() * depth;
} else {
total += dfs(nested.getList(), depth + 1);
}
}
return total;
}
};Ставь 👍 и забирай 📚 Базу знаний