339. Nested List Weight Sum

leetcode medium

#backtracking#csharp#graph#leetcode#medium#recursion

Task

Вам дан вложенный список целых чисел 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.

C# solution

matched/original

public class Solution {
    public int DepthSum(IList<NestedInteger> nestedList) {
        return Dfs(nestedList, 1);
    }
    
    private int Dfs(IList<NestedInteger> list, int depth) {
        int total = 0;
        foreach (var nested in list) {
            if (nested.IsInteger()) {
                total += nested.GetInteger() * depth;
            } else {
                total += Dfs(nested.GetList(), depth + 1);
            }
        }
        return total;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int DepthSum(IList<NestedInteger> nestedList) {
        return Dfs(nestedList, 1);
    }
    
    private int Dfs(IList<NestedInteger> list, int depth) {
        int total = 0;
        foreach (var nested in list) {
            if (nested.IsInteger()) {
                total += nested.GetInteger() * depth;
            } else {
                total += Dfs(nested.GetList(), depth + 1);
            }
        }
        return total;
    }
}

Java solution

matched/original

class Solution {

    public int depthSum(List<NestedInteger> nestedList) {
        return dfs(nestedList, 1);
    }

    private int dfs(List<NestedInteger> list, int depth) {
        int total = 0;
        for (NestedInteger nested : list) {
            if (nested.isInteger()) {
                total += nested.getInteger() * depth;
            } else {
                total += dfs(nested.getList(), depth + 1);
            }
        }
        return total;
    }
}

JavaScript solution

matched/original

var depthSum = function(nestedList) {
    function dfs(list, depth) {
        let total = 0;
        for (const nested of list) {
            if (nested.isInteger()) {
                total += nested.getInteger() * depth;
            } else {
                total += dfs(nested.getList(), depth + 1);
            }
        }
        return total;
    }
    return dfs(nestedList, 1);
};

Python solution

matched/original

class Solution:
    def depthSum(self, nestedList: List[NestedInteger]) -> int:
        def dfs(lst, depth):
            total = 0
            for nested in lst:
                if nested.isInteger():
                    total += nested.getInteger() * depth
                else:
                    total += dfs(nested.getList(), depth + 1)
            return total
        
        return dfs(nestedList, 1)

Go solution

matched/original

func depthSum(nestedList []*NestedInteger) int {
    return dfs(nestedList, 1)
}

func dfs(list []*NestedInteger, depth int) int {
    total := 0
    for _, nested := range list {
        if nested.IsInteger() {
            total += nested.GetInteger() * depth
        } else {
            total += dfs(nested.GetList(), depth + 1)
        }
    }
    return total
}

Explanation

Algorithm

Инициализация и вызов рекурсивной функции:

Создайте основную функцию, которая принимает вложенный список и вызывает вспомогательную рекурсивную функцию с начальной глубиной 1.

Рекурсивное исследование списка:

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

Возврат результата:

Возвращайте общую сумму на каждом уровне рекурсии. Основная функция возвращает итоговую сумму.

😎